constructive 566E 对于一对相邻的点 $(x,y)$，它们其它的相邻点之间的交集就是 ${x,y}$。且如果有两个相邻点交集的大小为 2 也一定是两个相邻的（出现的点如果不相邻那么它们路径上的也应该在交集中）。 这样可以求出所有非叶子节点之间的连边，剩下的都是叶子节点。叶子节点的连边就看是哪个点和它相邻的所有点都包含了它。 这样非叶…

Greedy 1472F 从左到右考虑每一列， 确定了前 $i-1$ 列，那么现在的第 $i$ 列哪些被覆盖就确定了。 可以求出第 $i$ 列覆盖的方案：如果没有空格/只有一个空格，则只能放横的；否则两个都是空格，一种是放两个横的，一种是放一个竖的，可以发现放两个横的和放两个竖的等价，不如变成放竖的，其它的之后再决策。 所以就变成，只要这一列没满，…

1523E 刚开始想的是直接 dp，记录当前两端都没有/左右有一盏/两端都有的答案，转移就考虑哪个范围能继续递归。 其实可以有另一种思路，期望等于 $i$ 次操作后还没结束的概率之和+1（即 $E(x)=1+\sum_{i\geq 1} P(x>i)$）。 那么每一盏灯（除了最后一盏）就要求它后面 $k-1$ 个位置都没有灯，组合数就能计算 …

给定 $n$ 和数字串 $a_1,a_2,\cdots,a_n$，$b_1,b_2,\cdots,b_n$。 定义一次操作为：将一个等长且不相交的前缀和后缀对应位置交换。举例：${1,2,3,4,5,6}$ 交换长度为 $2$ 的前后缀变为 ${5,6,3,4,1,2}$。 可以对 $a$ 进行任意次操作，问是否能变成 $b$。多组数据。 $1\l…

给定一个 $n$ 个点 $m$ 条边的无向图。有 $q$ 个人，第 $i$ 个人要从 $s_i$ 到 $t_i$。 现在你要给无向图的每条边定向。问是否存在一种定向方法使得所有人都能够到达目的地。 $n,m,q\leq 2\times 10^5,u_i\neq v_i,s_i\neq t_i$ sol 我的做法（186ms） 可以发现，对于一个边双…

如果 $max(a_1,a_2,\cdots,a_m)\cdot min(a_1,a_2,\cdots,a_m)\geq a_1+a_2+\cdots+a_m$，则整数序列 $a_1,a_2,\cdots,a_m$ 被称为好的。 如果 $a$ 的每个非空子序列都是好的，则整数序列 $a_1,a_2,\cdots,a_n$ 被称为完美的。 给定两个整…

给定一个 01 串 $s$，要求你找到一个与 $s$ 长度相等的 01 串 $t$ 并满足以下条件： 对于任意的 $l,r(1\leq l\leq r\leq n)$，$s[l:r]$ 和 $t[l:r]$ 的最长不下降子序列长度相同； $t$ 中 $0$ 的数量尽可能多。 有多解输出任意一种。$|S|\leq 10^5$。 sol 这个题非常有意…

给定 $n$ 个数字 $a_1,a_2,\cdots,a_n$，每次操作可以给某个 $a_i$ 加上 $2$ 的非负整数次幂。 求最少的操作次数使得 $n$ 个数相等。 $1\leq n\leq 10^5,0\leq a_i\leq 10^{17}$ sol 不妨先将 $a$ 从小到大排序。 设最后每个数都等于 $a_n+x(x\geq 0)$。那…