https://ac.nowcoder.com/order?itemId=28&itemType=ACM_CONTEST_CHARGE&couponId=AcABnfL

就这

考试题目的小数版本可以先考虑一个暴力， 就是枚举一个点作为最后的点， 然后枚举一个删边的序列。这个暴力显然比朴素的暴力复杂度要优秀一点。考虑基于这个思想来写题。可以枚举一个点作为最后的点， 然后出所有的删边序列。算出在这个序列下点保留下来的概率， 然后把所有的概率加起来，除以也就是左右序列的个数就是答案了。实际上下面的值是记录了一些序列， 然后取前一个前缀删掉。考虑设表示当的子树里面还有条边没有删掉的时候， 上述的概率和是多少。（模拟题意不难发现， 这题其实就是当做删边来理解并没有什么问题）。由于是概率的和， 实际上值里面包含的是很多个在当前子树内的边的删边排列的”合法概率和”。为了方便， 我...

复习笔记就离谱好吧 用途 大概是给你一个序列， 然后插入一条线段， 然后查询某一个位置上与所有线段交点的纵坐标的的最大值或者最小值。 然后就没了。 实现 定义一个区间的"优势线段"为在这个区间里面有超过一半的点在这个线段上取到最值。 考虑维护一个线段树， 每个节点上保存了一条线段， 初始的时候没有保存， 表示这个区间的"优势线段"。 然后考虑怎么维护这个东西。下面均以维护最大值为例。 若当前区间还没有记录最优势线段，则记录最优势线段并返回。 若当前区间的最优势线段被插入的线段完全覆盖，也就是完全...

题目大意： 求两条树上边不相交路径， 使得删掉这两条路径上的点以后剩下的连通块数量最多。 做法 两条路径在树上大概会长成两个倒着的‘V’字形， 考虑在某一个'V'的最上面那个点统计答案。 于是统计答案的时候我们发现有几种统计法： 父节点有一个'V'， 子节点有一个'V‘。 父节点上一条链到子节点， 子节点有一条链经过， 内部有一条路径， 合并两条链。 父节点被一条链经过， 子树内有一条路径， 子节点有一条链经过， 内部有一条路径。 发现当前点是否被经过了对于转移是有关系的， 所以设状态的时候不能够简单的设子树内选一条路径的方案数目。 设\(dp(x, 0)\)表...

