三轮省集

Day 1

模拟赛

A

Qoj4907 djq 学生物

容易想到一张图, 然后邻接矩阵的幂, 然后要求 $\sum_i M^i=\dfrac{1}{1-M}$.

然后容易想到换成”排列幂级数”多项式, 转移多项式 $F(x)=\sum_p c_p x^p$, $p$ 为一个排列, $x^p\cdot x^q=x^{p\circ q}$, 要求 $\sum_i F(x)^i=\dfrac{1}{1-F}$, 就是要给这个东西求逆. 容易发现若答案存在逆一定存在.

因为每一位分别做, 容易想到类似FWT的形式, 回想 “FWT本质” 类似物, 比如试着找矩阵 $C$ 使得 $C_{i, j}$ 为 $i\to j$ 的贡献, 然后变换完之后点积就对应卷积. 但是这里不适用(找不到合法的 $C$). $p\circ q$ 不交换本身性质不好, 拆成三个矩阵也是未知数少于方程数的.

然后感觉这里见识到更本质的FWT, 我们实际上是在找可逆线性变换 $T$ 使得 $T(a)\cdot T(b)=T(a\times b)$, $T$ 把数变换到矩阵也是合法的. 用矩阵强行模拟 $S_3$ 的结构, 构造出

$$
M_{123}=(\begin{Bmatrix}
1 & 0\0 & 1 \
\end{Bmatrix}, 1, 1)\
M_{132}=(\begin{Bmatrix}
1 & -1\0 & -1 \
\end{Bmatrix}, 1, -1)\
M_{213}=(\begin{Bmatrix}
0 & 1\1 & 0 \
\end{Bmatrix}, 1, -1)\
M_{231}=(\begin{Bmatrix}
-1 & 1\-1 & 0 \
\end{Bmatrix}, 1, 1)\
M_{312}=(\begin{Bmatrix}
0 & -1\1 & -1 \
\end{Bmatrix}, 1, 1)\
M_{321}=(\begin{Bmatrix}
-1 & 0\-1 & 1 \
\end{Bmatrix}, 1, -1)
$$

三个元素间做乘法是点乘, 矩阵做乘法就是矩阵乘.

你会好奇为什么要构造这个大小的而不直接用 $3\times 3$ 的置换矩阵, 但先别管

然后这个构造方式的话, 后面两维写全 $1$ 和 排列奇偶性显然是对的, 第一列可以考虑几何构造, 选择平面上三个点 $(0, 0), (0, 1), (1, 0)$ 分别代表 $1, 2, 3$, 找到一个矩阵可以交换两个点而第三个点位置不变即可.

构造出矩阵之后我们现在会做 $n=1$ 的情况, 就对于原序列是 $\sum_i c_i x^{p}$, $i\in [0, 5]$ 是 $p$ 的字典序编号(题目中的), 则设 $M=\sum_i c_iM_i$, 把 $M$ 求逆, 再变换回来(容易发现上面的线性变换满秩)即可.

现在要做高维的情况, 考虑矩阵的直积, 即 $A\otimes B=(a_{i, j}B){i, j}$(把 $A$ 的每个位置乘上 $B$ 这个矩阵, 得到一个新的巨大矩阵). 它有性质 $(A\otimes B)\times (C\otimes D)=(A\times C)\otimes (B\times D)$($\times$ 表示矩阵乘法). 所以多维用直积变换, 若 $a$ 一个位置表示成 $a{p_1, p_2, p_3\ldots p_k}$, 那么我们实际上算的是 $\sum\limits_{p_1\ldots p_k} a_ {\Large \otimes}i M{p_i}$.

然后变换完了你得到一个矩阵套矩阵的东西, 我们不看点积那层关系(认为形如 $(A, B, C)$ 的是三个不同的矩阵)你要对这个东西求逆, 求逆复杂度是 $\sum_i \binom{n}{i}2^{n-i}2^{3i}=10^n$

然后就做完了.

你会发现我们平时写的FWT都可以认为是这种矩阵直积的形式, 只不过底层是 $1\times 1$ 的矩阵.

B

Qoj8359 travel

看南外题解吧:

C

CF947I

todo

课

CF1924F Anti-Proxy Attendance

把题目转化为有 $n$ 个vector, 每次给定一个区间, 交互库会把区间内部pushback $0$, 外部pushback $1$, 或者正好相反($1$ 表示答案在这一侧), 那么如果出现连续 $3$ 个 $1$ 或连续 $3$ 个 $0$ 则这个位置必然不是答案, 可以被排除.

则只用考虑每个vector最后两个位置, 如果是00或11赋权值 $1$, 若为01或10赋权值 $\phi$, 若已经排除了赋权值 $0$, 则设上一次权值和为 $A$, 下一次交互库选择区间内部pushback $1$ 的权值为 $B_1$, 区间内部pushback $0$ 的权值为 $B_0$, 发现必然有 $\phi A=B_0+B_1$. 最后 $A=O(1)$, 一开始 $A=O(n)$, 所以交互库希望尽量大, 会选择 $\max (B_0, B_1)$ 给你, 则每次 $A$ 最多减小到 $\dfrac{\phi}{2}A$, 操作次数有下限 $O(\log_{\dfrac{2}{\phi}} n)$

考虑所有前缀, 问空前缀和问整个序列 $B_0, B_1$ 必然恰好交换, 则必然存在某处 $\vert B_0-B_1\vert$ 很小, 在这里问显然就是最优的. 就能做到 $O(\log_{\dfrac{2}{\phi}}n)$ 的次数了.

uoj883

大贪心讨论

显然我们要走所有黑点虚树的一个欧拉序, 考虑dp, 容易发现只要记录 $f_{u, 0/1, 0/1}$ 表示 遍历 $u$ 的子树, 从 $u$ / $u$ 的儿子开始, $u$ / $u$ 的儿子结束 的最小代价就是一个子问题, 考虑转移.

对于两个子树之间的问题, 只有 $(0, 0)\to (0, 0)$ 花费 $0$, 其他花费 $1$. 由此, 每个子树的选择应该是先游先取 $f$ 小的, 再取 $0$ 多的状态转移.

对于 $u$ 和自己第一个儿子, 只有 $u$ 是 $(1, x)$, $v$ 是 $(0, y)$ 花费 $0$, 其他花费 $1$, 同理对最后一个儿子只有 $u, v$ 分别是 $(x, 1), (y, 0)$ 花费 $0$.

