CF865E 首先考虑差的性质，也就是 $S = \sum_{i} a_i - b_i$ 我们会发现如果没有进位这个值就是 $0$，不然如果有进位那么每一位会多出来 $15$ 的贡献，可以发现合法的情况是 $S \equiv 0 \pmod {15}$。 不然就是不合法的。 然后我们需要钦定有多少位是进位的，复杂度是 $\binom{13}{6}$ 可以接受的样子。 又因为 $b$ 是 $a$ 的置换，本质上我们可以看成 $a_i - a_{p_i}$。我们不妨将这种情况连边 $i \to p_i$。可以连接成若干个环。对于每一个点的权值 $w_i = a_i - a_{p_i}$。但是对于每一个环我们统一进行处理会更加方便，也就是将整个环 $-1$ 直到出现 $0$。将两个 $0$ 点进行连边即可。 我们进行计算的时候因为对于图上来说，我们如果钦定了一个开始点，剩余的点本身就是一个差分，我们要还原之前的值就是前缀和。 我们再考虑一下 $S$ 的性质，发现 $15 = 16 - 1$ 也就是说明 $16 \times \frac{S}{15} - \f ...

CF1383C观察一下题目的性质，他说了同一种颜色可以有若干个一起变色，那么我们考虑将同一种颜色看成相同的东西。 考虑对于其建图，也就是如果 $A_i$ 变成 $B_i$ 就建立 $A_i \to B_i$ 的边。 然后本质上就是叫我们重新建立一张图满足 $A_i$ 和 $B_i$ 联通，边数最少的图。 本质上每一次变换都是需要一次操作。 但是不仅是如此，如果说 $u \to v$ 的路径是存在的，必须满足其路径上的边的变化时间是递增的。那么就是让我们对于边进行标号，然后满足图上任意路径都是递增的。 我们发现如果任意两个点都能互相到达，边数最少的就是一个环加上一条链。也就是这样的情况。这样我们需要消耗 $2n - 2$ 条边。 但是我们可以更优，也就是考虑对于这个图，找到一个最大的 $DAG$ 进行向链一样连边，然后后面的点进行这样的操作。 这样子肯定是最优的。然后我们考虑通过 $Dp$ 计算这个答案，发现直接计算选了 $S$ 中的点，最大 $DAG$ 的大小不好算。那么我们就找下面链的最少点个数。 我们对于每一个弱连通块分别考虑，设 $f(S)$ 表示考虑了集合 $S$ 中的 ...

CF848D对于一条 $S \to T$ 的路径我们一开始会考虑对于点的标号进行计算，但是事实上我们并不知道哪些点会在左边或者右边。 然后对于最小割我们转化成最大流进行计算，对于某一个中间点使得最大流是 $m$，你们左右两边的最大流的 $\min$ 就是 $m$。 我们发现本质上就是求经过 $n$ 次操作，使得最大流是 $m$ 的图的个数。 然后对于左右两边其实分成了一个子问题。 那么设 $f(n, m)$ 表示经过 $n$ 次操作，最大流是 $m$ 的图的个数。 然后进行转移的时候，设 $g1(n, m)$ 表示最大流大于等于 $m$ 的图的个数，$g(n, m)$ 是最大流恰好为 $m$ 的图的个数。 对于 $f$ 进行后缀和为 $F$。 那么 $g(n, m) = \sum_{i = 1} ^ {n - 1} F(i, m) \times F(n - i -1, m)$ 之后因为每一条路径本质只会贡献一次，所以 $g(n, m) = g1(n, m) - g1(n, m + 1)$ 。 这个和二项式反演不同，那个是同一条路径贡献多次。 然后我们考 ...

CF830E题目已经很简洁了，我们考虑对于样例进行分析。 首先不用脑子就能想到的就是环的情况，有环直接全部填 $1$ 就好了。 我指的是环所在的连通块。 之后研究样例发现对于树的情况也是有解的，然后我们会想到菊花的情况，对于菊花，也就是 $\exist i, deg_i \ge 4$ 就是有解的，中间填 $2$，周围填 $1$。 我们发现 $\forall i, deg_i \le 2$ 是无解的。 然后我们发现只有一个 $deg_i = 3$ 的情况不好算，我们先看两个的情况。也就是有两个度数为 $3$ 的点连在一起了，我们直接对于两个点赋值 $2$，其他为 $1$ 即可。 一开始我是想着两条链之间的点赋值 $2$，后面发现 $1$ 也是可以的，这样就很简洁了。 然后我们开始讨论只有一个 $deg_i = 3$ 的情况。本质上就是一个点，三条链的情况发现我们可以对于每一条链进行单独考虑。我们不妨设这样一条链从头到尾是 $a_1 \sim a_n$ 其中 $a_1$ 是图中的 $1$ 号节点。之后我们考虑使这个贡献最大，也就是使这个函数最大。$$- \ ...