发现题目给的很像一棵树。。。 就把这棵树建出来。 发现如果把大于小于号分别看成一条有向边， 发现这个题目就是求这个图有多少个拓扑序。对于每一个拓扑序， 直接$$12345$$这样标号就可以得到满足题目要求的序列。 考虑树\(dp\), 设\(f(i, j)\)为\(i\)这个点在这个子树所形成的拓扑序列中在第\(j\)位的方案数。 转移的时候实际上就是合并两个序列。 用\(x\)表示当前点,\(y\)表示儿子。 当\(x > y\)时， \(f(x,k) = \sum C(k - 1, i - 1) \times C(sz[x]+sz[y] -k, sz[x] -i)...

我们把位置在\((2i - 1, 2i)\)的两个点叫做一对点。 显然如果这对点两个都被限定了直接丢掉完事。 如果有一个没有被限定就先留下来。 注意到其他的形如\((-1, -1)\)的顺序是可以随便变化的， 所以先不考虑， 最后乘上一个阶乘就可以了。 考虑用\(f(i, j, k)\)表示当前填第\(i\)个数， 剩下\(j\)个\((-1, d)\)对， 这种对是自己搞出来的， 还剩下\(k\)个\((-1, e)\)对， 是被限定了的。 从这里可以发现， 我们的\(i\)应该从大到小枚举， 这样才可以避免后效性， 否则前面选了一个数， 后面就没法改变这一对的值， 从而出现后效性...

考虑\(1\)号点向外连出一条边之后， 整个圆被分成两个部分， 每个部分肯定是内部连边然后一个点连一条边出来跨越一号点连出的那一条线。考虑对这种形状的部分进行\(dp\)。 设\(f(i, j, k)\)表示\([i, j]\)这个区间内部匹配， \(k\)点向外连接的方案数， \(g(i,j,k)\)表示外面一点\(k\)连接到区间\([i, j]\)内， 区间内其他点两两匹配的方案数目。 考虑转移， 可以枚举左边和右边的小块， 然后连接， 再枚举中间的每一个点作为连出去的点转移， 因为只有左右两边连起来， 中间连出去才会是一棵树， 所以连出去的点除了一个点的情况， 其他时候都不该在区...

首先， 按照boshi巨佬的说法， 考虑每种联通块的出现次数。如果可以求出， 答案就是每种联通块的出现次数和。 再按照boshi巨佬的说法， 一种定义联通块长相的方法是用编号最小的点和编号最大的点表示。 于是设\(f[l][r]\)为\(l, r\)连通且外面的点不连接到里面的点， 里面的所有边都任意连接的方案数。 由于\(l, r\)连通不是很好做， 所以就用任意连的方案数目减去连通的方案数目。 设\(g[l][r]\)为\([l, r]\)内的点任意连接的方案数目， 有： \(f[l][r] = g[F(l, r)] - \sum f[l][k] \times g[F(k + 1...

显然要是没有限制那就全都是\(1\)对吧， 所以考虑这些\(0, 1\)到底限制了啥。 首先看到\(border\), 容易想到当年写\(kmp\)求最短回文子串的那题。因为\(kmp\)的\(next\)数组实际上就是最长\(border\)。我们也在那题积累一个结论， 就是对于原来的串一个长度为\(k\)的\(border\), 原串一定是由长度为\(n -k\)的子串循环而成的，但是最后一部分并不一定是一个完整的循环节。（实际上你也可以看成第一个不一定是一个完整的循环节， 这一部分画图很容易看出来）。那么如果有一组\(0,1\)的位置距离恰好是\(n-k\)，那显然就是不行的， 因为...

考虑每一条哈密顿回路在所有竞赛图中的出现次数。 发现如果确定一个环， 其他的边乱选就可以保证出现哈密顿回路。所以对于一条哈密顿回路， 出现次数为\(2^{C_n^2-n}\), 减去的\(n\)为那\(n\)条边。哈密顿回路是\(1-n\)的一个排列首尾拼在一起， 共有\(n!/n\)种。于是总贡献可以直接得出。 总贡献算好了， 问题转化为求有多少个存在哈密顿回路的竞赛图。 显然， 存在哈密顿回路的竞赛图一定强连通， 强连通的竞赛图一定有哈密顿回路。 所以问题就是求有多少个强连通的\(n\)个点的竞赛图。 设\(n\)个点的强连通的竞赛图个数为\(f_n\)。 考虑用所...

note: 最小环 是枚举已有的最短路和k点连接的两条边， 保证三个点不重合。 for(R int k = 1; k <= n; k ++) { for(R int i = 1; i < k; i ++) for(R int j = i + 1; j < k; j ++) { if(e[i][j] < 1e9) ans = min(ans, a[i][k] + a[k][j] + e[i][j]); } ...

lei/ \[\sum^n_{i = 1} lcm(i,n)=\sum^{n}_{i=1}\frac{in}{gcd(i, n)}= \] \[\sum^{n}_{d|n}\sum^{n}_{i=1}\frac{in}{d}[gcd(i,n)==d]= \] \[n \times \sum^{n}_{d|n}\sum^{\frac{n}{d}}_{i=1}i[gcd(i, \frac{n}{d})==1] \] 记\(\sum^{\frac{n}{d}}_{i=1}i[gcd(i, \frac{n}{d})==1]\)为\(f(a)\) \[sum(a)...

exgcd \[x = y \ \\ y = t - a /b \times y \] CRT \[ans = \sum_{i = 1}^n{b_i\times M_i\times inv(M_i,mod_i)} \] \[M_k=(\prod_{i=1}^n {} mod_i)/mod_k \] \[inv(M_i, mod_i)表示M_i在模mod_i意义下的逆元 \] EXCRT 原理：合并同余方程 对于 两个同余方程 \[x \equiv r_1(mod \ m_1) \\ x\equiv r_2(mod\ m_2) \] 有 ...