于是显然有

• 对 $f_{u, 0, 0}$, 儿子排列是 $u\to (1, 0)? \to (0, 0)\ldots \to (0, 1)(1, 0)\ldots\to (1, 1)\ldots \to u$, $?$ 表示不一定有.
• 对 $f_{u, 1, 0}$, 儿子排列 $(0, 0)\ldots \to (0, 1)(1, 0)\ldots \to (1, 1)\ldots \to u$. 对 $f_{u, 1, 0}$ 同理.
• 对 $f_{u, 1, 1}$, 注意此时一个取 $(1, 1)$ 的点变成取 $(0, 0)$ 可能加 $2$, 所以可能把所有子节点变成 $(0, 0)$, 且此时可能遍历不到 $u$ 需要加 $1$ 次操作. 而一般情况只要做 $(0, 0)\ldots \to (0, 1)(1, 0)\ldots \to (1, 1)\ldots\to (1, 0) \to u$ 即可.

uoj884

显然的暴力是 $f_{i, j}$ 表示走到这个格子的方案数. $f_{i, j}=f_{i-1, j-1}+f_{i, j-1}$, 有障碍的格子为 $0$.

考虑GF优化这个东西, 设 $F_i(x)=\sum_j f_{i, j}x^j$, 如果没有障碍则 $F_i(x)=\dfrac{F_{i-1}(x)}{(1-x)}$, 存在一个障碍就要把那个位置设为 $-\sum_{j<p} f_{i, j}$ 来抵消前面的贡献, 于是只要支持快速查单项式系数, 加单项式, 除 $1-x$.

但还是很慢, 时间分块重构, 每 $B$ 个重构, 于是维护 $\dfrac{F_i}{(1-x)^k}$ 的形式, 但这样底下的项数是 $O(n)$ 的, 不如维护 $G_i(1-x)^k$ 的形式, 在每块开始时设 $k=B$, 每次减 $1$, 这样查可以 $O(B)$, 修改时再维护修改的项 $\dfrac{H(x)}{x^l}$, 则因为 $H$ 项数也是 $O(B)$ 的就好做了. 然后只要每 $B$ 次进行重构, 也就是计算 $\dfrac{F(x)}{(1-x)^B}$, 注意到 $(1-x)^{509}\bmod 509 = 1-x^{509}$, 于是取 $B=509$, 除 $1-x^{509}$ 可以线性.

总复杂度是 $nB+\dfrac{n^2}{B}\approx n\sqrt n$

Day2

模拟赛

A

P3993 [BJOI2017] 同构

考虑区分的点在反图上点也是区分的, 于是相当于加最少的边让所有点区分, 然后你发现 $n$ 比较大的时候一个树肯定就弄完了, 然后你发现过不了样例, 可能是多个连通块省边, 那如果这个连通块 $m\ge n$ 就不能省一条边没有意义, 于是都是树, 且每个连通块互不同构, 最大化连通块数量. 于是显然从小到大选, 只要求每个大小的, 不自同构的无根树数量.

考虑一棵树不自同构的充要条件是, 不存在一条边/点, 使得删去它后剩下的若干连通块中有两个相同. 发现一个子树和一个子树补的不会做, 发现选重心为根就做完了,

Qoj4898. 基础图论练习题

考虑直接若干个等差数列合并在一起就是公差取gcd, 但限定长度之后不能直接这样做.

容易证明 ${d_i\vert 2d_i\le n}$ 可以合并成一个gcd, 可以考虑弱周期引理, 考场上没有意识到它和字符串的相关性, 那你就直接注意到任意时刻位置 $x$ 必然要么可以走集合中的至少一个, 否则终点一定在 $[1, n]$ 外, 即可.

那你现在应该想到弱周期引理啊, 你会意识到 $d$ 相当于给了一个周期, $n-d$ 就是一个border, 那么容易得到border/d构成 $\log n$ 段值域不交的等差数列, 于是周期, 那么有用的 $d$ 只有 $\log n$ 个.

考虑现在要能做到给你一个 $d$ 的集合 $S$ 找到等差数列, 这里不像普通字符串那样简单, 因为 $d$ 的集合是不完全的.

别字符串了, 类比TopCoder 12832 Huge Graph可以得到一个类似辗转相减gcd的方式: 考虑拿出最小的 $d_1$, 那么若当前节点编号 $x>d_1$, 你一定可以走 $x\to x-d_1\to x-d_i$, 于是用 $d_i-d_1$ 替换掉 $d_1$, 而对 $x\le d_1$ 不能进行下面的变换, 单向后连一个 $d_1$, 容易发现变换前后图等价. 此时前 $d_1$ 个点不对连通性产生影响(只有一条 $+d_1$ 连到后面), 可以删掉, 可以递归下去. 把不断相减变成取模(辗转相除), 容易发现只会递归log次, 复杂度是 $\vert S\vert\log n$

现在每个 $d$ 有不同的边权, 需要从小到大加入 $O(n)$ 次, 注意到这个过程中只有曾作为最小值的 $d$ 是有用的, 可以只保留它们做, 复杂度就 $a\log^2 n$ 了.

但还有一些散边, 考虑我们希望找到一个点在这个连通块中最小的代表元, 发现这个可以在上面的递归中同步进行, 找一个点复杂度是 $\log n$. 于是只要找到所有散边端点对应代表元, 考虑先算出所有整边($a$ 条)的答案, 那么散边的贡献只取决于散边代表元 在 加入整边的过程中的Kruskal重构树 上的虚树(其实是代表了它们每个点之间的整边边权最小值), 抽出这棵虚树之后跑Kru即可.

考虑怎么建这棵虚树, 显然对两个点什么时候连通可以二分, 那么整体二分, $f(l, r, S)$ 表示加入第 $l$ 组整边前 $S$ 中点两两不连通, 加入 $r$ 后两两连通, 求解出其中的点何时连通. 那么算出 $[1, mid]$ 的整边加入后的连通块是 $S_1\ldots S_k$, 递归计算 $f(l, mid, S_1)\ldots f(l, mid, S_k)$, 每个集合拿出一个元素组成 $T$ 调用 $f(mid+1, r, T)$ 即可.

复杂度是 $(a+b)\log^2 n$

课

开胃菜

有一个未知 $01$ 序列, 每次可以询问子集中 $1$ 的个数, 要求 $O(\dfrac{n}{\log n})$ 的次数问出序列.

