好文收藏夹

比赛地址 STring 和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。 代码 Minimum Sum 单调栈板子题。 代码 Tree Restoring 首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。 设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下： 若 $d$ 为奇数，则应有 $$ \begin{cases} cnt_i\geq 2,&i\in[\frac{d+1}{2}+1,d]\\ cnt_i=2,&i=\frac{d+1}{2}\\ cnt_i=0,&i\in[1,\frac{d-1}{2}] \end{cases} $$ 若 $d$ 为偶数，则应有 $$ \begin{cases} cnt_i\geq 2,&i\in[\frac{d}{2}+1,d]\\ cnt_i=1,&i=\frac{d}{2}\\ cnt_i=0,&i\in[1,\frac{d}{2}-1] \end{cases} $$ 代码 ~K Perm Counting 转化问题：给出一个 $n\times n$ 网格，其中 $(i,i\pm k)$ 是黑色的，其它格子是白色的，你需要选择 $n$ 个格子使得没有两个格子在同一行或同一列，求不选择黑色格子的方案数。 首先可以考虑容斥。设 $f_i$ 为选了至少 $i$ 个黑色格子的方案数，则答案为 $$ \sum_{i=0}^n(-1)^i(n-i)!f_i $$ 考虑计算 $f_i$。容易发现一件事是每个黑格子最多只会与两个黑格子冲突。我们把每个黑格子向与它冲突的黑格子连边，则会形成若干条链。然后对于每条链 DP。设 $dp_{i,j,0/1}$ 表示前 $i$ 位选了 $j$ 个，当前没选/选的方案数。 这样子最后需要卷积合并；有一种简单的方法是将所有链连成一条，并在交接处特判转移，就不需要卷积合并了。 代码 Sugigma: The Showdown 考虑游戏怎样才可以无限进行。 假如先手能到达某个点 $u$，且第一棵树上存在一条边 $...

比赛地址 Divide a Cuboid 如果有一边长为偶数，答案为 $0$。 否则找到最长的边切开。 代码 Colorful Slimes 枚举循环右移的次数，相当于每种颜色都可以通过选择某个范围内的颜色得到，直接取最小的即可。 代码 AND Grid 我们只需要想办法造两个矩阵使得整个图连通且两个矩阵不交。 通过人类智慧可以想到造成这样 #####. .....# #..... .##### #####. .....# #..... .##### #####. .....# #..... .##### 把左边并上原图作为第一个矩阵，右边并上原图作为第二个矩阵。 代码 Teleporter 显然 $1$ 城市的目的地只能为自己。 那么剩下的只有 $n-1$ 条边了，相当于一棵树，直接 DFS 一遍，子树高 $\geq k$ 时就断掉父边接到 $1$ 城市去。 代码 Salvage Robots 推荐食用 官方题解 。 考虑将所有机器人移动转化一下，变为出口以及边界移动。 设 $dp_{u,l,d,r}$ 表示出口已经到过的范围是以 $(u,l)$ 为左上角、$(d,r)$ 为右下角的矩形，最多能救的机器人数。 转移考虑一下往哪边扩大，容易算出能救的机器人（排除掉已消失的）所在的范围，通过前缀和即可算出数量，然后就可以转移了。 这么讲非常的不清楚，再次推荐使用 官方题解 。 我真的讲不清楚 /kel $dp$ 开 int 开不下，可以开 short 。 代码 Namori 戳这里

UVa Luogu 分析 这个东西应该叫做最大密度子图。 我们要让 $\frac{\sum E}{\sum V}$ 最大，显然是分数规划。 二分答案 $mid$，那么 $$ \frac{\sum E}{\sum V}>mid\Longrightarrow\sum E-mid\sum V>0 $$ 问题变为，选一个点的代价是 $mid$，选一条边的收益是 $1$，选一条边必须选它的两个顶点，求最大收益。 显然是一个最大权闭合子图问题，那么最大收益即为边数减最小割。 这样子就能求出最大值了，然而题目要方案，直接找到所有与源点相连的点输出就好了。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bits/stdc++.h> #define re register using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=2000+10,M=10000+10; const double eps=1e-9; const int inf=0x3f3f3f3f; int n,m,s,t,x[M],y[M]; vector<int> ans; struct edge { int v; double w; int nxt; } e[M<<1]; int head...

Luogu 分析 这是一个线性规划做法。下面举的栗子为样例。 设 $X_i$ 为第 $i$ 类志愿者的招募数，$P_i$ 为第 $i$ 天招募志愿者的数量，那么可以列出一些不等式 $$ \begin{cases} P_1=X_1\geq 2\\ P_2=X_1+X_2\geq 3\\ P_3=X_3\geq 4 \end{cases} $$ 设 $Y_i$ 为第 $i$ 天多招募的数量，那么可以把不等式化为等式 $$ \begin{cases} P_1=X_1-Y_1=2\\ P_2=X_1+X_2-Y_2=3\\ P_3=X_3-Y_3=4 \end{cases} $$ 令 $P_0=0,P_4=0$，上下相邻两项相减得 $$ \begin{cases} P_1-P_0=X_1-Y_1=2\\ P_2-P_1=X_2+Y_1-Y_2=1\\ P_3-P_2=-X_1-X_2+X_3+Y_2-Y_3=1\\ P_4-P_3=-X_3+Y_3=-4 \end{cases} $$ 注意到每个变量恰出现 $2$ 次且系数一正一负。 我们可以把每个等式看做一个点，正数代表流入，负数代表流出，那么等式相当于流量平衡。 因此我们得到了这样的建图方法： 如果 $P_i-P_{i-1}>0$，从源点向 $i$ 连容量为 $P_i-P_{i-1}$、费用为 $0$ 的边，否则从 $i$ 向汇点连容量为 $P_{i-1}-P_i$、费用为 $0$ ...

Luogu LOJ UOJ 这题面写得也太好了吧 QAQ 分析 我们先考虑怎么算根节点的答案。 先假设它只有两棵子树 $u$ 和 $v$，榕树之心在根节点处。 如果 $u$ 长出一个节点，$v$ 长出一个节点，那么榕树之心还在根节点处，相当于这两次操作抵消掉了。 那么我们只需要判断根节点的所有子树能否相互抵消掉。 注意每棵子树是可以自行抵消一部分的，因此可以设 $f_u$ 表示 $u$ 子树内最多可以自行抵消多少对。 考虑 $f_u$ 如何转移。设最大的子树的根为 $h$，则 如果 $sz_h-2\times f_h\leq sz_u-1-sz_h$，则最大的子树可以被消掉，剩下的子树中还可以再消掉偶数个点，因此此时 $f_u=\left\lfloor\frac{sz_u-1}{2}\right\rfloor$。 否则，其它所有的子树都不可以把最大的子树消掉，因此此时 $f_u=f_h+sz_u-1-sz_h$。 这样子就只需要做一遍树形 DP 就能得到 $f$ 了。 考虑如何算根节点的答案。我们还是找到根节点的最大的子树，设它的根为 $h$，那么只需要判断 $sz_h-2\times f_h$ 是否小于等于 $n-1-sz_h$ 就好了。 然后我们再扩展到算任意点的答案。我们可以认为是先把榕树之心从根移到了当前节点，因此只需要把根到当前节点的链缩成一个点视为根即可。这样子需要维护缩点的最大子树，因此需要预处理出每个节点的次大子树。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bits/stdc++.h> #define re register using namespace std; inline int read() { int X=0,w=1; char c=g...