ACGO十一挑战赛赛后题解（非官方）
2025-10-12 12:29:38
发布于：重庆
23阅读
0回复
0点赞
前言
为什么现在 10/12 了我才发，问就是突发奇想（
这次比赛令我高兴的一点是没有一道 DP！！！
（可惜这场我没打完
T1 NOON
字符串遍历题，秒切
注意不要图方便用 find 然后 erase，因为 NOON 头尾相同，可能出现 NOONOON。
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.length();
int cnt = 0;
for (int i = 0; i <= n - 4; i++)
{
if (s[i] == 'N' && s[i + 1] == 'O' && s[i + 2] == 'O' && s[i + 3] == 'N') cnt++;
}
cout << cnt << endl;
return 0;
}
T2 maple序列
暴力枚举 & 即可，没有什么好说的，一样秒切
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector <int> v(5005, 0);
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v[x]++;
}
int maxn = 0;
for (int s = 2; s <= 10000; s++)
{
int p = 0;
for (int x = 1; x <= s / 2; x++)
{
int y = s - x;
if (y > 5000) continue;
if (x == y) p += v[x] / 2;
else p += min(v[x], v[y]);
}
maxn = max(maxn, p);
}
cout << maxn * 2 << endl;
return 0;
}
T3 午枫的石子合并
我还以为是石子合并原题，吃罚时了（悲
将第 堆石子合并到第 堆时，若第 堆有 个石子，操作次数为 。最终所有石子合并到第 堆时， 堆需从第1堆向右合并， 堆需从第 堆向左合并。可预处理前缀和后缀的最小合并操作次数，枚举最终合并的位置，取最小总操作次数即可。
#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[200005];
long long pre[200005],ans[200005],sum,res=INT_MAX;
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) sum += a[i], pre[i] = pre[i-1] + (sum + k - 1) / k;
sum = 0;
for (int i = n; i >= 1; i--) sum += a[i], ans[i] = ans[i+1] + (sum + k - 1) / k;
for (int i = 1; i <= n; i++) res = min(res, pre[i - 1] + ans[i + 1]);
cout<<res;
return 0;
}
T4 午枫的彩排2
比较简单的一道模拟，每个舞台只用 或 操作更优。预处理 的后缀最大值，枚举分界点 ，取 的花费加上 的后缀最大值的最小值。听起来有点绕，实现非常 easy。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int b[200005];
pair <int, int> pa[200005];
int ptt[200005];
void f()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++)
{
pa[i].first = (b[i] - a[i] + m) % m;
pa[i].second = (a[i] - b[i] + m) % m;
}
sort(pa + 1, pa + n + 1);
for(int i = n; i; i--) ptt[i] = max(ptt[i + 1], pa[i].second);
int ans = INT_MAX;
for(int i = 0; i <= n; i++) ans = min(ans, pa[i].first + ptt[i + 1]);
cout << ans << '\n';
for(int i = 1; i <= n; i++){
ptt[i] = 0;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) f();
return 0;
}
T5 午枫勇闯移动迷宫
不难能看出是最短路，距离就是方向是否相同，若相同则两点距离为 （不需要改变方向），否则距离为 （改变方向），然后 就可以了。
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
struct P {
int dis;
int x, y;
bool operator<(const P& b) const {
return dis > b.dis; // 小根堆
}
};
map<char, int> dir;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> g(n + 1, vector<char>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
priority_queue<P> q;
vector<vector<bool>> vis(n + 1, vector<bool>(m + 1, false));
vector<vector<int>> d(n + 1, vector<int>(m + 1, INF));
d[1][1] = 0;
q.push({0, 1, 1});
while (!q.empty()) {
auto [dis, x, y] = q.top();
q.pop();
if (vis[x][y]) continue;
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (dir[g[x][y]] == i) {
if (d[nx][ny] > d[x][y]) {
d[nx][ny] = d[x][y];
q.push({d[nx][ny], nx, ny});
}
} else {
if (d[nx][ny] > d[x][y] + 1) {
d[nx][ny] = d[x][y] + 1;
q.push({d[nx][ny], nx, ny});
}
}
}
}
if (d[n][m] > k) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
int main() {
dir['O'] = 0;
dir['G'] = 1;
dir['B'] = 2;
dir['Y'] = 3;
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
T6 午枫的创造
压轴绿题，刚看的时候还以为是数学题（实际上就是）。
题目大意
给定一个字符串序列，可以修改任意位置的字符串。求有多少种修改方式，使得所有长度 ≥2 的子序列的字符集合与原序列相同。
思路
- 二进制表示：每个字符串用二进制整数表示（字符不重复）。
- 关键条件：所有长度 ≥2 的子序列的按位或值必须保持不变。
- 修改规则：
- 如果要修改 a[i]，必须保证 a[i] | x = b[i] | x（x 是相邻元素）。
- 对于每一位：
- 如果 a[i] | x 的某位是 0，则 b[i] 该位必须为 0。
- 如果 a[i] | x 的某位是 1 且 x 该位是 0，则 b[i] 该位必须为 0。
- 如果 a[i] | x 的某位是 1 且 x 该位是 1，则 b[i] 该位可以是 0 或 1（有 2 种选择）。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;
void solve()
{
int n,m;cin>>n>>m;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
{
string s;cin>>s;
for(auto x:s)
{
a[i]+=(1ll<<(x-'a'));
}
}
ll res=0;
for(int i=1;i<=n;i++)
{
int x=(1<<m)-1;
if(i>1) x&=a[i-1];
if(i<n) x&=a[i+1];
int cnt=0;
for(int j=0;j<m;j++)
{
if(x>>j&1) cnt++;
}
res+=(1ll<<cnt)-1;
}
cout<<res<<endl;
}
int main()
{
int T=1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
总结
可恶居然没有打完这个没有 的挑战赛！！！
有帮助，赞一个