分治, 考虑若已经能构造 $q$ 次解决长 $n$ 的问题, 拓展到 $2q+1$ 次解决长 $2n+q$ 的问题, 则把 $2n+q$ 分成 $n, n, q$ 三段, 设第一段的 $q$ 个询问是 $S_1\ldots S_1$, 第二段是 $T_1\ldots T_q$, 那么我们把新的询问分成 $q$ 个 $pair$, 每个pair询问 $x=S_i+T_i$ 和 $y=S_i-T_i+a_{2n+i}$(用多的一次询问 $[n+1, 2n]$, 通过询问补集算 $-T_i$), 则容易通过 $x+y$ 的奇偶性判断 $a_{2n+i}$, 然后求 $S$ 和 $T$ 是简单的, 分析一下就是 $\dfrac{n}{\log n}$.

P6837 [IOI2020] 数蘑菇

luogu题解写的很清楚

重点在于充分利用奇偶之类的信息.

P8531 [Ynoi2003] 戌亥彗星

先考虑一次询问怎么做.

考虑处理限制, 容易发现第二/三个限制有单调性, 第一个没有.

对于第二个限制考虑从小到大扫右端点, lct维护最大编号生成树, 则左端点是编号上的一个区间 $[l_{1, i}, r_{1, i}]$, 用两个lct双指针, 一个一直删直到变成树求出 $r$, 一个维护不考虑 $r$ 这条边一直删直到变成树求出 $l$.

对第三个限制我们在上面的过程可以知道那条环上的非树边, 维护环点度数大于等于 $2$ 的数量和非环点大于等于 $2$ 的数量即可找到 $[l_{2, i}, r_{2, i}]$, 取个交, 记为 $[L_i, R_i]$

对第一个限制, 由于上面两个已经满足, 只要 $\vert V\vert=\vert E\vert$. 而 $V$ 相当于数颜色.

考虑扫描线扫 $r’$, 则问题相当于维护序列 $a, b, c$, 支持:

• 对 $a$ 区间加
• 对 $b$ 所有 $a_i=0$ 的位置区间加
• 全局 $c_i\gets c_i+b_i$

注意 $a$ 最小值是 $0$, 那么第二个操作其实是最小值加, 考虑怎么设计标记和信息, 这里可以先不考虑 $c$ 的操作, 那么一次对 $a$ 的区间加后面接一次对 $b$ 的加后面这次一定无效, , 同理一次对 $b$ 的加后面接一次对 $a$ 的减前面这次也一定无效, 于是只要维护 $(a, b)$ 表示对 $a$ 区间减, 对 $b$ 加 或 $(b, a)$ 表示先对 $b$ 加再对 $a$ 加两种标记, 容易合并.

复杂度单log.

Uoj463

todo

Day3

模拟赛

A

写了一个假贪心然后似了.

不能观察得到, 较短的串选的一定是原串的一个前缀, 后面全填 $0$, 于是直接枚举前缀, $O(1)$ 维护值即可.

B

ZR 香雪兰

C

考虑连通块就是 $V-E=1$, 设 $f_{i, j}$ 表示前 $i$ 个选 $j$ 个, 扫描线扫 $i$ 线段树维护 $V-E$ dp, 复杂度 $nk\log n$, 卡常可过.

看看怎么做到 $nk$, 首先给根也加一个父亲, 然后把是连通块转化成有且仅有一个点满足 $i$ 在区间内而 $fa_i$ 在区间外, 即对 $[l, r]$ 贡献是 $\sum_{i\in [l, r]} [fa_i<l]+[fa_i>r]$. dp的时候扫 $r$ 的话, 显然后面这部分是单调的, 一个后缀, 前面的相当于加入一个点 $i$ 时对区间 $(fa_i, i]$ 做区间加. 而注意这个是只有区间加没有减的, 我们只要能维护和为 $0/1$ 的区间.

于是维护仅考虑 $[fa_i<l]$ 的部分, 所以满足条件位置的dp值即前缀和(以便查区间和), 而因为我们只有后缀加, 只要开俩栈, 加的时候从一个里取出来放到另一个即可. 复杂度 $nk+n\log n$.

课

GYM102028J

设 $f_i$ 表示只被 $i$ 覆盖的格子数.

若两个矩形无交只要求 $f_i$ 最大的两个.

然后枚举每个格子, 若它恰被两个地毯覆盖给这个对的贡献 $+1$. 然后只要找覆盖一个位置的两个元素, 于是二维前缀和, 查询覆盖每个位置的个数, 编号和, 编号平方和.

cf16_exhibition_final_e

容易发现不会有中转.

若有 $u\to v$ 连边 $(u, v)$, 考虑一个连通集合 $S$, 它一定是一棵树(否则有中转), 则每个点都会变成 $\dfrac{(\sum_i a_i-\sum_{(u, v)\in E} dis(u, v))}{\vert S\vert}$. 证明考虑新加一个叶子归纳.

于是一个点集只要求最小生成树.

于是求出每个集合最后会变成多少, 然后直接跑子集卷积, 复杂度 $n^22^n$

CF1239E

容易发现第一行单增第二行单减.

容易发现下凸, 于是最大值一定在两侧.

于是最小值放在左上角和右下角, 跑背包 $n^3V$ 就过了.

Qoj5874

meet in the middle, 枚举问号少的一半.

如果高位问号少, 你可以几乎确定平方根, 直接把后面全填 $0$ 开方然后往后找 $O(1)$ 个即可, 然后再确定低位是容易的.

如果低位问号少, 注意到若最低位是 $1$, 则高位加 $1$

[ARC160E] Make Biconnected

显然每个叶子都需要至少连一条边, 否则删掉它的父亲一定不合法.

我们希望这也是上界, 则叶子跑匹配, 于是考虑关于子树内叶子个数的带权重心, 那么一定能找到一个匹配使得任意一对点在两个不同的子树, 此时容易发现合法.

若叶子数为奇数, todo

CF1558F Strange Sort

todo

Day4

A

区间加, 区间对固定数取模, 区间和.

容易发现修改容易复合, 变成 $+a$, 取模, $+b$ 的形式, 然后 $+a$ 需要做区间rank, 所以分块. 每块维护 $a, b$ 和所有值的有序数组就做到 $n\sqrt n\log n$.

然后可以把一些log去掉, 比如修改散块重建的时候不sort而使用归并, 离线逐块处理干掉二分, 就可以把log放到根号底下.

