djwj233 的博客

djwj233 的博客

历年 NOIP/CSP 简要题解

posted on 2021-10-13 08:55:25 | under 比赛题解 |

配套题单

以下考虑的期望得分均不考虑挂分

NOIP 2015

Day 1

签到题,按照题面直接模拟即可,比儒略日不知道高到哪里去了!!1Code

简单题,直接一个 DFS 求出最小环所含有的结点数。Code

防 AK 题,做的时候不太会。正解应该是 DP,个人觉得大多数贪心实际都能被卡掉,而且也懒得写一些莫名其妙的特判。

DP 的方法是记录出现四次、三次、两次、一次的牌各有几种,然后转移转移转移。

但我们发现这种做法没法处理顺子,那么我们对每个询问暴搜打顺子处理。

可以去UOJ上交这题更强的数据。Code

Day 2

二分答案后转为判定,十分简单。Code

中规中矩的 DP。看到数据范围很小,大胆猜测时间复杂度是 $\Theta(nmk)$,然后我们发现从小到大枚举 $k$ 这一维即可列出$$ dp_{x,y,z}= \begin{cases} 0 &A_y\ne B_z\\ dp_{x,y-1,z-1}+\sum_{i=0}^{y-1}dp_{x-1,i,z-1}&A_y=B_z \end{cases} $$ 可以用前缀和搞掉那个和式,然后随便滚动数组一下即可。Code

比较难的一个图论题。注意到问题中带有最大值最小的约束,考虑二分答案。

二分完了我们发现所有计划中当前长度小于等于二分值 $x$ 的都不需要考虑,而大于 $x$ 的计划对应的路径中至少要有一条边覆盖到。

因此我们对这些路径整条路径的值加一,然后简单讨论,这可以用树上差分维护。

之前写过的代码:Code

总结

无论如何保底得分都应当有 $\texttt{100+100+?+100+100+50>450}$。(我们假使 D2T3 直接不会,打了个 $\mathcal O(n^2)$ 的暴力)

实际上除了 D1T3 以外所有的题都应当 AC,个人认为讨论 D1T3 的得分不太有意义

NOIP 2016

这整套题之前练过

Day 1

签到题,按照题面直接模拟加点小优化即可,比儒略日不知道高到哪里去了!!1

之前的代码:Code

毒瘤题。我们考虑将出现的时间看作一种物品,这样问题就转化成了路径添加物品、最后总体查询。

这已经可以套用雨天的尾巴里的做法,借助树上差分 + 线段树合并实现 $\mathcal O(n\log^2 n)$。

实际上这题不需要线段树合并,直接维护一个全局数组即可 $\mathcal O(n\log n)$。感觉这题和 T3 放反了?

重新写了一遍:Code

部分分的话有 20pts 的 $\mathcal O(n^2)$,链的 15pts 算是启发正解,后面两个特殊性质不知道是干嘛的。

这题看着比较艰难,再加上 T2 的加持会显得十分不可做。

实际上个人感觉这题出得很没水平,这个 Floyd 跑最短路的乱入是毫无意义的,而且这题主要难在前置知识而不是思维,T2 比它高得很。

具体做法就是 DP,列出状态转移然后硬搞,就没了。之前的代码:Code

Day 2

画风友好的简单题。由于 $k$ 在开始的时候已经给了,因此可以预处理出所有的值然后搞一个前缀和。

之前的代码:Code

经典题。首先很容易可以想到用一个堆通过记录全局生长差值去维护里面所有的蚯蚓,这是 $\mathcal O((m+n)\log n)$ 的,能拿到 85pts。

然后注意到排序后新插入的蚯蚓满足单调性,可以用队列换掉这一过程,这是 $\mathcal O(n\log n+m)$ 的满分做法。Code

大概算防 AK 题?直接状压然后 DFS,复杂度好像是 $\mathcal O(Tn^22^n)$,反正能拿到 75pts 左右。

之后做一些剪枝+精细化实现可以搞成 $\mathcal O(Tn2^n)$,卡进时限(?)Code

总结

五年前的毒瘤题在今天看来只是中等难度了吧。

保底得分应该达到 $\texttt{100+40+100+100+85+75=500}$ 吧。

