2021 ICPC 南京站

2021ICPC南京难金站。

比赛链接

游记？

能在难金站拿金还是很满意啦。

Day 0

看了眼知乎，发现原来自己碰上了诸神黄昏。。

考了习思想，啥都不会。

睡不着。

Day 1

两点钟才睡着，然后一直半睡半醒的状态到7点半。

起来后，室内体测，胖了好多，坐位体前屈都压不下去了。。

回宿舍瘫到9点45，然后去吃早餐。

11点比赛。

meaningful上来就发现A是签到，然后靠着巨快的手速拿到一血。

接着我简单告诉了meaningful M题题意，然后去看其他题。CRH380BL-2339一直在想D。期间发现J看来十分好做。

然后meaningful就会M了，我想了想后也会了。15min的时候交了1发然后WA。然后我突然想到 $n=1$ 要特判，加了以后就过了。

然后meaningful就把C秒了，我写了个线性最大子段和顺利的1A了。

接着开始写J，我天真的写了个dfs，结果十分显然的T了。

接着换CRH380BL-2339上，但是有点想错了，导致一直WA。而我在旁边想了好一会儿四元环计数发现不太会容斥，然后跃跃欲试想要把J加一个记忆化，以及和他们一起思考D题，结果发现完全帮不上忙。

最终J加了个记忆化立刻就过了，然后meaningful写了个H也1A了。

然后他们继续想D，我去退了一下E题的式子。

很快发现E题只需要维护前缀平方和的历史和，前缀平方和，前缀和等等的值就可以了，然后分类讨论画了三种情况，写了三个 $5\times 5$ 的矩阵就会了。

在我边打E的时候，D题也快有结果了。打到一半，D题改了一个位置就过了。E连着MLE两发，发现是5e4给我写成了5e5。。改了之后发现TLE了。

然后就疯狂的卡常时间，卡了好久，在meaningful的强烈建议下造了个极限数据，发现本地要跑8s…并不是很会优化复杂度。结果CRH380BL-2339一语惊醒梦中人，将矩阵乘法里遇到0就不乘法的优化加了上去就A了。

在全队的注视下meaningful很快写完了I，调了一会儿直接1A。

此时是286分钟，发现我们已经稳Au了，然后就再次开始了愉快的评价题目环节。

出来以后发现是Rank14，本赛季打得最好的一次。

题解

A

分四种情况讨论即可。

C

设 $s_{l,r}(x)$ 表示 $x$ 在 $[l,r]$ 的出现次数。那么就是枚举 $x$，然后选择一段区间，使得 $s_{1,n}(x)+(s_{l,r}(x-k)-s_{l,r}(x))$ 最大。

记 $s_i=[a_i=x-k]-[a_i=x]$，然后分开跑最大子段和。

时间复杂度 $O(n)$。

D

考虑进行完第 $i$ 轮操作之后，前面 $[1,i]$ 已经有序了。那么几乎所有的位置的贡献就是前面比他大的数有多少个，剩下的贡献有两次，最大的一次。

按照这个情况分类讨论就好了，有亿点细节。时间复杂度 $O(n\log n)$。

E

比赛时做法：维护前缀平方和的历史和，前缀平方和，前缀和等等的值就可以了，然后分类讨论，写三个 $5\times 5$ 的矩阵。

不用前缀和去做会方便很多，矩阵非常好看，还只用 $4\times 4$ 的矩阵。

H

简单树形DP，维护一下两种转移。

I

队友做的，回去了看一下，真的好简单啊，这榜也太歪了。。

从后往前DP一下，遇到一个转折点分两种情况都取其最大值就好了。

J

发现只用前两种操作，那么 $a-b$ 的值不变；用第三种的话，$a-b$ 除以一个质数 $p$。

那么最后 $a-b$ 变到 $1$，答案就出来了。因此，直接记 $f(a,b)$ 表示 $(a,b)$ 到最终结果的最小步数。

有这么一个性质：对于一个数 $x$，有若干整数 $a_1,a_2,\cdots,a_n$，用不同的顺序，不管上取整还是下取整去除 $x$，最终结果最多只有两种。

那这样对于某个特定的 $a-b$ 的因子 $d$ 而言，满足条件的 $(a,b)$ 最多只有几种，因此有用的 $f(a,b)$ 的个数为 $O(d(a-b))$。直接上记忆化就好了。

M

当 $n\geq 2$ 时，相当于给每个数选一个加还是减，至少有一个减，一个加。

当 $n=1$ 时，特判一下。