然后可以单根号, 不离线逐块二分, 分散层叠掉/cf

B

喵的为啥以前做过的题一点也想不起来!

JOI Open 2019 三级跳

C

容易发现很局部, 想到一个dp是 $f_{i, j, k}$ 表示长 $i$ 的区间, 还有 $j$ 次操作, 第 $k$ 个位置的答案, 然后在 $[l, r]$ 的第一次操作一定是在 $[l, r]$ 的一个中点, 把它分成两部分, 此时枚举 $k$ 表示左边分到 $k$ 个操作, 右边分到 $i-k$ 个操作, 把操作在时间轴上插起来分配系数转移. 转移是卷积可以优化到 $n^2\log n$

然后 $k$ 这一维显然必须杀了, 容易想到 $f_{l, r, i}$ 表示 $l, r$ 这个区间剩 $i$ 次操作, 转移还是一样分配系数, 然而把复杂度算错了, 注意到复杂度是 $n\log^3 n$. (而不是 $n^2\log n$)

再优化就搞成单侧递归, 显然长度为奇数的区间只要递归到一侧再把答案复制到另一边, 复杂度就是 $n\log n$ 了.

尝试不要ntt, 概率转方案数, 时间轴上分配操作的标号考虑EGF, 则 $F_{l, r}(x)=\sum_i \dfrac{x^i}{i! }f_{l, r, i}$, 有
$$
mid=\lfloor \frac{l+r}{2} \rfloor\
F_{l, r}(x)=
\begin{cases}
2n\int F_{l, mid-1}(x)(1+x)^{r-(mid+1)+1}+1, 2\nmid n\
n\int F_{l, mid-1}(x)(1+x)^{r-(mid+1)+1}+\int F_{l, mid}(x)(1+x)^{r-(mid+2)+1}+1, 2\mid n
\end{cases}
$$

课

loj2159. 「POI2011 R1」收缩点 Plot

显然先二分, 但判定是最小圆覆盖, 不能动态加点, 可以 $O(k)$ 解决规模 $k$ 的问题.

此时不能二分, 因为最坏每次只加一个点就似了, 我们希望它和下一段长度有关, 于是先倍增尝试, 若以 $i$ 为左端点, $i+2^k$ 可行而 $i+2^{k+1}$ 不可行, 再在这个区间二分, 复杂度就 $n\log n\log V$ 了.

[trick] 二分/倍增并非完全等价, 当有均摊时

Timus 2057

考虑什么时候无解, 全 $a$ 无解, 考虑整个串一定是回文串, 那么拿到 $a$ 后第一个 $b$, 显然回文中心不在这之前, 然后如果回文中心恰好是这个 $b$ 显然无解, 回文中心在这之后, 尝试在第一个 $b$ 后面砍一刀, 剩下的递归下去, 得出最后一种无解可能是 $abababa\ldots$ 这样的.

于是就会判无解.

然后直接dp, 让 $j$ 能转移到 $i$ 当且仅当这个区间有解, 然后处理 $i$ 往前极长的 $abab$ 和 $a$ 区间, 会对奇数/偶数的 $j$ 分别有上界限制, 然后对 $aa\ldots baa\ldots$ 的情况对每个 $i$ 是唯一的, 就做完了.

Qoj7303

考虑模 $2$ 很关键, 考虑给每个集合 $S$ 一个容斥系数 $w(S)$, 使得对连通的集合是 $1$ 而其他的是 $0$, 想到算 $2^{c}\bmod 4$, $c$ 为连通块个数, 于是最后只要算 $(\sum_S 2^{c_S})\bmod 4$, 等价于把连通块染色, 或者说把每个点黑白灰染色, 要求不存在黑白边.

于是扫编号维 $3^13$ 状压dp即可.

[ARC160D] Mahjong

考虑建立操作序列到原序列的双射, 对同一位置的 $k$ 次区间加替换成单点加, 证明考虑把原序列模 $k$ 然后差分应该对应操作序列.

然后数数是GF简单题.

loj3911

显然是最终子序列的一个前缀/后缀拼接, 于是先预处理 $f_{i, j}$ 表示前缀和为 $j$ 的本质不同子序列个数.

这个也得dp, 设 $f_{i, j, k}$ 表示前 $i$ 个字符, 前缀和为 $j$, 长度为 $k$ 的, 每次枚举子序列下一个字符转移.

然后拼接的时候也可能有重复, 钦定求 $s_a+s_b$ 的问题时拼接得到的 $s_a$ 极大的匹配即可, 那么若我们希望下一个匹配的是字符 $c\in {L, R}$, 就要求 $s$ 在最后一个位置之后没有出现过, 然后就做完了.

[AGC056B] Range Argmax

要构造 $x$ 到 $p$ 的双射, 从大到小每次填一个最大值, 删去包含这个最大值的 $x$, 递归到两边, 为了避免数重我们希望这个最大值是满足条件的最前面.

于是dp, 要从 $[l, r]$ 以最大值 $k$ 处分开, 那么对 $[l, k-1]$ 的最大值 $k’$, 有 $k$ 是合法的最左位置当且仅当存在区间同时包含 $k’, k$, 否则容易发现可以让 $k’$ 当这个最大值, 于是 $f_{l, r, k}$ 表示区间 $l, r$ 且最大值位置必须在 $k$ 之后的方案数, 即可dp.

[ARC165E] Random Isolation

考虑转化成可以任意删点, 但只统计连通块大于等于 $k$ 的次数, 然后拆贡献算一个点 $u$ 被删时连通块大于等于 $k$ 的概率.

让连通块以 $u$ 为根, 设这个连通块大小为 $a$, 和这个连通块有边但比它早删的点数为 $b$, 数数.

后面是二维卷积树形dp.

Day5

模拟赛

A

容易想到一个 $n^3$ 的区间dp.

容易想到 $n^3\log n$ 的区间dp.

容易想到把二分干掉改成枚举答案, 每次把一个区间点亮.

但是复杂度都很劣.

不容易想到这个题正解是bitset的 $n^3$. 然后用bitset的find_first/next查找下一个点亮的区间就做完了.

B

容易发现 $b$ 从大到小排序, 得到一个 $n^2$ dp, $f_{i, j}$ 表示前 $i$ 个, 已经选了 $j$ 个的最小值. 有 $f_{i, j}=\min(f_{i-1, j}, f_{i-1, j-1}+a_i+(j-1)\cdot b_i)$ 容易发现固定 $i$ dp值是凸的.