「CEOI2019」游乐园 题解首先看到这个是一个数图的题目。这里有一个转化，考虑翻转边本质上就是对这个图进行一个定向，容易想到翻转的边和自己定向的 $DAG$ 是一一对应的。 所以我们考虑给定一个无向图，对于每一条边进行定向，求定向后是 $DAG$ 的图的贡献。 然后我们考虑对于一个 $DAG$ 我们把所有的边都翻转了肯定也还是一个 $DAG$。 所以对于每一个合法的方案都有一个可以和其进行配对的图，其贡献之和是 $m$。所以每一张图的贡献可以当做 $\dfrac{m}{2}$ 来计算。 发现 $n \le 18$ 使用状压 $Dp$。设 $f(S)$ 表示只选用了 $S$ 中的点，构成合法图的方案数，之后考虑转移是通过枚举一个集合进行转移。对于 $S$ 通过 $S’$ 转移到 $T$，我们必须要保证 $S’$ 内部是没有边的，才可以让我们进行定向。然后对于 $S’$ 其贡献又会被计算多次，也就是对于其每一个子集其都会被计算一次贡献，当然转移肯定不能使空集，所以总共被计算的次数是 $2^{|S|} - 1$。直接进行容斥就好了。 至于容斥系数，我们直接考虑只有一个点转移就是 $1$， ...

P3293 [SCOI2016]美味 一道好的二分题目。 对于常规的来说肯定是考虑在 $Trie$ 树上找一个最优的点。 但是我们发现这里是 $b_i \ \text{xor}\ (a_j + x)$ 对于 $b, x$ 都是固定的，但是异或却没有分配律，所以就会难搞一点。 我们考虑二分一下答案，和平时的二分答案不一样，我们不能快速地判定可行性，但是我们可以判定对于一位是否可行。 也就是说我们对于每一位分别进行考虑，不妨当前可以得到的前面几位的答案是 $ans$。如果这一位是 $0$，是第 $j$ 位，那么我们就尽量要得到 $1$，所以我们会得到一个合法的选择区间，也就是 $[ans, ans + 2^j - 1]$，如果说这里面有数，那么我们这一位就可以得到 $1$。另一种情况同理。 这样我们就可以转换成查询一个区间中是否有数，直接可持久化线段树就好了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616 ...

P3758 [TJOI2017]可乐 首先考虑一个 $Dp$。会想到 $f(t, i, j)$ 表示在时刻 $t$ 走到位置 $(i, j)$ 的方案数。但是因为我们是从 $1$ 开始走。那么完全可以设 $f(t, i)$ 表示从 $1 \to i$ 在时刻 $t$ 的方案数。转移的话就枚举之后可以走到的位置进行转移。 然后处理一下爆炸的情况，可以建立一个新的节点，之后进行转移，然后每个点只能进入不能出来。 我们发现本质上我们的 $t$ 意味着死亡时间最晚是 $t$ 所以之前的状态需要继承。然后要对于新建的节点再来一个自环，进行转移。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>using namespace std;#def ...

P5283 [十二省联考2019]异或粽子 首先把题目转换一下，可以得到以下题面： 有一个长度为 $n$ 的序列 $a$，求两两异或的前 $K$ 大值。 本质和 CF241B Friends 一样。 $Tricks:$ 补全三角形矩阵，答案 $\div 2$。 考虑建立可持久化 $Trie$。之后考虑两种情况。 如果 $K$ 和 $n$ 是同阶的，我们可以得到一个 $K \log K$ 的算法。 我们维护一个大根堆，常规维护一下第 $K$ 小。之后考虑每一个位置的贡献。我们不妨考虑每一个位置作为右边位置的贡献。那么就是求左边异或第 $K$ 小。 对于每一个位置都这样做。可以保证有答案。 当取出一个元素的时候，更新答案，然后使用当前元素计算比其小 $1$ 个 $rank$ 的答案，放入堆。 可以得到复杂度是 $O((n + k) \log (nk))$。 $n$ 是插入的复杂度， $k$ 是堆的复杂度。 如果 $n$ 比较小，然后 $k$ 是 $n^2$ 级别的呢？ 我们考虑对于所有的数都插入到 $Trie$ 里面。 发现如果可以得到第 $K$ 大的值，那么计算比其小的值可 ...