可能可以尝试在场上想出 D1T2 或 D2T2。

NOIP 2017

Day 1

结论题,答案是 $a\times b-a-b$,可以找规律,这里证一下。

由于输入数据的保证可得 $a,b\geq 2$。由 $a,b$ 互质知 $\exists x,y\in \mathbb Z,ax+by=1$。

易证 $x,y$ 有通解:$$ > x=kb+x_0,\ y=ka-y_0,\ k\in \mathbb Z > $$ 因此我们可以取 $x,y$ 使得 $x\in (0,b]$,此时由不等式可以推得 $y\in (-a,0]$。

那么我们对等式两边同时加上 $ab-a-b$ 可以得到:$$ > (x-1)a+(y+a-1)b=ab-a-b+1 > $$ 这时我们发现 $x-1\in[0,b), y+a-1\in[0,a)$。若有 $ax^\prime+by^\prime=ab-a-b$,则 $a(x-1-x^\prime)+b(y+a-1-y^\prime)=1$。

因此 $\exists k,kb+x_0=x-1-x^\prime$,把 $x$ 里的那个 $x_0$ 约掉,里面原来的 $kb$ 移过来。同理处理 $y$ 一式,可得$$ > \exists p,q\in \mathbb Z,pb=x^\prime+1,qa=y^\prime+1 > $$ 因此 $ax^\prime+by^\prime=a(pb-1)+b(qa-1)=(p+q)ab-a-b=ab-a-b$,比较可得一定有 $p+q=1$。

但是由 $x^\prime,y^\prime \geq 0$ 可以得出 $qa,pb>0,\ p,q>0$,因此由 $p,q\in \mathbb Z$ 可知 $p+q\geq 2$,推出矛盾。

综上所述,$ab-a-b$ 无法被表示。现在证 $\forall n\geq ab-a-b+1$,$n$ 都能被表示。

由于我们上面已经构造出了 $ab-a-b+1$ 的一种表示,考虑数学归纳。

现在若对 $n\geq ab-a-b+1$,有 $x_0,y_0\in\mathbb Z,ax_0+by_0=n$。那么由反证法可得 $x_0\geq b-1$ 和 $y_0\geq a-1$ 中必有一个成立。由上面的推论$$ > \exists x_n\in (0,b],y_n\in (-a,0],ax_n+by_n=1 > $$ 我们在 $ax$ 中减去 $ab$,$by$ 中加上 $ab$ 可得:$$ > \exists x_m\in (-b,0],y_m\in (0,a],ax_m+by_m=1 > $$ 现在若 $x_0\geq b-1$,我们可以构造 $x_1=x_0+x_m,y_1=y_0+y_m$;否则一定有 $y_0\geq a-1$,我们可以构造 $x_1=x_0+x_n,y_1=y_0+y_n$。

这样无论如何都有 $x_1,y_1\geq 0,ax_1+by_1=n+1$。这样便证明了上面的结论。