不知道怎么发现, dp的两种转移分别是一个前缀和一个后缀, 于是只要支持区间加等差数列, 区间加, 区间平移 $1$, 平衡树维护即可.

怎么发现呢, zzk表示注意到 $b\le 10$ 的部分分, 此时对每个 $b$ 把 $a$ 排序, 每个 $b$ 要选 $a$ 的一个前缀 $a_{1\ldots k}$, 这个 $k$ 是有决策单调性的, 然后类比过来.

另一个做法是考虑贪心, 容易发现一开始最小的 $a_p$ 一定会被选, 删掉它之后考虑剩余的数贡献变化, 若 $b_i>b_p$ 则 $a_i\gets b_i$, 否则按 $b$ 排序后 $i$ 会插入到 $p$ 前面, $a_i\gets a_i+b_p$. 然后接着选最小的重复即可.

于是只要支持区间加, 区间加等差数列, 区间和, 复杂度 $n\log^2 n$.

C

首先转化到, 每个人让 $[l_i, r_i]$ 加 $1$, 可以翻转为让 $[1, l_i)\cup (r_i, n]$ 加 $1$, 最小化最大值.

然后注意到, 若存在两个不交的区间都被翻转, 他们翻转后覆盖完全包含他们翻转前, 所以一定不优, 于是有存在一个位置被所有翻转的区间包含.

于是一个部分分是二分答案 $mid$, 枚举这个被所有区间包含的位置 $x$, 对 $i<x$, 一个包含 $i$ 的区间翻转后必然不包含 $i$, 于是设 $pre_i$ 表示左端点在 $i$ 及之前的翻转区间个数, 有 $(a_i-pre_i)+(pre_x-pre_i)\le mid$, 可以得到 $pre_i$ 的下界, 枚举 $pre_x$ 可以得到每个 $pre_i$ 的限制.

然后显然左边翻转的区间的 $r$ 越大越好, 于是从 $1$ 到 $x$ 贪心, 到 $i$ 时把所有 $l=i, r\ge x$ 的区间按 $r$ 加入大根堆, 取走并翻转堆顶若干个区间直到满足 $pre_i$ 的限制, 最后判断右边是否合法. $n^3\log^2 n$

设未翻转前每个位置覆盖次数为 $a_i$, 翻转后为 $b_i$

然后注意到, 存在一种最优方案, 使得若所有被翻转区间的交是 $[l, r]$, 有 $[l, r]$ 中 $b$ 的最大值和全局 $b$ 最大值最多差 $1$. 考虑若差 $2$ 以上选择 $[l, ? ]$ 和 $[? , r]$ 翻转不劣.

然后注意到, 存在一种最优方案, 使得设 $t=\argmin_{i\in [l, r]} a_i$, $k=\argmin_i a_i$, $a_k=a_i$. 证明考虑反证, 若 $a_k>a_t$ 有 $k\notin [l, r]$, 一开始有 $a_k\ge a_t+1$, 由上面的性质有 $b_t\ge a_k-1$, 相加并调整就有 $a_k-b_k\ge a_t-b_t$, 矛盾.

于是不需要枚举 $pre_i$, 有 $mid\in {b_t, b_t+1}, b_t=a_t-pre_x$, 于是 $pre_x\in {a_t-mid, a_t-mid+1}$. $n^2\log^2 n$

然后注意到, 我们枚举的 $x$ 可以选择任意 $a_x=\max_{i=1}^n a_i$, 考虑反证, 设 $k\notin [l, r]$ 且 $a_k$ 也是 $a$ 的全局最大值, 于是有 $a_k-b_k\ge a_x-b_x-2$(翻转一个区间有 $2$ 的差), 由上一个注意知道 $a_x=a_k$, 于是 $b_k-b_t\ge 2$ 与第二个注意矛盾.

课

「Dwango Programming Contest 6th」Cookie Distribution

把 $\prod_i c_i$ 拆组合意义, 表示每个人再从自己的cookie中选一个. 然后直接按天dp, 每天分配若干个选中的和若干个没选中的.

「JOISC 2015 Day2」Keys

对每个时间间隔分类讨论, 什么时候一个间隔可以关门:

• 前一个人进入, 后一个人出门, 总是可以.
• 两人都进, 要求后一个人有钥匙
• 两人都出, 要求前一个人有钥匙
• 前一个人出后一个人进要求两人都有钥匙

注意到只有第四种情况和两人都有关, 此时把两个人连边, 一定得到若干条链, 对每条链分别dp最后卷起来, 复杂度 $n^2$.

「JOISC 2020 Day4」治疗计划

好离奇.

设 $f_i$ 表示当前的方案推到某个时刻 $t_i$ 可以治疗 $[1, r_i]$ 的最小代价. 若 $i<j$, 则 $[1, r_i]$ 推到时刻 $j$ 应该是 $[1, r_i-t_j+t_i]$ 这样的感觉.

有了这个之后因为我们不知道转移顺序, 用仿dij的形式每次拿最小的更新即可做到 $n\log n$.

有一种从扫时间到扫序列维的感觉, 所以这个神奇的状态是怎么想到的.

「JOISC 2020 Day3」星座 3

对楼建大根笛卡尔树, 设当前处理最大值为 $a_u$ 的区间, 注意到两边低于 $a_u$ 的星星是子问题, 高于 $a_u$ 的左右子树分别至多剩一个, 我们只关心它的高度, 于是设 $f_{u, i}$ 表示 $a_u$ 为最大值的区间, 保留的最高的星星高度为 $i$ 的答案, 有 $f_{u, i}=\max(f_{l, i}+\max_{k<i} f_{r, k}, f_{r, i}+\max_{k<i} f_{l, k})$, 对 $u$ 这一列的单独转移, 容易发现都可以线段树合并维护.

AGC033D Complexity

考虑设 $f_{l, r, u, d}$ 表示这个矩形的凌乱度, 容易做到 $n$, 而你注意到凌乱度不超过 $\log (n+m)$ 量级, 于是交换一维变成 $f_{l, u, d, v}$ 表示最大的 $r$ 使得凌乱度为 $v$

把它分成横着两个矩形的转移时容易的, 对竖着的需要一个分界点, 注意到这个分界点有单调性可以二分, 或者双指针.

就过了.

PKUSC2024 独立

