P1971 [NOI2011] 兔兔与蛋蛋游戏 题解
Description 这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。 这个游戏是在一个 nnn 行 mmm 列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。 每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为： 兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。 蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移
支配树
在有向图 G 中，存在源点 s，若从 s 出发的到达点 y 的路径都经过点 x，称 x 支配 y。 注意：若源点 s 有多个，则可以虚拟一个起点。 性质 1：源点 s 支配所有的点，点 x 一定支配 x 本身。 性质 2：支配的传递性，若 x 支配 y，y 支配 z，则 x 支配 z。 性质 3：若 x 支配 y，y 支配 x，则 x=y。 性质 4：若 x 支配 z，y 支配 z，则 x 和 y
lgv 引理
lgv 引理：在一张有向无环图中，有边权，给定起点点集A，终点点集B，且A、B中点数一致。 定义P表示dag中一条路径 定义w(P)表示路径P上的边权乘积。 定义e(a,b)表示a到b的所有路径的边权乘积之和，即e(a,b)=∑Pi∈a→bω(Pi)e(a,b)=\sum_{P_i\in a\to b}{\omega(P_i)}e(a,b)=∑Pi∈a→bω(Pi)
best 定理
对于有向欧拉图G，其不同欧拉回路的总数cnt(G)为： cnt(G)=T⋅∏i∈V(degi−1)!cnt(G)=T\cdot\prod_{i\in V}{(deg_i-1)!} cnt(G)=T⋅i∈V∏(degi−1)! 其中T表示对于任意节点x的G的内向树的的生成树个数。
牛客 215E 黄魔法师 题解
Description 给出 n,kn, kn,k，求一个长度为 nnn 的数组 aaa, 满足有恰好 kkk 对数对 (i,j)(1≤i<j≤n)(i, j) (1 \leq i < j \leq n)(i,j)(1≤i<j≤n) 满足 ai+aja_i + a_jai+aj 为完全平方数。如果不存在，输出 −1-1−1。 link Solution 显然如果 k>
P4707 重返现世 题解
Description 为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 nnn 种原料，只需要集齐任意 kkk 种，就可以开始制作。 Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 iii 种原料被生成的概率是 pim\frac{p_i}{m}mpi。如果 Yopill
min-max 容斥
min-max 容斥也称之为最值反演。 Max(S)=∑T⊆S,T≠∅(−1)∣T∣−1⋅Min(T)Max(S)=\sum_{T\subseteq S,T\neq \varnothing}{(-1)^{|T|-1}\cdot Min(T)} Max(S)=T⊆S,T=∅∑(−1)∣T∣−1⋅Min(T) 定义 kMax(S)kMax(S)kMax(S) 等于 SSS 的第 kkk 大值，那么
CF1361E James and the Chase 题解
Description 给定一个有 nnn 个点 mmm 条边的有向强连通图。称一个点是好的当且仅当它到其他点都有且只有一条简单路径。如果好的点至少有 20%20\%20% 则输出所有好的点，否则输出 -1。 单个测试点内有多组数据。 1≤T≤2×103,1≤n≤105,1≤m≤2×105,∑n≤105,∑m≤2×1051\leq T\leq 2\times 10^3,1\leq n\leq 1