CSDN第11次竞赛题解与总结

前言

2022/11/27 CSDN第11次竞赛 由「壹合原码 & CSDN」联合主办

本次奖励还是不错的 (毕竟有赞助商)，前三十名都有奖励，连以前第1名才有的高级定制背包都改成了4~10名， (又嫖了一个包真好)

昨天刚比完NOIP今天就拿了AK真不戳
但我NOIPT1多组数据忘清数组了，100—>12，被迫AFO(吐槽:ccf出样例能不能不要这么水，三个样例全T=1，还有第三样例输出114 514真臭)
T2没看懂(这题是内涵某微信小程序？)
T3明显tarjan缩成树然后树形dp
T4 一眼想到ST表维护区间最值然后线段树(莫队好像也行，但我不会用)，然鹅不知如何对 $2^{64}$取模的我直接开摆(但我同学说开ull自然溢出就是对它取模,白给75分)
总结：成绩证明没了，***，退钱，准备AFO去卷whk了

建议

正文前先提些建议
题目能不能出难点，有点原创性，我AK平均一题12行
如T3:
这01背包也太裸了吧

T4: codeforces原题

而且出这种模板题,原题已经不是第一次了，第九次竞赛的第二题就是上古贪心题，第四题也是codeforces原题

接下来是

题解

T1圆小艺

最近小艺酱渐渐变成了一个圆滑的形状-球！！ 小艺酱开始变得喜欢上球！ 小艺酱得到n个同心圆。 小艺酱对着n个同心圆 进行染色。
相邻的圆范围内不能有相同的颜色。相隔一层的圆颜色相同。 小艺酱想知道圆最外层的那种颜色全部染了多 少？

水题，圆环面积小学生都会求
$$S=\pi (R^2-r^2),R>r$$
先按半径大小排序
奇数层染一种颜色，偶数层染一种
最后根据n的奇偶性输出
注意精度问题 (博主因π只设到3.1415926导致80分卡了10min)
当然要精准的可以 $\pi =\arccos (-1)$

扩展

$x\&1$表示取二进制最后一位，若$x\&1=1$表示其为奇数，
等同于$x\mathrm{m}\mathrm{o}\mathrm{d}2=1$

完整代码

#include
using namespace std;
const double pie = 3.1415926535897932846;
double a[11000],s1,s2;
int main(){
	int n; cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
		if(i & 1) s1 += pie*(a[i]*a[i]-a[i-1]*a[i-1]);
		else s2 += pie*(a[i]*a[i]-a[i-1]*a[i-1]);
	if(n&1) printf("%.3lf",s1);
	else printf("%.3lf",s2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

T2K皇把妹

存在n个节点，目标节点在m。
每个节点有自己的权值a。
在权值k内（含k值）选择一个权值非0节点且与目标节点距离最近。
节点i与节点j的距离为abs(i-j)

$abs()$为绝对值函数，初一大家就学过
a b s ( x ) = { x , x ≥ 0 − x , x < 0 abs(x)=\left \{

\right. abs(x)={x,x≥0−x,x<0​
这题就是简单的模拟，从点m出发，两边扩展判断是否合法，找到第一个就是最近的

for(int i=m-1;i>=1;i--)
	if(a[i] <= k&& a[i] != 0){
		ans = min(ans,m-i);
		break;
	}
for(int i=m+1;i<=n;i++)
	if(a[i] <= k && a[i] != 0){
		ans = min(ans,i-m);
		break;
	}
1
2
3
4
5
6
7
8
9
10

或者也可以从1到n全遍历一遍，维护合法最小值

for(int i=1;i<=n;i++){
	if(i==m) continue;
	if(a[i]<=k && a[i]!=0) ans = min(ans,abs(i-m));
}
1
2
3
4

完整代码

#include
using namespace std;
int a[1010],n,m,k,ans = 99999999;
int main(){
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++){
		if(i==m) continue;
		if(a[i]<=k && a[i]!=0) ans = min(ans,abs(i-m));
	}
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

T3筛选宝物

已知存在n个宝物，每个宝物都有自己的质量m和价值v，在考虑选择宝物时只能选择总质量小于等于M的方案，
请问在最优方案下选择宝物，能获取到最大价值V是多少？

01背包版子题，关于它的讲解到处都是，这里不再讲解，
找了一篇写得不错的，供大家参考 这里

完整代码

#include
using namespace std;
int n,s,m[1010],v[1010],f[101];
int main(){
	cin >> n >> s;
	for(int i=1;i<=n;i++) cin >> m[i] >> v[i];
	for(int i=1;i<=n;i++)
		for(int j=s;j>=m[i];j--)
			f[j] = max(f[j],f[j-m[i]]+v[i]);
	cout << f[s];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

T4圆桌

有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边，但是每位客人希望自己左右边上分别有一些空座位，
不然会觉得害羞。注意，如果一个客人所在的圆桌只有他一个人，那么他左边的空座位数量就是他右边的空座位数量。 试
问主人需要准备多少个座位，才能让每个客人舒适的坐下。

codeforces原题，亏我还做过
贪心水题，策略如下

题目要求椅子数最少，就要使两人之间公用的椅子最多。
因为可以自由安排座位,所以就只需要把 $l_i$ 和 $r_i$ 排序来找。
因此只需要找排序后的 $l_i$ 和 $r_i$​，取 $\max (l_i,r_i)$ 累加。

记得开longlong

完整代码

没错只有九行

#include
long long n,ans,l[101000],r[101000];
signed main(){
	std::cin >> n;
	for(int i=1;i<=n;i++) std::cin >> l[i] >> r[i];
	std::sort(l+1,l+1+n); std::sort(r+1,r+1+n);
	for(int i=1;i<=n;i++) ans += std::max(l[i],r[i]);
	std::cout << ans+n; return 0;
}
1
2
3
4
5
6
7
8
9

总结

送了一个包，真不戳
还有我上次的签名书什么时候发货，快递单号多少，为何我一点消息都无？