容易想到一个暴力时 $f_{u, i, j}$ 表示 $u$ 子树内, 可选可不选 $/不选u$ 的最大独立集分别是 $i, j$ 的方案数. 结合小N的独立集容易想到只需要记录 $j-i$ 的差, 有 $f_{u, a}*f_{v, b}\to f_{u, \max(a+b, 0)}$.

转移显然是卷积形式, 但问题是值域很大, 不过容易发现一个方案是否合法只和相对大小关系有关, 一般这种情况可以猜多项式, 归纳容易证明 $f_{u, x}$ 是关于 $x$ 的 $siz_u$ 次多项式, 于是只存前 $siz_u$ 个点值即可.

转移的时候, 要先把点值扩张到 $siz_u+siz_v$, 即我们要支持已知一个多项式的点值快速求另一些点值, 直接写成拉格朗日插值, 形式就是卷积, 扩张完了之后直接卷即可.

Day6

模拟赛

A

原题是P5972 [PA2019] Desant

考虑dp, 则若从前往后dp到第 $i$ 个, 我们只需要记录前 $i-1$ 选了哪些数, 在注意到我们只要记录考虑 $[i+1, n]$ 把整个序列划分成若干个区间, 只要记录每个区间里有几个数, 以这个为状态就过了.

分析考虑你的状态数实际上是求 $\sum_i a_i=n, \max \prod a_i$, 容易发现是 $3^{\dfrac{n}{3}}$ 的.

B

