[六省联考2017]分手是祝愿 [六省联考2017]分手是祝愿 对于每一种情况，我们肯定是从大到小依次进行操作，那么对于一次操作是不能用其他操作进行代替的。 如果可以代替要么代替的那个变得不合法，要么其本身就是不用进行操作的。 所以我们可以直接计算出来原来序列需要进行多少次方案。 根据期望的线性性，而且现在本质上只和操作正确的次数有关，我们直接对于有几个还要操作进行 $\tt Dp$。 设 $f(i)$ 表示从还有 $i$ 个需要进行操作到 $i - 1$ 个需要的期望步数。$$f(i) = \frac{i}{n} + \frac{n - i}{n} \times (f(i + 1) + 1) \f(n) = 1$$然后题目的限制得到 $f(i) = 1, i \le K$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include < ...

全局平衡二叉树 P4751 【模板】"动态DP" P4751 【模板】”动态DP”&动态树分治（加强版） 有事没事就用 $\tt vector$ 总会有天废掉的。 注意在 $\tt c++11$ 之后 $\tt vector$ 不管是是否在 $O2$ 的条件下，速度都比常规数组慢很多，甚至比链表要慢 $4$ 倍。 死亡写法： 123456789struct Tree : vector<vector<int>> { Tree() : vector<vector<int>>(2, vector<int>(2, -inf)) {} Tree operator * (const Tree &z) { Tree res; for(int i = 0; i < 2; ++ i) for(int j = 0; j < 2; ++ j) for(int k = 0; k < 2; ++ k) ...

CF1559D2 Mocha and Diana (Hard Version) CF1559D2 Mocha and Diana (Hard Version) 做过 /qd 暴力就是直接枚举每条边是否被加入。 证明一下这个东西： 如果说存在有一条边不被加入，然后可以多增加两条边。那么增加的两条边肯定是连接了 $3$ 个连通块，而断掉一条边只能产生 $2$ 个连通块，说明肯定有一个连通块之前没有加入，和最优秀的情况矛盾，所以成立。 那么根据之前这个结论我们直接进行暴力加边即可。 我们发现对于最终的情况本质上肯定是对于任意一个 $A$ 中的连通块想和其他联通块相连，$B$ 中肯定都是同一个连通块。 那么肯定是可以构成树的。 我们直接考虑钦定树上任意一个节点作为根进行计算即可。 那么现在这一步就是贪心了，先加入两边都可以加入的边。不然的话就是如果一边已经加入了边，那么另外一边显然也是可以加入的，使用并查集维护一下即可。 复杂度是 $O(n \alpha(n))$。

CF449C Jzzhu and Apples CF449C Jzzhu and Apples 肯定会想到偶数肯定需要来匹配的，之后发现对于奇数的情况，对于每一个奇数肯定都是若干个质数的倍数。那么越大的质数越难被匹配，我们考虑从大到小对于质数进行考虑。 对于当前质数 $p$ 找到所有没有被匹配过的数，如果有偶数个直接进行匹配即可，不然的话肯定需要舍弃一个数，发现 $2$ 是一个质数，那么我们舍弃一个 $2$ 的倍数即可。 这样可以发现匹配到最后我们最多舍弃一个数，不可能更优了。

CF1375E Inversion SwapSort CF1375E Inversion SwapSort 发现逆序对不是很好入手，考虑最终构成的序列是单调递增的情况。 不妨考虑这是一个排列的情况。 显然离散化一下答案不会改变。 发现 $n$ 肯定是在最后面，那么对于一开始的序列我们不妨考虑将 $n$ 放到最后面之后转化成一个子问题。 那么对于一个合法的子问题，我们必须保证对于原来 $a_u < a_v$ 的情况，还有 $a_u < a_v$。 不妨考虑之前最后一个位置是 $x$，那么对于 $\ge x$ 的数我们可以进行一次循环移位，这样可以保证位置 $n$ 肯定是在正确的位置的。 具体来说就是 $x + 1$ 和 $x$ 交换位置， $x + 2$ 和 $x + 1$ 交换位置。也就是向后进行循环移位，可以发现肯定是合法的。 之后直接根据子问题去做即可复杂度 $O(n^2)$。

CF1380D Berserk And Fireball CF1380D Berserk And Fireball 其实不能算一个构造题，主要难在代码实现。 考虑每一个区间，对于这个区间选择一个最优的方法删除即可。 显然我们考虑用当前区间最大的数去删除其他的数，之后再将其删除即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include <bits/stdc++.h>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT;#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 2 ...

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$ 的数量。 当我们找到这个 ...