ACGO 挑战赛 #20 全题解

userId_undefined

ppl 大帝

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

2025-07-13 22:02:20

发布于：浙江

180阅读
0回复
0点赞

ACGO 挑战赛 #20 全题解

声明：如果您阅读本题解只是学术价值，请跳过每道题的“前言”部分。

故事的开端

Link
然后有一个我们都不认识的人说了一句话

结果实在是太需要 fs 了，等不了疯癫赛，就肝一篇较长的指导性文章 Link。
可是主播的 fs 数依旧没有任何增长，然后刚好碰上了挑战赛，想着先写一篇题解。
于是就有了这篇文章。

T1 小午的222

前言


T1 可是道难题啊（（（
我们的 @AAA水泥批发BaiRX哥，@复仇者_帅童，@亚洲卷王 AK IOI 等等 dalao 都被罚了一道两发（（（

他们可真 fw 啊（纯恶意

题面描述

给定一个大整数 n=a×10b(1≤a<10)n=a \times 10^b(1 \le a \lt 10)，请找出一个整数 tt 使得 n2t\frac{n}{2^t} 为正整数，求 tt 的最大值。

题目分析

容易发现，n≤10106n \le 10^{10^6}，显然不可使用普通变量存储，但打高精度有太麻烦了，考虑常数求值。
首先我们令 f(x)f(x) 为使得 x2t\frac{x}{2^t} 为正整数的最大整数 tt，然后考虑一个性质，即 f(x)=f(y)+f(z)(1≤y,z<x,x=yz)f(x)=f(y)+f(z)(1 \le y,z \lt x,x=yz)（这里不做证明，留给读者自己思考），所以 f(n)=f(a)+f(10b)=f(a)+f((2×5)b)=f(a)+f(2b×5b)=f(a)+f(2b)+f(5b)=f(a)+b+0f(n)=f(a)+f(10^b)=f(a)+f((2 \times 5)^b)=f(a)+f(2^b \times 5^b)=f(a)+f(2^b)+f(5^b)=f(a)+b+0。除了第一项，其它均为常数，而第一项又可以在短时间时间内求出。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int sum[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0};//打表打法，其实也可以不要
string s;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	int tmp = s[0] - '0';
	cout << s.size() - 1 + sum[tmp];//输出 
	return 0;
}

T2 午枫的01树中心

前言


T2 也是道难题啊（（（
我们的 @dream_陆军展览 dalao 也罚了一发，不过因为人数少于 T1，所以难度应该会简单点。

题面描述

给定一棵树，每个节点都有一个点权（00 或 11），求对于一个点与它相连接的所有点中满足这点与他们的点权均不相同的点的个数

题目分析

T2 其实真的不难，它没有涉及到任何算法以及思考，无脑模拟即可，而 T1 还需要进行一定的转换。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int n, a[maxn];
vector<int>e[maxn];//邻接表存储 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	//存树 
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		bool flag = 1;
		for (auto j : e[i]) if (a[i] == a[j]) {
				flag = 0;
				break;
			}
		if (flag) ans++;//判定 
	}
	cout << ans;//输出 
	return 0;
}

T3 午枫爱搬家2

前言


T3 确实不难，就是一道 01 背包的板子。不过 ppl 第一发还是 RE 了，大概是调了五六分钟才调出来，代码放附件了，看看你们需要多久找出来。

题面描述

01 背包板子

题目描述

无。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e3 + 10, maxm = 2e4 + 10;
int n, m, w[maxn], v[maxn], f[maxm];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++) for (int j = m; j >= w[i]; j--) f[j] = max(f[j - w[i]] + v[i], f[j]);
	cout << f[m];
	return 0;
}
//如果有不会 01 背包的同学可以看一下这个 https://oi-wiki.org/dp/knapsack/#0-1-%E8%83%8C%E5%8C%85

T4 午枫的又一个01串

前言


我个人认为 T4 可能是本场比赛的防 AK 题（大雾

题面描述

给定一个 01 串，定义“度”为整个串中的连续段数量减一，每次需找出一个区间 [l,r][l,r]，满足区间合法长度大于 11 且 sl=0,sr=1s_l=0,s_r=1，对区间内的每个元素进行取反操作。请问进行做多 mm 次操作后“度”最小为多少。

题目分析

