挑战赛 #20 全题解！

userId_undefined

复仇者_帅童

小有名气CSP-J一等奖出题人

2025-07-14 12:42:37

发布于：湖南

241阅读
0回复
0点赞

感谢 @AAA混泥土批发ppl哥 让我喜提干儿子 @dream_陆军展览 和 @AAA水泥批发BaiRX哥（

T1

个人难度：红上

设 n=m×10k(1≤m≤10n=m\times 10^k(1\le m\le 10，m,km,k 均为正整数))，

则 n=m×2k×5kn=m\times 2^k\times 5^k，kk 为 nn 的位数 −1-1。

所以我们只需要看 mm，即 nn 的首位，能被 22​ 的几次方整除即可。

我们可以用 __builtin_ctz 来实现。这个函数可以统计一个数转换成 22 进制后末尾 00 的数量。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	cout << s.size() - 1 + __builtin_ctz(s[0] - '0');

	return 0;
}

时间复杂度：O(∣n∣+log⁡w)O(|n|+\log w)，其中 w=32w=32。

T2

个人难度：橙下

先放代码。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[200005];
vector <int> v[200005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);//建树
		v[y].push_back(x);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		bool flag = 1;
		for(int j:v[i]){
			if(a[i] == a[j]) flag = 0;//判断是否相同
		}
		ans += flag;
	}
	cout << ans;

	return 0;
}

诶，这时就有酮穴要问了，这个代码怎么不会 TLE 啊？

我们分析一下时间复杂度，发现瓶颈在遍历边判断是否相同的操作。

显然，一个点遍历的次数就是它的度数。而我们又知道无向图所有点的度数之和是边的数量的 22 倍，所以不会 T。

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

T3

个人难度：橙中

01 背包板子，不作解释。注意 dp 数组大小。

挑战赛已经水成这样了吗

#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
int dp[20005], a[5005], b[5005];
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] >> b[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= a[i]; j--) dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
	}
	int ans = 0;
	for(int i = 1; i <= m; i++) ans = max(ans, dp[i]);
	cout << ans;

	return 0;
}

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

T4

个人难度：橙上/黄下

依旧 01 串。依旧修改左 0 右 1。依旧 10610^6。

由于连续相同的数对最小值没有影响，所以为了简化，将字符串压缩。如 11000111100101，就压缩成 1010101。

我们先统计一下每个 1 的贡献：

  • 在一个中间部分的 1，会贡献两个那啥。
  • 在边上的 1，会贡献一个。

而一次操作可以将两个中间的 1 合并，使那啥 −2-2，所以当操作数没那么充足时，答案为初始的那啥 −2m-2m。

而当 mm 足够大可以使 01 串只有一个中间的 1 （类似 10101）时，我们还可以额外进行操作：

  1. 将中间的 1 与左边的进行合并，当最左边有 1 时，那啥 −2-2，否则那啥 −1-1。
  2. 将左边的 1 与右边的进行合并，那啥 −1-1。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
string s, s2;
int n, m;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s;
	s = ' ' + s;
	s2 = ' ';
	for(int i = 1; i <= n; i++){
		if(s[i] != s[i - 1]) s2.push_back(s[i]);//压缩
	}
	s = s2;
	n = s.size() - 1;
	if(n == 1){//不知道有没有用的特判
		cout << 0;
		return 0;
	}
	int ct = 0, ans = 0;
	bool flag1 = 0, flag2 = 0;
	for(int i = 1; i <= n; i++){
		if(i == 1 && s[i] == '1') flag1 = 1, ans++;
		else if(i == n && s[i] == '1') flag2 = 1, ans++;//统计贡献
		else if(s[i] == '1') ct++, ans += 2;
	}
	if(m <= ct - 1){//m不够大时
		cout << ans - m * 2;
		return 0;
	}
	ans -= (ct - 1) * 2, m -= (ct - 1);//进行额外操作
	if(m) ans -= (flag1 + 1), m--;
	if(m && flag2) ans--;
	cout << ans;
	
	return 0;
}

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

T5

个人难度：黄中/上

不是哥们，为啥大家的难度都比我低啊

这个题目可以如下转化：
给定一个数列 AA，初始值为 −∞-\infty，

