CSDN第11次竞赛题解与总结

• 前言
• 建议
• 题解
• T1圆小艺
• • 扩展
  • 完整代码
• T2K皇把妹
• • 完整代码
• T3筛选宝物
• • 完整代码
• T4圆桌
• • 完整代码
• 总结

前言

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表维护区间最值然后线段树(莫队好像也行，但我不会用)，然鹅不知如何对 2642^{64}264取模的我直接开摆(但我同学说开ull自然溢出就是对它取模,白给75分)
总结：成绩证明没了，***，退钱，准备AFO去卷whk了

建议

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

T4: codeforces原题

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

接下来是

题解

T1圆小艺

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

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

扩展

x&1x \& 1x&1表示取二进制最后一位，若x&1=1x\&1=1x&1=1表示其为奇数，
等同于xmod2=1x\mod 2 =1xmod2=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;
}

T2K皇把妹

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

abs()abs()abs()为绝对值函数，初一大家就学过
abs(x)={x,x≥0−x,x<0abs(x)=\left \{\begin{aligned}x,x\ge0\\-x,x<0\end{aligned}\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到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));
}

完整代码

#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;
}

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;
}

T4圆桌

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

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

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

记得开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;
}

总结

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