xixike

# Description Luogu 传送门 # Solution 最大费用最大流 虽然叫方格取数加强版，但是感觉跟方格取数没半毛钱关系（ 我们还是要从当前点向下，向右连边。 观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。 建一条流量为 1，费用为 www 的边。 再建一条流量为 k−1k - 1k−1，费用为 0 的边。 表示第一次走可以获得 www 的收益，但只能走一次，后面再走到当前点时没有收益。 从当前点向下方和右方连一条流量为 kkk，费用为 0...

# 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...

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

# 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)...

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