历年 NOIP/CSP 简要题解

[配套题单](https://www.luogu.com.cn/training/113616) 以下考虑的期望得分**均不考虑挂分**。 ## NOIP 2015 ### Day 1 - **A.** [P2615 [NOIP2015 提高组] 神奇的幻方](https://www.luogu.com.cn/problem/P2615) 签到题，按照题面直接模拟即可，比儒略日不知道高到哪里去了！！1[Code](https://www.luogu.com.cn/record/59740154) - **B.** [P2661 [NOIP2015 提高组] 信息传递](https://www.luogu.com.cn/problem/P2661) 简单题，直接一个 DFS 求出最小环所含有的结点数。[Code](https://www.luogu.com.cn/record/59743926) - **C.** [P2668 [NOIP2015 提高组] 斗地主](https://www.luogu.com.cn/problem/P2668) / [P2540 [NOIP2015 提高组] 斗地主 加强版](https://www.luogu.com.cn/problem/P2540) 防 AK 题，做的时候不太会。正解应该是 DP，个人觉得大多数贪心实际都能被卡掉，而且也懒得写一些莫名其妙的特判。 DP 的方法是记录出现四次、三次、两次、一次的牌各有几种，然后转移转移转移。 但我们发现这种做法没法处理顺子，那么我们对每个询问暴搜打顺子处理。 可以去[UOJ](https://uoj.ac/problem/151)上交这题更强的数据。[Code](https://uoj.ac/submission/512012) ### Day 2 - **A.** [P2678 [NOIP2015 提高组] 跳石头](https://www.luogu.com.cn/problem/P2678) 二分答案后转为判定，十分简单。[Code](https://www.luogu.com.cn/record/59767608) - **B**. [P2679 [NOIP2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679) 中规中矩的 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](https://www.luogu.com.cn/record/59784197) - **C.** [P2680 [NOIP2015 提高组] 运输计划](https://www.luogu.com.cn/problem/P2680) 比较难的一个图论题。注意到问题中带有**最大值最小**的约束，考虑二分答案。 二分完了我们发现所有计划中当前长度小于等于二分值 $x$ 的**都不需要考虑**，而大于 $x$ 的计划对应的路径中至少要有一条边覆盖到。 因此我们对这些路径**整条路径的值加一**，然后简单讨论，这可以用树上差分维护。 之前写过的代码：[Code](https://www.luogu.com.cn/record/39864564) ### 总结 无论如何保底得分都应当有 $\texttt{100+100+?+100+100+50>450}$。（我们假使 D2T3 直接不会，打了个 $\mathcal O(n^2)$ 的暴力） 实际上除了 D1T3 以外所有的题都应当 AC，~~个人认为讨论 D1T3 的得分不太有意义~~。 ## NOIP 2016 ~~这整套题之前练过~~ ### Day 1 - **A.** [P1563 [NOIP2016 提高组] 玩具谜题](https://www.luogu.com.cn/problem/P1563) 签到题，按照题面直接模拟加点小优化即可，比儒略日不知道高到哪里去了！！1 之前的代码：[Code](https://www.luogu.com.cn/record/50582370) - **B.** [P1600 [NOIP2016 提高组] 天天爱跑步](https://www.luogu.com.cn/problem/P1600) 毒瘤题。我们考虑将出现的时间看作一种物品，这样问题就转化成了路径添加物品、最后总体查询。 这已经可以套用雨天的尾巴里的做法，借助树上差分 + 线段树合并实现 $\mathcal O(n\log^2 n)$。 实际上这题不需要线段树合并，直接维护一个全局数组即可 $\mathcal O(n\log n)$。感觉这题和 T3 放反了？ 重新写了一遍：[Code](https://www.luogu.com.cn/record/59829036) 部分分的话有 20pts 的 $\mathcal O(n^2)$，链的 15pts 算是启发正解，后面两个特殊性质不知道是干嘛的。 - **C.** [P1850 [NOIP2016 提高组] 换教室](https://www.luogu.com.cn/problem/P1850) 这题看着比较艰难，再加上 T2 的加持会显得十分不可做。 实际上个人感觉这题出得很没水平，这个 Floyd 跑最短路的乱入是毫无意义的，而且这题主要难在前置知识而不是思维，T2 比它高得很。 具体做法就是 DP，列出状态转移然后硬搞，就没了。之前的代码：[Code](https://www.luogu.com.cn/record/50595608) ### Day 2 - **A.** [P2822 [NOIP2016 提高组] 组合数问题](https://www.luogu.com.cn/problem/P2822) 画风友好的简单题。由于 $k$ 在开始的时候已经给了，因此可以预处理出所有的值然后搞一个前缀和。 之前的代码：[Code](https://www.luogu.com.cn/record/50600181) - **B.** [P2827 [NOIP2016 提高组] 蚯蚓](https://www.luogu.com.cn/problem/P2827) 经典题。首先很容易可以想到用一个堆通过**记录全局生长差值**去维护里面所有的蚯蚓，这是 $\mathcal O((m+n)\log n)$ 的，能拿到 85pts。 然后注意到排序后新插入的蚯蚓满足单调性，可以用队列换掉这一过程，这是 $\mathcal O(n\log n+m)$ 的满分做法。[Code](https://www.luogu.com.cn/record/50600647) - **C.** [P2831 [NOIP2016 提高组] 愤怒的小鸟](https://www.luogu.com.cn/problem/P2831) 大概算防 AK 题？直接状压然后 DFS，复杂度好像是 $\mathcal O(Tn^22^n)$，反正能拿到 75pts 左右。 之后做一些剪枝+精细化实现可以搞成 $\mathcal O(Tn2^n)$，卡进时限（？）[Code](https://www.luogu.com.cn/record/50607417) ### 总结 五年前的毒瘤题在今天看来只是中等难度了吧。 保底得分应该达到 $\texttt{100+40+100+100+85+75=500}$ 吧。 可能可以尝试在场上想出 D1T2 或 D2T2。 ## NOIP 2017 ### Day 1 - **A.** [P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目](https://www.luogu.com.cn/problem/P3951) 结论题，答案是 $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](https://www.luogu.com.cn/record/59902151) - **B.** [P3952 [NOIP2017 提高组] 时间复杂度](https://www.luogu.com.cn/problem/P3952) 大模拟，和儒略日一样恶心！！1 可以用栈来维护这个递归过程，个人感觉比儒略日好写 $998244353$ 倍，而且大样例强度不小，不容易挂分。 [Code](https://www.luogu.com.cn/record/59907164) - **C.** [P3953 [NOIP2017 提高组] 逛公园](https://www.luogu.com.cn/problem/P3953) 毒瘤题，看了题解。做时想到应该是 $\mathcal O(Tmk)$ 的 DP，但是不知道怎么写（ 如果不考虑 $0$ 环，首先容易想到的一个思路是**按层在 Dijkstra 上 DP**，但这样是 $\mathcal O(Tk(m+n)\log n)$ 的，显然过不去。[Code](https://www.luogu.com.cn/record/60243376) 然后我们发现每次 $dis(x)$ 的值是不变的，因此可以提前排好序然后转移，这样就变成了 $\mathcal O(T[(m+n)\log n+km])$ 的。 问题来了，怎么判哪些点在 $0$ 环上捏？我们考虑对每条 $0$ 边，判断它是否可能在答案路径上，这可以用两次最短路判断。 [Code](https://uoj.ac/submission/512718) ### Day 2 - **A.** [P3958 [NOIP2017 提高组] 奶酪](https://www.luogu.com.cn/problem/P3958) 小清新送分题。注意到 $n$ 是 $10^3$，那么就 $\mathcal O(n^2)$ 连边然后 并查集/BFS 随便做。 以前的代码：[Code](https://www.luogu.com.cn/record/43110250) - **B.** [P3959 [NOIP2017 提高组] 宝藏](https://www.luogu.com.cn/problem/P3959) 是一道状压 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](https://www.luogu.com.cn/record/60318117) - **C.** [P3960 [NOIP2017 提高组] 列队](https://www.luogu.com.cn/problem/P3960) 看到是一个神仙 DS 题，不过前 80pts 暴力挺白给的。参考了题解。 我们发现如果直接考虑维护每一行的所有数是不可行的，这样的空间复杂度会达到 $\mathcal O(nm)$，显然爆炸。 这里我们用一个 $q$ 不大的性质，对这 $q$ 个操作过的数单独拉出来维护，别的数先预处理再搞。 由于赛时卡常所以我们得用树状数组维护。 巨难调！！！[Code](https://www.luogu.com.cn/record/60373816) ### 总结 很恶心的一年。D1T1, D2T2 的负区分度直接使期望得分难以预计。 不过如果把暴力打满，应该能比较轻松地搞到 $\texttt{60+100+30+100+70+80=440}$； 稍微加点灵感可以搞到 $\texttt{100+100+70+100+(70+)+80}$ 吧，不过两天的 T3 都十分神仙。 ## NOIP 2018 ### Day 1 - **A.** [P5019 [NOIP2018 提高组] 铺设道路](https://www.luogu.com.cn/problem/P5019) 经典结论题，贪心即可。虽然是原题，但比儒略日不知道高到哪里去了！！1。[Code](https://www.luogu.com.cn/record/26556993) - **B.** [P5020 [NOIP2018 提高组] 货币系统](https://www.luogu.com.cn/problem/P5020) 背包搞一搞。[Code](https://www.luogu.com.cn/record/40373070) - **C.** [P5021 [NOIP2018 提高组] 赛道修建](https://www.luogu.com.cn/problem/P5021) 二分答案，然后用 `set` 配合一个贪心过程。 但是千万注意不能这么贪心： ```c++ 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} ``` 因此贪心地从大到小匹配**能够找出最大的匹配对数但不能找到剩下的最大值**。 应该改成： ```c++ 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 - **A.** [P5022 [NOIP2018 提高组] 旅行](https://www.luogu.com.cn/problem/P5022) / [P5049 [NOIP2018 提高组] 旅行 加强版](https://www.luogu.com.cn/problem/P5049) $\mathcal O(n^2)$ 直接断边暴力，$\mathcal O(n)$ 是个巨大多分讨...... 懒得写了，之前的代码：[Code](https://www.luogu.com.cn/record/53516139) - **B.** [P5023 [NOIP2018 提高组] 填数游戏](https://www.luogu.com.cn/problem/P5023) 不会。看了题解，貌似是打表找规律 不过 50pts 还是挺好拿的，只要打满 $3\times 3$ 的暴搜和 $n=2$ 的部分就可以了。 貌似也可以状压 DP，不过也要有一个找规律的过程。 - **C.** [P5024 [NOIP2018 提高组] 保卫王国](https://www.luogu.com.cn/problem/P5024) 一眼动态 DP 板子，然后我们考虑不用 DDP，用一个倍增去搞掉这一个过程。 我们注意到题目给了两个点值，因此我们考虑是不是从链上下手。 于是大力分讨，各种倍增 DP 就搞完了。 代码极其难写，参考了题解。[Code](https://www.luogu.com.cn/record/60486299) ### 总结 一场莫名其妙的联赛。Day 1 三个大原题，Day 2 暴力 - 找规律 - 科技，难度严格递增，这组题人怕不是个 nt...... 这就是为什么 NOIP2018 六个题有四个在 UOJ 上评分为负数...... 分数大概得有 $\texttt{100+100+100+100+50+44}$ 吧。 ## CSP 2019 ### Day 1 - **A.** [P5657 [CSP-S2019] 格雷码](https://www.luogu.com.cn/problem/P5657) 直接模拟即可，比儒略日不知道高到哪里去了！！1。[Code](luogu.com.cn/record/62199076) - **B.** [P5658 [CSP-S2019] 括号树](https://www.luogu.com.cn/problem/P5658) 算一个比较经典的括号问题。 我们记 $dp_i$ 为根到 $i$ 号结点的串中有几个合法串以 $i$ 结尾，于是我们维护一个栈处理括号信息。 如果一个搜到一个点上刚好匹配上了 $x$ 位置的左括号，那么有： $$ dp_{i} = dp_{fa_x} + 1 $$ 若没有则为 $0$。 那么 $ans_i=ans_{fa_i} + dp_i$。[Code](https://www.luogu.com.cn/record/62201887) - **C.** [P5659 [CSP-S2019] 树上的数](https://www.luogu.com.cn/problem/P5659) 这题是一道经典的不可做题。有一个 10pts 的十分 naive 的指数级暴力。 然后我们观察小样例，发现有一个小随机图、一条链、一朵菊花和一束蒲公英，然后。 我们尝试考虑一下正解。 由于字典序最小，因此我们发现最优策略一定是从小到大枚举数字，然后把它换到一个尽量小的位置。 我们发现极限数据是 $2\times 10^3$，因此猜想正解是 $\mathcal O(n^2)$ 的。 首先能发现一个显然的性质：删完一条边之后，树就被划分成了两个不沟通的连通块，别的数就无法转移了。 因此，如果一个数最后留在了某个位置，那么： - 这一定不是它原来所在的位置。 - 这个数走的一定是一条简单路径。 - 这个位置最后一步删边就换到了这个数。换言之，这个数来之前别的边都被删完了。 我们考虑扩展这些性质： - 我们把一条数走的路径上的点分为起始点、途径点和到达点。那么就有如下性质： - 起始点和到达点不可能相同，且路径是简单的。 - 对每个起始点而言，路径中的这条边一定是最先选的，称为首边。 - 对每个途径点而言，路径中的这两条边一定是相继选的。否则这个数走的就不是这条路径了。 - 对每个到达点而言，路径中的这条边一定是最后选的，称为尾边。 然后我就卡住了，期间想过并查集，但是完全是朝另一个方向想的。看了题解。 怎么维护这个贪心？基于 $\mathcal O(n^2)$ 的复杂度，我们可以每次枚举起点一遍 DFS 找出最大的可行终点。 但是怎么样是可行的呢？我们发现，如果只看当前情况，可能会导致之后的某个时刻不存在合法方案。 因此我们得保证之后都是合法的。我们考虑对每个点用一个并查集、链表维护**连接这个点的所有边的选择顺序**，那么需要保证： - 起始点后的边加入时： - 这条边不能有前驱； - 起始点不能有别的首边。 - 途径点两边的边加入时： - 前面的边不能有后继，后面的边不能有前驱； - 前面的边不能是尾边，后面的边不能是首边； - 前后的边不能在同一个集合中，否则一定会形成一个环。 - 到达点前的边加入时： - 这条边不能有后继； - 到达点不能有别的尾边。 - 对于所有边： - 加入时都不能被用过。 - **如果并入这两条边会导致首尾边串到了一起，那么不能还有别的没并进来的边**。（这是为了保证之后合法，容易漏掉） 这样能通过洛谷、LOJ 的数据了，但是在 UOJ 上会被 hack。主要是要特判 $n=1$ 的毒瘤情况，此时数不移动。 [Code](https://uoj.ac/submission/516760) ### Day 2 - **A.** [P5664 [CSP-S2019] Emiya 家今天的饭](https://www.luogu.com.cn/problem/P5664) 看完题感觉不太有思路，所以看到部分分。 有一个显然的 $\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](https://www.luogu.com.cn/record/62275815) - **B.** [P5665 [CSP-S2019] 划分](https://www.luogu.com.cn/problem/P5665) 早就听说这题要打高精，因此我们准备好了刚开放的 `__int128`。 然后发现这题卡空卡时卡范围......读入方式还巨恶心...... 这种东西显然要 DP。我们猜个结论，就是说每一段都要尽可能地小。 也就是说，计算 $dp_i$ 时我们存一个 $cur_i$，表示最后一段的大小。我们可以向前找到最近的一个 $j$ 使 $cur_j\le\sum_{j+1}^i$，然后转移。 这是 $\mathcal O(n^2)$ 的，有 64 分，考虑怎么优化。 我们输出一下转移，发现这个 $j$ 是单调递增的！这其实也十分直观。 那么我们维护一个单调队列记录转移，这题就做完了。 不是，其实这样场上只有 $88$ 分（ [Code](https://www.luogu.com.cn/record/54183306) - **C.** [P5666 [CSP-S2019] 树的重心](https://www.luogu.com.cn/problem/P5666) 我们发现这是 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](https://www.luogu.com.cn/record/62310365) ### 总结 这套题大众分好像有 $\texttt{100+100+10+64+64+75=413pts}$ ？ 实际上可以尝试把 D2T1 打满，D2T2 打到 88 分（（ 不过这个 Day2 真的送了一大堆分，暴力能打到 203pts，打正解反而不如拍暴力期望高。 ## CSP 2019 - 江西 - **A.** [P5690 [CSP-S2019 江西] 日期](https://www.luogu.com.cn/problem/P5690) 直接贪心，一道标准的送分题。[Code](https://www.luogu.com.cn/record/62659708) - **B.** [P5686 [CSP-S2019 江西] 和积和](https://www.luogu.com.cn/problem/P5686) 这里用了一个算贡献的做法：对每个对 $(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](https://www.luogu.com.cn/record/62662564) - **C.** [P5687 [CSP-S2019 江西] 网格图](https://www.luogu.com.cn/problem/P5687) 贪心。我们考虑用小根堆来维护一个贪心的过程，然后一个数一个数地加入答案。 如果选的全是列那么相互之间没有影响，然后考虑一下行与列之间的相互影响。具体看代码。 [Code](https://www.luogu.com.cn/record/62674816)（欸我不用 STL 用平板电视就是皮） - **D.** [P5688 [CSP-S2019 江西] 散步](https://www.luogu.com.cn/problem/P5688) 听说是全场最难题，貌似确实（主要是码量不小。 我们考虑先预处理出如果没有 $l$ 的限制，每个人会从哪个出口离开。然后对出口维护一个 `set`记录最小时间，然后用链表各种处理。 记录一下把我卡了的数据（指写挂了） ``` 2 1 8 1 0 0 0 7 ``` [Code](https://www.luogu.com.cn/record/62701266) - **E.** [P5689 [CSP-S2019 江西] 多叉堆](https://www.luogu.com.cn/problem/P5689) 显然这个找到每个结点目前属于哪个堆可以用并查集实现，然后考虑怎么计算合并两个堆 $A,B$ 的答案（下面都是 $B$ 合并到 $A$）。 我们发现，由于合并后的总大小为 $|A|+|B|$，那么去掉一个堆顶后，各子树内的答案都是独立的。 那么实际上合并出来的新堆的答案就是 $$ ans_{A+B}=ans_A\times ans_B\times\binom{|A|+|B|-1}{|B|} $$ [Code](https://www.luogu.com.cn/record/62727657) ### 总结 这场毕竟是给江西出的，所以难度相对平缓，也没有难题压轴。 要是场上调的出 T4 的话期望能 AK （？ ## CSP 2020 - **A.** [P7075 [CSP-S2020] 儒略日](https://www.luogu.com.cn/problem/P7075) 直接模拟，十分恶心。 其实这种小学奥数大模拟难写难调，场上碰到这题差点心态炸掉，最后打了 2h 还是 80pts。[Code](https://www.luogu.com.cn/record/63024360) - **B.** [P7076 [CSP-S2020] 动物园](https://www.luogu.com.cn/problem/P7076) 考察位运算，属于小清新送分题。 注意特判 $2^{64}$。[Code](https://www.luogu.com.cn/record/41877912) - **C.** [P7077 [CSP-S2020] 函数调用](https://www.luogu.com.cn/problem/P7077) 其实这题场上直接暴力递归有 $75$ 分（ 题面非常恶臭，不过考虑到这个东西构成一个 DAG，显然考虑拓扑排序。 然后我发现如果每次都把底层操作展开复杂度显然爆炸，于是考虑对于每个加法操作算出它的贡献。 那么我们建出反图，然后在反图上 DP 每个点的贡献，也即（考虑乘法操作）后这个操作会被执行几次。 注意处理时需要倒着处理乘法。[Code](https://www.luogu.com.cn/record/63548433) - **D.** [P7078 [CSP-S2020] 贪吃蛇](https://www.luogu.com.cn/problem/P7078) 很 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$ 都不会是最弱蛇，没有被吃掉的可能。 这样如果我们假设一条蛇吃掉最小的蛇后会变成最弱的，那么它就一定不吃，就可以写出[这样一份代码](https://www.luogu.com.cn/record/63555643)。 但是你一测，发现过不去大样例（有些离答案恰好相差 $1$），而且你还不会调。 hack： ``` 1 4 2 2 2 3 ``` 如果 $4$ 号蛇选择吃，那么局面会变成 `1 2 2`。这时候如果 $3$ 号蛇选择吃 $4$ 号蛇，那么它下一句就会被 $2$ 号蛇吃掉，因此 $3$ 号蛇不会去吃。 这样来说，**即使这条蛇吃完后变成了最弱的，如果它可以判断出下一条蛇不吃自己，那么就还是会吃**。 那么怎么判断下一条蛇会不会吃自己捏？这其实就变成了一个子问题：若下一条蛇吃自己后不是最弱的或再下一条蛇不选择吃它，那么它会吃。 这么说，这条蛇吃当且仅当吃后**再下一条蛇选择吃下一条蛇**。我们可以写出一个非常高明的代码：[Code](https://www.luogu.com.cn/record/63558703) 我超，这就过了？？？不过实际上你去 UOJ 上交一发它会 T 飞，原因是这个做法是 $\mathcal O(Tn\log n)$ 的，正解要求是 $\mathcal O(Tn)$，我们考虑怎么把这个 `set` 去掉。 通过刚才的分析，我们发现**重新插入的数是单调递减的**，那么我们考虑沿用上面[P2827 [NOIP2016 提高组] 蚯蚓](https://www.luogu.com.cn/problem/P2827)的做法，将 `set` 换成两个队列即可。 但你如果直接那么写，是会 WA 50pts 的。原因在于**如果当前重新插入的数是最小的，那么如果之后的数出现不是最小值的情况就不一定单调**。 这里的话有一车奇妙的做法，比如每次把插入的数和之前的最小数做比较，如果当前插入的数更大就 `swap`。 实际上，由于我们只关心是否出现之后的数出现不是最小值的情况，因此不用担心最后的 $q$ 中是否单调，这样是正确的。 [Code](https://uoj.ac/submission/518471) ### 总结 T1 毒瘤！！！ 不过（不考虑挂分）应该要到 $100+95+75+20=290$，尽管我菜考不到（。 可能发挥好点能到 $100+95+100+70=365$？ ## NOIP 2020 - **A.** [P7113 [NOIP2020] 排水系统](https://www.luogu.com.cn/problem/P7113) 拓扑排序板子题，很恶心的一点是答案会爆 `long long`，要打高精。 打个锤子，我直接一个 `__int128_t` 无敌了。[Code](https://www.luogu.com.cn/record/63602395) > 这里分析一下答案分母的上界： > > 你以为分母上界是 $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 - **B.** [P7114 [NOIP2020] 字符串匹配](https://www.luogu.com.cn/problem/P7114) 我场上的做法： > 我们注意到 $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](https://www.luogu.com.cn/record/63900833) 当然还有严格 $\mathcal O(n)$ 的 Z 函数做法，不过我不会。 - [P7115 [NOIP2020] 移球游戏](https://www.luogu.com.cn/problem/P7115) 构造题 1. 先考虑一个 40pts 做法，操作复杂度是 $\mathcal O(nm^2)$ 的。 我们遍历 $1\cdots n$ 中的每种颜色，然后将所有的这种颜色的球都移到对应的柱子上。 怎么移动呢？我们可以发现，这实际上是一个把原有的不合法球换出来的过程。 也就是说，我们要考虑构造一种能交换两个球的操作，这自然是非常容易的：先把两个球 $\mathcal O(m)$ 地换到顶部，然后交换。 至于怎么实现交换到顶部这个操作，参考小样例，我们发现我们可以找一个别的柱子把它的顶部移到 $n+1$，然后把要移球上面全部扔到 $n+1$ 中。 然后移过来这边的搞搞搞。[Code](https://www.luogu.com.cn/record/63941965) 但是这只有 40pts。 2. 赛后我们听说 $\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](https://www.luogu.com.cn/record/64010815)，其中最大的操作跑了大概 $9\times 10^5$ 次，考虑卡常。 看了眼题解，发现这个大致方向是对的，只是这个操作实现的不够好。 题解中有一种做法能够减少大致一半的操作，就是不把空柱还原为 $n+1$，继续用那根柱子。 但是之前有一个构造全 0 柱的操作，较为繁琐，还是正解好打。 3. 看题解，发现 $\mathcal O(nm\log n)$ 的牛逼做法？这应该是正解。 我们看到唯一的特殊性质部分分是 $n=2$，于是分析一下 $n=2$ 怎么做。 然后我们手玩那个大样例，就得出了一个做法，[这篇题解](https://www.luogu.com.cn/blog/Kawai-Dzhao/solution-p7115)里写的很详细。 然后考虑**分治**。我们每次定一个阈值 $mid$，然后将 $\le mid$ 的移到左半区间，剩下的移到右半区间。 接下来讨论怎么处理这个分开的过程。类似于归并排序，我们搞两个指针，每次操作这两个指针的位置。 ```c++ 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](https://www.luogu.com.cn/record/64018677) - [P7116 [NOIP2020] 微信步数](https://www.luogu.com.cn/problem/P7116) ### 总结 个人认为这是目前难度最高的一次 NOIP。 除去 T1 恶心人的高精，题目质量非常不错。 结合数据强度，可能应该得到 $90 + 100 + 40 + 30= 260$？但是这成绩貌似还是很丢人/kk ## CSP 2021 - [P7913 [CSP-S 2021] 廊桥分配](https://www.luogu.com.cn/problem/P7913) - [P7914 [CSP-S 2021] 括号序列](https://www.luogu.com.cn/problem/P7914) - [P7915 [CSP-S 2021] 回文](https://www.luogu.com.cn/problem/P7915) - [P7916 [CSP-S 2021] 交通规划](https://www.luogu.com.cn/problem/P7916) ## NOIP 2021 - **A.** [P7960 [NOIP2021] 报数](https://www.luogu.com.cn/problem/P7960) - **B.** [P7961 [NOIP2021] 数列](https://www.luogu.com.cn/problem/P7961) - **C.** [P7962 [NOIP2021] 方差](https://www.luogu.com.cn/problem/P7962) 场上没搞出来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](https://www.luogu.com.cn/record/64032391) - [P7963 [NOIP2021] 棋局](https://www.luogu.com.cn/problem/P7963)