xixike

# Description Luogu传送门 # Solution 首先看到 n≤20n \leq 20n≤20，可以想到状压，然后题目要求我们求从全部为 1 的状态到全部为 0 状态的最短时间，不难想到使用最短路或者 dp\text{dp}dp 来解决。 对于这道题，我们使用最短路。 把每一种状态当作一个节点，每次处理一个节点时枚举所有的补丁，判断该补丁能否使用，如果可以，直接计算出使用该补丁之后的状态，即为当前点能到达的下一个点。 那么这时还有两个问题： 如何判断当前点能否使用。 把每个补丁必须有的 bug\text{bug}bug 存到 b1b_1b1​ 里，必须没有的...

# Descirption Luogu传送门 # Solution 题目要求我们求出符合某种条件的方案数，不难想到使用容斥或者二项式反演。 考虑二项式反演的套路，设至少 blablabla 的方案数 g(i,j,k)g(i, j, k)g(i,j,k)，恰好 blablabla 的方案数 f(i,j,k)f(i, j, k)f(i,j,k)，然后通过一定方法来计算。 回到这道题目上，我们设： 至少有 iii 行 jjj 列没有染色，且有 kkk 种颜色没有使用的方案数为 g(i,j,k)g(i, j, k)g(i,j,k)。 恰好有 iii 行 jjj 列没有染色，且有 kkk...

# 二项式系数 # 定义 符号：(nk)\dbinom{n}{k}(kn​)，读作：“nnn 选 kkk”。 组合意义：从有 nnn 个元素的集合中选出 kkk 个元素作为子集的方案数。 我们称 nnn 是 上指标，称 kkk 是下指标。 (nk)={n(n−1)⋯(n−k+1)k(k−1)⋯1=nk‾k!,k≥0;0,k<0.\dbinom{n}{k}=\left\{ \begin{aligned} & \frac {n(n - 1)\cdots(n - k + 1)}{k(k - 1)\cdots1} = \frac...

最大流，数数 + 二项式反演，分块 + manacher

# Visits S 手玩一遍样例，找找最优决策，不难发现一个环中最优情况瞎只有一个点不能选。 并且题目给出的关系是一个基环树森林。 所以先求一下总和， 然后 Tarjan\text{Tarjan}Tarjan 找每一个环上的最小值，用总和减去即可。 另外要判一下环的大小大于等于 2 时才能减（一个点时显然是可以加上的）。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include...

树的重心 + 二分，后缀自动机 + LCT + 树状数组，搜索

# Description Luogu传送门 # Solution 一直以为这是道数学题，结果是 dp\text{dp}dp…… 观察题目给的式子，不难发现，这就是个长为 ai+aja_i + a_jai​+aj​，宽为 bi+bjb_i + b_jbi​+bj​ 的矩阵，让你求从左下角走到右上角的方案数。 转移方程也非常简单： dpi,j=dpi−1,j+dpi,j−1dp_{i, j} = dp_{i - 1, j} + dp_{i, j - 1} dpi,j​=dpi−1,j​+dpi,j−1​ 但是转移完之后我们还是要 O(n2)O(n^2)O(n2)...

平衡树（线段树 / 树状数组二分），AC 自动机 + zkw 线段树，状压 dp

说是游记其实就是在在机房里考的啦。 全程摸鱼警告 10:55 的时候就开始新建文件夹了，58分的时候发现没登录，赶紧登录了一波。 11:00 准时开题，发现这题面怎么都巨大长啊，看到了叫做 “THUPC” （后来改成“画图”了）的题目，感觉可能是签到题，点进去看了一眼，发现是个毒瘤模拟，让你判断输入的线段是否构成 THUPC 字样，果断放弃。 这时机房里几个 dalao 已经开始切 K 了，是模拟题，输入一个字符矩阵让你求正方体个数头顶标数法应用，感觉也是非常的毒瘤。 开考 6 分钟的时候首 A 诞生了，切的是 A 题，于是滚去看 A。听到旁边 qq 已经搜到 A...

# Description Luogu传送门 # Solution （感谢 @Acestar 提供的思路） 初始情况下，每头奶牛匹配一个礼物，所以我们把奶牛和礼物当作一个点。 如果奶牛 iii 非常不要脸的去抢奶牛 jjj 的礼物（iii 向 jjj 连单向边），而且不幸的是奶牛 jjj 还打不过奶牛 iii，那么 jjj 就被迫去抢别人的礼物 qwq，所以 jjj 就必须向它能抢到的别的奶牛连边。 因此我们这个图就建出来了，找一组解只需要跑一遍传递闭包即可，顺便拿个 bitset\text{bitset}bitset 优化一下，时间复杂度 O(n3ω)O(\frac...