当前位置：首页 > news >正文

20251124 - 月度检测总结

news 2026/5/11 21:14:04

20251124 - 月度检测总结

题号	实际分数	应得分数	罚时
A	AC	AC	0
B	AC	AC	0
C	AC	AC	0
D	WA	AC	null
E	AC	AC	-2
F	null	AC	null
G	null	null/AC	null
H	null	null	null
后面不用看了！	null	null	null

一句话总结：CF 思维的题目做少了。。。

A - ASCII Art Contest

签到题，排个序特判一下即可。

时间复杂度：$ O(n\log n) \approx O(1)$

void solve() {for (int i = 0; i < 3; i++) {scanf("%d", &a[i]);}sort(a, a + 3);if (abs(a[2] - a[0]) >= 10) {puts("check again");return;}printf("final %d\n", a[1]);
}

B - Dungeon Equilibrium

可以发现，如果数量小于数字，那么就只能全删了，否则删掉多余的部分。

时间复杂度：$ O(n\log n)$

void solve() {scanf("%d", &n);map<int,int>mp;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);mp[a[i]] ++;}int ans = 0;for (auto v : mp) {// printf("%d %d\n",v.first,v.second);if(v.first > v.second) {ans += v.second;}else if (v.first == v.second) {}else {ans += v.second - v.first;}}printf("%d\n", ans);
}

C - Your Name

判断字符串是否相等，可以先排序，在判断一下就好了。

时间复杂度：$ O(n\log n)$

void solve() {scanf("%d", &n);string a, b;cin >> a >> b;sort(a.begin(), a.end());sort(b.begin(), b.end());if(a == b)puts("YES");elseputs("NO");
}

D - Expansion Plan 2

可惜考场上没有做出来。

总结：CF 的题做少了。

题目可以看做从 $(0,0)$ 出发，每次有两种方案，一种是行 $+1$ 或列 $+1$，一种是行 $+1$ ，列 $+1$或行和列都 $+1$。

那么 $4$ 联通的就是曼哈顿距离，$8$ 联通就是**切比雪夫距离 **。

因为 $8$ 联通走一步就是 $4$ 联通走两步，所以最远的距离就是他们的曼哈顿距离。

注意：还要判断一下切比雪夫距离是否超过 $n$。

时间复杂度：$O(n)$

补题代码：

void solve() {scanf("%d%d%d", &n, &x, &y);scanf("%s", s + 1);int cnt8 = 0, cnt4 = 0;for (int i = 1; i <= n; i++) {if (s[i] == '4') cnt4++;if (s[i] == '8') cnt8++;}x = abs(x);y = abs(y);if (x + y <= cnt4 + 2 * cnt8 && max(x, y) <= n) {puts("YES");}else {puts("NO");}
}

E - 兔子与兔子

简直就是字符串 hash 的板子。

时间复杂度：$O(n)$

void init(){power[0] = 1;for (int i = 1;i <= n; i++) {h[i] = h[i - 1] * base + s[i];power[i] = power[i - 1] * base;}
}
ull get_hash(int l, int r) {return h[r] - h[l - 1] * power[r - l + 1];
}
void solve() {scanf("%s", s + 1);scanf("%d", &t);n = strlen(s + 1);init();while (t--) {int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if(get_hash(l1, r1) == get_hash(l2, r2))puts("Yes");elseputs("No");}
}