ARC154-526互联

和一定差小积大，竟可能的使两个数差大即可。

复杂度 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int n;
string s, t;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s >> t;
	s = "." + s; t = "." + t;
	for (int i = 1; i <= n; ++i) {
		if (s[i] < t[i]) swap(s[i], t[i]);
	}
	ll x = 0, y = 0;
	for (int i = 1; i <= n; ++i) {
		x = x * 10 % mod + s[i] - '0';
		x %= mod;
		y = y * 10 % mod + t[i] - '0';
		y %= mod;
	}
	cout << x * y % mod << endl;
	return 0;
}

[ARC154B] New Place

贪心。

我们找到 \(t\) 最长的后缀，满足其为 \(s\) 子序列，然后答案就是 \(n\) 减去其长度。

复杂度 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
int n, cnts[N], cntt[N];
string s, t;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s >> t;
	s = "." + s; t = "." + t;
	for (int i = 1; i <= n; ++i) {
		++cnts[s[i] - 'a'];
		++cntt[t[i] - 'a'];
	}
	for (int i = 0; i < 26; ++i) {
		if (cnts[i] != cntt[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	int cur = n;
	for (int i = n; i >= 1; --i) {
		if (s[cur] == t[i]) --cur;
	}
	cout << cur << endl;
	return 0;
}

[ARC154C] Roller

和上一题挺像的。

我们先把 \(B\) 序列同色块合并，\(A\) 序列倍长。

然后枚举 \(A\) 长为 \(n\) 的子段，看 \(B\) 是否为其子序列即可。

至于证明，感性理解。

复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
int T, n, a[N], b[N], c[N], tot, cur;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n; tot = 0;
		for (int i = 1; i <= n; ++i) cin >> a[i], a[i + n] = a[i];
		for (int i = 1; i <= n; ++i) {cin >> b[i]; if (b[i] != b[i - 1]) c[++tot] = b[i];}
		if (tot > 1 && c[tot] == c[1]) --tot;
		int ans = 0;
		if (tot == n) {
			ans = 1;
			for (int i = 1; i <= n; ++i) ans &= (c[i] == a[i]);
		} else {
			for (int i = 1; i <= n; ++i) {
				cur = 1;
				for (int j = i; j <= i + n - 1; ++j) {
					if (a[j] == c[cur]) ++cur;
				}
				ans |= cur > tot;
			}
		}
		if (ans) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

[ARC154D] A + B > C ?

交互题。

定义 \(\operatorname{cmp}(x,y)\) 为 \(a_x+a_{fir}>a_y\)，其中 \(fir\) 为 \(1\) 的位置。

我们先跑一边，找到 \(1\) 的位置。

然后将 \(\operatorname{cmp}(x,y)\) 作为比较函数跑 stable_sort 排序。

不用 sort 是放置比较次数过多被卡。

最后输出答案即可。

复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;
int a[N], ans[N], fir, n;
bool cmp(int i, int j) {
	cout << "? " << i << " " << fir << " " << j << endl;
	fflush(stdout);
	string s; cin >> s;
	if (s == "Yes") return true;
	return false; 
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fir = 1;
	for (int i = 2; i <= n; ++i) {
		if (cmp(fir, i)) {
			fir = i;
		}
	}
	for (int i = 1; i <= n; ++i) a[i] = i;
	swap(a[1], a[fir]);
	stable_sort(a + 1, a + n + 1, cmp);
	for (int i = n; i >= 1; --i) ans[a[i]] = n - i + 1;
	cout << "!" << " ";
	for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
	cout <<endl;
	fflush(stdout);
	return 0;
}

inversion reverse 154e arc