CF1391D 505 CF1391D 505 直接粗略看去没有什么可以入手的地方，考虑什么时候是不合法的。 发现样例给出了 $7, 15$ 的时候是不合法的。 考虑手造几组小样例，发现如果一个大的平方矩阵恰好包含偶数个小的平方矩阵就是不合法的。 考虑 $a^2 = k\times b^2$ 直接暴力带入一下 $b = 2$ 的情况，发现 $a = 4, k = 4$。那么显然对于 $n > 3, m > 3$ 的情况是不合法的。 那么剩下的状态就很少了，选择行列比较短的一个位置进行状压即可，我们只需要状压当前列的状态然后枚举前面状态进行转移即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include <bits/stdc++.h>using namesp ...

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 = ...