题意有一棵 $N$ 点的树，有 $Q$ 次询问 $(a,b,c,d)$ ，问 $a\rightarrow b$ 与 $c\rightarrow d$ 是否相交。$N,Q\le 100000$ 。题解可以发现两条边相交，就一定存在一条边的最高点在另一条边上，即端点的 $\text{LCA}$ 。所以只用求 $\text{LCA}$ 就行了。第一次写倍增 $\text{LCA}$ ，感觉还是树剖...
题意要从一个 $N$ 点 $M$ 边的有向图的 $1\rightarrow N$ ，每秒可以走 $2^k$ 条边（$k$ 是任意自然数），求最少要花多少秒。$N\le 50 \ , \ M\le 10000$ 。题解用一个 bool 数组 $s[i][j][p]$ 表示能否走 $2^p$ 条边从 $i\rightarrow j$ ，可以通过倍增预处理出所有情况。这样就得到了所有能在 $1s$...
题意给出 $N,A,B$ ，求 $N_0$ 的最值，使得 $\lfloor N^A+N^B \rfloor = \lfloor {N_0}^A+{N_0}^B \rfloor$ 。有 $T$ 组数据，答案为每组数据中 $\max N_0 - \min N_0$ 的和。输入方式请看原题。$4\le N\le 5 \ , \ 5\le A,B\le 10 \ , \ T\le 5\times 1...
题意有 $N$ 张卡片，使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格，如果跳到就输了，求跳到终点的方案数。$N\le 24 \ , \ M\le 2$ 。题解用 $cnt[i]$ 表示当前走到的格子，很容易想出状压方程：$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\n...
题意有 $N$ 个人要排队，要求一队的站在一起，共有 $M$ 队。调整队列的方法为让一部分人出队，再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压，用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ，设之前排到了第 $l$ 个人，那么现在要排的是 $[l+1,...
题意有 $N$ 个人去执行 $N$ 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。（直接用题面）$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ，枚举任务 $j$ ，很容易得到方程：$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...
题意用 $K$ 个硬币购买 $N$ 个物品。商店不设找零，可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。$N\le 100000 \ , \ K\le 16$ 。题解看到 $K\le 16$ ，状压。用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品；预处理出 $v[i][j]$ 表示硬币 $i$ ，从 $j$ 物品开始买，能买到哪个物品；枚举当前用的硬币 $...
题意在一棵 $N$ 个点的树上放 $K$ 个监听器，每个监听器可以监听与它直接相连的节点，但不能监听自己。要求所有节点都被监听，求方案数。$N\le 100000 \ , \ K\le 100$ 。题解真·毒瘤题目。用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了，放了 $i$ 个监听器，$x$ 上放没放监听器，$x$ 有没有被监听到 的方...
题意将一棵 $N$ 个点的树上 $K$ 个点染黑，另外的点染白。求黑点两两之间距离和加上白点两两之间距离和的最大值。$N,K\le 2000$ 。题解考虑每一条边的贡献，即为 边权 $\times ($ 一侧的黑点个数 $\times$ 另一侧的黑点个数 $+$ 一侧的白点个数 $\times$ 另一侧的白点个数 $)$ 。用 $f[x][i]$ 表示以 $x$ 为根的子树，黑点有 $i$ ...
由于Pjax与自带反垃圾保护的冲突，请在 设置->评论 中关闭反垃圾保护！ 否则可能无法评论。推荐使用插件smartspamGithub镜像（更快下载）示例站点Edge[edʒ]n.边缘；棱；角；锋Feature一款棱角分明的主题。Pjax 支持。代码高亮、文章目录支持。使用下载（或clone）后将文件夹命名为 Typecho-Theme-Edge ，然后放入 /usr/themes/...
题意有 $N$ 个小球，每个小球的坐标为 $(x_i,y_i)$ ，即水平为 $x_i$ ，高度为 $y_i$ ， 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ，每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数，分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球，求最高分数。$N\le 1000$ 。题解比较容易想到区...
题意可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ，可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。字符串长度 $N\le 100$ 。题解设需要处理的字符串为 $S$ ，用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。显然可以从两个字符串拼接而来。枚举断点 $k$ ，$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。也可...
最难受的事情莫过于比赛还剩20min，你锁了题，然后叉了自己。锁题有风险，叉人需谨慎。A. Choose Two Numbers题意从两个序列中各选取一个数，要求这两个数的和不属于这两个序列。序列长度 $N\le 200$题解水题，$N^2$ 枚举。#include<bits/stdc++.h>
using namespace std;
inline int read()
{...
题意给一个长度为 $N$ 的木板染色，木板有初始颜色，要求染成一种颜色。每次可以选择一段连续的格子染色，颜色可以被覆盖。求至少要染多少次。$N\le 50$ 。题解用 $f[l][r]$ 表示将 $[l,r]$ 染成一种颜色的最少次数。当 $S_l=S_r$ 时，可以在染一边时顺便把另一边染了，即 $f[l][r]=\min(f[l+1][r],f[l][r-1])$ 。否则可以枚举中间点 ...
题意有 $N$ 座城堡和 $S$ 个玩家，每个玩家有 $M$ 个士兵。能占领城堡要求自己驻扎的兵力严格大于对方的两倍，玩家之间两两都会有独立的城堡争夺，占领第 $i$ 个城堡的收益是 $i$。现在已知 $S$ 个玩家的驻军情况，求如何分配兵力，可以获得最大收益。$S,N\le 100 \ \ \ \ M\le 20000$ 。题解很显然的背包问题，只是需要预处理一下重量。用 $v[i][j]...