不妨考虑找出每个可能的左端点和右端点，然后进行配对，注意，这里的配对过程有一个小小的贪心，就是我们要对每个右端点配对最小的左端点，而不是对每个左端点配对最大的右端点，这里读者可以自己思考一下缘由。配对完之后再计算每个区间可以减少的度的数量，每次优先选择最多的，最后再处理一些细节就 AC 了。
你可能会觉得不可思议，甚至我自己都不敢相信，可能自己没有办法证明这样是正确的，但容易发现确实没有任何反例能使得这样做错。
这就是第六感。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int n, m;
char s[maxn];  // 存储01串（下标从1开始）
int l[maxn], r[maxn];  // 存储左端点和右端点位置
int pl[maxn], pr[maxn];  // 存储配对区间的左右端点
int len[maxn];  // 存储每个配对区间的度减少量
int cntl, cntr, cntp, sum;  // 计数器：左端点、右端点、配对区间、减少量数组
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> (s + 1);  // 读入数据，字符串从下标1开始存储
	// 计算初始连续段数量（度 = tmp - 1）
	int tmp = 1;  // 初始至少1个连续段
	for (int i = 2; i <= n; i++)
		if (s[i] != s[i - 1])
			tmp++;
	// 收集所有左端点（0开头的位置）
	for (int i = 1; i <= n; i++)
		if (s[i] == '0') {
			if (i == 1) l[++cntl] = i;  // 字符串开头是0
			else if (s[i - 1] == '1') l[++cntl] = i;  // 前一位是1，当前是0开头
		}
	// 收集所有右端点（1结尾的位置）
	for (int i = 1; i <= n; i++)
		if (s[i] == '1') {
			if (i == n) r[++cntr] = i;  // 字符串结尾是1
			else if (s[i + 1] == '0') r[++cntr] = i;  // 后一位是0，当前是1结尾
		}
	// 对左右端点排序（升序）
	sort(l + 1, l + cntl + 1);
	sort(r + 1, r + cntr + 1);
	// 贪心配对：为每个右端点匹配最小的可用左端点
	int p = 1, last = -1;  // p:左端点指针 last:上次使用的右端点
	for (int j_idx = 1; j_idx <= cntr; j_idx++) {
		int j = r[j_idx];
		if (j <= last) continue;  // 跳过已覆盖的右端点
		while (p <= cntl && l[p] <= last) p++;  // 跳过已使用的左端点
		if (p <= cntl && l[p] < j) {  // 找到有效配对
			pl[++cntp] = l[p++];  // 记录配对左端点
			pr[cntp] = j;  // 记录配对右端点
			last = j;  // 更新上次使用的右端点
		}
	}
	// 计算每个配对区间的度减少量
	sum = 0;  // 减少量数组索引
	for (int i = 1; i <= cntp; i++) {
		int l = pl[i], r = pr[i];
		int red = 0;
		if (l > 1) red++;  // 左端点不是开头：可与左侧合并
		if (r < n) red++;   // 右端点不是结尾：可与右侧合并
		len[++sum] = red;  // 记录减少量
	}
	// 将减少量从大到小排序（优先选择减少量大的操作）
	sort(len + 1, len + sum + 1, greater<int>());
	// 选择前m个操作（或全部）
	int cnt = 0, num = min(m, sum);  // cnt:总减少量 num:实际操作数
	for (int i = 1; i <= num; i++) cnt += len[i];  // 累加减少量
	// 计算配对区间的最小左端点和最大右端点
	int minl = n + 1, minr = 0;
	for (int i = 1; i <= cntp; i++) {
		minl = min(minl, pl[i]);
		minr = max(minr, pr[i]);
	}
	if (cntp == 0) {  // 无配对区间时的边界处理
		minl = n + 1;
		minr = 0;
	}
	// 检查特殊操作1：能否从开头操作
	bool type1_ok = false;
	if (s[1] == '0') {  // 开头是0才可能操作
		// 查找第一个≥2的右端点（操作需要至少2个字符）
		int* it = lower_bound(r + 1, r + cntr + 1, 2);
		if (it != r + cntr + 1 && *it < minl)  // 存在且在配对区间之前
			type1_ok = true;
	}
	// 检查特殊操作2：能否操作到结尾
	bool type2_ok = false;
	if (s[n] == '1') {  // 结尾是1才可能操作
		// 查找第一个>max_r_k2的左端点（在配对区间之后）
		int* it = upper_bound(l + 1, l + cntl + 1, minr);
		if (it != l + cntl + 1 && *it < n)  // 存在且在配对区间之后
			type2_ok = true;
	}
	// 计算最终度 = 初始度 - 配对操作减少量 - 特殊操作减少量
	int sp = min(1LL * (type1_ok ? 1 : 0) + (type2_ok ? 1 : 0)/*特殊操作最大减少量*/, m - num/*剩余操作次数*/);//实际可用的特殊操作减少量
	// 输出最终结果（度非负）
	cout << max(0LL, tmp - 1 - cnt - sp);
	return 0;
}

T5 午枫的彩排

前言


T5 其实不难，主要还是要想到这是一道数据结构题。

题面描述

