GCJ2015 还原集合 提交地址找不到 /qd。 假设说我们知道一个数 $x, x > 0$ 我们考虑对其进行背包，不妨假设上一个背包的数组为 $f$。 发现对于一个新的数组位置 $i$ 会对应 $i - x, x$ 两个位置。 然后考虑一下 $x, x < 0$ 的情况，位置 $i$ 会对应 $x, i + x$ 两个位置。 发现本质上还原的两个位置只相差了 $x$，所以我们最后还原出来的数列也只是位置相差了 $x$。这个 $x$ 是由若干个数拼接而成的，也就是将一个数取反得到的。 我们考虑如何得到最终答案的一个数，如果当前集合和的最大值减去次大值肯定只有几种情况。 少了一个最小的正数。 多了一个最大的负数。 结合一下就是得到的数的绝对值是最小的。我们不妨将所有的数都当做正数来考虑，那么最后得到初始的 $f$ 数组也就是只有 $f_0 = 1$ 。那么我们找那个唯一有值的情况，之后进行背包即可。 如果 $f_0 \ne 1$ 呢？肯定是有若干个 $0$ 组成的集合，也就是 $2^{sum - 1}$，其中 $sum$ 是 $0$ 的数量。 当我们找到这个 ...

CF1416B Make Them Equal CF1416B Make Them Equal 论我脑子有点问题这一事。 发现如果 $i = 1$ 这个肯定是很好做的，我们考虑将每个数都放到位置 $1$ 上，每个数最多被使用 $3$ 次，所以复杂度是 $O(3(n - 1))$。 我们具体来说，对于一个位置 $j$，如果 $j | a_j$ 显然我们直接将其放到位置 $1$ 上即可，不然的话我们考虑将这个位置补齐即可。 我们考虑通过归纳法证明这个事情，如果前 $i$ 个数是合法的，对于第 $i + 1$ 个数，最多需要 $i$ 个单位才能变成整除。而前面位置都是合法的，所以肯定有 $\ge i$ 个单位在 $1$ 上，那么肯定是合法的。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#incl ...

CF1385E Directing Edges CF1385E Directing Edges 题目描述： 给定一个图，有无向边和有向边。对于无向边进行定向，问能否给出一个方案使得定向后的图是无环的，图不一定要联通。 我们先不考虑无向边，对于有向边组成的图，不妨进行一次拓扑排序找到每一个节点遍历的先后顺序。 我们先判掉有环的情况，也就是存在一条边 $u \to v$ 而且点 $u$ 的遍历时间比 $v$ 要晚。 之后考虑我们肯定可以构造出一种合法的图，也就是对于所有的无向边我们考虑连接的两个几点，只要保证边 $u \to v$ 而且点 $u$ 的遍历时间比 $v$ 早即可。 具体实现的时候因为图不一定联通，所以我们不妨对于每一个节点进行 $\tt dfs$ 在搜索完儿子之后再将自己加入。这样可以保证及时搜索节点的顺序不同也可以保证是拓扑序列。 之后取反即可，因为现在是逆着的拓扑序。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 ...

LOJ #2269. 「SDOI2017」切树游戏 #2269. 「SDOI2017」切树游戏 没错我在某谷被卡掉了，之后会了全局平衡二叉树再更新那个做法。 不考虑修改怎么做。 设 $f(i, j)$ 表示以 $i$ 为根的子树（必须包含点 $i$）异或值为 $j$ 的方案数， $G(i, j)$ 以 $i$ 为根的子树的答案。 考虑更新。对于上一个答案 $f’(i, j)$ 当前儿子 $v$ 可以更新得到：$$\begin{aligned}f(i, j) = \sum_{j = k \otimes x} f’(i, k) \times (f(v, x) + 1)\end{aligned}$$其中 $\otimes$ 是异或运算，显然我们可以使用 $fwt$ 进行优化，不妨考虑 $f(i)$ 表示已经进行 $fwt$ 后的答案，$G$ 也是如此。这样我们最后只要 $ifwt$ 即可。 那么转移方程显然有 $f(i) = f’(i) \times (f(v) + one)$。 $G(i) = G’(i) + (f(v) + one)$ 之后 $G$ 别忘了加上当前位置的贡献。 ...

CF1344B Monopole Magnets CF1344B Monopole Magnets 多打 $CF$ 你也会懂一点英语。 笔者很菜，入手点是没有找到。就是考虑南磁铁不行的话，我们可以考虑一下两个黑色的格子的关系。也就是说如果这两个在同一个行的话，那么可以考虑到两个格子到当前行的南磁铁路径上肯定都是黑色的。 那么我们考虑是否会存在两个南磁铁的情况，如果存在那么肯定是为了处理有两段黑色的情况，但是下面的南磁铁同样是可以吸引上面的北磁铁，那么这种情况肯定是不行的。 所以可以得出第一个限制 每行每列最多只有一段黑色。 之后写了一下，发现过不了样例。样例提示我们这个限制还不够。 一开始想着特判一下 $1 \times n, n \times 1$ 的情况，但是发现对于 $2 \times n$ 的情况，同样会出现类似的不合法的情况。 具体来说就是如果一行是全部白色的，又因为这一行必须要填一个南磁铁。如果对于列来说填的位置是白色，而且这列是有黑色的，那么肯定是不合法的。会导致多刷点。 那么唯一合法的情况就是 如果存在一行是白色的，至少存在一列是白色的。 直接考虑这两种情况 ...

POJ 3613 Cow Relays POJ 3613 Cow Relays 真心想吐槽一下，这个不能用 $11$ 真的挺难受的。 首先看去像一个板子题，之后发现如果直接对于每个点建图的话时间是过不了的。 之后发现边的数量其实不是很多，一条边最多只有两个不同的点，所以实际上有用的点数是 $2m + 2$ 个。我们对于这个直接进行矩阵快速幂即可。 其实还有一个稍微难写一点的方法，我们考虑对于每一条边建立矩阵，之后如果两条边能互相到达就赋值为其权值，具体来说是 $i \to j, j \to z$ 边权分别是 $a_x, a_y$。那么图上 $G(x, y) = a_y, G(y, x) = a_x$。也就是具体表示走到了这条边的尽头的贡献。 那么我们发现 $n \ge 2$ 实际上我们考虑先让 $S$ 走到能走到的边的尽头作为答案矩阵。之后直接矩阵快速幂更新即可。 这个是我一开始想到的，后面发现其实离散化一下就可以了，所以就没写。 12345678910111213141516171819202122232425262728293031323334353637383940 ...

SP1716 GSS3 - Can you answer these queries III SP1716 GSS3 - Can you answer these queries 也真是服了，浪费几分钟来搞这种题目。 直接线段树维护一下端点信息即可，具体来说就是左右端点的权值最大值，答案还有区间权值和。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include <bits/stdc++.h>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT;#define gc() (iS == iT ? (iT = (iS = ...

SP1716 GSS3 - Can you answer these queries III 可以初步理解一下动态 $\tt Dp$ 的思想，不用矩阵而已。题解 #2269. 「SDOI2017」切树游戏 题解，姑且先算完成吧，已经会全局平衡了，在码了。 全局平衡二叉树 树剖解法题解 说实在的这种码量还是少写吧，之后要以构造题为主