省流:只有 \(1000\) 分,遗憾离场。
这篇文章用来警示大家不要在比赛中犯相同的错误。
A. OS Versions
AI 出来解释一下 \(\texttt{newer than}\) 翻译成“更新”何意味?
请判断版本 \(X\) 与版本 \(Y\) 是否相同或更新。
噢,原来是要 \(X\) 比 \(Y\) 更(四声)新。
语法题,会写条件语句就行。
B. The Odd One Out
语法题,找不同。
C. Upgrade Required
唐得离谱了。
内心 OS:前缀和?差分?
然后发现不对劲。
注意到一共就 \(n\) 台电脑,那就用桶记录数量,每次暴力更新就行。前面归零的桶直接不管,每个桶只被暴力归零一次,时间复杂度 \(O(n)\)。
这是入门题啊,我在想什么???
真的怒了!
D. Pop and Insert
很快发现性质:要通过形如 00111111000
的 \(ABA\) 型子串进行线性计算。无非就是把 \(AB\) 推出去,然后再塞回来或把 \(BA\) 推出去,然后塞回来,又或是把两边的 \(A\) 推出去再塞回来,分别用式子计算取最小值就可以了!
不知道为什么写了那么久……
请输入文字
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, a[N], tot, b[N];
string s;
void solve() {cin >> n >> s; int cnt1 = 0, cnt0 = 0; tot = 0; for(auto v : s) cnt1 += (v == '1'), cnt0 += (v == '0'); //cnt1,cnt0分别是1的总数和0的总数int tmp = 1; for(int i = 1; i < n; i++) {if(s[i] == s[i - 1]) {++tmp; }else {a[++tot] = tmp; b[tot] = s[i - 1] - '0'; tmp = 1; }}a[++tot] = tmp, b[tot] = s[n - 1] - '0'; int minn = INT_MAX; if(tot == 1) {puts("0"); } else if(tot == 2) {printf("%d\n", min(cnt1, cnt0)); } else {for(int i = 3; i <= tot; i++) {int tmp1 = 0, tmp0 = 0; if(b[i] == 1) {tmp1 += a[i] + a[i - 2], tmp0 += a[i - 1];if(minn > (cnt0 - tmp0) * 2 + cnt1) {minn = (cnt0 - tmp0) * 2 + cnt1; //cout << i<<' '<<minn << endl; }minn = min(minn, cnt0 + (cnt1 - tmp1 + a[i - 2]) * 2); minn = min(minn, cnt0 + (cnt1 - tmp1 + a[i]) * 2); }else { //mid = 1tmp1 += a[i - 1], tmp0 += a[i] + a[i - 2];if(minn > (cnt1 - tmp1) * 2 + cnt0) {minn = (cnt1 - tmp1) * 2 + cnt0; //cout << i<<' '<<minn << endl; } minn = min(minn, cnt1 + (cnt0 - tmp0 + a[i - 2]) * 2); minn = min(minn, cnt1 + (cnt0 - tmp0 + a[i]) * 2); }}printf("%d\n", minn); }return;
}
int main(){int t; cin >> t; while(t--) {solve(); }return 0;
} //AC 100