ABC279 复盘

思路解析：纯模拟，遍历到哪个字母就加几分

#include<bits/stdc++.h>
using namespace std;
string str;
int main() {
	cin >> str;
	long long ans = 0;
	for(int i = 0; i < str.size(); i++) {
		if(str[i] == 'w') {
			ans += 2;
		}
		else if(str[i] == 'v') {
			ans++;
		}
	}
	cout << ans;
	return 0;
}

[ABC279B] LOOKUP

思路解析：最基础的字符串匹配，用朴素算法即可，但我很皮手打了个 kmp ^_^

#include<bits/stdc++.h>
using namespace std;
string s, t;
int nxt[114514];
int main() {
	cin >> s >> t;
	for(int i = s.size(); i > 0; i--) {
		s[i] = s[i - 1];
	}
	for(int i = t.size(); i > 0; i--) {
		t[i] = t[i - 1];
	}
	for(int i = 2, j = 0; i <= t.size(); i++) {
		while(j && t[i] != t[j + 1]) {
			j = nxt[j];
		}
		if(t[i] == t[j + 1]) {
			nxt[i] = j + 1;
		}
	}
	for(int i = 1, j = 0; i <= s.size(); i++) {
		while(j && s[i] != t[j + 1]) {
			j = nxt[j];
		}
		if(s[i] == t[j + 1]) {
			j++;
			if(j >= t.size()) {
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
	return 0;
}

[ABC279C] RANDOM

思路解析：由于只能交换列，所以我们把每个列用一个 string 存下来，然后排序将每个 string 进行比较，若全部相同则说明两个字符矩阵中的每一列都有另一个字符矩阵中的一列对应

错因：没想到如何在输入时就存下来单独的一列，因此爆内存

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int n, m;
string sa[N], sb[N];
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			char ch;
			cin >> ch;
			sa[j].push_back(ch);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			char ch;
			cin >> ch;
			sb[j].push_back(ch);
		}
	}
	sort(sa + 1, sa + m + 1);
	sort(sb + 1, sb + m + 1);
	for(int i = 1; i <= m; i++) {
		if(sa[i] != sb[i]) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

[ABC279D] Freefall

思路解析：整数三分裸板子，直接套即可

错因：没背好整数三分的边界。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a, b;
double f(double g) {
	return (double)b * ((double)g - 1) + (double)a / sqrt((double)g);
}
int main() {
	cin >> a >> b;
	ll l = 1, r = 1e18;
	while(l < r) {
		ll lmid = l + (r - l) / 3;
		ll rmid = r - (r - l) / 3;
		if(f(lmid) < f(rmid)) {
			r = rmid - 1;
		}
		else {
			l = lmid + 1;
		}
	}
	printf("%.10lf", f(l));
	return 0;
}

[ABC279E] Cheating Amidakuji

思路解析：考场手撕。我们可以发现如果删除第 \(i\) 次操作，但是操作交换的两个数不影响 \(1\) 所在的位置，直接输出预处理的不删操作的结果。若影响，则说明当前的 \(1\) 以后一直都在被交换的另一个数应该在的位置上，则输出被影响的另一个数在正常情况下的位置即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N];
int jh1[N];
int c[N], d[N];
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		c[i] = i;
		d[i] = i;
	}
	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		swap(c[a[i]], c[a[i] + 1]);
	}
	for(int i = 1; i <= n; i++) {
		d[c[i]] = i;
	}
	for(int i = 1; i <= n; i++) {
		c[i] = i;
	}
	jh1[0] = 1;
	for(int i = 1; i <= m; i++) {
		jh1[i] = jh1[i - 1];
		int temp = jh1[i];
		if(jh1[i - 1] == a[i]) {
			jh1[i]++;
		}
		else if(jh1[i - 1] == a[i] + 1) {
			jh1[i]--;
		}
		cout << d[c[jh1[i]]] << "\n";
		swap(c[a[i]], c[a[i] + 1]);
	}
	return 0;
}

[ABC279F] BOX

思路解析：实践不难，重点是想到思路。我们可以发现操作 \(1\) 其实就是并查集的合并操作，但是每一个箱子合并后当前的箱子就不可用了（因为已经和另一个合并到一起了），所以这时只需再新建一个箱子代表当前编号的箱子即可。

注意：由于需要新建箱子，所以就必须把数组大小再开大一倍

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, q;
int ball[N * 2], id[N * 2], box[N * 2], fa[N * 2];
int fd(int x) {
	while(fa[x] != x) x = fa[x] = fa[fa[x]];
	return x;
}
int main() {
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		ball[i] = i;
		id[i] = i;
		box[i] = i;
		fa[i] = i;
	}
	int cnt = n;
	int lst = n;
	while(q--) {
		int op, x, y;
		cin >> op;
		if(op == 1) {
			cin >> x >> y;
			fa[fd(box[y])] = fd(box[x]);
			cnt++;
			box[y] = cnt;
			id[cnt] = y;
			fa[cnt] = cnt;
		}
		else if(op == 2) {
			cin >> x;
			ball[++lst] = box[x];
		}
		else if(op == 3) {
			cin >> x;
			cout << id[fd(ball[x])] << "\n";
		}
	}
	return 0;
}