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)$如下：

for i in range(1,n+1):
    for j in range(i,n+1):
        if a[i]<a[j]:
            swap(a[i],a[j])

求对于每个$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)

2021 ICPC南京站¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

M¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

2021 ICPC南京站 ¶