个人技术分享

前言：

今天发烧了，感觉脑子是被烧坏了，今天只做出来A~D，题解思路可能有点乱，请各位谅解

A - AtCoder Line

题目大意：

给定X,Y,Z,判断Z是否在X,Y之间

解题思路：

这题$N$没什么用，
直接$for()$循环，在$X,Y$之间找$Z$,如果找到了，输出"$Yes$",否则"$No$".

核心代码：

int n, x, y, z;
void solve() {
	// 竞赛程序
	cin >> n >> x >> y >> z;
	if(x < y) {
		for(int i = x; i <= y; i++) {
			if(i == z) {
				cout << "Yes" << endl;
				return;
			}
		}
	} else {
		for(int i = x; i >= y; i--) {
			if(i == z) {
				cout << "Yes" << endl;
				return;
			}
		}
	}
	cout<<"No"<<endl;
}

B - Typing

题目大意：

给定字符串 $s,t$ 。$s$ 是 $t$ 的子序列。现就近匹配，找到 $s$ 的每个字符就近匹配到的 $t$ 中的每个下标。

解题思路:

按照就近匹配原则，匹配一次子序列即可。

• auto是你的好伙伴（确信）

string s, t;
void solve(){
    // 竞赛程序
    cin >> s >> t;
    auto bin = t.begin();
    for (auto c : s) {
        while (bin != t.end() && *bin != c) {
            bin = next(bin);
        }
        cout << (bin - t.begin() + 1) << ' ';
        bin = next(bin);
    }
    cout << endl;
}

C - Standing On The Shoulders

题目大意：
给定$n$个巨人，巨人有肩高$a_i$和头高$b_i$。

现依次放置每个巨人，每个巨人放在上一个巨人的肩上。

问最高的巨人的头高有多高。

解题思路:

枚举最后的巨人是哪个，那么其头高就是$b_i+{\sum }_j\ne i$ $a_j $。(不会打捏QWQ)

所有可能的情况取最大值即为答案。

void solve(){
    // 竞赛程序
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    long long suma = accumulate(a.begin(), a.end(), 0ll);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(suma - a[i] + b[i], ans);
    }
    cout << ans << endl;
}

我头又开始晕了

D - Permutation Subsequence

题目大意：

给定一个排列 $p_i$ 和一个数 $k$。找出 $k$ 个下标，最小化下标极差，使得对应的 $p_i$ 组成的集合是一个连续的 $k$ 个数的集合。

代码：

long long n, k;
long long usee[N];
void solve(){
    // 竞赛程序
    cin >> n >> k;
    for (long long i = 0; i < n; i++) {
        long long x;
        cin >> x;
        x--;
        usee[x] = i;
    }
    long long ans = n + 1;
    deque<long long> minn, maxx;
    for (long long i = 0; i < n; i++) {
        while (!minn.empty() && i - minn.front() >= k) {
            minn.pop_front();
        }
        while (!maxx.empty() && i - maxx.front() >= k) {
            maxx.pop_front();
        }
        while (!minn.empty() && usee[i] <= usee[minn.back()]) {
            minn.pop_back();
        }
        while (!maxx.empty() && usee[i] >= usee[maxx.back()]) {
            maxx.pop_back();
        }
        minn.push_back(i);
        maxx.push_back(i);
        if (i >= k - 1)
            ans = min(ans, usee[maxx.front()] - usee[minn.front()]);
    }
    cout << ans << endl;
}

不行我要去吃药了（扶额）