给定 nn 个区间，你要对 AA 进行 nn 次操作，每次将 Aj(Li≤j≤Ri)A_j(L_i\le j\le R_i) 赋值为 min⁡{Aj,Xi}\min\{A_j,X_i\}，

接下来询问每个区间的左端点的值。

由于 Li,Ri≤109L_i,R_i\le 10^9，过于巨大，所以考虑离散化，使 Li,Ri≤2nL_i,R_i\le 2n，然后将区间按 LiL_i 排序。

接下来枚举每个 AjA_j，用个小根堆记录当前区间 XiX_i 的最小值，如果有区间的 LiL_i 就加入堆，如果堆顶的区间不包含 jj 了，直接删除。

但是现在，就有销货般要问了：那这样也没有把离开的区间删干净啊！

你先别急，仔细思考什么时候区间才会对 AjA_j 发挥贡献：一定是 XiX_i 最小的时候！所以 XiX_i 不是当前在堆中最小的时，可以暂时不用管他。

这就是 "Lazy Delete" 思想！

代码如下。

//以下头文件全都得用 
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
using namespace std;
struct node{
	int x, y, z, id;
	bool operator < (const node &b) const{
		if(x == b.x) return id < b.id;
		return x < b.x;
	}
	bool operator > (const node &b) const{
		if(z == b.z) return id > b.id;
		return z > b.z; 
	}
}a[1000005];
map <int, int> mp;
priority_queue <node, vector <node>, greater <node>> q;//使用>的重载进行排序 
int ans[1000005];
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].z >> a[i].x >> a[i].y;
		a[i].id = i;
		mp[a[i].x] = 0;
		mp[a[i].y] = 0;
	}
	for(pair <int, map <int, int>::iterator> tmp = {1, mp.begin()};
	tmp.second != mp.end(); tmp.first++, tmp.second++) tmp.second -> second = tmp.first;//离散化
	for(int i = 1; i <= n; i++){
		a[i].x = mp[a[i].x];
		a[i].y = mp[a[i].y];
	}
	sort(a + 1, a + n + 1);//按左端点 L_i 排序
	vector <int> v(mp.size() + 5);
	int cur = 1;
	for(int i = 1; i <= mp.size(); i++){
		while(!q.empty() && q.top().y < i) q.pop();//lazy delete
		while(cur <= n && a[cur].x <= i) q.push(a[cur++]);//区间在就加
		v[i] = q.top().z;//按方法算出 A_i
	}
	for(int i = 1; i <= n; i++){
		ans[a[i].id] = a[i].z - v[a[i].x];//查询
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << ' ';

	return 0;
}

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

题外话：受ppl邀请打了一下这个OJ的CSPS模拟赛，T1 我就是用的这种方法，结果题解是：

T6

个人难度：橙上

很版的差分，最水的一集。

由于是整体偏移，所以考虑操作 11 直接在原字符串上偏移后进行操作。例如字符串长度 77，当前修改区间 [1,5][1,5]，偏移量 33，则在原字符串修改的区间为 [6,7][6,7] 和 [1,3][1,3]。

注意最后输出时也得偏移。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
string s;
int dif[1000005];
int n, m, cur;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> s >> m;
	while(m--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int l, r, val;
			cin >> l >> r >> val;
			l = (l - 1 - cur + n) % n + 1;//偏移
			r = (r - 1 - cur + n) % n + 1;
			val %= 26;
			if(l > r){//[l,n],[1,r]
				dif[1] += val, dif[r + 1] -= val;
				dif[l] += val, dif[n + 1] -= val;
			}else{//[l,r]
				dif[l] += val, dif[r + 1] -= val;
			}
		}else{
			int val;
			cin >> val;
			cur = (cur + val) % n;//增加偏移
		}
	}
	for(int i = 1; i <= n; i++){
		dif[i] += dif[i - 1];//前缀和操作
	}
	for(int i = 0; i < n; i++){
		s[i] = (s[i] - 'a' + dif[i + 1]) % 26 + 'a';
	}
	s = s.substr(n - cur) + s.substr(0, n - cur);//加上偏移后的s
	cout << s;

	return 0;
}

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

userId_undefined
去预览
0/2000

全部评论 13

热门讨论