[HNOI2013]游走 [HNOI2013]游走 考虑每一条边的单独贡献，发现这个不是很好计算，而且边数其实很多。 我们考虑对于一条 $u \to v$ 的边，其贡献是 $\dfrac{f(u)}{deg(u)} + \dfrac{f(v)}{deg(v)}$。 其中 $f(i)$ 表示点 $i$ 期望被经过的次数，别忘了一开始点 $1$ 就被经过一次了。 考虑走到别的点之后再走回来更新这个点：$$f(u) = \sum_{v \in son(u)} \frac{f(v)}{deg(v)}$$如果 $u = 1$ 还要 $+ 1$。 发现数据范围很小，我们直接进行高斯消元即可。 之后对于边的期望经过次数进行贪心即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#i ...

[HNOI2015]亚瑟王 [HNOI2015]亚瑟王 根据期望的线性性质，我们考虑每一张牌的贡献。也就是每一张牌被使用的概率。 显然第一张牌使用的概率就是 $1 - (1 - p_1) ^ r$。 但是发现之后的牌的使用依赖于前面的牌的使用，因为如果前面有 $j$ 张牌被使用了，相当于有 $j$ 轮对于当前牌是无效的。 我们考虑进行 $\tt dp$，设 $f(i, j)$ 表示前 $i$ 张使用了 $j$ 张牌的概率。$$f(i, j) =\begin{cases}f(i - 1, j) \times \left(1 - p_i\right)^{r - j} \f(i -1, j - 1) \times \left[1 - (1 - p_i)^{r - j + 1}\right]\end{cases}$$ $$F(i) =\begin{aligned}\sum_{k \le i} f(i - 1,k) \times \left[1 - (1 - p_i)^{r -j}\right]\end{aligned}$$ 12345678910111213141516171819202 ...

[六省联考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$。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#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 ...