模拟赛笔记
LinkZelda
·
·
个人记录
NOIP 计划
Day 1
T1 给定一个字符串，只有大小写字母和数字，大小写转换，数字变成 9 减去它本身后输出。
送温暖模拟题。
T2 给定一个序列，求所有长度为 m 的子序列删去最大值和最小值之后剩下数的乘积，对所有满足条件的子序列的答案求乘积，对 10^9+7 取模，n\leq 5000,3\leq m\leq n，a_i 两两不同。
考虑每个数的贡献，直接求出现次数比较复杂，我们转化为最多出现次数减去作为最大值或者最小值时的出现次数。
前者就是剩下的数中选 m-1 个的方案数，即 \binom{n-1}{m-1}。
后者就是暴力算出比每个数小的数的个数 x 和比它大的数的个数 y，这样的方案数是 \binom{x}{m-1}+\binom{y}{m-1}。
因为要求乘积，那我们用费马小定理降幂，预处理组合数，时间复杂度为 O(n^2)。
T3 给一棵树，带边权，每次询问一条链上权值 \leq x 的边权异或和。n,q\leq 5\cdot 10^5,a_i\leq 10^9。
边权异或和套路地转化为两点树上前缀和，考虑离线。
我们从小往大加边权，会影响的前缀和只有子树内的点，树状数组维护即可，O(n\log n+q)。
T4 给一棵完全图的生成树，求剩下的边任意边集加上后边双连通分量个数为 i 的方案数，对每个 i 求出答案。n\leq 200。
首先考虑暴力就是枚举边集，进而联想到枚举点集（虽然这个做法好像假了），想到这里 check 一个点集合法的情况必然是一个连通块后，就发现可以 dp 了。
设 dp_{i,j,k} 表示在点 i 的子树内，删去 j 条边，点 i 所在的连通块大小为 k 的方案数。我们发现转移很困难，因为删边的时候连通块内的边难以保证可以使得整个连通块恰好成为一个边双，于是考虑二项式反演容斥。
状态转为 dp_{i,j,k} 表示在点 i 的子树内，删去至少 j 条边，点 i 所在的连通块大小为 k 的方案数。然后最后我们套用一下二项式反演的式子把至少转化为恰好即可。
dp 相当于是树上二维背包，所以复杂度为 O(n^4)。
Day 2
T1 每个数字 i 都有一个权值 a_i。对于一个数 n，定义一次变换为把 n 改为 n 的每位数字的对应权值加起来。给定 n,k，求 n 经过 k 次变换后的值。n\leq 10^{18},k\leq 10^9,a_i=\{13,1,2,3,5,4,4,2,2,2\}，多测 T\leq 500。
我们发现这个变换对权值的影响收敛很快，我们暴力做几次之后讨论一下即可。
还有一种通用的做法就是倍增，我们发现 10^{18} 内的数变换一次之后 <500，我们直接预处理 st_{i,j} 表示 j 变换 2^i 次之后得到的值即可。
T2 给定一个长度为 n 的简化 python 代码序列，只含 F 表示循环语句和 P 表示输出语句，每段循环语句后至少有一句语句缩进比它恰好多 1。第一句不缩进。求加上缩进后合法的代码片段种数。n\leq 1000。
考虑 dp，设 $dp_{i,j}$ 表示现在考虑到第 $i$ 句，目前所在位置循环层数为 $j$。
如果 $S_{i-1}$ 是 `F` 那么这句循环层数必须 $+1$。
否则，讨论一下就可以通过 $dp_{i-1,\cdot}$ 的一个后缀转移过来，后缀和优化即可。
> **T3** 给定一个长度为 $n$ 的序列，你可以相邻两项为一队或者单独一项为一队，一个队的权值为队内所有权值之和，求最小的分队权值极差。$n\leq 10^5$。
我们发现可能的队权值只有 $O(n)$ 种，于是我们可以暴力枚举 $\max$ 之后 dp 出来最大的 $\min$。
考虑扫描线（或者这里说双指针也差不多），我们从大往小枚举 $\max$，我们考虑一个 dp。
设 $f_i$ 表示前 $i$ 个数在当前枚举的最大值下最大的最小值，那么有
$$
f_i=\max\{\min\{f_{i-1},a_i\},\min\{f_{i-2},[a_{i-1}+a_{i}\leq \max](a_{i-1}+a_i)\}\}
$$
考虑优化，我们修改最大值其实只会影响到 $O(1)$ 个位置，我们考虑使用线段树维护动态 dp，我们写成矩阵的形式。
$$
\begin{bmatrix}
f_{i-1}&f_{i-2}
\end{bmatrix}\times
\begin{bmatrix}
a_i & +\infty\\ [a_{i-1}+a_i\leq \max](a_{i-1}+a_i)&0
\end{bmatrix}=
\begin{bmatrix}
f_i&f_{i-1}
\end{bmatrix}
$$
然后线段树维护即可，$O(n\log nk^3)$，$k$ 为矩阵大小。
> **T4** 给定一棵树，每个点有一个权值 $a_i$，每个点至多被经过 $k$ 次，但权值只会获得一次，求从 $1$ 号点出发可以获得的权值和最大值（不需要回到 $1$ 号点，出发时算经过一次）。$n,k\leq 2\cdot 10^5$，$a_i\in[1,2000]$。
我们考虑一个子树内，我们走进这个子树时会经过一次，然后从一个子树出来再去到另一个子树内时也会经过一次，最后如果返回这个子树的祖先又会经过一次。因为权值均为正数，所以我们肯定去的子树越多越好。
我们考虑设 $f_{i,0/1}$ 表示在 $i$ 的子树内，不返回或者返回该子树的祖先，在子树内获得的最大权值和。
我们直接 dfs，然后对所有子树的答案排序之后贪心取即可。注意如果该结点不返回祖先，我们取的子树也可以有至多一个不返回祖先。时间复杂度为 $O(n\log n)$。
## Day 3
> **T1** 给定一个字符串，你需要把它镜像翻转（特殊地，J 变成 L，$2$ 变成 $5$）。
> $|S|\leq 10^5$。
变换完特别的字符后 reverse 即可。
> **T2** 给定一个边带权无向图，你可以选择路径至多 $k$ 条边把边权 $w$ 变为 $\lfloor\frac{p}{q}\cdot w\rfloor+b$，保证 $q>p$，求 $1$ 到 $n$ 的最短路。$n\leq 5000,m\leq 5\cdot 10^4,k\leq 10$。
分层图最短路即可。
> **T3** 给定 $n$ 个数 $a_i$，多组询问求 $a_i$ 的 $x$ 阶前缀和的第 $y$ 项。$n,q\leq 8000,x\leq 10^9$。
打表可以发现循环节为 $2^w$，$w$ 为最小的数满足 $2^w\geq n$，直接暴力预处理即可 $O(1)$ 回答。
bouns：$n,q\leq 10^5$。
> **T4** 给定一棵树，每次给定 $x,k$ 询问以 $x$ 为根时，有多少个点 $y$ 满足 $y$ 的子树内离 $y$ 最远的点的距离 $\leq k$。$n,q\leq 10^6$。
考虑暴力怎么做，我们可以预处理出每个点子树内最远点的距离然后用树状数组维护值域上的答案，即可 $O(n^2\log n)$。
我们可以利用类似换根 dp 的做法，考虑换根的贡献，我们发现我们需要删去某些子树的答案，且支持求子树 $\max$，所以可以使用一个 set 维护每个结点的儿子的最远点距离，然后换根的时候就可以 $O(\log n)$ 时间内处理。把全部询问离线下来跑一次即可，时间复杂度为 $O(n\log n)$。
当然这样常数会非常大，考场上写这个被卡掉了，实际上我们并不需要维护出来整个 set，我们关心的只是每个点子树的最大值和非严格次大值，直接讨论一下就行，这样的理论复杂度不变，但树状数组的常数很小，可以通过。
正解是线性的。考虑找出树上的一条直径（设其长度为 $d$），如果某个点的子树内包含的这个直径的终点，那么这个点的最远距离必然 $\geq \frac d2$。考虑一个换根操作，实际上我们会影响的只有原树根和当前根路径上的结点，假设我们树根为直径终点，那么该路径上的最远距离恰好是一个等差数列，这是换根后的贡献。
那我们考虑如何减去原树上的贡献，现在的问题就变成了查询一条点到根路径上 $\leq k$ 的点个数，我们可以把所有询问离线用桶排按 $k$ 排序询问，因为原树上每个点的最远距离肯定是从下往上递增的，那么我们可以使用并查集向上合并，维护集合内 $min_{dep}$，树上并查集可以证明是 $O(n)$ 的，因此时间复杂度为 $O(n)$。但其实这个做法常数较大而且难写，$O(n\log n)$ 好写好想而且树状数组自带 $\frac 12$ 的常数。
## Day 4
> **T1** 给定 $n$ 个物品，第 $i$ 个物品有一个权值 $a_i$。给定权值 $L$，表示一个背包的容量，你需要对每个 $x=1,\cdots,n$ 输出至少需要多少个背包才能按顺序装完下标在 $[x,n]$ 中的所有物品，且每个背包不超载。$n\leq2\cdot 10^5,a_i,L\leq 10^9$。
我们发现直接暴力是 $O(n^2)$ 的，但从每个装一个背包可以到达的位置是确定的，于是我们可以直接倍增优化跳到装了 $2^k$ 个背包后到达的位置，这样是 $O(n\log n)$ 的。
但这题有特殊性质，所有询问的右端点都是 $n$，所以我们可以直接从后往前 dp，计算的时候使用双指针即可做到 $O(n)$。
> **T2** 给定一个有 $m$ 个数的集合 $B$，以及一个正整数 $n$，每次你可以选择一个集合中的数 $x$，让 $n$ 变为 $\lfloor\frac nx\rfloor$，你可以进行任意次操作，求 $n$ 可以变成的数的种数。$m\leq10,n\leq 10^{15}$。
因为集合中的数很少，所以答案也不会很大（即使数很多答案也不会很大，根据整除分块的结论是 $O(\sqrt n)$ 级别的）。于是我们直接 dfs 暴力，并且记忆化 dfs 过的值剪枝一下即可。
> **T3** 给定一张无向完全图，每个结点有一个权值 $a_i$，任意两个点 $i,j(i<j)$ 之间连边的权值为 $a_j-a_i$，求原图的最小生成树。$n\leq 3\cdot 10^5$。
考虑 prim 算法的过程，我们需要支持的操作就是向集合中加入一个点，查询集合内与集合外的点边权最小值。我们可以直接使用线段树维护，相当于是对每个点记录一个 $b_i=0/1$ 表示这个点在或者不在集合内，查询 $b_i$ 不同的两个点之差的 $\min$，我们对线段树每个结点记录 $b_i=0$ 的 $\min,\max$ 以及 $b_i=1$ 的 $\min,\max$，合并的时候就可以 $O(1)$ 了，把点加入集合就是一个单点修改，时间复杂度为 $O(n\log n)$。
> **T4** 给定一个字符串 $S$，定义一个字符串是好的当且仅当它可以写成 $\text{xyxyxyx...}$ 的形式，其中 $x\neq y$。多次询问一个区间内最长的好的子序列，输出长度以及满足条件的字典序最小的 $x,y$。$n\leq 1.5\cdot 10^6,q\leq 10^5,|\Sigma|\leq 26$。
乍一眼看上去都是线段树维护，但复杂度都比较大，而且难以平衡。
考虑钦定某个字符 $i$ 后，那么字符串就被划分成了若干段，我们预处理一个数组 $app_{i,j,k}$ 表示字符 $j$ 在钦定字符 $i$ 划分后的第 $k$ 段中是否出现，然后我们对第三维求一个前缀和，第三维可以动态开，因为段数和 $i$ 的出现次数有关，时空复杂度为 $O(n|\Sigma|)$。我们再预处理出 $pre_{i,j}$ 和 $nxt_{i,j}$ 表示位置 $i$ 前面和后面最近的一个 $j$ 的位置。
然后我们查询直接暴力枚举 $x,y$，定位出区间内最左和最右的 $x$ 的位置，然后用 $app$ 的前缀和数组即可计算出答案，可能需要一些简单分类讨论。时间复杂度为 $O(n|\Sigma|+m|\Sigma|^2)$。
## Day 5
> **T1** 给定一个数 $n$，你每次可以乘上一个只含 $1,4,7$ 的数。你需要使得操作若干次后末尾的连续 $0$ 最多，你需要输出操作后最小的 $n$，$n\leq 10^9$。
容易发现只有 $\times 4$ 是有意义的，我们一直 $\times 4$ 直到末尾第一个非 $0$ 位不是 $5$ 即可。
> **T2** 给定 $n$ 个物品，每个物品有颜色 $a_i$ 和大小 $b_i$，从中选若干个物品使得不同颜色数 $\geq m$，求所有方案的物品大小之和的和。$n,m\leq 40$。
哈哈，这题数据范围大诈骗。
首先我们考虑暴力就是枚举每个物品选或者不选然后判断即可。我们发现数据范围很小，考虑对颜色进行 meet in middle，令 $mid=\max(a_i)/2$，对前 $mid$ 和后 $mid$ 种颜色直接暴力算出选 $k$ 种不同颜色盒子的方案的答案之和以及方案数，然后枚举分别选了多少种合并一下即可，时间复杂度为 $O(2^{\frac{\max(a_i)}2})$。
但其实我们可以直接背包，对每种颜色分别考虑选或者不选统计答案和方案数即可，$O(nm)$。
## Day 6
> **T1** 给定 $n,k,p$，求有多少个长度为 $n$ 的排列 $p$ 经过 $2^k$ 次复合后可以得到 $1\cdots n$。
>
> $n,k\leq 10^5,p\leq10^9$，不保证 $p$ 是质数。
考虑一个经典转化，把排列看成是 $i$ 和 $p_i$ 之间连边，那么问题就转化为求 $n$ 个点，构成任意多个 $2^t,t\in[0,k]$ 大小的环的方案数，点有标号。
为了不重不漏，我们假设新加入的环必定包含 $1$ 这个点，对应的方案下标加个偏移量即可，设 $dp_i$ 表示 $i$ 个点的答案，我们直接枚举新加入的环的大小，考虑第一个点必然为 $1$，第二个点有 $i-1$ 种选择...... 以此类推，即
$$
dp_i=\sum_{0\leq t\leq k,2^t\leq n}(i-1)\cdots(i-2^t+1)dp_{i-2^t}
$$
直接做是 $O(n^2)$ 的，我们考虑倍增预处理这个系数，即预处理出 $st_{i,t}=(i-1)\cdots(i-2^t+1)$ 即可，时间复杂度为 $O(n\log n)$。
> **T2** 给定循环节为 $n$ 的序列 $a$ 的前 $n$ 项以及循环节为 $m$ 的序列 $b$ 的前 $m$ 项，求 $i\in [1,k]$ 中满足 $a_i<b_i$ 的位置个数。
$n,m\leq 10^5,k\leq 10^{12}$。
考虑对于数组 $b$ 中的某个元素 $b_j$，有哪些 $a_i$ 会和它匹配。即 $i+km\equiv j\pmod n$ 有解。
$$
i+km\equiv j\pmod n
$$
$$
i+k_1m=j+k_2n
$$
$$
k_1m-k_2n=j-i
$$
设 $d=\gcd(n,m)$，那么根据裴蜀定理，这个方程有解的条件是 $j-i\equiv 0\pmod {d}$，那么我们考虑对下标按 $i\bmod d,j\bmod d$ 的值分类，那么问题转化为 $\gcd = 1$ 的问题。
我们对把数组重排，即令 $c_i=a_{im\bmod n+1}$，计算完全部都需要比较的情况之后，问题转化为对某个 $b_j$ 计算数组 $c$ 的一个区间 $<b_j$ 的数个数，二位数点即可。$O(n\log n)$。
> **T3** 给定一个无向图，有白边和黑边两种边，求恰好有 $k$ 条白边的最小瓶颈生成树。
>
> $n,m\leq 10^5$。
原题就是要最小化最长边，考虑二分答案。类似某个 wqs 二分经典题（恰好 $k$ 条白边最小生成树），但我们只需要 check 是否有解，所以就分别把白边权设为 $\inf$ 和 $-\inf$ 跑两次最小生成树看看 $k$ 是否在这两个所用白边数量之间即可，时间复杂度为 $O(m\log V\log m)$。
# ZROI AB 组十连测
## Day 1
大毒瘤模拟赛。
开场先看了三个题，感觉 T2 很不可做，T1 感觉还好，直接开始。首先暴力 dp 用 st 表维护是比较简单的，写完之后打了个表发现有决策单调性而且答案关于 k 是凸的（这个性质我不知道咋用 qwq），然后写了个分治 $O(nk\log n)$。然后开 T3，首先看到部分分 $n\leq 18$，考虑状压 dp，暴力找出每个点所在连通块集合，然后随便转移一下即可。
然后 T2 想了好久也不知道怎么快速判断合法，T3 发现链上可以预处理区间，写掉！（写的时候顺便发现状压写挂改了一手）~~然后开始摆烂。~~最后一分没挂，$95$，rk 17。感觉打比较好的就是写了链的性质和发现了决策单调性。
接下来是补题。
首先就是 T3，考虑计算每个节点子树内的贡献。我们可以发现真正有用的信息只有最上面一个可以扩展出去的点 $A$ 以及最下面一个需要被扩展到的点 $B$，而且我们会发现这两个信息不会同时存在。因为如果存在其他子树内一个点 $A'$ 可以扩展到子树内最深一个需要被扩展到的点，那 $A$ 直接就被 $A'$ 代替了。所以我们可以设 $f[u][A]$，$g[u][B]$ 两个状态分别转移，因为第二维能取到的值只有 $O(sz_u)$ 种，用类似树上背包的转移方式即可做到 $O(n^2)$。
然后是 T1。我们可以转化问题，转化为需要把序列划分为 $k$ 个区间，每个区间内恰好一个位置乘 $1$，一个位置乘 $-1$，其它位置均乘 $0$，求所有区间和最大。考虑一个暴力区间 dp，设 $dp_{l,r,0/1/2,0/1/2,k}$ 表示区间 $[l,r]$ 内，最左侧区间没放/多放了一个 $-1$/多放了一个 $1$（右侧类似），一共放了 $k$ 段的情况下答案最大值。
首先我们发现这个 dp 状态过多，那么可以考虑分治做，设 $dp_{id,0/1/2,0/1/2,k}$ 表示分治区间 $[l,r]$ 编号为 $id$，左右边情况，放了 $k$ 段的最大值。我们可以对最后一维开一个 vector，因为最后一维的和只有 $O(n\log n)$。那么我们考虑如何合并两个区间，我们通过打表发现答案关于 $k$ 是上凸的，于是我们可以使用求上凸包闵可夫斯基和的经典做法（two-pointer）合并两个区间的答案。时间复杂度为 $O(n\log n)$。
- **上凸包闵可夫斯基和**
我们使用凸包上的点 $(i,p_i)$ 中的 $p_i$ 来考虑。如果对 $p$ 数组差分，根据上凸包的性质，差分数组肯定是单调不增的，所以合并这样两个凸包就是对差分数组归并排序一下。直接两个指针扫一下每次取差分值较大的那个加进答案即可，时间复杂度为两个凸包点集大小之和。
最后是大毒瘤 T2，假设水管口对着的边为 $1$，不对着的边为 $0$，那么局面合法当且仅当每条边要么对着两个口，要么一个口都不对着。考虑高级水管实际上就是上下，左右对边分别恰好一个 $0$ 一个 $1$。然后我们对于行和列的限制分别考虑，如果两条边不能全放高级水管那么我们对这两条边中间的格子缩点，如果两个行列限制有交并且这个位置可以放低级水管，那么就连上一条边。问题转化为求最小边覆盖，转化为网络流问题即可。（感觉思路很妙，细节很多）
## Day 2
三个原题，我一个都不会。
开场发现，T1 看上去很简单。然后 T2 看上去博弈论，不会！T3 感觉有点像高斯消元，但数据范围怎么 $10^5$，不会！
T1 首先考虑莫队，发现我只会在一边加，两边加不会，但我是写完了才发现这个问题，此时已经过去 $1$ h，然后发现我貌似根本不会这个题，三位数点？？？分块？？然后最后只能打了个暴力跑路。
然后看看 T2，发现样例解释写挂了。然后尝试找规律，对着大样例发现好像和普通 nim 游戏类似，随机数据到第 30 个代价就不是直接加了，考虑维护最大权线性基。发现我根本不会这东西......而且感觉也没道理啊，然后毛估估写完发现过不了大样例，最后又是交了个暴力上去。
T3 开头直接弃疗，交暴力，最后 15 分钟发现好像第一个位置确定之后后面的位置都确定了，开始写写写，发现看错数据范围了 $\forall i\in [2,n],p_i<i,p_1\neq 1$，前面的限制不包含 1。
补题。
T1 是维护区间子区间信息的经典套路，可以离线之后扫描线扫右端点，维护左端点对应区间的答案，我们可以把询问差分为扫描线到 $x$ 时区间 $[l,r]$ 的历史信息和。历史和可以直接打标记维护，因为只有 ${\rm Xor} \ 1$ 的操作（相当于维护 $1$ 和 $0$ 的和，修改时 swap 一下值和标记就行），历史和就给 $1$ 打上一个加上区间内 $1$ 的个数的标记就行。强制在线可以主席树。
T2 原题好像是 ccpc 金牌题。~~但怎么感觉题解就是两个板子拼起来。~~ 首先有一个 nim 游戏的拓展。
> 给定若干堆石子，每次可以取至多 $k$ 堆中的任意多个，但不能不取，问最优策略下，先手是否存在必胜策略。
**结论**：先手必败当且仅当把所有石子写成二进制数后，每一位上 $1$ 的个数都是 $(k+1)$ 的倍数。
因为题目保证了一种石子有两堆，所以可以直接消元，于是我们要维护的就是最大权线性无关子集，直接用线性基维护，如果某位上已经有值那就判断一下权是否更优，如果更优就交换，然后继续像正常线性基插入一样做，维护的时候计算每个位的时候 $\mod 3$ 即可，直接做是 $O(n\log ^2V)$ 的，可以压成四进制位做到 $O(n\log V)$。
## Day 3
> 给定 $n$ 求长度为 $n$ 的括号序列最长合法括号子序列长度为 $k$ 的方案数，对 $k\in[0,n]$ 输出答案。$n\leq 10^6$。
首先有一个暴力 dp（和正解没啥关系）
$dp_{i,j,k}$ 表示前 $i$ 个位置，最长合法括号子序列为 $j$，左括号 - 右括号为 $k$。
$dp_{i,j,k}=dp_{i-1.j,k-1}$（放左括号）
$dp_{i,j,k}=dp_{i-1,j-1,k+1}$ （放右括号，且还有可匹配的左括号）
$dp_{i,j,0}=dp_{i-1,j,0}$ （放右括号，且没有可匹配的左括号）
然后我们发现如果把左括号看成 $1$，右括号看成 $-1$，前缀和数组为 $s_i$，那么最长合法括号子序列的长度为 $k=n+2\cdot \min\{s_i\}-s_n$。
我们把括号序列画成一条折线，然后发现第一次在 $x$ 轴下方的下降线段是没有贡献的（因为右括号一定找不到能匹配的左括号），那么对应的后面左括号会比折线上多出来没有匹配上这些右括号的个数，我们把这些拿来和后面在 $x$ 轴下方的部分匹配，那么只有 $s_i$ 小于前缀 $\min$ 处会继续多出右括号，那就相当于产生 $\min\{s_i\}$ 个不会匹配上的右括号。
那么我们少算的就只差最后多出来的左括号。假设完全匹配，最后多出来的左括号个数就是 $s_n$，但现在多出来了 $\min\{s_i\}$ 个没匹配上的左括号，所以我们要加上这个（因为 $\min\{s_i\}\leq 0$ 所以其实是 $-\min\{s_i\}$，上面同理），所以 $k=n+\min\{s_i\}-(s_n-\min\{s_i\})=n+2\cdot \min\{s_i\}-s_n$。
那么考虑我们现在要算出某个确定的 $k$ 的答案。首先我们根据 $\min\{s_i\}\leq 0,s_n-\min\{s_i\}\geq 0$ 可以算出 $k-n\leq s_n\leq n-k$，因为 $k$ 肯定是偶数，并且 $n$ 和 $s_n$ 的奇偶性肯定相同（因为只有 $+1,-1$），所以 $s_n$ 有 $n-k+1$ 种取值。那么问题转化为求网格图上从 $(0,0)$ 走到 $(n,s_n)$ 且恰好碰到 $y=\min\{s_i\}$ 并且不碰到 $y=\min\{s_i\}-1$ 这条直线的方案数，然后差分一下，类似卡特兰数的推导方式（折线公式）可以推出答案即为
$$
(n-k+1)\left(\binom{n}{\frac{k}{2}}-\binom{n}{\frac{k}{2}-1}\right)
$$
> **折线公式**：从 $(0,0)$ 走到 $(n,s_n)$，不碰到 $y=p$ 直线的方案数，首先直接走的方案数是 $\binom{n}{\frac{n+s_n}{2}}$，碰到的方案数可以对称成走到 $(n,2p-s_n)$ 的方案数，即 $\binom{n}{\frac{n+2p-s_n}{2}}$，两个相减即可。
## Day 4
自闭的一天，也是模拟赛完全开摆的起点。
T1，首先时光倒流转化为加边维护变双连通块，写了 1h 后又想了 30min 发现不懂怎么合并两棵树，感觉就算想到了也写不完，开摆。
T2，感觉看完提示后有点感觉，盲猜模 $2$ 意义下的既约多项式不会很多，问了 EI 后发现我在说什么，可以任意多，开摆。
T3，不经过对角线！！卡特兰数！！怎么 $n=2$ 只有十分，还没有样例测，打完开摆，发现根本不懂怎么扩展到更高维的情况。
补题未完待续。
## Day 5
$-130$，警钟敲烂。
T1 发现这不就是我刚看完的矩阵乘上自己的转置吗，然后根号分治一下，然后一直想 $\geq \sqrt L$ 咋做，一直往矩阵那想，然后没想出来（应该换种思路的）。
T2 是计数，感觉是个容斥，但不知道咋 dp，写了个爆搜。
T3 感觉是经典题，但为啥我只会 $O(nk)$，还没有这个部分分，敲完爆搜开摆。
然后成功 $-130$。
## Day6
阳间场，但我又在摆qwq。
T1 一眼想到裴蜀定理把问题转化为求序列中的数两两 $\gcd=k$ 的约数且加起来 $\geq k$，写完暴力之后开始反演，推完式子才发现没有处理 $\geq k$ 的情况，加上这个条件后发现我也不会了。（其实应该考虑反演的本质的，或者先弱化掉第一个条件，然后最后再容斥算的）
T2 感觉上就是分治，但好像按最值分治复杂度是错的，然后写了一个小常数暴力。
T3 不在一个子树内的情况直接树剖，当时想着另一种情况也差不多就没管开写，写完才发现这个问题，后来第二种情况暴力写挂，喜提 0 分。
## Day7
鱼大毒瘤场。
T2，T3 感觉十分不可做，T1 是构造 nb 题，看部分分感觉可以手推出一些，把直角和暴力写完就没了一个多小时了，然后开摆。
## Day8
鱼大毒瘤场。
好像阳间了一点，第一题博弈论，想到这个我只会 nim 游戏和 SG 函数，没想到题目就是一个有向图游戏，求每个游戏的 SG 函数即可，暴力 40 打掉，然后更大的情况感觉是分类讨论，很不懂这些qwq。
第二题本来打算手算出 $\leq 6$ 的情况，然后推到 $n=m=3$ 发现就不懂了。
第三题交互直接暴力只有两分，毛估估算了一下发现我写的暴力过不了，然后没写了。（赛后看到 myt 好像就写了我那个，然后 TLE 了）
## Day9
NOI Day1 难度。
只写了暴力。（为啥暴力分给这么少哦）
# ZROI CSP 七连测
## Day1
## Day2
# ZROI NOIP 十联测
## Day1
## Day2