#创作计划# 挑战赛 #23 全题解

userId_undefined

cjdstttttt

时空双修者题解仙人尊贵铂金勇敢小狗CSP-J一等奖出题人

2025-10-07 23:46:45

发布于：广东

75阅读
0回复
0点赞

ACGO 正在蒸蒸日上！

赛时至少出现 33 个影响解题的大问题，比赛出成这样也是没谁了。

T1

看不出来哪里有橙。这玩意不 ABC A 题难度吗。

直接贴代码。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	int ans = 0;
	for(int i = 3; i < s.size(); i++){
		if(s[i - 3] == 'N' && s[i - 2] == 'O' && s[i - 1] == 'O' && s[i] == 'N') ans++;
	}
	cout << ans;

	return 0;
}

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

T2

这场挑战赛质量最高的一题，真的。

我们开个桶，然后枚举 maple 序列两个元素的和是多少，求出对应的长度，取最大值。

#include <iostream>
#include <cstdio>
using namespace std;
int a[200005];
int bucket[10005];
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], bucket[a[i]]++;
	int ans = 0;
	for(int i = 1; i <= 10000; i++){
		int cur = 0;
		for(int j = 1; j * 2 < i; j++){
			cur += min(bucket[j], bucket[i - j]);
		}
		if(i % 2 == 0) cur += bucket[i / 2] / 2;
		cur *= 2;
		ans = max(ans, cur);
	}
	cout << ans;

	return 0;
}

时间复杂度：O(V2)O(V^2)。

T3

由于只能往相邻的移动，所以最优方案就是选定一个点，然后让其他石子全都往这个点移动。而且要从两边开始移，这样可以使得多组石头一次移动，移动次数尽量小。

用两个前缀和和两个后缀和数组。

第一个前缀和数组和后缀和数组记录第 ii 个以前/以后的石子个数，第二个前缀和数组和后缀和数组记录前面/后面的石头搬到第 ii 个点所需最小次数。

然后枚举每一个点查询即可。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[200005];
int qzh[200005], pzh[200005];
int qzh2[200005], pzh2[200005];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++){
		qzh[i] = qzh[i - 1] + a[i];
		qzh2[i] = qzh2[i - 1] + qzh[i - 1] / m + bool(qzh[i - 1] % m);
	}
	for(int i = n; i; i--){
		pzh[i] = pzh[i + 1] + a[i];
		pzh2[i] = pzh2[i + 1] + pzh[i + 1] / m + bool(pzh[i + 1] % m);
	}
	int ans = 0x3f3f3f3f3f3f3f3fll;
	for(int i = 1; i <= n; i++){
		ans = min(ans, qzh2[i] + pzh2[i]);
	}
	cout << ans;

	return 0;
}

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

T4

还是前缀和题。

注意到一个点可以向下 (Bi−Ai+m)mod  m(B_i-A_i+m)\mod m 次调到 AiA_i，也可以向上 (Ai−Bi+m)mod  m(A_i-B_i+m)\mod m 次调到 AiA_i。

而问题九转化成了分成两组，一组向下调，一组向上调，求次数最大值之和的最小值。

我们可以按向下调的次数排序，显然这样向上调的次数就是降序的。

