Contestant(alt). Rank 209. Rating +155.
A. Cipher Shifer
题意
给定一个字符串，定义操作如下：
选择一个字符；
在该字符后面插入若干和该字符不一样的字符；
将选择的字符插入
如，对于 \(a\)，我们可以操作为 \(abcda\)，\(a, bcd, a\) 对应上面的三个操作。
现在，给出操作后的字符串，还原为原字符串。
思路
既然不会出现一样的字符，那么我们直接暴力枚举，配对头和尾即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int pre = -1;
string ans = "";
for(int i=0;i<n;i++){
if(s[i] == pre){
pre = -1;
}else if(pre == -1){
pre = s[i];
ans += pre;
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}题目怎么这么阅读理解（
B. Binary Cafe
题意
给定 \(k\) 个商品，第 \(i\) 个商品的价格为 \(2 ^ i\)，在总价格不超过给定 \(n\) 的条件下，输出购买方案的总数。
思路
二进制数有一个特点：任意一位的权重 等于 小于他权重的所有位的权重和 \(+1\)。
那么，如果第 \(p\) 位可以选上，从 \(0\) 开始计数的话，前面 \(p\) 个也一定能选上。
也就是说，\((2 ^ p - 1) + 1 = 2 ^ p\) 既是方案数，也是价格总数。
因此，\(\min(2 ^ k, n)\) 就是答案。
显然，因为 \(n\) 范围已知，所以可以特判 \(k\) 的大小，防止爆 \(long\ long\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
if(k >= 60) cout << n + 1 << '\n';
else cout << min((int) pow(2, k), n + 1) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}比较抽象
C. Ski Resort
题意
给定长为 \(n\) 的序列以及两个整数 \(k, q\)，输出不包含大于 \(q\) 的元素且长度大于等于 \(k\) 的所有连续子序列的个数。
思路
显然，我们直接扫一遍，并记录以当前位置为区间尾部，区间内不包含大于 \(q\) 元素的最大长度 \(cnt\)，那么以当前位置为子序列尾部的字符列个数就是 \(cnt - k + 1\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
int ans = 0, cnt = 0;
for(auto e : a){
if(e <= q) cnt ++;
else cnt = 0;
if(cnt >= k) ans += cnt - k + 1;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}怎么比 \(B\) 还水
D. Wooden Toy Festival
题意
给定三个工匠，每个工匠有固定的加工样式 \(x\)，加工一个样式 \(y\) 需要 \(|y - x|\) 时间，同一个工匠可以在同一时刻加工任意数量的工件。
对于 \(n\) 个人，每个人有需要加工的一个样式，在任意选择工匠的加工样式的条件下，输出最后耗费的最长时间的最小值。
思路
既然我们可以自由确定工匠的加工样式，那么我们就可以升序排序所有人需要加工的样式，然后分成连续的三段，由三个工匠加工。
观察题面，求最大值的最小值，我们不难想到二分答案。
如果我们确定了答案，也就是耗费的最长时间，那么我们不妨用这个最长时间去划分段落。如果我们划分出三段，那么这就可以作为答案，否则，如果小于三段，这个最大值就太大了，否则就太小了，显然具有单调性。
因而，我们直接二分即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(all(a));
int ans = 0;
auto check = [&](int mid) -> bool{
int cnt = 1, sum = a[0] + mid;
for(auto e : a){
if(abs(e - sum) > mid){
sum = e + mid;
cnt ++;
}
}
return cnt <= 3;
};
int l = 0, r = a[n - 1], mid;
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)){
r = mid - 1;
ans = mid;
}else l = mid + 1;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}二分二分
E. Character Blocking
题意
给定两个长度相等的字符串，编号为 \(1, 2\)，定义询问如下：
\(1\ \ pos\)，锁定两个字符串 \(pos\) 位置的字符 \(t\) 秒；
\(2\ \ 1/2\ \ pos1\ \ 1/2\ \ pos2\)，将对应标号的对应位置的字符交换
\(3\)，询问跳过锁定的字符后两个字符串是否相同
对于第二个操作：
\(2\ 1\ 3\ 2\ 4\)，就是把第 \(1\) 个字符串的 \(3\) 位置字符和第 \(2\) 个字符串的 4 位置字符交换；
\(2\ 2\ 3\ 2\ 4\)，就是把第 \(2\) 个字符串的 \(3\) 位置字符和 4 位置字符交换。
现在，给定锁定时间 \(t\)，以及 \(q\) 个询问，一个询问占用 \(1\) 秒，执行对应的操作。
思路
我们不妨用 \(set\) 维护当前不同的字符出现在哪些下标，那么只要最后 \(set\) 为空，两个字符串就是相同的。
那么，我们来考虑如何更新它：
首先我们可以预处理出当前不相同的位置，然后先放入 \(set\) 中；
显然，同一个时刻不会有多个位置被锁定，也不会由多个位置被解锁，所以我们可以用某种数据结构来维护当前的锁定状态，我们将需要锁定的开始时间以及下标放入该数据结构中，并在每个时刻判断最初放入的锁定字符是否到达锁定时间，满足先入先出的条件，我们选择队列。 因而，我们用队列维护当前的锁定状态，如果有一个位置被锁定，那么这个位置的字符就可以被当作相同，我们将其从 \(set\) 中移除；同样的，当一个位置解除锁定的时候，我们判断一下这个位置的字符是否相等，不相等就放入 \(set\) 中；
至于交换，我们直接模拟即可，交换后判断一下这两个位置是否相同，并更新 \(set\)。
按上述操作模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
vector<string> s(3);
cin >> s[1] >> s[2];
int n = s[1].size();
s[1] = "#" + s[1], s[2] = "#" + s[2];
set<int> st;
for(int i=1;i<=n;i++){
if(s[1][i] != s[2][i]) st.emplace(i);
}
int t, q;
cin >> t >> q;
queue<pii> qu;
for(int i=1;i<=q;i++){
int cur;
cin >> cur;
if(!qu.empty()){
auto [dead, pos] = qu.front();
if(dead == i){
if(s[1][pos] != s[2][pos]) st.emplace(pos);
qu.pop();
}
}
if(cur == 1){
int pos;
cin >> pos;
if(st.count(pos)){
st.erase(pos);
qu.emplace(i + t, pos);
}
}else if(cur == 2){
int w1, p1, w2, p2;
cin >> w1 >> p1 >> w2 >> p2;
swap(s[w1][p1], s[w2][p2]);
if(s[1][p1] != s[2][p1]) st.emplace(p1);
else if(st.count(p1)) st.erase(p1);
if(s[1][p2] != s[2][p2]) st.emplace(p2);
else if(st.count(p2)) st.erase(p2);
}else{
cout << (st.empty() ? "YES\n" : "NO\n");
}
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}模拟模拟！
F. Railguns
题意
给定一个 \(n \times m\) 的平面，以及起点 \((0,0)\) 和终点 \((n,m)\)，定义一次操作为：从 \((i,j)\) 位置移动到 \((i+1,j)\) 或 \((i,j+1)\) 或不移动。
给定 \(r\) 个射击，每个射击会在给定 \(t\) 时刻末发射，射击是横向或纵向的，因此给出方向 \(d\) 以及射击的某一行或某一列的标号 \(coord\)。
输出人物避开所有射击从起点走到终点的时间最小值。
待补充（不能白翻译吧
G1. In Search of Truth (Easy Version)
待补充
G2. In Search of Truth (Hard Version)
待补充