2021 ICPC南京站¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 18/638 | 7 | 7 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by JLK
题意¶
给定一个长度为\(n\)的序列\(a_i\)，以及\(k\)，可以选择一个区间\([l,r]\)（也可以不选），将\(a_l , \dots ,a_r\)全部加\(k\)。要让整个序列的众数出现次数最多，求这个最多次数。
\(1 \le n \le 10^6,-10^6 \le k,a_i \le 10^6\)
题解¶
考虑枚举众数\(x\)。如果需要做操作，那么在选定的操作区间内，\(a_i=x\)的贡献是-1，\(a_i=x-k\)的贡献是1。把这两个取值的数拉出来，就是一个1和-1的序列，求一个最大子段和。线性求解即可。由于每个取值的数只会被枚举两次，所以总复杂度仍然是线性。
\(O(n)\)
赛时没想仔细，直接用线段树维护子段和了，不加优化会TLE。
D¶
solved by JLK
题意¶
定义\(SORT(A)\)如下：
1 2 3 4 | |
求对于每个\(1 \le k \le n\)，\(SORT(A_{1..k})\)中swap了几次。
\(1 \le n \le 10^5,1 \le a_i \le n\)
题解¶
先考虑一下这个sort的本质。
枚举某个\(i\)时，相当于是把\(a_i\)拉出来，当做整个序列的第一个，然后找到这个序列的单调栈，循环右移一次（再把\(a_i'\)放回原位）。swap数为单调栈里的个数-1。
再考虑在序列后面插入一个数，会发生什么。
如果插入的数小于等于前面的最大值，那么原先的最大值在最后一轮之前都会挡在前面，新的数不会产生贡献。在最后一轮，产生的贡献就是单调栈里比它大的数的个数。
如果插入的数就是新的最大值，先假设老的最大值（新的次大值）只有一个。那么在第一轮，次大值被换到最后，而最大值在第一个。此后，最大值的行为和次大值在没插入时的行为相同。直到最后一轮，再把最大值和次大值调回来。这样产生的贡献是2。
如果次大值不止有一个，那么就会有更多的贡献。比如2 2 1 3，插入3的时候，第一轮后为3 2 1 2，第二轮后为2 3 1 2，第三轮后为1 2 3 2。第二、三轮的时候产生了额外贡献。
第二轮，原来2 2并不用换，但是3 2就要换一次，也就是，次大值如果有多个，除了第一个以外，都需要多一次贡献。
第三轮，因为前三位如果是2 2 1，只需要换一次，但是2 3 1就需要换两次。也就是，由于原序列中在第二个次大值（2）之后还有一个1，导致在1这一轮中，增加了一次swap。
综合两种情况可以发现，多出来的贡献就是，第二个次大值之后出现的数的个数。可以在扫的时候顺便维护。大于某个数的个数用BIT维护。
总复杂度\(O(n\log n)\)
E¶
**upsolved by **
题意¶
题解¶
F¶
**upsolved by **
题意¶
题解¶
G¶
**upsolved by **
题意¶
题解¶
H¶
solved by YZW
题意¶
题解¶
I¶
solved by JLK
题意¶
二维平面上有\(n\)个障碍物，\(m\)个金币，在\(y=0\)和\(y=H\)处有两条线为边界，从\((0,0)\)出发，初始速度为\((1,1)\)，碰到障碍物或者边界后，\(v_x\)不变，\(v_y\)反向。能够移除任意数量的障碍物，求拿到最多金币的数量。
$1 \le n,m \le 10^5,2 \le H \le 10^9 $
题解¶
考虑没有障碍物，只靠边界反弹的情况。那么将所有点的\(x\)坐标对\(2H\)取模，如果有两个点在这样的\(2H\times(H+1)\)的区域内处于同一条折线上，那么坐标小的那个一定能到达坐标大的那个。
考虑DP。
可以对于每个金币和障碍物都找到所在的折线。具体来说，可以根据方向倒推，直到\(x=0\)，记下\(y\)坐标当做折线编号。（两种方向的折线不同）
那么在同一条折线上的点就可以从坐标小的转移到坐标大的。还需要考虑障碍物，可以给每个点记录一个方向，到达某个障碍物的时候可以选择变方向或者不变方向，到金币的时候则不能变方向，但是dp值+1。
\(O((n+m)\log(n+m))\)（需要对折线离散化）
J¶
solved by YZW
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
solved by TYB
题意¶
签到。
题解¶
略。
记录¶
JLK过A(0:6)，然后开始写C，TYB和YZW讨论M。
TYB会M了，把JLK顶下来开始写，然后WA了两次（corner case）后AC(0:37)。
JLK继续写C，WA一次TLE一次（线段树，不是最优复杂度），加了一些优化后AC(0:49)。
YZW过H(1:21)，JLK写D，对拍之后AC(1:57)。
TYB用分块写E，写了一会发现假了。换YZW写J，TLE一次（没注意记忆化）后AC(2:48)。
JLK和YZW讨论I，JLK写，WA一次后AC(3:58)。
然后一起想E。还剩半小时多的时候JLK想到矩阵乘法，开始码，最后10min敲完，但是没过。
总结¶
JLK：写题有点慢，罚时有点多，没有看出E是经典模型。
Dirt¶
C(-2)
I(-1)
J(-1)
M(-2)