有 nn 位演员，每个演员都有三个指标 wi，si，tiw_i，s_i，t_i，他们会在 sis_i 时刻进入舞台，并在 ti+0.1t_i+0.1 时刻准时离场。我们令 f(x)f(x) 表示第 xx 位演员入场时在场包括自己所有人的 wiw_i 指标（即能力值）最小值，最后对于每位演员请输出 wi−f(i)w_i-f(i)。

题目分析

我们先从暴力做法入手，首先求出一个人的 f(x)f(x) 时间复杂度为 O(n)O(n)，那么求出 nn 个人即为 O(n2)O(n^2)，显然过不了。
接下来考虑优化，对于第二个 nn 显然优化不了，那么考虑第一个 nn，既然是只求最小值不求次小值，很容易想到优先队列 priority_queue。然后又出来一个问题，对于堆内的元素该如何进行过期删除，我个人认为最简单的方法就是存一个 pair 类，第一位存 wiw_i，第二位存 tit_i，每次取出队头最小值时判断是否过期，如果是就再取一个直到队列为空。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn = 2e6 + 10;
int n;
struct Node {
	int w, l, r, idx;
} a[maxn];
priority_queue<pii, vector<pii>, greater<pii>>q;//小根堆 
bool cmp(Node x, Node y) {
	return x.l < y.l;
}
int ans[maxn];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].w >> a[i].l >> a[i].r;
		a[i].idx = i;
	}
	sort(a + 1, a + n + 1, cmp);//排序 
	int now = 0;
	for (int i = 1; i <= n; i++) {
		int help = LONG_LONG_MAX;//先设为最大值，下面再判负取0 
		now = a[i].l;
		while (!q.empty() && q.top().second < now) q.pop();//过期删除 
		if (!q.empty()) help = q.top().first;
		ans[a[i].idx] = max(a[i].w - help, 0LL);//存储答案，注意这里不可以直接输出，因为数组顺序经过排序后已经乱了 
		q.push({a[i].w, a[i].r});
	}
	for (int i = 1; i <= n; i++) cout << ans[i] << " ";//输出 
	return 0;
}

T6 午枫的字符串修改

前言


我觉得 T6 还是有点难度的，但是被 @AAA水泥批发BaiRX哥 dalao 用平衡树爆切了，%%%。

这就说明了 ta 肯定用 AI 了（大雾

题面描述

给定一个长为 nn 字符串，对其进行 qq 次操作，求最终字符串。

题目分析

对于操作一，既然是区间循环加，果断考虑使用差分，但是由于存在操作二，所以整个字符串的下标会收到影响。
但是注意到操作二是进行循环移动，不妨维护一个变量 tmp，用于表示整个字符串经过了多少次循环移动。进行操作一时先用 tmp 计算出真实下标进行差分即可。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5;
char s[maxn];
int n, q, tmp = 0;
int d[maxn];
void type1(int l, int r, int x) {
	x %= 26;
	if (x == 0) return;
	int len = n;
	int real_l = ((l - 1 - tmp) % len + len) % len + 1,
	    real_r = ((r - 1 - tmp) % len + len) % len + 1;//计算真实下标 
	if (real_l <= real_r) {
		d[real_l] = (d[real_l] + x) % 26;
		d[real_r + 1] = (d[real_r + 1] - x + 26) % 26;
	} else {
		d[real_l] = (d[real_l] + x) % 26;
		d[n + 1] = (d[n + 1] + x) % 26;
		d[1] = (d[1] + x) % 26;
		d[real_r + 1] = (d[real_r + 1] - x + 26) % 26;
	}
}
void type2(int x) {
	tmp = (tmp + x) % n;//更新 tmp
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> (s + 1) >> q;
	for (int i = 1; i <= q; i++) {
		int op;
		cin >> op;
		if (op == 1) {
			int l, r, x;
			cin >> l >> r >> x;
			type1(l, r, x);
		} else {
			int x;
			cin >> x;
			type2(x);
		}
	}
	int sum = 0, sh[maxn];
	for (int i = 1; i <= n; i++) {
		sum = (sum + d[i]) % 26;
		sh[i] = sum;
	}//对差分数组求前缀和计算原数组 
	for (int i = 1; i <= n; i++) {
		int pos = ((i - 1 - tmp) % n + n) % n + 1;
		cout << char('a' + (s[pos] - 'a' + sh[pos]) % 26);//因为存在循环移动，所以输出也会受到影响 
	}
	return 0;
}

附件

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e3 + 10, maxm = 2e4 + 10;
int n, m, w[maxn], v[maxn], f[maxn];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++) for (int j = m; j >= w[i]; j--) f[j] = max(f[j - w[i]] + v[i], f[j]);
	cout << f[m];
	return 0;
}

彩蛋

#1 与 cjdst 的赌约

其实就是赌 T3 的难度，上文找不到了（（（

#2 与 BaiRX 的赌约

userId_undefined
去预览
0/2000

全部评论 18

热门讨论