所以我们只需要枚举向下调多少次之内就向下调是最优的，用前缀和优化。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a[200005];
int b[200005];
pair <int, int> cur[200005];
int pzh[200005];
void solve(){
	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++){
		cur[i].first = (b[i] - a[i] + m) % m;
		cur[i].second = (a[i] - b[i] + m) % m;
	}
	sort(cur + 1, cur + n + 1);
	for(int i = n; i; i--){
		pzh[i] = max(pzh[i + 1], cur[i].second);
	}
	int ans = 0x3f3f3f3f3f3f3f3fll;
	for(int i = 0; i <= n; i++){
		ans = min(ans, cur[i].first + pzh[i + 1]);
	}
	cout << ans << '\n';
	for(int i = 1; i <= n; i++){
		pzh[i] = 0;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(∑nlog⁡n)O(\sum n\log n)。

T5

已完成今日输出 Yes No 大学习。

很板的 01BFS。

题意可以转化成在这个方向上的权值为 00，不在的权值为 11。

BFS 的过程只需要权值为 00 的边加队首，权值为 11 的边加队尾就行了。

不会的也可以 dij。

#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
using namespace std;
string a[1000005];
vector <vector <bool>> vis;
int dir[4][2]{-1, 0, 0, -1, 0, 1, 1, 0};
struct node{
	int x, y, step;
};
void solve(){
	int n, m, k;
	cin >> n >> m >> k;
	vis.resize(n + 1, vector <bool>(m + 1, 0));
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] = ' ' + a[i];
		for(int j = 1; j <= m; j++){
			if(a[i][j] == 'O') a[i][j] = 0;
			else if(a[i][j] == 'Y') a[i][j] = 1;
			else if(a[i][j] == 'G') a[i][j] = 2;
			else a[i][j] = 3;
		}
	}
	deque <node> q;
	q.push_back({1, 1, 0});
	while(!q.empty()){
		auto head = q.front();
		q.pop_front();
		if(vis[head.x][head.y]) continue;
		vis[head.x][head.y] = 1;
		if(head.x == n && head.y == m){
			cout << (head.step <= k ? "YES\n" : "NO\n");
			vis.clear();
			return;
		}
		for(int i = 0; i < 4; i++){
			int xx = head.x + dir[i][0];
			int yy = head.y + dir[i][1];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
				if(a[head.x][head.y] == i){
					q.push_front({xx, yy, head.step});
				}else{
					q.push_back({xx, yy, head.step + 1});
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(∑nm)O(\sum nm)。

T6

我认为这题的问题有：

  1. 这题出了有什么意义。
  2. 这玩意为什么能作为挑战赛最难题。
  3. 神人题面自己都弄不明白，数据也能乱造的吗。
  4. 这题哪来的绿难度。
  5. 施氏食狮史。

为简化问题，BiB_i 集合变成一个具体的数值 ∑c∈Bi2c−′a′\sum_{c\in B_i} 2^{c-'a'}。

注意到不需要判断所有区间是否满足条件，只需要判断修改后的 [i−1,i][i-1,i] 和 [i,i+1][i,i+1] 就行了。

先考虑 [i−1,i][i-1,i]。

显然修改后的 Bi′B'_i 必须满足 Bi′∣Bi−1=Bi∣Bi−1B'_i|B_{i-1}=B_i|B_{i-1}。

所以 Bi′B'_i 在 Bi∣Bi−1⊕Bi−1B_i|B_{i-1}\oplus B_{i-1} 这些位必须为 11，而 Bi∣Bi−1B_i|B_{i-1} 没有的地方必须为 00。

那么 Bi′B'_i 的 (Bi∣Bi−1)⊕(Bi∣Bi−1⊕Bi−1)=Bi−1(B_i|B_{i-1})\oplus (B_i|B_{i-1}\oplus B_{i-1})=B_{i-1} 这些位可以为 00 也可以为 11。

同理，可以得出对于 [i,i+1][i,i+1]，Bi′B'_i 的位可以为 00 也可以为 11 也只有 Bi+1B_{i+1}，其余都是固定的。

所以修改 BiB_i 结果不变就只有 2popcount(Bi−1&Bi+1)2^{\text{popcount}(B_{i-1}\&B_{i+1})} 种情况。注意要减去等于 BiB_i 的一种情况。

加起来即可。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
string a[200005];
int b[200005];
void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		for(char c:a[i]){
			b[i] ^= (1 << (c - 'a'));
		}
	}
	b[0] = b[n + 1] = (1 << m) - 1;
	int ans = 0; 
	for(int i = 1; i <= n; i++){
		ans += (1ll << (__builtin_popcount(b[i - 1] & b[i + 1]))) - 1;
	}
	cout << ans << '\n';
	for(int i = 0; i <= n + 1; i++){
		b[i] = 0;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(∑nm)O(\sum nm)。

userId_undefined
去预览
0/2000

全部评论 6

  • userId_undefined

    暴力出奇迹，结果TLE

    7月全勤卷王8月全勤卷王出道萌新时空双修者荣耀黄金快乐小狗


    333个吗，那ACGO是真的蒸蒸日上了

    1周前 来自 上海

    0
  • userId_undefined

    宋雨琦才是真神

    时空双修者荣耀黄金

    《qzh》这个是前缀和
    《pzh》这个是什么？

    2025-10-08 来自 天津

    0
    • userId_undefined

      cjdstttttt

      回复宋雨琦才是真神

      攀枝花市，四川省辖地级市，别称渡口、钢城，地处中国西南川滇结合部，位于四川省最南端，东、北面与四川省凉山彝族自治州的会理、德昌、盐源3县接壤，西、南面与云南省的宁蒗、华坪、永仁3县交界，地处攀西裂谷中南段，属浸蚀、剥蚀中山丘陵、山原峡谷地貌，夏季长，四季不分明，而旱、雨季分明，全市总面积7440平方千米。截至2022年10月，全市辖3个区、2个县。2023年末，攀枝花市户籍总人口106.65万人，常住人口121.8万人。 [62]

      2025-10-08 来自 广东

      0
    • userId_undefined

      cjdstttttt

      回复宋雨琦才是真神

      很显然，p是反着的q，所以是后缀和（

      2025-10-08 来自 广东

      0
    • userId_undefined

      宋雨琦才是真神

      回复cjdstttttt

      o~~~好有道理（不愧是dalao%%%

      2025-10-08 来自 天津

      0
  • userId_undefined

    ppl 大帝

    传道者题解仙人CSP-J一等奖尊贵铂金出题人代码纠察员

    s b数组名

    2025-10-08 来自 浙江

    0
    • userId_undefined

      cjdstttttt

      回复ppl 大帝

      在代码中使用 qzh 和 pzh 作为前缀和与后缀和的变量名，这是一种基于拼音的命名约定。让我详细分析这种命名的意义和背后的考量：

      命名来源分析

      qzh = 前缀和 (Qián zhuì hé)

      • 前 (qián) → q
      • 缀 (zhuì) → z
      • 和 (hé) → h

      pzh = 后缀和 (Hòu zhuì hé)

      • 后 (hòu) → p（这里需要注意：汉语拼音中"后"的声母是h，但可能是为了避免与"和"的h重复，选择了p）

      这种命名的意义

      优点：

      1. 简洁性：相比完整的英文单词，拼音缩写更短

        // 对比示例
vector<int> prefixSum;  // 英文全称
vector<int> qzh;        // 拼音缩写

      2. 中文思维友好：对于中文母语的开发者更直观

      3. 代码紧凑：在算法竞赛中很常见，节省打字时间

      缺点：

      1. 可读性降低：非中文背景的开发者难以理解
      2. 容易混淆：pzh中的p与"后"的拼音不对应，可能造成混淆
      3. 维护困难：在团队协作或长期维护时可能存在问题

      实际应用示例

      // 前缀和与后缀和计算
vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();

// 前缀和 qzh
vector<int> qzh(n + 1, 0);
for (int i = 0; i < n; i++) {
    qzh[i + 1] = qzh[i] + arr[i];
}

// 后缀和 pzh  
vector<int> pzh(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
    pzh[i] = pzh[i + 1] + arr[i];
}

      更好的命名实践

      对于生产环境代码，建议使用更清晰的命名：

      // 推荐命名方式
vector<int> prefixSum;  // 前缀和
vector<int> suffixSum;  // 后缀和

// 或者更简洁但仍清晰的
vector<int> preSum;     // 前缀和
vector<int> sufSum;     // 后缀和

      总结

      使用 qzh 和 pzh 主要体现了：

      • 算法竞赛文化的影响
      • 中文编程习惯的体现
      • 编码效率的考量

      但在实际工程项目中，建议权衡可读性与简洁性，选择更适合团队协作的命名约定。

      2025-10-08 来自 广东

      2
  • userId_undefined

    ༺ཌༀཉི༒白·羊༒༃ༀད༻

    禁言
    出道萌新时空双修者荣耀黄金快乐小狗GESP6级CSP-J一等奖

    你是帅童还是dream还是ppl

    2025-10-08 来自 上海

    0
  • userId_undefined

    ༺ཌༀཉི༒白·羊༒༃ༀད༻

    禁言
    出道萌新时空双修者荣耀黄金快乐小狗GESP6级CSP-J一等奖

    你的代码和我的好像

    #include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int t,n,m,a[200009];
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            int cnt=0;
            for(auto p:s)
                cnt|=(1<<(p-'a'));
            a[i]=cnt;
        }
        int ans=0,u=0;
        for(int i=1;i<=n;i++){
            int z=a[i]&(~u);
            int te=__builtin_popcount(u);
            if(z!=0)
                ans+=(1<<te)-1;
            else
                ans+=(1<<te)-2;
            u|=a[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

    2025-10-08 来自 上海

    0
  • userId_undefined

    cjdstttttt

    时空双修者题解仙人尊贵铂金勇敢小狗CSP-J一等奖出题人

    d

    2025-10-07 来自 广东

    0

热门讨论