POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
标签 构造 下的文章
- 首页
- 构造
洛谷3516 [POI2011]PRZ-Shift
Luogu LOJ 分析 假设已经排好了 $1\sim i$，考虑如何把 $i+1$ 放到 $i$ 后面。可以构造出这样的方案： 首先用 ka 把 $i+1$ 移到最前面。 重复使用 2a 1b 把 $i$ 后面的元素两个两个地移到 $i+1$ 和 $1$ 之间。 如果最后 $i+1$ 后面还有一个元素，使用 1a 2b 把它移到 $i+1$ 和 $1$ 之间。 这样子有一个问题，即当 ...
ARC103F Distance Sums
AtCoder Luogu 分析 不难发现 $d_i$ 最大的节点一定是叶子节点，$d_i$ 最小的节点一定是重心。 考虑某个叶子节点 $u$ 的父节点 $f$ 应该满足什么。显然有 $d_v=d_f+(n-sz_u)-sz_u$ 即 $d_f=d_v+2sz_u-n$。于是我们只要随便找一个这样的 $f$ 连上去即可，如果找不到则无解。这个 $f$ 可以通过二分来找。 这样子我们就可以按照...
CF1060H Sophisticated Device
Codeforces Luogu 分析 首先确定基本的计算方式 则我们需要平方、减法、乘法（除以 $2$ 就是乘逆元）这三种运算。 既然要造计算机，那么一定要先求出一个 $0$ 来。因为 $1+1\times(p-1)\equiv 0\pmod p$，所以可以快速乘一下。 for (int i=p-1;i;>=1) { // 0 -> o[16] if (i&1...
CF568E Longest Increasing Subsequence
Codeforces Luogu 分析 考虑普通 LIS 问题的解法，即设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，转移时二分即可。 考虑沿用到这道题中。设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，$g_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值所在位置；再设 $l_i$ 表示以 $i$ 结尾的 LIS 长度，$p_i$ 表示以 $i$ 结尾...
AGC035C Skolem XOR Tree
AtCoder Luogu 分析 可以发现 $(2i)\oplus (2i+1)=1$，因此可以想到大致的构造方法：连 $(1,2i)$、$(1,2i+1)$、$(2i+1+n,2i)$、$(2i+n,2i+1)$。这样子就满足了 $2i$ 和 $2i+1$。 然而有一些问题。一个问题是 $1$ 如何处理。可以仿照样例，使 $2$ 和 $3$ 不按上面的方式连边，而是连 $(1,2)$、$(...
ARC103D Robot Arms
AtCoder Luogu 分析 首先，如果存在 $i,j$ 满足 $|x_i+y_i|$ 与 $|x_j+y_j|$ 的奇偶性不同，则无解。因为走到 $(x,y)$ 的步数一定与 $|x_i+y_i|$ 的奇偶性相同。 先考虑 $|x_i+y_i|$ 全部为奇数的情况。 先考虑步长的问题。可以利用二进制进行构造，即令步长为 $2^0,2^1,\cdots$。容易发现最大只需要到 $2^{3...
CF1276C Beautiful Rectangle
Codeforces Luogu 分析 考虑枚举短边的长度 $r$。设数 $i$ 有 $cnt_i$ 个，那么我们至多能填 个数到矩形中。因此当短边长度为 $r$ 时长边至多为 $\left\lfloor\frac{s_r}{r}\right\rfloor$。 因为短边长度不超过 $\sqrt{n}$，因此我们可以在 $\mathcal{O}(n\sqrt{n})$ 的时间内求出答案。 现...
CF343E Pumping Stations
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论：第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...
CF468C Hack It!
Codeforces 分析 首先可以发现，当 $x<10^{18}$ 时有这样一个关系式 也就是说，当 $[l,r]$ 从 $[1,10^{18}]$ 变成 $[x+1,x+10^{18}]$ 时，$\sum_{i=l}^rf(i)$ 增加了 $x$ 。 设 $\sum_{i=1}^{10^{18}}f(i)=q$ ，显然一组合法的 $[l,r]$ 为 $[a-q+1,a-q+10^...