"蔚来杯"2022牛客暑期多校训练营7¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 8/1277 | 8 | 10 | 12 |
A¶
solved by TYB
题意¶
分类讨论。
题解¶
略。
B¶
upsolved by JLK
题意¶
给一个\(n\)个点的凸多边形，任意绕着对称轴旋转，问能覆盖多少体积。
\(3 \le n \le 10^5\)
题解¶
首先考虑一下任意旋转得到的形状。
- 如果没有对称轴，体积为0
- 如果有一个对称轴，那么就是绕着这个对称轴转
- 如果有至少两个对称轴，那么会转成一个球。
那么就要找对称轴。一种方法是，按一定顺序列出边和角，再全部循环一次，得到\(4n\)的数组。对称轴可能在边上或者角上，如果选定了一个对称轴，那么两边应当构成一个回文。也就是说，这样排列后长度\(\ge 2n\)的回文串中心就可以作为对称轴。
找到对称轴之后要求出对称轴所在的直线。可以通过几何关系向量搞搞，也可以直接取当前点和整个多边形对面对应的那个点。"点"指的是，如果对称轴在边上，就是求两个端点的中点，在角上则就是角上的这个点。
那么现在找到了对称轴。如果只有一个，可以积分求出旋转后的体积。具体来说，考虑对称轴切开的半边凸包，积分计算每条边的贡献（转一下，利用投影和点到直线距离即可算出）。
如果有两个对称轴，那么找到对称轴的交点，再找到距离交点最远的点，它们的距离即为球的半径。交点可以直接选两个对称轴直线求交，也可以求重心（是等价的）。
用马拉车就是\(O(n)\)的。
C¶
solved by YZW
题意¶
题解¶
D¶
**upsolved by **
题意¶
题解¶
E¶
upsolved by TYB
题意¶
给一个长度为\(n\)的序列，每个数各不相同，对于其每个前缀，求出将其变成单峰序列的最小相邻交换次数。
\(n\le2\times10^5\)
题解¶
赛时考虑贡献的方向错了。
单峰序列有上凸和下凹两种，是对称的，只需要考虑其中一种情况。不妨只考虑上凸。
可以从小到大考虑每个数，那么每个数要么移动到最左边，要么移动到最右边。移动到左边的步数是左边比其大的数个数\(L\)，移动到右边的步数是右边比其大的数个数\(R\)，那么这个数的贡献就是\(\min(L,R)\)，我们要求的就是\(\sum \min(L,R)\)。
从左到右考虑每个前缀，当一个数加入时，它的\(L\)已经固定，而\(R\)会不断增大。因此我们可以维护\(L\)的和以及\(\sum\min(0,R-L)\)。这个是可以动态维护的，大概是当一个位置的值到\(0\)后，暴力删掉这个位置。需要线段树支持区间加，区间最大值等，比较麻烦。
看了一下其他队伍的短代码，发现了另一个思路。考虑每个数的贡献，是个分段函数，一开始是\(R\)，随着\(R\)增大，后面就变成\(L\)了。对于每个数，可以二分求出这个分界点~树状数组上二分和直接二分好像都很快~，这样就可以更简单地维护贡献了。
\(\mathcal{O}(n\log n)\)
F¶
solved by JLK
题意¶
有一个环形数组\(a_i\)，每次可以把相邻的一对相同或者和为\(x\)的数拿掉。问最多能进行多少次操作。
\(1 \le n \le 10^5,1 \le x ,a_i \le 10^9\)。
题解¶
考虑对于一个\(a\)所有能消的组合。\((a,a),(a,x-a),(x-a,a),(x-a,x-a)\)。
也就是说\(a\)和\(x-a\)是等价的，可以把大于\(\frac {x}{2}\)的\(a\)全部变成\(x-a\)，之后就是相同的数删除了。
其实策略就是能删则删。如果当前某一对\(a_i,a_{i+1}\)不删，而是留着给其他数配对，那肯定不优。
比如\(\cdots,a,x\cdots,a,a,y\cdots,a,\cdots\)，如果第二个\(a\)留着给第一个\(a\)配对，第三个\(a\)和第四个配对，说明\(x\cdots\)和\(y\cdots\)都消掉了，那不如直接第二个和第三个配对，第一个和第四个配对。
维护一个栈就可以了，每次能删就弹出，最后还需要把栈顶和站底消一消。
\(O(n)\)
G¶
solved by YZW
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
solved by TYB
题意¶
签到。
题解¶
略。
K¶
solved by TYB
题意¶
\(A,B\)取石子，\(A\)先手，无法操作者输。
每次选择一堆，取出至少一个石子，然后可以选择将这堆剩下的所有石子与另外一堆石子合并。
给出一个长度为\(n\)的序列，\(q\)次询问，每次询问\([l,r]\)中有多少子串构成的游戏，先手必胜。
\(n,q\le10^5\)
题解¶
这种新的博弈，一般从简单的情况开始考虑。
一堆先手必胜，两堆若相同先手必败，否则必胜，这是比较显然的。
考虑三堆，先手必胜。若已存在两堆相同，可以直接把第三堆拿完；否则拿最多的那一堆，再合并一下，也能让剩下的两堆一样。
考虑四堆，那么每个人都不想取完任意一堆，否则必败。那么将每堆石子的个数\(-1\)的普通尼姆游戏就与之等价。
有了这四种情况，可以大胆猜想了：奇数堆先手必胜，偶数堆SG值即为石子个数\(-1\)的异或和。
那么莫队搞一下即可。
L¶
solved by JLK
题意¶
给一个简单无向联通图，有边权，求一个最大的每条边只经过一次的环，使得环上边权（最大值-最小值）最大。
保证有环。
\(3 \le n,m \le 10^5\)。
题解¶
相当于是找两条边，然后用两条边不相交的路径串成一个环。
显然一个边双里的任意两条边都能满足。而不是一个边双里的一定不行。
那么就是求出边双，然后每个边双记一下最大的边和最小的边（注意边权全部相同的时候不能记录同一条边）。现在就是要找这两条边构成的环。
比赛时想的一个乱搞做法就是，指定第一条边的端点和第二条边的端点，随便找一个（不经过割边和这两条边的）路径，然后删掉所有边，再找另一对端点之间的路径，最后合起来。这个显然是假的。但是通过乱搞还是可以通过。具体来说就是指定端点的时候把每个pair都试一遍，一共8种情况，都跑一遍感觉挺难卡掉的。
实际上直接flow就可以了。把两条边看做源点和汇点，连到两个端点，然后无向图每条边流量为1。不能两个方向都建边，否则可能跑出来走了两次的环。应该把两个方向建在一对边上。
也就是说，不能
1 2 3 4 | |
而应该
1 2 | |
流一遍得到一个最大流为2的图。把图抠出来就是环了。由于只需要增广两次，复杂度是线性的。
记录¶
YZW过C(0:15)。
JLK过F(0:33)。
TYB过J(0:43)。
YZW过G(0:47)。
TYB和JLK看K，推了比较小的情况之后JLK猜了个结论，但是不太会证明。TYB决定冲，然后过了(1:46)。
JLK试了一发L的乱搞，MLE（其实是死循环了，也就是没找到）。
此时YZW和TYB讨论出了I，YZW开始写。TYB和JLK看A、L。
I过了(3:26)。
YZW找到了Hack数据并提出加强版乱搞，JLK改了改就过了L(3:40)。
然后搞A，一开始打算高斯消元，想了想直接手玩也不难。两个人各写了一份然后校对了一下，后来YZW补充了一种情况，就过了(4:43)。
总结¶
Dirt¶
L(-1)