和一定差小积大，竟可能的使两个数差大即可。
复杂度 \(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;
}
贪心。
我们找到 \(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;
}
和上一题挺像的。
我们先把 \(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;
}
交互题。
定义 \(\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;
}