先考虑 $n=2$, 显然每个点值经过一次, 而且这种东西应该考虑分治, 且若从第 $l$ 列走到第 $r$ 列($l<r$)一定只会从左往右走, 于是一个分治区间内的子问题不会走到外面, 此时只要对 $(mid, 1), (mid, 2)$ 处跑单源最短路, 设左边第 $i$ 个点经过 $(mid, x)$ 的距离为 $a_{x, i}$, 右边是 $b_{x, i}$, 那么你想算 $\sum_{i, j} \min(a_{0, i}+a_{1, i}, a_{2, i}+a_{2, j}$

C

经典结论是背包在体积模 $\mathrm{lcm}(w_1\ldots w_n)$ 的每个等价类是凸的, 而显然 $b_i$ 相同的时候模 $b_i$ 的位置是凸的, 跑闵和即可.

另一个做法是凸函数和非凸函数做max+卷积可以决策单调性单log, 所以就不依赖背包数组的凸性了.

课

AGC043C

首先图的笛卡尔积在说什么, 相当于你在三个图上各有一个点, 每次挪动一个位置, 形成的图.

显然我们要贪心, 按 $x+y+z$ 从大到小能选就选, 那么把边从 $(x+y+z)$ 小的连到大的, 则你会选所有没有出边的点, 然后连到他们的点不能选, 再往下可以选, 那么我们看成三张图的组合游戏, 于是答案就是所有先手必败点的权值和. 而因为三个图独立所以直接求SG值做异或就是合并的SG值.

注意到SG值最大是 $\sqrt m$, 暴力做异或卷积即可.

AGC034D

把曼哈顿距离转化成 $4$ 个max, 于是建 $4$ 个点表示四种绝对值是否取负情况, $S$ 向所有代表红球的连边, 红球向 $4$ 个虚点连边, 再向蓝球连边, 再连到 $T$.

可以模拟费用流做到 $n\log n$. 设点是 $S\to R_i\to F_{1\ldots 4}\to B_i \to T$. 就是最短路一定是从 $S\to R_i\to F_{q_1}\to R_{p_1}/B_{p_1} \ldots F_{q_k} \to B_j \to T$, 用堆维护出 $S\to F_i, F_i\to T$, $F_i\to F_j$(只经过一个中转点)的最短路径, 然后跑全源最短路.

loj6703. 小 Q 的序列

考虑一个dp, 直接做自然是 $f_{i, j}$ 表示前 $i$ 个选了 $j$ 个, $f_{i, j}=f_{i-1, j}+f_{i-1, j-1}(a_i+j)$, 然后直接GF, 容易发现这里对 $i$ 列GF是困难的($a_i$ 是点
乘), 于是 $F_i(x)=(1+a_ix+x^2\mathrm{D})F_{i-1}(x)$, 然后不会了.

做一个转换, $k=i-j$, 有 $f_{i, k}=f_{i-1, k-1}+f_{i-1, k+1}(a_i+i-k)$, 就又 $F_i(x)=(x+(a_i+i)-x\mathrm{D})F_{i-1}(x)$.

再做变换 $G_i(x)=e^{-x}F_i(x)$, 有

$$
e^{-x}F_i(x)=x(e^{-x}F_{i-1}(x)+e^{-x}F_{i-1}’(x))+(a_i+i)F_{i-1}(x)\
G_i(x)=xG_{i-1}’(x)+(a_i+i)G_{i-1}(x)\
g_{i, j}=g_{i-1, j}(a_i+i+j)
$$

于是直接有 $g_{n, i}=g_{1, i}\prod_{j=1}^n(a_j+j+i)$, 设多项式 $\prod_{j=1}^n(a_j+j+x)$ 多点求值就做完了.

[think] 感觉关键在于我们的目标是让后面的项和前面尽可能少的项有关, 另外导数的次数是重要的(会有较大影响), 对此多尝试一些变换. 然后就是用 $e^x$ 合并导数和常数部分.

ARC105F

考虑一个连通二分图只有两种染色, 那么对于一种点的染色相当于要求一些边能选一些边不能选, 选出连通图的方案数.

考虑容斥, 对任意一个图, 是一个包含 $1$ 的连通块和剩下一个任意图, 于是设 $f_S$ 表示子集 $S$ 是连通二分图的答案, $g_S$ 表示子集 $S$ 是二分图的答案, 就有 $f_S=g_S-\sum_{T\subsetneq S} 2f_Tg_{S/T}$.

暴力是 $3^n$, 可以半在线子集卷积搞成 $n^22^n$

别容斥了, 不如集合幂级数ln, 对 $g$ 直接ln就好了啊.

loj2398. 「JOISC 2017 Day 3」自然公园

首先怎么确定一条链, 若已知两个链头链尾, 容易找到一个 $i$ 使得保留 $1\ldots i$ 连通而 $1\ldots {i-1}$ 不连通, 此时必有 $i$ 在这条链上, 分成左右两边递归下去, 复杂度是 $n\log n$.

于是现在考虑维护一个与 $0$ 相连的连通块, 每次加入一个与这个连通块有边的点, 那么对连通块dfs序编号, 容易二分到这个点和这个连通块第一个相连的点, 删掉它分裂成多个连通块递归找到其他所有边, 每个连通块只要一次二分.

最后要能找到一个与连通块有边的点, 那么随便找到一个点和连通块中一个点, 用链的方法递归的找即可.

loj3038. 「JOISC 2019 Day3」穿越时空 Bitaro

经典套路先给 $L_i, R_i$ 分别减去 $i$, 就没有走路需要消耗 $1$ 个时间的代价了.

然后考虑线段树, 若序列 $[l, r]$ 中的所有区间有交我们只要记录这个交, 如果无交那么发现进去之后走法是唯一的, 一定是贴着边走, 仍然可以线段树维护(记录进入区间和出口).

复杂度单log.

JOISC 2020 Day1 扫除

首先考虑如果没有加点, 那么发现所有被操作过至少一次的点是一个左上到右下的阶梯, 于是可以用平衡树维护阶梯实现操作.

但现在有加点会破坏阶梯的性质, 考虑线段树分治, 用修改和查询把点的存在时间分到区间上, 每次先处理左区间, 然后把左区间处理完后每个点传到右区间作为起始位置.

复杂度 $n\log^2 n$

P5606 小 K 与毕业旅行

看到这个相邻两项乘积/和不大于啥, 考虑扫值域dp连续段, 把每个数在 $\min(x, m/x)$(在对于 $x>m/x$, $x$ 在这之前必须是孤立点)处插入, 可以做到 $n^2$.

考虑构造更好的转移顺序, 使得可以把点分成两类, A类点和后面每个点都满足条件, B类点和后面每个点都不满足条件, 那么每插入一个B类点已让空位减少 $1$, 每增加一个A类点让空位增加 $1$, 就能线性了.

然后考虑负数, 显然一正一负一定能拼

Day7

模拟赛

A

容易发现一定有一个全集一个空集, 对剩下的四个集合容易想到它们之间的”结构”不多, 于是想到考虑有 $2^{m-2}$ 种不同状态的元素(被哪几个集合包含), 每个状态的元素是一个集合, 若确定这些集合显然就确定了答案, 然后 $2^{2^{m-2}}$ 的枚举每个状态集合是空的的情况去check, 显然若有 $f_i$ 种方案有 $i$ 个非空集, 答案就是 $\binom{m}{2}{n\brace i}f_i$, 就做完了.

B

容易想到匹配, 但匹配之间的限制不能直接做, 考虑网络流, 直接二分答案, 然后每个时间建一层图, 每层图的每个点再拆两个点中间连 $1$ 限制不能相交, 然后跑最大流就行了.

C

容易想到枚举相同的前缀, 于是问题变成了一棵树儿子大于父亲拓扑序, 且限制若干点等于某值, 限制一个点大于某值的方案数, 这个东西就直接从大到小排序二项式系数选一选就行了啊.

课

CCPC Final 2022 E

因为排列设 $(x, y)=(a_u, b_v)$.

不妨设 $u<v$, 那么 $u$ 之后的每次取 $max/min$ 是确定的, 且设 $y$ 在 $u$ 时刻是 $y$, 经过若干次取max/min后最后得到的值一定是 $\min(\max(y, c), d)$ 的形式, 于是 $y$ 一定是 $c, d$ 中的一个. 只要能维护 $y$ 可能取值的最小值或最大值即可, 这个用值域线段树维护 $x=i$ 处时 $y$ 的值, 每次是对一个区间取max/min.

对 $u>v$ 同理, 考虑 $u=v$, 前面一定都取max/min, 后面要满足 $c, d$ 的限制, 也容易判断. .

Shenzhen 23 C

首先注意到 $k$ 可以模 $7$, 只要考虑 $k=1\ldots 6$.

直接dp是 $f_{i, s_1\ldots s_6}$ 表示考虑前 $i$ 个, 前 $i$ 个 $k=1\ldots 6$ 的和模 $7$ 分别是多少, 复杂度 $n7^6$ 看起来就过不了.

注意到模 $4, 5, 6$ 分别相当于模 $-1, -2, -3$, 即若某个 $k\in{4, 5, 6}$ 的奇数位和偶数位带权和分别是 $a, b$, 则要求 $b-a\not\equiv 0\pmod{7}$, 于是对奇数偶数分别跑dp, 然后枚举顶到的上界位置合并, 枚举偶数的一项, 把对 $b$ 的限制 $[a\ne b]$ 容斥成 $1-[a=b]$, 容斥复杂度是 $3^3$, 总复杂度 $n21^3$

ECF2023C Equal Sums

直接dp, 设 $f_{i, j, s}$ 表示一边前 $i$ 个, 一边前 $j$ 个, 差为 $s$.

转移的时候若 $s>0$ 加一个 $y$, $s<0$ 加一个 $x$, 就能保证 $\vert s\vert\le 500$, 优化到 $n^3$.

Day8

模拟赛

A

显然看起来大多数数都直接相同的两两匹配消了, 现在还剩下若干个 $x\bmod 2$. 另外容易发现奇数的话我们已经钦定了大小关系, 后面可以直接确定; 偶数的话, 考虑一定是前面一段上下相同的, 紧接着两个可能不同的, 直接枚举这两个数, 此时大小关系又被确定, 可以按照奇数的填.

然后就是一些细节, 比如答案可能很大需要高精度; 若枚举的两个数正好差 $1$, 可能存在前面把两个 $0$ 或 $9$ 放到后面的情况; 若枚举完前面只剩 $0$ 需要把这些 $0$ 放到后面填.

B

容易想到LGV, 于是只要能算 $1/2 \to n-1/n$ 的方案数.

注意复杂度关于交点个数是没啥问题的, dp即可.

为了减小常数, std是每次加入一条弦, 记录 $f_i$ 表示第 $i$ 条弦最后一个交点处的方案数.

C

首先你可以直接根据排列得到唯一的 $n-1$ 项rand序列, 容易想到设一开始种子的每一位是 $x_0\ldots x_w$, 则可以表示出之后的每一个数为 $\sum_i w_i \sum_{j\in S_i} x_j$ 的形式, 同时, 若 $x\equiv a\pmod p$, $p=q\times 2^t$, 就能列出关于 $x$ 的 $2^t$ 个同余方程, 然后可能不满秩, 但可以枚举自由元的取值, 就做完了.

课

Qoj7901. Basic Substring Structure

考虑修改一个位置 $x$ 时, 若一个后缀的lcp $y<x-1$ 一定没变, 若 $y\ge x$ 一定会变成 $x-1$, 只要考虑 $y=x-1$ 的后缀, 显然每个后缀只在 $x$ 的一个修改方案有 $y=x-1$, 那你就直接枚举所有有至少一个 $y=x-1$ 的修改方案暴力算lcp即可.

P9623 [ICPC2020 Nanjing R] Baby’s First Suffix Array Problem

考虑先假装后缀的顺序就是sa中的顺序, 而不对, 即 $rk_a<rk_b, s_{a\ldots n}>s_{b\ldots n}$ 当且仅当仅考虑这个区间, $b$ 是 $a$ 的前缀, 在这个区间外能比出来, 考虑数这种反例.

那么分成两类, 设询问的是后缀 $s_{k\ldots n}$, 而 $i$ 与其构成反例.

若 $i<k$, 则限制为 $l\le i\lt k\le r, rk_i\lt rk_k, lcp(i, k)\ge r-k$, 容易发现 $lcp(i, k)\ge r-k$ 在 $rk$ 的限制上是一个区间, 所以这是个二维数点.

若 $i>k$, 则限制为 $l\le k<i\le r, rk_i>rk_k, lcp(i, k)\ge r-i$. 考虑这其实是一个 $[k, r]$ 这个区间的border, 于是只要能求区间字符串的border, 这个东西考虑基本子串字典.

另一种做法是对着上面的上DS, 考虑cdq分治, 计算右边的 $i$ 对左边的 $k$ 的贡献, 那么扫出 $pm_i$, $sm_i$ 分别表示左右两边的前缀min, 则限制就是 $pm_i+i\ge r, sm_k+i\ge r, i\le r$ 这样, 这样剩下的问题是个二维数点, 直接做就好了. 复杂度 $n\log^2 n$.

Uoj608. [UR #20]机器蚤分组

首先考虑这是一个最小链覆盖, 那么转化成最长反链覆盖, 而一个反链一定可以调整成长度相同的, 所以答案其实是 某长度的本质不同子串个数 的最大值.

再注意到, 当长度大时主要收区间限制, 当长度小时主要是字符串内容限制, 于是注意不到, 当且仅当长度 $k$ 满足区间内所有长度 $k$ 的所有串互不相同时, 答案由 $k$ 产生. 直觉考虑若这个长度有两个串相等, 那么这两个串的所有对应子串都相等, 容易发现长度更短不优.

于是对全局, 答案既是 $n-\max_{i<j} lcp(s_{i\ldots n}, s_{j\ldots n})$, 放到后缀树上就对应lca, 那么在后缀树上对endpos启发式合并, 每次合并两个集合时, 有贡献的只有合并两个集合归并起来后, 相邻两项来自不同集合的对, 这个显然只有 $n\log n$ 对. 剩下就是简单ds.

Uoj656. [ULR #2]霸占排行榜

对AC自动机跑DAG剖分/kx

考虑肯定是把 $T$ 在AC机上跑一遍, 考虑先求 $dir_{u, i}$ 表示 $u$ 走过 $s_i$ 后的位置, $end_{u, i}$ 表示最大的 $j$ 使得 $u+s_{i, 1\ldots j}$ 还在AC机中. 把匹配 $s$ 的过程分成 $u\to end_{u, i}\to fail_{end_{u, i}}\to dir_{u, i}$, 考虑 $v=fail_{end_{u, i}}$, 若 $dep_v\le dep_{end_{u, i}}-dep_u$, 相当于 $u$ 的信息全丢了, 可以直接从 $1$ 开始匹配, 即 $dir_{u, i}=dir_{1, i}$, 否则可以看出只有 $u$ 长为 $l=dep_v-(dep_{end_{u, i}}-dep_u)$ 的后缀是有用的, 那么在 fail 树 上跳直到这个串的长度(即 $dep$)为 $l$ 即可.

则若已知每个 $end_{u, i}$, 我们可以 $O(nl)$ 求出每个 $dir_{u, i}$, 然后对每个 $s$ 单独做, 我们知道它在每个位置被插入了多少次, 求每个节点被经过次数. 仍然沿用上面的讨论, 把一个节点开始走一个 $s$ 的过程拆成 $u\to end_{u, i}\to dir_{u, i}$, 第一部分是一个祖先链加, 第二个部分可以递归的做, 就可以 $O(nl)$ 的解决这个问题.

于是考虑怎么求 $end_{u, i}$, 树剖, 则对于一条链能走多远是一个lcp的问题, 可以exkmp, 直接跳容易做到 $nl\log n$. 然后把要从一个位置开始跳一个 $s$ 的后缀这个询问挂在轻儿子上. 把所有 $s$ 的后缀排序, 对一个轻子树, 按照字典序从小到大遍历这些后缀则每个点只会经过一次. 于是复杂度就是轻子树大小和 $l\log l$ 了.

总复杂度是 $nl+l\log l+S\log S$, $S=\sum_i \vert s_i\vert$.

重点是, 把AC自动机上匹配分成 $u\to end_u\to dir_u$ 使得可以递归处理, 以及把问题分成重链+轻子树.

Uoj772. [UER #11]企鹅游戏

考虑AC自动机后, 问一个串就是走一遍, 每次到根的链加. 但你当然不用都加, 注意到 $s$ 在 $t$ 中的出现次数是 $L^{4/3}$ 量级, 那么只要记录AC自动机上每个点到根的链上第一个代表 $s$ 中元素的节点, 往上跳, 且不跳相同的节点即可.

CF1909G Pumping Lemma

枚举 $s$ 中 $y$ 和 $z$ 的分界线, 则现在要求 $y^{k-1}$ 有多少个循环节同时是 $x+y$ 的后缀. 而是 $x+y$ 的后缀就是要求 $\vert y\vert \le LCS(s_{1\ldots i}, s_{i+1\ldots i+(n-m)})$, 那么当 $i$ 增加的时候只要比较 $s_{i+1}$ 和 $s_{i+n-m+1}$, 若不相等清空可行集合, 否则可行的 $y$ 集合中增加一个, 而原来集合的每个都是可以的, 于是只要hash检验新增的这个, 就做完了.

[think] 枚举你要枚举的