CSP2021 训练记录

这东西已经变成日记了 [前传](https://djwj233.blog.luogu.org/2021-shu-ji-xun-lian-ji-lu-8-yue) ### 9月4日 - [P2491 [SDOI2011]消防](https://www.luogu.com.cn/problem/P2491) 一道不错的题目，实际上就是[P1099 [NOIP2007 提高组] 树网的核](https://www.luogu.com.cn/problem/P1099)的加强版。 **引理：答案的路径一定是树的直径的一段。** 证明：反证法。设直径为 $A\to B$，答案路径为 $U\to V$，讨论： 1. $U\to V$ 和直径不相交。 设路径 $U\to A$ 上**最后一个在 $U\to V$ 上的点**为 $a$，**首个在 $A\to B$ 上的点**为 $b$。 由于树上两点之间路径唯一，那么容易发现 $U\to V$ 上的每一个点到达 $A\to B$ 都需要经过 $a$ 和 $b$。 设与 $U\to V$ 距离最远的点为 $x$，这个距离为 $ans$。那么若没有一个 $x$ 在 $A\to B$ 上，则有： $$ \mathrm{len}(a\to x)\geq ans > \mathrm{len}(a\to V) > \mathrm{len}(b\to V) $$ 因此有： $$ \mathrm{len}(A\to B)=\mathrm{len}(A\to b)+\mathrm{len}(b\to V)<\mathrm{len}(A\to b)+\mathrm{len}(a\to x) $$ 于是： $$ \mathrm{len}(A\to B)<\mathrm{len}(A\to b)+\mathrm{len}(a\to b)+\mathrm{len}(a\to x)=\mathrm{len}(A\to x) $$ 与 $A\to B$ 是直径矛盾。因此存在一个 $x$ 在 $A\to B$ 上，分析性质可知 $x$ 必为端点之一，不妨设为 $A$。 那么由于 $A\to B$ 是直径，那么可得对任意不在 $A\to b$ 上的点 $y$ 有 $\mathrm{len}(b\to B)\geq \mathrm{len}(b\to y)$。 由于 $\mathrm{len}(b\to A)\geq \mathrm{len}(b\to B)$，那么在直径上取一段包含 $b$ 的路径，有： $$ ans>\mathrm{len}(b\to A)\geq\mathrm{len}(b\to B)\geq \mathrm{len}(b\to y) $$ 那么易知答案更优。 2. $U\to V$ 和直径相交。 设与 $U\to V$ 距离最远的点为 $x$，同上可证存在一个 $x$ 是直径端点之一，不妨设为 $A$。 由于树上两点之间路径唯一，那么 $U,V$ 中必有一点不在 $A\to B$ 上，不妨设为 $V$。 并设路径 $U\to V$ 上**最后一个在 $A\to B$ 上的点**为 $a$，同上可得对任意不在 $A\to a$ 上的点 $y$ 有 $\mathrm{len}(b\to B)\geq \mathrm{len}(b\to y)$。 因此删去 $a\to V$ 的路径，然后在直径上扩展，答案不会更差。 综上所述，一定存在树的直径的一段作为答案。 我们两遍 DFS 求出树的直径 $a_{1\cdots k}$，然后对每个 $a_i$ 求出它**不经过直径中的其它点能到达的最远距离 $d_i$**。 那么答案即为： $$ \min_{\mathrm{len}(a_u\to a_v)\le s}\left\{\max\left\{ \max_{i=u}^v d_i,\ \mathrm{len}(a_1\to a_u),\ \mathrm{len}(a_v\to a_k) \right\}\right\} $$ 用单调队列维护 $\max\limits_{i=u}^v d_i$ 可以做到 $\Theta(n)$。 实际上，$\forall i<u,\ d_i\le \mathrm{len}(a_1\to a_i)< \mathrm{len}(a_1\to a_u)$，因此 $\max\limits_{i=u}^v d_i=\max\limits_{i=1}^v d_i$。同理上式也等于 $\max\limits_{i=1}^k d_i$。 这样便可以省去一个单调队列。复杂度 $\Theta(n)$。 **Status：AC.** [Code](https://www.luogu.com.cn/record/57788048) ### 9月11日 - [P7847 「dWoi R2」Elevator / 电梯](https://www.luogu.com.cn/problem/P7847) 先把 $N=1$ 的情况特判掉，再进行讨论。 不难想到一个预处理前缀和的思路：我们对每个 $c$ 都算出其对应的方案数、答案，然后在方案数中累加上之前的所有方案数。 题目中那个式子可推得： $$ ab+ac=bc $$ 由于 $ac>0$，因此 $ab<bc$，有 $a<c$。 考虑一种暴力：我们对每个 $c$，暴力地枚举 $a\in [1,c)$，每次判断 $$ b=\frac{ca}{c-a} $$ 是否为整数且是否有 $\gcd(a,b,c)=1$ 即可。复杂度 $\Theta(n^2)$。 问题在于如何优化这个枚举 $a$ 的过程。我们发现式子中的分母不太好处理，于是我们令 $c-a=x$，有 $$ x\mid ca \Leftrightarrow x\mid c(c-x)\Leftrightarrow x\mid c^2-xc \Leftrightarrow x\mid c^2 $$ 又因为 $x\in [1,c)$，因此 $x$ 是 $c^2$ 的较小的因数，有 $x<\dfrac{c^2}{x}$。 那么由于 $\gcd(a,c)=\gcd(c-a,c)=\gcd(x,c)$，因此 $\gcd(a,b,c)=\gcd(\gcd(x,c),b)$。 又因为 $$ b=\frac{c^2-xc}{x}=\frac{c^2}{x}-c $$ 因此设 $\gcd(x,c)=k$，则 $\gcd(k,b)=\gcd(k,\dfrac{c^2}{x})$。 再设 $\dfrac{x}{k}=\alpha,\dfrac{c}{k}=\beta$，有 $\gcd(\alpha,\beta)=1$，且 $$ \gcd(k,\frac{k^2\beta^2}{k\alpha})=1\Rightarrow\gcd(k,\frac{k\beta^2}{\alpha})=1 $$ 由于 $\gcd(\alpha,\beta)=1$，所以 $\gcd(\alpha,\beta^2)=1$，有 $\alpha\mid k$。 若 $\alpha<k$，则 $\gcd(k,\dfrac{k}{\alpha})>1$，矛盾，因此有 $\alpha=k$，故 $x=\gcd(x,c)^2$。 另一方面，可以证明取任意 $x$ 使 $x=\gcd(x,c)^2$ 时，所得的 $b$ 都是整数且有 $\gcd(a,b,c)=1$。 那么现在的问题变得简单多了。由算术基本定理，我们对 $c$ 进行标准分解：（这可以通过素数筛实现） $$ c=\prod_{i=1}^{cnt} p_i^{a_i}\quad(p_i\in \mathbb P,a_i>1) $$ 那么我们取的 $\gcd(x,c)$ 质因数分解后第 $i$ 项的次幂**要么是 $0$，要么是 $a_i$**。 对于第一问，看上去答案为 $2^{cnt}$，但这是不正确的。我们注意到有一个 $x<c$ 的要求，因此需要 $\gcd(x,c)^2<c$。 易知 $2^{cnt}$ 种答案一一对应地有 $>\sqrt{c}$ 和 $<\sqrt{c}$ 两种情况，且不可能有 $=\sqrt{n}$ 的情况出现。 因此答案就是 $2^{cnt-1}$。 对于第二问，让 $a$ 最小其实就是让 $x$ 最大。 那么我们反着来，枚举一个 $d=\gcd(x,c)$，枚举所有是 $d$ 的倍数且 $>d^2$ 的 $c$，逐一判断是否有 $\gcd(d^2,c)=1$ 并更新答案即可。 **Status：AC.** [题解](https://djwj233.blog.luogu.org/solution-p7847) - [P2597 [ZJOI2012]灾难](https://www.luogu.com.cn/problem/P2597) 一看就是一个要建支配树的毒瘤东西，不过由于图是 DAG，因此建树较为容易。 具体地，先新建一个虚拟源点连接到所有入度为 $0$ 的点上，然后以它为根建一棵支配树。 如果扫描到一条非树边 $(u,v)$，其中 $v$ 还没有被加入树中，那么我们就要把 $v$ 的父亲 $fa_v$ 改为 $\operatorname{LCA}(u,v)$。 但是如果对每个未被加进树中的 $v$ 都维护一个倍增数组会导致时间爆炸。如何优化？ 我们发现显然 $v$ 不能是 $u$ 的祖先，因此有 $$ \operatorname{LCA}(u,v)=\operatorname{LCA}(u,fa_v) $$ 这样就可以只维护已经加入树中的点的倍增数组。 最后再对支配树跑一遍 DFS 求出所有子树的大小即可。 **Status：AC.** [Code](https://www.luogu.com.cn/record/57880798) ### 9月15日 - [P2175 小Z的游戏分队](https://www.luogu.com.cn/problem/P2175) 这题难度还可以。题目大意是给定一张图，判断它能不能被分为两张完全图和一些剩余的边。 我们先把两条相反的有向边并成一条无向边，单的一条扔掉。 注意到 $n\le 2000$ 很诡异，因此可以考虑**建反图**，而建完反图之后完全图就没有边。 因此，我们直接判断反图是否是二分图即可。 那么如果有解，我们发现整张图可以被分为几个联通块。算出每个连通块左右部的大小之差做一个 01 背包即可。 可以用 bitset 减少码量，复杂度 $\Theta(n^2)$。[Code](https://www.luogu.com.cn/record/58062828) - [P3025 [USACO11OPEN]Forgotten Password S](https://www.luogu.com.cn/problem/P3025) 随机跳题跳到的，暴力 DP 即可。复杂度 $\Theta(L\times NW\times 20)$。 复习了一下 string 的用法。[Code](https://www.luogu.com.cn/record/58066059) - [P7383 「EZEC-6」加减](https://www.luogu.com.cn/problem/P7383) 一直感觉洛谷对这类思维题的难度评价都偏低.…… 结论是 $m\le \sum_{i=2}^{n+1} i$ 时无解，否则构造 $m-1$ 不合法，不过很难证。 - [P7384 「EZEC-6」分组](https://www.luogu.com.cn/problem/P7384) 首先每个 $0$ 可以单独分为一组，然后处理正整数。 我刚开始的做法是对每个数二分其最高位、最低位，然后将其间所有位合并，用并查集维护一下。 然后这东西能被 hack： ``` 2 2 5 ``` 正确答案是 $2$。自然想到应当枚举每个数所含有的位，将它们合并。但这是 $\Theta(n\log a)$ 的，过不了。wtcl，看了题解才会。 二分出来最高位之后，我们发现最高位相同的数一定在同一个组内。于是对每个最高位都维护一个或和，最后统一处理即可。 [Code](https://www.luogu.com.cn/record/58077355) ### 9月22日 - [P7864 「EVOI-RD1」摘叶子](https://www.luogu.com.cn/problem/P7864) 碰到这种奇怪的博弈论题，第一思路先 $\operatorname{SG}$ 函数乱搞，随便画出几张图，然后就不会做了，看了题解才会。 题解里面充分发扬了人类智慧，采用每个叶子向上找**第一个度数大于 $2$ 的祖先**，然后根据距离的奇偶性构造必胜策略。 [Code](https://www.luogu.com.cn/record/58388678) 之后 VP 了一场[普及组模拟赛](https://www.luogu.com.cn/contest/51260)，发现自己 FST 严重/yun 然后 D 好像有一个做法不过很难打，况且没有题解，于是就扔掉了。 ### 9月23日 - [P3576 [POI2014]MRO-Ant colony](https://www.luogu.com.cn/problem/P3576) 简单 DP，不过由于 `long long` 的问题挂了很多次/kk [Code](https://www.luogu.com.cn/record/58438536) ### 9月24日 - [P7287 「EZEC-5」魔法](https://www.luogu.com.cn/problem/P7287) 显然 $\texttt{+1}$ 操作应该在所有 $\mathtt{\times 2}$ 操作之前。 然后可以证明的是，执行完所有 $\texttt{+1}$ 操作后，全局 $\mathtt{\times2}$ 一定不比局部 $\mathtt{\times2}$ 差。 然后我们枚举 $\mathtt{\times2}$ 的次数，然后二分 $\mathtt{+1}$ 的次数即可，注意答案最大达到 $2\times 10^{18}$。 复杂度 $\mathcal O(n\log^2 s)$。[Code]() - [P7386 「EZEC-6」0-1 Trie](https://www.luogu.com.cn/problem/P7386) 怎么我现在每道题都要看题解啊/kk 很 nb 的一个 DP。由于最后一个为 $\texttt{1}$，那么倒数第二个一定是 $\texttt{0}$，我们可以先把这两个删掉。 设 $f(c\in\{0,1\},x,y)$ 为一棵**以 $c$ 为根的、每条路径上含有 $x$ 个 $0$ 和 $y$ 个 $1$ 的** Trie 的大小。 有边界 $f(0,1,0)=f(1,0,1)=1$。 $$ f(1,x,y)=f(0,x,y-1)+1 $$ $$ f(0,x,y)=f(0,x-1,y)+f(1,x,y-1)+1 $$ $$ =f(0,x-1,y)+f(0,x-1,y-1)+2 $$ 由隔板法，总串数为 $\dbinom{m-1}{n-1}$，每个串中最后的两个字符被忽略了。 因此答案即求 $f(0,n-1,m-1)+2\dbinom{m-1}{n-1}$，问题转化为如何求 $f(0,n-1,m-1)$。 实际上，我们可以忽略 $f(1,\cdots,\cdots)$，然后发现这个 $f(0,\cdots,\cdots)$ 的递推式是一个类似于组合数的东西，于是考虑把常数吃掉。 记 $g(i,j)=f(0,i,j)+2$，可得 $g(i,j)=g(i-1,j)+g(i-1,j-1)$，然后就不会了。 题解区有人就这么找出规律了 由于我不会推式子，考虑一个组合意义的做法。先写出几个较小的值： | | 0 | 1 | 2 | 3 | 4 | 5 | | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | 0 | 2 | / | / | / | / | / | | 1 | 3 | 4 | / | / | / | / | | 2 | 4 | 7 | 6 | / | / | / | | 3 | 5 | 11 | 13 | 8 | / | / | | 4 | 6 | 16 | 24 | 21 | 10 | / | | 5 | 7 | 22 | 40 | 45 | 31 | 12 | 我们发现边界的扩大： $$ g(i,0)=g(i-1,0)+1 $$ $$ g(i,i)=g(i-1,i-1)+2 $$ 因此考察 $g(x,y)$ 的值，它由左边边界上冒出的若干个 $1$ 和右边边界上的若干个 $2$ 合并得到。 左边边界上 $g(i,0)$ 的 $1$ 的贡献为 $\dbinom{x-i}{y}$，这部分的贡献就是 $$ \sum_{i=1}^{x-y}\binom{x-i}{y}=\sum_{i=y}^{x-1}\binom{i}{y}=\binom{x}{y+1}=\binom{m-1}{n} $$ 右边边界上 $g(i,i)$ 的 $2$ 的贡献为 $2\dbinom{x-i}{y-i}$，这部分的贡献就是 $$ \sum_{i=0}^{y}2\dbinom{x-i}{y-i}=2\sum_{i=x-y}^x\binom{i}{x-y}=2\binom{x+1}{x-y+1}=2\binom{m}{n-1} $$ 因此答案就是 $$ \binom{m-1}{n}+2\binom{m}{n-1}-2+2\binom{m-1}{n-1} $$ $$ =\binom{m}{n}+2\binom{m}{n-1}+\binom{m-1}{n-1}-2 $$ $$ =\binom{m+1}{n}+\binom{m}{n-1}+\binom{m-1}{n-1}-2 $$ 用 Lucas 算出来即可。复杂度 $\mathcal O(p+T\log_pn)$，其中 $p=18888913$。 [Code](https://www.luogu.com.cn/record/58541832)（常数太大，开了 O2） ### 9月26日 在打 [ABC 220](https://atcoder.jp/contests/abc220)。 赛时写出 A~F，然后看到 H 是个 NP-Hard 就弃掉去写 G，然后被卡精度了 拿了 rank 157，Performance 2317，赛后看到这个 sb 出题人写： > When using decimal types, be very careful of the computational errors. > > For this problem, we think it would be safer to use only integer types. 还有： > We can either divide into cases, or treat lines in a form of $ax+by+c=0$ instead of $y=ax+b$. 肺直接气炸了！！！ 题是不可能补的，这垃圾场狗都不补。 ### 9月27日 一直在调 P4200 后来就弃掉了。[最新版本](https://www.luogu.com.cn/paste/eksl9deo) - [P1485 火枪打怪](https://www.luogu.com.cn/problem/P1485) Binary Search 大法好！！！1111 考虑二分 $p$ 的值，然后转为判定。容易想到一个从右向左贪心然后暴力修改的思路，这样是 $\Theta(n^2\log m_i)$ 的。 考虑优化修改的过程，我们注意到这东西是一个二次函数，三阶导数恒为 $0$，因此对修改量序列维护一个三阶差分来优化修改过程，复杂度 $\Theta(n\log m_i)$。 实现时可以考虑先翻转序列再处理。[Code](https://www.luogu.com.cn/record/58655663) - [CF1466C Canine poetry](https://www.luogu.com.cn/problem/CF1466C) 随机跳题跳出来的。 我们发现，可以只关注长度为 $2$ 或 $3$ 的回文串，直接贪心即可。 由于字母有 $26$ 个，因此可以证明一定能有一种合适的取法。 [Code](https://www.luogu.com.cn/record/58664717) - [AT2068 [ARC061B] すぬけ君の塗り絵 / Snuke's Coloring](https://www.luogu.com.cn/problem/AT2068) 同上，随机跳题跳出来的。 考虑到 $n$ 很小，所以大多数格子都是白的。 我们对每个黑格子周围扩展一层，只有这一层中答案不为 $0$。 这里总格子数的上限是 $9n$，直接暴力计算即可。 复杂度 $\mathcal O(9^2n)$。[Code](https://www.luogu.com.cn/record/58667220) --- 以后计划： | 时间 | 第一安排 | 第二安排 | | :--: | :-------: | :--------------: | | 上午 | 集训作业 | 学 whk（除作业） | | 下午 | 学新东西 | 写 whk 作业 | | 晚上 | 比赛 / VP | 补集训作业 | 这段时间感觉自己挺颓的。 按洛谷的评级，做题的最高水平停留在绿题、蓝题。碰到一道紫的就不太会做，黑的就只能看题解。 有时候紫题看了题解还调不出来，只能弃掉 Splay 维护序列这种打了不下三四个，没一个调得出来，关键 Splay 还在大纲里面。 打算明天下午搞搞 Splay 吧。 ### 9月28日 （前几道是作业） - [AT5661 [AGC040C] Neither AB nor BA](https://www.luogu.com.cn/problem/AT5661) 看到 $n$ 级别是 $10^7$，猜想复杂度 $\mathcal O(n)$。 观察前两个样例，发现实际上答案和 $3^n$ 相差不大，这启发我们算出不合法的然后做一个容斥。 然后就不会了，看了题解。 题解里面**黑白染色**的思路比较神仙。对每个点黑白染色，将黑色位上的 $\texttt{A}$/$\texttt{B}$ 互换，容易发现它们一一对应。 这样限制就变成了不能删 $\texttt{AA}$/$\texttt{BB}$，这说明我们每删去一个 $\texttt{A}$/$\texttt{B}$ 就有一个不一样的字母要删去。 那么转化为**当且仅当 $\texttt{A}$ 的数量 $>\dfrac{n}{2}$ 或 $\texttt{B}$ 的数量 $>\dfrac{n}{2}$ 时不合法**。 假如是第一种情况，我们枚举 $\texttt{A}$ 的数量 $x$，答案即为 $\dbinom{x}{n}\times 2^{n-x}$，有两种情况乘 $2$ 即可。 这里复习了一下 $\mathcal O(n)$ 筛阶乘的逆元。先可以 $\mathcal O(n)$ 筛出 $1\cdots n$ 中每个数的逆元，然后考虑： $$ n!\times(n-1)!^{-1}\times n^{-1}\equiv 1\pmod{P} $$ 这样就可以可以线性递推。[Code](https://www.luogu.com.cn/record/58677457) 深究这个思路是怎么来的，就是利用了**每次都删两个**这一性质，考虑黑白染色。 实际上想这道题时已经想出了之后的大部分内容，就是缺一个染色。 - [AT4929 [AGC033F] Adding Edges](https://www.luogu.com.cn/problem/AT4929) 神仙题，完全没思路。看了[这篇题解](https://www.cnblogs.com/nealchen/p/AGC033F.html)大致会做了。 大致思路是：先转换 $G$ 到一个与 $T$ 相似的 $G^\prime$，尽可能地使 $G^\prime$ 中的每条边都是 $T$，然后统计答案。 不想写详细解了，场上碰到也不会做。[Code](https://www.luogu.com.cn/record/58686235) - [CF4D Mysterious Present](https://www.luogu.com.cn/problem/CF4D) 简单题，对其中一维排序然后另一维求 LIS。 可以用 BIT 维护做到 $\mathcal O(n\log n)$，不过懒得打离散化因此是 $\mathcal O(n\log h_i)$。[Code](https://www.luogu.com.cn/record/58688294) - [P2656 采蘑菇](https://www.luogu.com.cn/problem/P2656) 然而下午根本没时间打 Splay...... 碰到有向图先缩点，然后对 SCC 拓扑排序。 我们发现若到达某个 SCC，那么它内部的资源都是可以掠夺完的，而 SCC 间的边至多被走一次。 暴力 DP 即可，复杂度 $\mathcal O(n+m)$。[Code](https://www.luogu.com.cn/record/58695794) 发现自己老是漏下`if(ins[y])`（ - [AT3537 [ARC083D] Collecting Balls](https://www.luogu.com.cn/problem/AT3537) 看了看题解，大致会做了。问题可以被转化为求内向树森林的拓扑序个数。 代码暂时咕着，感觉还是建图的思路想不到。 --- 怕自己明天起不来床，因此没打算打今天的 CF。 VP 了 [CodeForces Edu. Round 114](https://codeforces.com/contest/1574)，认识到自己罚时吃到饱，是个 sb。 最后还是只搞出 ABCD，看到 EF 两个数数题随便想了想不会就逃了。 赛后发现差点想到 E 的做法（（（一个 key observation 已经在手里了，只是没有做下去的信心 F 好像也不是很难......还是不够勇。 ### 9月29日 上午考了数学，有一车题不会做 之后把昨天的 E 题 A 掉了。下午在打 XJ 的模拟赛，挂了 30 pts，机房 rk 2。 感觉还行？（晚上把 F 题 A 掉了，开始随机跳题。 - [AT4821 [ABC161E] Yutori](https://www.luogu.com.cn/problem/AT4821) 容易想到一个从左往右算和从右往左算出每个点左边、右边的值然后 DP。 打完发现假了，看了题解。（！！！！！黄题） 然后发现我 sb 了，应该根据工作日算出 `lbound` 和 `rbound` 然后处理。 [Code](https://www.luogu.com.cn/record/58756898) - [AT5243 [ABC161F] Division or Substraction](https://www.luogu.com.cn/problem/AT5243) ~~板刷 ABC~~ 我们发现 $k\nmid n\Rightarrow k\nmid n-ak,a\in \mathbb N$，因此实际操作时都是先尽量除后面不断减。 设 $n=k^\alpha n^\prime,\ k\nmid n^\prime$。减出来最后是 $1$ 说明 $n^\prime\equiv 1\pmod{k}$。 然后看到 $n\le 10^{12}$，猜想这是个约为 $\mathcal O(\sqrt{n})$ 的做法，然后就好办了。 1. 若 $n^\prime=1$，显然 $\alpha\ne0$，简单讨论： - $\alpha=1$，当且仅当 $k=n$。 - $\alpha>1$，则 $n=k^\alpha n^\prime\geq k^2$，有 $k\le \sqrt{n}$。 2. 若 $n^\prime>1$，则 $n^\prime\geq k+1$。讨论： - $\alpha=0$，设 $n=ak+1$，易见答案就是 $n-1$ 的约数个数减去 $1$。（由于 $k>1$，因此要把 $1$ 减掉） - $\alpha\geq1$，则 $n=k^\alpha n^\prime\geq k(k+1)>k^2$，有 $k\le n$。 综上，除了两种特殊情况以外，别的 $k$ 都是不大于 $\sqrt{n}$ 的，可以一一枚举判断。 由于除的次数至多是 $\log n$，因此复杂度 $\mathcal O(\sqrt{n}\log n)$。 注意在枚举时要排除 $\alpha=0$ 的情况。[Code](https://www.luogu.com.cn/record/58759951) - [AT5799 [AGC043B] 123 Triangle](https://www.luogu.com.cn/problem/AT5799) 瞎猜了个结论，然后假了（（（（看了题解。 神仙思路，大致是利用**如果数列中存在 $1$，那么答案只可能是 $0$ 或 $1$**，否则可以全局除 $2$ 转化为这个问题。 而加上一个数和减去一个数奇偶性相同，可以判断是 $0$ 还是 $1$，因此只需组合数算贡献。 由于 $0$ 对 $2$ 没有逆元，可以考虑用 Lucas 定理。[Code]() 思路应该是**抓住只有三种可能这一性质**，排除一种然后奇偶性。 - [AT3537 [ARC083D] Collecting Balls](https://www.luogu.com.cn/problem/AT3537) 上次落下的题，非常难。这里注意到且一个球**恰有两种选择**，可能会想到 2-SAT。 但是这样直接做会导致边数爆炸。可以考虑另一种思路，即： > 把每个球（即 2-SAT 中的变量）作为**一条边**，然后用点去匹配边。 不过这种做法需要保证**每个点都只能作为一个点的选择**，因此这个做法普遍性不强，一般只适用于**行列支配类**问题。 这样建出图后，我们发现它是一个基环树森林，且除了环上的边以外边的选择都是固定的。 于是直接枚举环上是顺时针还是逆时针就可以确定每个点要支配哪条边，此时我们已经把基环树上的点和边捆绑在了一起。 之后，我们对题目中对支配的顺序限制连成一张 DAG，答案就是其拓扑序的个数。 但是我们好像并不会对 DAG 的拓扑序进行多项式的计数？ 继续挖掘性质，发现一个行机器人至多是一个列机器人的先决条件，同理对列机器人也是。 因此这个 DAG 就是一个内向树森林。套用内向树的拓扑序计算公式：（$\text{size}(i)$ 为各子树大小） $$ \frac{n!}{\prod_{i=1}^n\operatorname{size}(i)} $$ 注意联通块之间的计算需要用：（$\text{size}(i)$ 为各联通块大小） $$ \dfrac{(2n)!}{\prod_{i=1}^{num}\text{size}(i)} $$ 也即**多重集全排列公式**。 好难打啊啊啊啊啊啊啊啊啊啊啊啊！！！！！！1111111111111111 [Code](https://www.luogu.com.cn/record/58790110) ### 10月3日 听说以后都要持续打某高质量模拟赛，每天两场 也就是说根本没有自己做题的时间只能说 xxy sb  下午打了洛谷 10 月月赛，由于菜打的是 div.2。 场上切了 A 和 B，想了好一会儿才会 D，C 不会（ 最后 365 pts，全场 rk 10，貌似还行？ - [CF1419E Decryption](https://www.luogu.com.cn/problem/CF1419E) 过来做几道 MO 风格的数论题。自然地想到质因数分解，然后就可以猜结论。 显然当且仅当 $n$ 能被分解为两个不同的质数之积时需要一次操作，其它情况都不需操作。 构造一个不需操作的序列是难点，不过我们可以用格雷码完成这一过程。 [Code](https://www.luogu.com.cn/record/59049692) 开了字符串的大坑，打算从 Border 学起到 KMP/exKMP 再到 ACAM 最后 SA/SAM。 ### 10月4日 今天生日！ 好像今天只有上午的比赛呢 ~ 晚上调不出[P4156](https://www.luogu.com.cn/problem/P4156)，十分自闭，发扬优良传统，就又扔掉了。 - [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139) 写个小清新数论题。 我们设题目中那个数为 $S$，则有： $$ 2^S\equiv S\pmod{n} $$ 然后一直尝试解方程，就不会了/kk 看了题解，不得不说十分精妙。注意到： $$ S\equiv 2^S\equiv2^{S\ \bmod\ \varphi(n)+\varphi(n)}\pmod{n} $$ 这样便能把问题转化为求 $S\bmod\varphi(n)$，缩小了问题规模。复杂度 $\mathcal O(n+T)$。 总之，**带有指数的求同余一律考虑 费马小定理 / 欧拉定理**。 还有就是考虑找到分治的思路，由于大纲中东西不多，所以会把很基础的知识点考得很难来区分掉我这种没脑子的选手。 [Code](https://www.luogu.com.cn/record/59158468) ### 10月5日 JacderZhang 放了一套 NOI Plus 模拟赛，赛后还是只会 A 题 qwq 大致 A 题部分分是 CDQ，B 题是 SAM，C 题是神仙构造，爬了爬了。 $\color{black}\text{z}\color{red}\text{houAKngyang}$ 230  - [P5683 [CSP-J2019 江西] 道路拆除](https://www.luogu.com.cn/problem/P5683) 这个 djwj233 菜到不行，来做 PJ 题目了 猜一个结论，最后的图肯定是一条链或者一个丁字路。 那么依赖跑一个 Dijkstra，枚举丁字路的中心暴力更新答案。 复杂度 $\mathcal O((m+n)\log n)$。不知道为什么 $n$ 只开到 $3\times 10^3$ [Code](https://www.luogu.com.cn/record/59240204) - [P5684 [CSP-J2019 江西] 非回文串](https://www.luogu.com.cn/problem/P5684) 显然可以做一个容斥，算出回文串的方案数再搞。 然后判断是否有 $>1$ 种字母数量为奇数，然后多重集排列。 复杂度 $\mathcal O(n)$，依旧不知道为什么 $n$ 只开到 $2\times 10^3$  [Code](https://www.luogu.com.cn/record/59235506) 果然做普及题让人极度舒适。 ### 10月6日 上午模拟赛四个普及题，↑↓出题人还卡精度 终于把 KMP 搞完了 - [P7470 [NOI Online 2021 提高组] 岛屿探险](https://www.luogu.com.cn/problem/P7470) 神仙题 显然我们需要差分 $[1\cdots l_i-1]$ 和 $[1\cdots r_i]$ 的答案。 考虑如果把式子中的 $\min(b,d)$ 换成 $d$，那么显然可以用一个可持久化 Trie 解决。 而如果把式子中的 $\min(b,d)$ 换成 $b$，实际上可以在插入原数时对 Trie 打一些 tag。 接下来考虑 $l_i=1,\ r_i=n$ 的情况，我们发现可以将数对按 $b$ 排序，将询问按 $d$ 排序，然后结合上面两个做法分别处理前后两部分。 这样就有 65pts 了，然后就不会了qwq 又看了题解。有一篇题解中的做法是**把每个询问拆成线段树上的 $\mathcal O(\log n)$ 个区间**然后离线处理，真的神仙啊 过了！！1 [Code](https://www.luogu.com.cn/record/59348181) 需要注意的是代码里 two pointers 一部分需要写成上面： ```c++ while( p<p2 && arrq[p+1].first <= b[x] ) ``` 下面： ```c++ while( p>1 && arrq[p-1].first > b[x] ) ``` 总之恰好有一个取等号，主要是避免 $b=d$ 时答案被重复计算或者被漏算。 ### 10月7日 今天没有高质量模拟赛 - [P5537 【XR-3】系统设计](https://www.luogu.com.cn/problem/P5537) 神仙题！！1 我们记录从根结点到每个点的路径，然后 hash。 处理询问时直接 Binary Search，修改可以用线段树维护。 但是这样是 2log 的，会被卡掉，我们可以维护一个 hash 表，在线段树上二分即可。 [Code](https://www.luogu.com.cn/record/59384821)。非常想骂 xht37，因为他不仅卡了双模 hash 的常数还卡单模 hash 的模数！！ 我调了一页半才弄过去！！1 - [P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈](https://www.luogu.com.cn/problem/P2252) 把板子题当练习题做（ 首先 $\mathcal O(n^2)$ 的 DP 是非常好写的。然后先打个小一点的表： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | :--: | :----------: | :----------: | :----------: | :----------: | :------: | :----------: | :------: | | 0 | **后手必胜** | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | | 1 | 先手必胜 | 先手必胜 | **后手必胜** | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | | 2 | 先手必胜 | **后手必胜** | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | | 3 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | **后手必胜** | 先手必胜 | | 4 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | | 5 | 先手必胜 | 先手必胜 | 先手必胜 | **后手必胜** | 先手必胜 | 先手必胜 | 先手必胜 | | 6 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 先手必胜 | 实际上我们发现后手必胜的情况非常稀有。忽略 $(0,0)$ 的情况，观察 $(1,2)$，$(3,5)$ 的特性并向下画一个草图，易见： > 设第 $i$ 个后手必胜态为 $(a_i,b_i)\ [a_i\le b_i]$，则有 $b_i-a_i=i$。 原理非常明白，因为每个必败态都会标记一整条主对角线。 然后我们来讨论 $a_i$ 的取值，找规律发现相邻两个 $a_i$ 的取值之差呈 $1,2,1,2\cdots$ 排列。 于是我们写出 $a_n=3\left\lfloor\dfrac{n}{2}\right\rfloor+n\bmod 2$，然后交上去发现 WA 了一个点 `8 13`，于是特判掉即可。 不是不是我是傻逼吗？？！！！！1111 正解自然不是这种傻逼东西，而且这个结论其实是完全错的，答案应该是： $$ a_n=\left\lfloor\dfrac{\sqrt{5}+1}{2}n\right\rfloor $$ 那么问题来了，这个 $\dfrac{\sqrt{5}+1}{2}$ 是哪里蹦出来的 nya？ 显然 $a_i$ 应取 $\mathrm{mex}\left\{a_{1\cdots i-1}\cup b_{1\cdots i-1}\right\}$，因此集合 $\{a_i\},\{b_i\}$ 不交。 然后有个什么 Beatty 定理： > 设 $a,b$ 是正无理数且 $\dfrac{1}{a} +\dfrac{1}{b} =1$，记 $P=\left\{ \left\lfloor na\right\rfloor\ |\ n\in \mathbb N\right\}$，$Q=\left\{ \left\lfloor nb\right\rfloor\ |\ n\in \mathbb N\right\}$，则有： > > - $P\cap Q=\varnothing$ > - $P\cup Q=\mathbb N^+$ 由于 $b_i=a_i+i$，因此 $\forall n\in \mathbb N,\ \left\lfloor nb\right\rfloor=\left\lfloor na\right\rfloor+n=\left\lfloor n(a+1)\right\rfloor$，有 $b=a+1$。 解 $\dfrac{1}{a} +\dfrac{1}{a+1} = 1$ 得 $a=\dfrac{\sqrt{5}+1}{2}$，$b=\dfrac{\sqrt{5}+3}{2}$。（负根已舍去） 关于 $a$ 为什么不是有理数：设 $a=\dfrac{p}{q},b=\dfrac{p+q}{q}$，取 $n=pq,m=q(p+p)$，就有 $\left\lfloor nb\right\rfloor=\left\lfloor ma\right\rfloor$，矛盾。 [Code](https://www.luogu.com.cn/record/59423293) ### 10月8日 某些 nt 还是差不多得了 /流汗黄豆 - [P5535 【XR-3】小道消息](https://www.luogu.com.cn/problem/P5535) 首先考虑为什么要取到 $n\le10^{14}$，我们猜想这个算法一定是 $\mathcal O(\sqrt{n})$ 级别的。 由切比雪夫定理，$\forall n\in \mathbb N^+,\ n>1$，在 $(n,2n)$ 中有一个质数 $p$，这样**一旦 $p$ 被标记，则 $[2,2n]$ 中的数都会被标记**。（因为 $p$ 最小的倍数 $2p>2n$） 因此我们先判断当前符不符合这个情况，若符合则答案为 $1$，否则一定有： 1. 当前数是一个合数 2. $[2,n+1]$ 中有当前数的大于本身的倍数 二者之一，即不可能存在一次的情况，现在我们证明最多两次就能全部标记。 取 $[2,n+1]$ 中最大的质数 $p$，若 $2p\le n+1$，则 $(p,2p)$ 中还有一个质数，矛盾。因此 $2p>n+1$，$[2,n+1]$ 中没有当前数的大于本身的倍数。 因此 $\forall x\in[2,n+1],\ \gcd(x,p)=1$，可以通过 $k+1\to p\to \text{all numbers in} [2,n+1]$ 的路径实现两次。 [Code](https://www.luogu.com.cn/record/59432743) - [P4063 [JXOI2017]数列](https://www.luogu.com.cn/problem/P4063) 打算做一下一些套题（ 我们模拟这个过程，发现实际上执行的是**不断地向有序集合中插入一个数，且必须与前一个数相邻**。 实际上这就是一个不断划分区间的过程，考虑 DP。 然后一直在写，气死了，懒得写题解了,贴个代码。 ```c++ #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define il inline typedef long long ll; const ll P=998244353; const int N=60, M=160; int n,m,lim[N]; ll dp[M][M][M],s[2][M][M],w[M]; void add(ll &x,ll y) { x=(x+y)%P; } int main() { cin>>n; fo(i,1,n) scanf("%d",&lim[i]), m=max(m,lim[i]); fo(i,1,lim[1]) dp[i][0][m+1]=1;//不能取[1,m] fo(i,2,n) { memset(s,0,sizeof(s)); fo(x,1,m+1) w[x]=dp[x][x][x]; fo(x,1,lim[i-1]) fo(l,0,x-1) fo(r,x+1,m+1) { add(w[x],dp[x][l][r]), add(w[l],dp[x][l][r]), add(w[r],dp[x][l][r]); //由于l<x<r，因此只有这三种情况能转移到 x=l=r （出现相同数）的情况 add(s[0][l][x],dp[x][l][r]), add(s[1][x][r],dp[x][l][r]); } memset(dp,0,sizeof(dp)); fo(x,1,lim[i]) fo(l,0,x-1) fo(r,x+1,m+1) { add(dp[x][l][r],s[0][l][r]);// 区间缩小，由于不能出现相同数所以都是开区间 add(dp[x][l][r],s[1][l][r]); } fo(x,1,lim[i]) dp[x][x][x]=w[x];//这是为了避免不合法（>lim[i]）的转移 } ll ans=0; fo(x,1,lim[n]) fo(l,0,x) fo(r,x,m+1) add(ans,dp[x][l][r]); printf("%lld\n",ans); return 0; } ``` - [P4064 [JXOI2017]加法](https://www.luogu.com.cn/problem/P4064) 前两题的难度根本不是一个级别的好吗！！！ ~~可能是我 DP 太渣~~ 显然二分答案然后用堆维护一个贪心。[Code](https://www.luogu.com.cn/record/59469777) 于是发现自己最大的问题还是 DP（ ### 10月9日 XJ 的 NOIP 模拟赛放三个集训队作业的加强版 下午在整理差分约束系统的笔记，晚上在打 ABC 222，拿了`Rank 238, Performance 2130`，逊欸！！ ### 10月10日 由于要打疫苗所以回了一趟家。 补了昨天 ABC 的 G。 晚上打 CF Edu Round 115，好像能上 newbie 了。 ### 10月11日 今天下雨，不用跑操，好耶！！1 - [P3628 [APIO2010]特别行动队 ](https://www.luogu.com.cn/problem/P3628) 裸的斜率优化，直接做即可。[Code](https://www.luogu.com.cn/record/59623142) - [P4065 [JXOI2017]颜色](https://www.luogu.com.cn/problem/P4065) 不会 qwq 题解里面有一个神仙做法是 hash！！！ 也可以用一个线段树的做法： 1. 枚举右端点 $r$，考虑计算有几个 $l$ 满足要求。 2. 若有一个颜色 $j$ 满足 $l_j\le r$ 且 $r_j>r$，则范围只能在 $(l_j,r]$ 间选取。 这可以用单调栈维护。 3. 若有一个颜色 $j$ 满足 $l_j\le x$ 且 $r_j>x$，则 $x$ 不能被计入 $l$ 的答案。 这可以用线段树维护。 [Code](https://www.luogu.com.cn/record/59655422) 总结：多想想 hash！ - [P7818 [RC-05] 排列](https://www.luogu.com.cn/problem/P7818) 绿题，好难，不会 看了看题解，好神仙！！1就是维护一棵线段树然后贪心即可。[Code](https://www.luogu.com.cn/record/59679334) ### 10月12日 貌似明天开始停课 - [P7817 [RC-05] 迷失自我](https://www.luogu.com.cn/problem/P7817) 诈骗题！！！[Code](https://www.luogu.com.cn/record/list?pid=P7817&user=114558) - [P7849 「JZOI-2」猜数列](https://www.luogu.com.cn/problem/P7849) 憨憨题！[Code](https://www.luogu.com.cn/record/59725434) ### 10月13日 今天没有模拟赛，好耶！！ - [P2706 巧克力](https://www.luogu.com.cn/problem/P2706) 因为怕自己黄题、绿题都写不出过来写写简单题。 直接贪心乱搞即可。[Code](https://www.luogu.com.cn/record/59733192) 开了个坑打算补补之前联赛的题。 ### 10月14日 今天模拟赛大失败。A 是一个憨憨题，切了；B 是一个弱智 DP，以为是贪心然后由于 subtask 制爆蛋了。 C 是一个数数题，完全不会；D 是一个神仙构造题，骗了 60pts 跑路了。 气温 29℃，热热热热热热热热热热热热热热热死我了！！！！！！！！！1111111111111111111111 补了之前 Edu Round 的 F，随机组了套题想做做。 - [CF1537D Deleting Divisors](https://www.luogu.com.cn/problem/CF1537D) 猜结论。猜到： 1. 若 $\exists x\in \mathbb N,s.t. 2^x=n$，则当且仅当 $2\mid x$ 时先手必胜。 2. 否则当且仅当 $2\mid n$ 时先手必胜。 证明： > - 第二个东西可以归纳证明。 > - 若偶数 $n$ 不是 $2$ 的次幂，则它一定有一个大于 $1$ 的奇数因子，相减得奇数，因此先手必胜； > - 奇数 $n$ 的因子都是奇数，相减得奇数，因此后手必胜。‘ > - 对 $2$ 的次幂，利用上面的结论简单归纳也可以证出。 [Code](https://www.luogu.com.cn/record/59840695) ### 10月15日 今天没有模拟题，好耶！ - [AT5312 [ABC156E] Roaming](https://www.luogu.com.cn/problem/AT5312) 差点被一个 ABC 1500 分的 E 卡住（ 首先可以发现每个人都是一样的，此外由于 $n\geq 3$，因此可以从所有 $k$ 的情况构造 $k+1$ 的情况。 因此 $k\geq n$ 时答案等价于 $k=n-1$。注意到 $k$ 的约束等价于**数列中之多出现 $k$ 个 0**，因此答案就是 $$ \sum_{i=0}^k\dbinom{n}{i}\dbinom{n-1}{n-i-1} $$ [Code](https://www.luogu.com.cn/record/59866634) - [P4182 [USACO18JAN]Lifeguards P](https://www.luogu.com.cn/problem/P4182) 直接 DP，由于数组开小卡了好一会儿（ 我们贪心地删除一些线段使剩下的 $l_i,r_i$ 分别单调递增。记 $dp_{i,j}$ 为有 $i$ 个空档的以 $r_j$ 结尾的最大答案，有 $$ dp_{i,j}=\begin{cases} \max_{k\in[0,j)} dp_{i-j+1+k,k}+r_j-l_j & \text{if}\ r_k\le l_j\\ \\ \max_{k\in[0,j)} dp_{i-j+1+k,k}-r_k+r_j & \text{if}\ r_k> l_j \end{cases} $$ 然后上面那个东西可以用一个单调队列维护 $r_k>l_j$ 的位置，剩下的用单变量维护。 [Code](https://www.luogu.com.cn/record/59878652) - [SP10079 STAMMER - Stammering Aliens](https://www.luogu.com.cn/problem/SP10079) 二分答案然后直接 hash 即可。[Code](https://www.luogu.com.cn/record/59888139) ### 10月18日 打了 x义x 的模拟赛，被打爆了/kk ### 10月19日 感觉今天的模拟赛比较可做qwq ### 10月20日 还有两天，好慌啊！！ - [P2481 [SDOI2010]代码拍卖会](https://www.luogu.com.cn/problem/P2481) 打算重做一遍这题。过了。 - [P6878 [JOI 2020 Final] JJOOII 2](https://www.luogu.com.cn/problem/P6878) 直接 Binary Search。[Code](https://www.luogu.com.cn/record/60440058) - [AT2264 [AGC008B] Contiguous Repainting](https://www.luogu.com.cn/problem/AT2264) 猜结论，然后贪贪贪。 ### 10月21日 - [P7356 「PMOI-1」游戏](https://www.luogu.com.cn/problem/P7356) 直接乱搞。 最后一场模拟赛打了 200pts，感觉这次要 2= 退役了（ ### 10月22日 - [ARC004D 表現の自由 ( Freedom of expression )](https://www.luogu.com.cn/problem/AT187) - [CF1286E Fedya the Potter Strikes Back](https://www.luogu.com.cn/problem/CF1286E)