- SYUCTACM双周赛#3
出题人题解
- @ 2026-11-12 17:22:14
SYUCTACM 双周赛 #3 题解
| 比赛 | 赛制 | 题目数 | 时长 |
|---|---|---|---|
| SYUCTACM 双周赛 #3 | ICPC(罚时制) | 11 | 150 分钟 |
| 题号 | 题目 | pid | 主要考点 | 难度 |
|---|---|---|---|---|
| A | 学姐别骂我了我再也不往周赛塞石了呜呜呜 | P0887 | 字符串 / 去重 | 入门 |
| B | 01 Game | P0877 | 博弈 / 贪心 | 入门-普及 |
| C | 最小行列覆盖 | P0878 | 构造 | 普及 |
| D | 周期字符串检查 | P0879 | 字符串 | 入门 |
| E | 消除相邻重复字符 | P0880 | 贪心 / 字符串 | 普及 |
| F | 成绩统计 | P0881 | 模拟 | 入门 |
| G | Cells Not Under Attack | P0883 | 计数 | 普及 |
| H | Spy-string | P0884 | 枚举 / 暴力 | |
| I | 机房过载预警 | P0885 | 线段树 / 懒标记 | 普及+/提高 |
| J | Fix You | P0876 | 观察 | 普及 |
| K | Perfect Square | P0882 | 枚举 / 轨道 | 普及+/提高 |
A. 学姐别骂我了我再也不往周赛塞石了呜呜呜
- 题目 ID:P0887 时限 1 s 内存 256 MB
思路
顺序扫描字符串,单开一个数组标记是否第一次出现即可
复杂度:O(|s|)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
vector<bool> v(26, false);
for (int i = 0 ; i < s.size() ;i++)
{
int id = s[i] - 'a';
if (v[id]==false)
{
cout << s[i] ;
v[id] = true;
}
}
return 0;
}
B. 01 Game
- 题目 ID:P0877 时限 1 s 内存 256 MB
思路
只要 0 和 1 都还有剩余,两者之间必然存在一处相邻的 "01" ,也就是总能继续操作。所以游戏长度恰好是 min(cnt0, cnt1)。
于是 Alice 获胜当且仅当 min(cnt0, cnt1) 为奇数。
复杂度:O(|s|)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
int c0 = 0, c1 = 0;
for (int i = 0 ; i < s.size() ;i++)
{
if (s[i] == '0') c0++ ;
else c1++ ;
}
int k = min(c0, c1);
if (k % 2 == 1) cout << "YES" << endl ;
else cout << "NO" << endl ;
}
return 0;
}
C. 最小行列覆盖
- 题目 ID:P0878 时限 1 s 内存 256 MB
思路
同时满足行列:构造对角线即可
复杂度:O(n^2)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, r, c;
cin >> n >> r >> c;
r-- ; c-- ;
vector<int> p(n);
for (int i = 0 ; i < n ;i++) p[i] = i;
swap(p[r], p[c]);
vector<string> g(n, string(n, '.'));
for (int i = 0 ; i < n ;i++) g[i][p[i]] = 'X';
for (int i = 0 ; i < n ;i++) cout << g[i] << endl ;
return 0;
}
D. 周期字符串检查
- 题目 ID:P0879 时限 1 s 内存 256 MB
思路
对所有 i ≥ k 检查 s[i] 是否等于 s[i−k],全部相等输出 YES。
复杂度:O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
string s;
cin >> n >> k >> s;
bool ok = true;
for (int i = k ; i < n ;i++)
{
if (s[i] != s[i-k]) ok = false;
}
if (ok==false) cout << "NO" << endl ;
else cout << "YES" << endl ;
}
return 0;
}
E. 消除相邻重复字符
- 题目 ID:P0880 时限 1 s 内存 256 MB
思路
把字符串按「连续的相同字母」切段,比如 aaabbcd 切成 aaa bb c d。
只看每段的长度 L:段内最多只能保住 L - L/2 个字符不动,所以这一段至少要改 L/2 次(向下取整);
所以答案就是:
答案 = Σ ⌊每段长度 / 2⌋
aaabbcd 就是 ⌊3/2⌋ + ⌊2/2⌋ = 1 + 1 = 2。
复杂度:O(|s|)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.size();
int ans = 0;
for (int i = 0 ; i < n ;i++)
{
int j = i;
while (j < n && s[j] == s[i]) j++ ;
ans += (j - i) / 2;
i = j - 1;
}
cout << ans << endl ;
return 0;
}
F. 成绩统计
- 题目 ID:P0881 时限 1 s 内存 256 MB
思路
按照题意模拟即可
复杂度:O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int mx = -1, mn = 101, pass = 0;
long long sum = 0;
for (int i = 0 ; i < n ;i++)
{
int x;
cin >> x;
sum += x;
if (x > mx) mx = x;
if (x < mn) mn = x;
if (x >= 60) pass++ ;
}
cout << fixed << setprecision(2);
cout << mx << ' ' << mn << ' ' << (double)sum / n << ' ' << pass << endl ;
return 0;
}
G. Cells Not Under Attack
- 题目 ID:P0883 时限 1 s 内存 256 MB
思路
格子 (i, j) 不被攻击 ⟺ 第 i 行没有车、第 j 列也没有车。 每放一个车就标记它的行与列。 记已被占用的不同行数为 r、不同列数为 c,则安全格子数 = (n − r) · (n − c)。
复杂度:O(n + m)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<bool> row(n + 1, false), col(n + 1, false);
int r = 0, c = 0;
for (int i = 0 ; i < m ;i++)
{
int x, y;
cin >> x >> y;
if (row[x]==false)
{
row[x] = true;
r++ ;
}
if (col[y]==false)
{
col[y] = true;
c++ ;
}
long long ans = 1LL * (n - r) * (n - c);
cout << ans << ' ' ;
}
cout << endl ;
return 0;
}
H. Spy-string
- 题目 ID:P0884 时限 2 s 内存 256 MB
思路
随便挑一个给定字符串当作答案的起点。如果最终答案存在,那它只好是两种情况之一:
不动,直接就用它;或 只改一个字母:枚举改哪一位(m 种),再枚举改成 26 个字母里的哪一个。 所以最多试1 + 26m个候选。每个候选都跟 n 个字符串比一遍,看是否每个都至多差一位;全都不行就输出 -1。
复杂度:O(m · 26 · n · m)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<string> v(n);
for (int i = 0 ; i < n ;i++) cin >> v[i];
string ans = "";
for (int pos = -1 ; pos < m && ans == "" ;pos++)
{
for (char ch = 'a' ; ch <= 'z' && ans == "" ;ch++)
{
string s = v[0];
if (pos >= 0) s[pos] = ch;
bool ok = true;
for (int i = 0 ; i < n ;i++)
{
int d = 0;
for (int j = 0 ; j < m ;j++)
{
if (s[j] != v[i][j]) d++ ;
}
if (d > 1) ok = false;
}
if (ok==true) ans = s;
}
}
if (ans == "") cout << "-1" << endl ;
else cout << ans << endl ;
}
return 0;
}
I. 机房过载预警
- 题目 ID:P0885 时限 2 s 内存 512 MB
思路
本题是zkw线段树的模板题,详细请看oiwiki(大一不需要现在就会)
复杂度:O((n + q) log n)
参考代码
#include <bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN / 4;
int M; // 叶子数(2 的幂)
vector<long long> mx, lz;
void apply(int p, long long v)
{
mx[p] += v;
if (p < M) lz[p] += v;
}
void pull(int p)
{
mx[p] = max(mx[p << 1], mx[p << 1 | 1]) + lz[p];
}
void push(int p) // 把 p 到根的标记下推
{
for (int s = __lg(M) ; s >= 1 ;s--)
{
int i = p >> s;
if (lz[i] != 0)
{
apply(i << 1, lz[i]);
apply(i << 1 | 1, lz[i]);
lz[i] = 0;
}
}
}
void add(int l, int r, long long v) // 对 [l, r] 加 v(1-indexed)
{
l = l + M - 2;
r = r + M; // 1-indexed 闭区间 [l, r] -> 叶子开区间 (l, r)
int L = l, R = r;
push(L);
push(R);
while ((l ^ r) != 1)
{
if ((l & 1) == 0) apply(l ^ 1, v);
if ((r & 1) == 1) apply(r ^ 1, v);
l >>= 1;
r >>= 1;
}
for (int i = L >> 1 ; i ;i >>= 1) pull(i);
for (int i = R >> 1 ; i ;i >>= 1) pull(i);
}
long long query(int l, int r) // 求 [l, r] 的最大值(1-indexed)
{
l = l + M - 2;
r = r + M; // 同上,转成叶子开区间 (l, r)
int L = l, R = r;
push(L);
push(R);
long long res = NEG;
while ((l ^ r) != 1)
{
if ((l & 1) == 0) res = max(res, mx[l ^ 1]);
if ((r & 1) == 1) res = max(res, mx[r ^ 1]);
l >>= 1;
r >>= 1;
}
return res;
}
int main()
{
int n, q;
cin >> n >> q;
M = 1;
while (M < n + 2) M <<= 1;
mx.assign(M << 1, NEG);
lz.assign(M << 1, 0);
for (int i = 1 ; i <= n ;i++) cin >> mx[M + i - 1];
for (int i = M - 1 ; i >= 1 ;i--)
{
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
for (int i = 0 ; i < q ;i++)
{
int op, l, r;
long long v;
cin >> op >> l >> r >> v;
if (op == 1) add(l, r, v);
else
{
if (query(l, r) >= v) cout << "YES" << endl ;
else cout << "NO" << endl ;
}
}
return 0;
}
J. Fix You
- 题目 ID:P0876 时限 1 s 内存 256 MB
思路
会掉出去的格子只有两种:最后一列写了 R、最后一行写了 D。其余方向都还在网格里,最多就是走到边上,然后由边上那一列/一行把你带到右下角。
因此最少修改次数就等于这两类格子的总数:
最后一列里 R 的个数 + 最后一行里 D 的个数(右下角那个 C 不算)
复杂度:O(n·m)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<string> g(n);
for (int i = 0 ; i < n ;i++) cin >> g[i];
int ans = 0;
for (int i = 0 ; i < n - 1 ;i++) if (g[i][m - 1] == 'R') ans++ ;
for (int j = 0 ; j < m - 1 ;j++) if (g[n - 1][j] == 'D') ans++ ;
cout << ans << endl ;
}
return 0;
}
K. Perfect Square
- 题目 ID:P0882 时限 2 s 内存 256 MB
思路
旋转 90° 不变 ⟺ 每格与它旋转 90°/180°/270° 后的三格字符相同;n 为偶数时这 4 格互不相同,构成一个 4 元轨道。
轨道之间互不影响,分别求最小代价再相加。单个字符 c 变成目标 t 的代价是 (t − c) mod 26。
t 只可能取这四个字符之一,枚举 4 种取最小;遍历左上角四分之一区域即可,每个格子代表一条轨道。
复杂度:O(n^2)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<string> g(n);
for (int i = 0 ; i < n ;i++) cin >> g[i];
long long ans = 0;
for (int i = 0 ; i < n / 2 ;i++)
{
for (int j = i ; j < n - 1 - i ;j++)
{
int v[4];
v[0] = g[i][j];
v[1] = g[j][n - 1 - i];
v[2] = g[n - 1 - i][n - 1 - j];
v[3] = g[n - 1 - j][i];
int best = 1 << 30;
for (int k = 0 ; k < 4 ;k++)
{
int cost = 0;
for (int x = 0 ; x < 4 ;x++) cost += (v[k] - v[x] + 26) % 26;
best = min(best, cost);
}
ans += best;
}
}
cout << ans << endl ;
}
return 0;
}