貌似这个证明还是挺优美的(

事实上这题可以也可以用同余最短路来给出一个直观解释,此处略去。

最后,D1T1 出这种题真的阴间。Code

大模拟,和儒略日一样恶心!!1

可以用栈来维护这个递归过程,个人感觉比儒略日好写 $998244353$ 倍,而且大样例强度不小,不容易挂分。

Code

毒瘤题,看了题解。做时想到应该是 $\mathcal O(Tmk)$ 的 DP,但是不知道怎么写(

如果不考虑 $0$ 环,首先容易想到的一个思路是按层在 Dijkstra 上 DP,但这样是 $\mathcal O(Tk(m+n)\log n)$ 的,显然过不去。Code

然后我们发现每次 $dis(x)$ 的值是不变的,因此可以提前排好序然后转移,这样就变成了 $\mathcal O(T[(m+n)\log n+km])$ 的。

问题来了,怎么判哪些点在 $0$ 环上捏?我们考虑对每条 $0$ 边,判断它是否可能在答案路径上,这可以用两次最短路判断。

Code

Day 2

小清新送分题。注意到 $n$ 是 $10^3$,那么就 $\mathcal O(n^2)$ 连边然后 并查集/BFS 随便做。

以前的代码:Code

是一道状压 DP 经典题。显然我们考虑到若尝试暴力记录每个点的深度作为状态,总的状态数就会到达 $\mathcal O(n^n)$,直接爆炸。

我们尝试通过一些操作把深度这一维给压掉。记 $dp_{i,j}$ 为当前 DP 到第 $i$ 层,状态为 $j$ 的最小花费,可得:(以下把状态写作一个集合)$$ dp_{i,j}=\min_{k\subseteq j}\{dp_{i-1,k}+i*w(k,j)\} $$ 其中 $w(k,j)$ 表示把状态 $k$ 扩张到状态 $j$ 需要的最少花费。

可以发现,那些没有意义的转移(如从第二层直接转移到第四层)都会使答案变大,因此总有另一种更优的合法解。

这样直接写就无需枚举每个起点,复杂度是 $\mathcal O(n^24^n)$ 的,有点小卡。

考虑进行一些计算 $w$ 时的优化,如 lowbit 计算等。

  1. 若把这个转移改造成向后转移,就变成 $\mathcal O(n4^n)$ 了,在洛谷上开个 O2 可过。
  2. 若依旧向前计算,就是 $\mathcal O(n^2 3^n)$ 的,貌似也能过。

Code

看到是一个神仙 DS 题,不过前 80pts 暴力挺白给的。参考了题解。

我们发现如果直接考虑维护每一行的所有数是不可行的,这样的空间复杂度会达到 $\mathcal O(nm)$,显然爆炸。

这里我们用一个 $q$ 不大的性质,对这 $q$ 个操作过的数单独拉出来维护,别的数先预处理再搞。

由于赛时卡常所以我们得用树状数组维护。

巨难调!!!Code

总结

很恶心的一年。D1T1, D2T2 的负区分度直接使期望得分难以预计。

不过如果把暴力打满,应该能比较轻松地搞到 $\texttt{60+100+30+100+70+80=440}$;

稍微加点灵感可以搞到 $\texttt{100+100+70+100+(70+)+80}$ 吧,不过两天的 T3 都十分神仙。

NOIP 2018

Day 1

经典结论题,贪心即可。虽然是原题,但比儒略日不知道高到哪里去了!!1。Code

背包搞一搞。Code

二分答案,然后用 set 配合一个贪心过程。

但是千万注意不能这么贪心:

while(s.size()) {
    auto it=(--s.end());
    auto it2=s.lower_bound(cur-(*it));
    if(it2==s.end()||it2==it) break;
    ans++, s.erase(it), s.erase(it2);
}

hack:

cur = 5
s = {2,3,4}

因此贪心地从大到小匹配能够找出最大的匹配对数但不能找到剩下的最大值

应该改成:

while(s.size()) {
    auto it=s.begin(), it2=s.lower_bound(cur-(*it));
    if(it2==it) it2++;
    if(it2==s.end()) f[x]=max(f[x],(*it)), s.erase(it);
    else ans++, s.erase(it), s.erase(it2);
}

即从小到大匹配。[Code]()

Day 2

懒得写了,之前的代码:Code

不会。看了题解,貌似是打表找规律

不过 50pts 还是挺好拿的,只要打满 $3\times 3$ 的暴搜和 $n=2$ 的部分就可以了。

貌似也可以状压 DP,不过也要有一个找规律的过程。

一眼动态 DP 板子,然后我们考虑不用 DDP,用一个倍增去搞掉这一个过程。

我们注意到题目给了两个点值,因此我们考虑是不是从链上下手。

于是大力分讨,各种倍增 DP 就搞完了。

代码极其难写,参考了题解。Code

总结

一场莫名其妙的联赛。Day 1 三个大原题,Day 2 暴力 - 找规律 - 科技,难度严格递增,这组题人怕不是个 nt......

这就是为什么 NOIP2018 六个题有四个在 UOJ 上评分为负数......

分数大概得有 $\texttt{100+100+100+100+50+44}$ 吧。

CSP 2019

Day 1

直接模拟即可,比儒略日不知道高到哪里去了!!1。Code

算一个比较经典的括号问题。

我们记 $dp_i$ 为根到 $i$ 号结点的串中有几个合法串以 $i$ 结尾,于是我们维护一个栈处理括号信息。

如果一个搜到一个点上刚好匹配上了 $x$ 位置的左括号,那么有:$$ dp_{i} = dp_{fa_x} + 1 $$ 若没有则为 $0$。

那么 $ans_i=ans_{fa_i} + dp_i$。Code

这题是一道经典的不可做题。有一个 10pts 的十分 naive 的指数级暴力。

然后我们观察小样例,发现有一个小随机图、一条链、一朵菊花和一束蒲公英,然后。

我们尝试考虑一下正解。

由于字典序最小,因此我们发现最优策略一定是从小到大枚举数字,然后把它换到一个尽量小的位置。

我们发现极限数据是 $2\times 10^3$,因此猜想正解是 $\mathcal O(n^2)$ 的。

首先能发现一个显然的性质:删完一条边之后,树就被划分成了两个不沟通的连通块,别的数就无法转移了。

因此,如果一个数最后留在了某个位置,那么:

  • 这一定不是它原来所在的位置。
  • 这个数走的一定是一条简单路径。
  • 这个位置最后一步删边就换到了这个数。换言之,这个数来之前别的边都被删完了。

我们考虑扩展这些性质:

  • 我们把一条数走的路径上的点分为起始点、途径点和到达点。那么就有如下性质:
  • 起始点和到达点不可能相同,且路径是简单的。
  • 对每个起始点而言,路径中的这条边一定是最先选的,称为首边。
  • 对每个途径点而言,路径中的这两条边一定是相继选的。否则这个数走的就不是这条路径了。
  • 对每个到达点而言,路径中的这条边一定是最后选的,称为尾边。

然后我就卡住了,期间想过并查集,但是完全是朝另一个方向想的。看了题解。

怎么维护这个贪心?基于 $\mathcal O(n^2)$ 的复杂度,我们可以每次枚举起点一遍 DFS 找出最大的可行终点。

但是怎么样是可行的呢?我们发现,如果只看当前情况,可能会导致之后的某个时刻不存在合法方案。

因此我们得保证之后都是合法的。我们考虑对每个点用一个并查集、链表维护连接这个点的所有边的选择顺序,那么需要保证:

  • 起始点后的边加入时:

    • 这条边不能有前驱;
    • 起始点不能有别的首边。
  • 途径点两边的边加入时:

    • 前面的边不能有后继,后面的边不能有前驱;
    • 前面的边不能是尾边,后面的边不能是首边;
    • 前后的边不能在同一个集合中,否则一定会形成一个环。
  • 到达点前的边加入时:

    • 这条边不能有后继;
    • 到达点不能有别的尾边。
  • 对于所有边:

    • 加入时都不能被用过。
    • 如果并入这两条边会导致首尾边串到了一起,那么不能还有别的没并进来的边。(这是为了保证之后合法,容易漏掉)

这样能通过洛谷、LOJ 的数据了,但是在 UOJ 上会被 hack。主要是要特判 $n=1$ 的毒瘤情况,此时数不移动。

Code

Day 2

看完题感觉不太有思路,所以看到部分分。

有一个显然的 $\mathcal O\left(n\left(\dfrac{n}{2}\right)^m\right)$ 的 64 分 DP,但这么点分显然不够。

然后我们考虑数据范围没那么大,因此正解估计也是 DP。

由于题目中有不能出现一半以上这个条件,所以我们考虑容斥。这样只需要枚举哪一道菜超过了一半以上,那么别的一定不会超过了。

因此这样是不会算漏的。而且我们看到样例解释二中是一个枚举做菜数的方式,因此猜想可能就是这样搞。

这样我们可以列出一个四维的 DP 方程,复杂度 $\mathcal O(n^3m)$,拿到 84 分。

然后我们考虑记录不合法食材数量和总菜数的那两维有点浪费,考虑合并成一维。

具体地,设我们考虑到前 $i$ 道烹饪方法,第 $j$ 种食材不合法,且第 $j$ 种食材的菜数 - 别的食材的总菜数的值为 $k$ 的方案数为 $dp_{i,j,k}$。

令 $S_i =\sum_{j=1}^m a_{i,j}$,那么有:$$ dp_{i,j,k}=dp_{i-1,j,k}+a_{i,j}\times dp_{i-1,j,k-1}+(S_i-a_{i,j})\times dp_{i-1,j,k+1} $$ 答案就是$$ \prod_{i=1}^n (S_i+1) - 1 - \sum_{j=1}^m \sum_{k=1}^n dp_{n,j,k} $$ 然后我们把 $i$ 这维滚动掉,时间复杂度 $\mathcal O(n^2m)$,空间复杂度 $\mathcal O(nm)$。

Code

早就听说这题要打高精,因此我们准备好了刚开放的 __int128

然后发现这题卡空卡时卡范围......读入方式还巨恶心......

这种东西显然要 DP。我们猜个结论,就是说每一段都要尽可能地小。

也就是说,计算 $dp_i$ 时我们存一个 $cur_i$,表示最后一段的大小。我们可以向前找到最近的一个 $j$ 使 $cur_j\le\sum_{j+1}^i$,然后转移。

这是 $\mathcal O(n^2)$ 的,有 64 分,考虑怎么优化。

我们输出一下转移,发现这个 $j$ 是单调递增的!这其实也十分直观。

那么我们维护一个单调队列记录转移,这题就做完了。

不是,其实这样场上只有 $88$ 分( Code

我们发现这是 D2T3,因此拿点部分分。

  1. 40 pts:$\mathcal O(n^2)$ 暴力,非常好打。

  2. 15 pts:链,那么重心就是中点,略难打一点点。

  3. 20 pts:完美二叉树。手模小数据可以发现:

    • 树是完全对称的,所以每层点的答案一样,可以考虑算贡献。

    • 设树的最大深度为 $d$,那么删一条深度为 $x$ 的边会对本子树内深度为 $x$ 有贡献。

      另一个树中的重心只有整棵树的根和根的另一个儿子,那么我们暴力特判是不是就可以了。

我们考虑怎么多拿那 25pts。

设以一个点 $x$ 为根,最大的子结点是 $y$,子树大小为 $f_x$;次大子结点是 $z$,大小是 $g_x$。

我们发现,$x$ 能作为重心,当且仅当:

  • 一个非 $y$ 的子结点中的一棵大小为 $h$ 的子树被删去,则必须 $n-h\ge 2f_x$。

    也就是 $n-2f_x\ge h$。

  • $y$ 的子树中的一棵大小为 $h$ 的子树被删去,则必须:

    • $n-h\ge 2(f_x - h)\Rightarrow n+h\ge 2f_x$;
    • $n-h\ge 2g_x$。

    也就是 $n-2g_x\ge h \ge 2f_x - n$。

然后考虑维护这个 $h$ 的个数我就不会了,看了题解 QAQ

原来我是 sb,直接换根然后用树状树组维护一下就可以了。

代码还是没那么好写...... Code

总结

这套题大众分好像有 $\texttt{100+100+10+64+64+75=413pts}$ ?

实际上可以尝试把 D2T1 打满,D2T2 打到 88 分((

不过这个 Day2 真的送了一大堆分,暴力能打到 203pts,打正解反而不如拍暴力期望高。

CSP 2019 - 江西

直接贪心,一道标准的送分题。Code

这里用了一个算贡献的做法:对每个对 $(a_i,b_j)(i\le j)$,我们发现它在 $i\times(n-j+1)$ 个对中算到,总贡献是 $(i\times a_i)\times((n-j+1)\times a_j)$。

那么我们预处理出所有 $i\times b_i$ 和 $(n-i+1)\times b_i$ 的值然后做前缀和、后缀和,这题就做完了。

Code

贪心。我们考虑用小根堆来维护一个贪心的过程,然后一个数一个数地加入答案。

如果选的全是列那么相互之间没有影响,然后考虑一下行与列之间的相互影响。具体看代码。

Code(欸我不用 STL 用平板电视就是皮)

听说是全场最难题,貌似确实(主要是码量不小。

我们考虑先预处理出如果没有 $l$ 的限制,每个人会从哪个出口离开。然后对出口维护一个 set记录最小时间,然后用链表各种处理。

记录一下把我卡了的数据(指写挂了)

2 1 8

1
0 0
0 7

Code

显然这个找到每个结点目前属于哪个堆可以用并查集实现,然后考虑怎么计算合并两个堆 $A,B$ 的答案(下面都是 $B$ 合并到 $A$)。

我们发现,由于合并后的总大小为 $|A|+|B|$,那么去掉一个堆顶后,各子树内的答案都是独立的。

那么实际上合并出来的新堆的答案就是$$ ans_{A+B}=ans_A\times ans_B\times\binom{|A|+|B|-1}{|B|} $$

Code

总结

这场毕竟是给江西出的,所以难度相对平缓,也没有难题压轴。

要是场上调的出 T4 的话期望能 AK (?

CSP 2020

直接模拟,十分恶心。

其实这种小学奥数大模拟难写难调,场上碰到这题差点心态炸掉,最后打了 2h 还是 80pts。Code

考察位运算,属于小清新送分题。

注意特判 $2^{64}$。Code

其实这题场上直接暴力递归有 $75$ 分(

题面非常恶臭,不过考虑到这个东西构成一个 DAG,显然考虑拓扑排序。

然后我发现如果每次都把底层操作展开复杂度显然爆炸,于是考虑对于每个加法操作算出它的贡献。

那么我们建出反图,然后在反图上 DP 每个点的贡献,也即(考虑乘法操作)后这个操作会被执行几次。

注意处理时需要倒着处理乘法。Code

很 nb 的题,我们先考虑 70pts 做法。可以发现:

  1. 如果一条蛇吃掉实力最弱的蛇后还是实力最强的蛇,那么它一定会选择吃;
  2. 否则这条蛇就有被吃掉的风险,但是它不一定不吃

比如样例二中的第二个数据。

那么我们对着样例大力猜结论:如果一条蛇吃掉最小的蛇后不会变成最弱的,那么它就一定会吃。

为什么?我们设吃完后最弱的能力值为 $x$,这条蛇原来是 $a$,吃了一条 $y$ 的蛇变成了 $a-y$,当前最大的是 $b$。

那么由于 $y\le x,b\le a$ 必定有 $b-x\le a-y$,也就是说如果 $b$ 选择吃 $x$,那么就会比 $a-y$ 还弱。

简单归纳可知,之后任意时刻 $a-y$ 都不会是最弱蛇,没有被吃掉的可能。

这样如果我们假设一条蛇吃掉最小的蛇后会变成最弱的,那么它就一定不吃,就可以写出这样一份代码

但是你一测,发现过不去大样例(有些离答案恰好相差 $1$),而且你还不会调。

hack:

1
4
2 2 2 3

如果 $4$ 号蛇选择吃,那么局面会变成 1 2 2。这时候如果 $3$ 号蛇选择吃 $4$ 号蛇,那么它下一句就会被 $2$ 号蛇吃掉,因此 $3$ 号蛇不会去吃。

这样来说,即使这条蛇吃完后变成了最弱的,如果它可以判断出下一条蛇不吃自己,那么就还是会吃

那么怎么判断下一条蛇会不会吃自己捏?这其实就变成了一个子问题:若下一条蛇吃自己后不是最弱的或再下一条蛇不选择吃它,那么它会吃。

这么说,这条蛇吃当且仅当吃后再下一条蛇选择吃下一条蛇。我们可以写出一个非常高明的代码:Code

我超,这就过了???不过实际上你去 UOJ 上交一发它会 T 飞,原因是这个做法是 $\mathcal O(Tn\log n)$ 的,正解要求是 $\mathcal O(Tn)$,我们考虑怎么把这个 set 去掉。

通过刚才的分析,我们发现重新插入的数是单调递减的,那么我们考虑沿用上面P2827 [NOIP2016 提高组] 蚯蚓的做法,将 set 换成两个队列即可。

但你如果直接那么写,是会 WA 50pts 的。原因在于如果当前重新插入的数是最小的,那么如果之后的数出现不是最小值的情况就不一定单调

这里的话有一车奇妙的做法,比如每次把插入的数和之前的最小数做比较,如果当前插入的数更大就 swap

实际上,由于我们只关心是否出现之后的数出现不是最小值的情况,因此不用担心最后的 $q$ 中是否单调,这样是正确的。

Code

总结

T1 毒瘤!!!

不过(不考虑挂分)应该要到 $100+95+75+20=290$,尽管我菜考不到(。

可能发挥好点能到 $100+95+100+70=365$?

NOIP 2020

拓扑排序板子题,很恶心的一点是答案会爆 long long,要打高精。

打个锤子,我直接一个 __int128_t 无敌了。Code

这里分析一下答案分母的上界:

你以为分母上界是 $5^{11}$?NAIVE。

考虑这样 $m=3$,它们到终点的路径上的 $d$ 都分别是 $3,4,5$。

这样能卡到上界 $2^{22}\times 3^{11}\times 5^{11}\approx3.6\times 10^{19}$,会爆 unsigned long long

正解是两个 long long 当高精。场上如果开 long long,求 gcd 时先乘后除 60pts,先除后乘 60pts

我场上的做法:

我们注意到 $AB$ 一定是 $S$ 的一个周期,于是我们跑一遍 KMP 求出所有 $\pi(i)$。

然后我们跑出每个前缀的最小整周期(若 $i-\pi(i)\mid i$ 则为 $i-\pi(i)$,否则就是 $i$)。

然后对于每个 $i$ 预处理前缀、后缀 $F$,然后枚举 $AB$ 的长度,调和级数地向上跳算贡献。

用一个树状树组优化,复杂度 $\mathcal O(nH(n)\log |\Sigma|)$​,可以卡过

然后我们发现这东西太垃圾了,考虑优化到 $\mathcal O(n\log |\Sigma|)$。(这部分看了题解)

考察 $AB$ 的性质,我们发现:对于一个给定的 $AB$,后面的 $F(C)$ 只有两种不同的取值。(这东西是最难想的一步)

所以我们先求出每个前缀最多能向后拓展几遍,然后奇偶性讨论。

鬼知道这思路怎么想到的 Code

当然还有严格 $\mathcal O(n)$ 的 Z 函数做法,不过我不会。

构造题

  1. 先考虑一个 40pts 做法,操作复杂度是 $\mathcal O(nm^2)$ 的。

我们遍历 $1\cdots n$ 中的每种颜色,然后将所有的这种颜色的球都移到对应的柱子上。

怎么移动呢?我们可以发现,这实际上是一个把原有的不合法球换出来的过程。

也就是说,我们要考虑构造一种能交换两个球的操作,这自然是非常容易的:先把两个球 $\mathcal O(m)$ 地换到顶部,然后交换。

至于怎么实现交换到顶部这个操作,参考小样例,我们发现我们可以找一个别的柱子把它的顶部移到 $n+1$,然后把要移球上面全部扔到 $n+1$ 中。

然后移过来这边的搞搞搞。Code 但是这只有 40pts。

  1. 赛后我们听说 $\mathcal O(n^2m)$ 卡常是能过的(实际上预估是 70pts),于是考虑这个东西怎么做。

观察复杂度,我们发现这个东西可以被理解为每根柱子至多被翻开 $n$ 轮

那么我们猜想做法是不是就是每次修理一个柱子时,对别的同一个柱子上的球统一处理。

我们考虑一个操作:把一根柱子上的某种颜色的球移到最上面。

这个东西的一种实现:

设当前柱子中这种颜色的球有 $c$ 个,随便找一个别的柱子扣掉 $c$ 个扔到 $n+1$。

然后翻出当前柱子里的所有球,匹配的扔到那个别的柱子,否则扔到 $n+1$。

然后从 $n+1$ 中拿 $m-c$ 个扔回去,把那 $c$ 个匹配的放回去,最后还原那个别的柱子。

综上,我们对每个柱子之后的柱子都搞一遍这个操作。

之后我们把每根柱子最上面的球全部移到 $n+1$,然后把 $i$ 柱上的球补到 $i+1\sim n$ 中,最后把 $n+1$ 中的球移回 $i$。

我的实现直接交一发会 WA 80pts,其中最大的操作跑了大概 $9\times 10^5$ 次,考虑卡常。

看了眼题解,发现这个大致方向是对的,只是这个操作实现的不够好。

题解中有一种做法能够减少大致一半的操作,就是不把空柱还原为 $n+1$,继续用那根柱子。

但是之前有一个构造全 0 柱的操作,较为繁琐,还是正解好打。

  1. 看题解,发现 $\mathcal O(nm\log n)$ 的牛逼做法?这应该是正解。

我们看到唯一的特殊性质部分分是 $n=2$,于是分析一下 $n=2$ 怎么做。

然后我们手玩那个大样例,就得出了一个做法,这篇题解里写的很详细。

然后考虑分治。我们每次定一个阈值 $mid$,然后将 $\le mid$ 的移到左半区间,剩下的移到右半区间。

接下来讨论怎么处理这个分开的过程。类似于归并排序,我们搞两个指针,每次操作这两个指针的位置。

int p = l, q = mid + 1;
while(p <= mid && q <= r) {
    move(p, q, mid);
    if(cnt(p, mid) == 0) p++;
    if(cnt(q, mid) == m) q++;
}

可以发现,每次操作至少导致一个指针被移动,因此 move 至多执行 $len$ 次,而且完全跑不满。

move 的复杂度不大于 $5m$。分治下去的复杂度是 $T(n)=2T(\dfrac{n}{2})+5nm$ 的,复杂度 $\mathcal O(5nm\log n)$。

最大的点跑了大概 $4.2\times 10^5$ 次。Code

总结

个人认为这是目前难度最高的一次 NOIP。

除去 T1 恶心人的高精,题目质量非常不错。

结合数据强度,可能应该得到 $90 + 100 + 40 + 30= 260$?但是这成绩貌似还是很丢人/kk

CSP 2021

NOIP 2021

场上没搞出来qwq

注意到这个 $a_i\gets a_{i-1}+a_{i+1}-a_{i}$ 十分奇妙,我们考虑观察它的本质。

于是手模样例可以发现 $a$ 中的差分数列是不变的,也即:这个变化过程本质上是对 $a$ 差分数列的重排。这可以很轻松地证明。

然后我们就能打出 $\mathcal O(n\cdot n!)$ 的暴力。

打开样例二,输出一下答案序列,发现答案中最后的差分数列呈单谷排列,即 V 字型形状。这可以感性理解。

然后我们推一下方差乘上 $n$ 的平方是什么东西:$$ n^2D=n^2\dfrac{1}{n}\sum_{i=1}^n (a_i-\overline{a})^2 = n\sum_{i=1}^n (a_i^2-2a_i\overline{a}+\overline{a}^2) = n^2 \left( \dfrac{\sum_{i=1}^n a_i}{n}\right)^2-2n\dfrac{\sum_{i=1}^n a_i}{n}\times\left(\sum_{i=1}^n a_i\right) + n\sum_{i=1}^n a_i^2 $$ 继续化化可得答案为:$$ n\sum_{i=1}^n a_i^2 - \left(\sum_{i=1}^n a_i\right)^2 $$ 所以答案只和 $a_i$ 之和以及平方和有关。我们注意到值域很小,因此考虑一个 DP。

我们把差分从小到大排序,每次就是向开头或者结尾加入一个数。记 $dp_{i,j}$ 为考虑了前 $i$ 个差分,和为 $j$ 的答案。

(以下的 $a$ 均指排序后的差分序列)

这里和第二题一样,采取向后计算贡献的方法。我们有:$$ dp_{i, j+\sum_{j=1}^i a_j}\gets \min\left\{dp_{i, j+\sum_{j=1}^i a_j}, dp_{i-1,j}+\left(\sum_{j=1}^i a_j\right)^2\right\} $$

$$ dp_{i, j+a_i\times i} \gets \min\left\{dp_{i, j+a_i\times i}, dp_{i-1,j}+i\times a_i^2+2\times a_i\times j\right\} $$

其中第一个式子中的 $\sum$ 可以前缀和预处理,这样复杂度就是 $\mathcal O(n^2a_n)$ 的,可以拿到 88 pts。

我们考虑满分做法。观察数据范围 $a_i$ 只有 $50$,这启发我们想到差分数组中不为 $0$ 的数的个数至多有 $a_n$ 个

因此我们只需要直接忽略掉差分数组中的那些 $0$ 就可以优化到 $\mathcal O(n {a_n}^2)$ 了。Code