笔记

https://qoj.ac/problem/8008

不难发现，

随机到某些位置，之后最短路

先O（nm）预处理出能到的点，

考虑最小的随机位置

首先，我们将求和式进行展开：

$$\sum _{j=1}^{\infty }j{\left(\frac{n-i}{n}\right)}^{j-1}\frac{i}{n}$$

将 ${\left(\frac{n-i}{n}\right)}^{j-1}$ 视为常数，记为 $x$，则上式可以重写为：

$$\frac{i}{n}\sum _{j=1}^{\infty }j{x}^{j-1}$$

这是一个常见的等比数列求和，其和为：

$$\frac{i}{n}\cdot \frac{1}{(1-x{)}^2}$$

将 $x$ 恢复为 ${\left(\frac{n-i}{n}\right)}^{j-1}$，得到最终结果：

$$\frac{i}{n}\cdot \frac{1}{{\left(1-\left(\frac{n-i}{n}\right)\right)}^2}=\frac{i}{n}\cdot \frac{1}{{\left(\frac{i}{n}\right)}^2}=\frac{n}{i}$$

因此，经过推导求证，我们得到了结论：
$$\sum _{j=1}^{\infty }j{\left(\frac{n-i}{n}\right)}^{j-1}\frac{i}{n}=\frac{n}{i}$$

---

CF741C

考虑二分图染色，

对于每一对情侣，相互连边，

相邻的2i和2i-1也连边，都代表颜色不同，

---

CF1656G

限制是只有一个环，

先随便造一个回文排列

现有一个排列p

如果i，j处在同一个环，

那么pipj相互指向

拆成两个环

回文只需要第i位和第n-i位相同

考虑将一些小环合并成大环

i，j，n-i+1，n-j+1两对可以同时交换

---

https://www.luogu.com.cn/problem/CF1844E

这个题需要一些打表

考虑手玩一下

发现只要确定第一行第一列就可以确定所有的格子

之后容易发现一个小规律

a	b	a	c	b	a
c	a	c	b	a	c
b	c	b	a	c	b
a	b	a	c	b	a
b	c	b	a	c	b
a	b	a	c	b	a

不难发现行于行之间，列于列之间有重复

用1，2，3，分别表示a,b,c

在模三意义下就可以加一得出合法矩阵

---

https://qoj.ac/problem/6376

考虑高斯消元

共三个方向，

也就是三个变量，

但是有接近n方个限制
也就是n方个方程

考虑从中选一部分，

使用这些方程消元求解

考虑两个方向

发现只考虑左右六十度即可有2n-1个变量

依次写为x1–x2n-1

发现成为一条链状结构

每个限制只链接两个变量

模拟即可

---

https://qoj.ac/problem/5416

考虑倒着做

如果某个角匹配到了某个模型，

就可以将这个矩阵改为通配符

之后贪心

---

Empty up a Bottle

对水量操作可以看作成2的k次方

一次可以进行一组操作，所以如果a+b为奇数，

则可乘2的k次方，也可除2的k次方

不妨设a，b是偶数，c为奇数，

保证c是奇数后

辗转相减求gcd

只要在O（log（A+B））轮内完成

---

https://qoj.ac/problem/1436

每个盒子贡献是x

要大的数尽量占更多的=盒子

所谓更大指更高位

若最高位为2的b次方，

且只有不超过k-1个数字有，

发现他们单独放一个盒子一定为最优解

设x1，y一个盒子

x2一个盒子

且
$$x_1,x_2<2^b<=y$$

$$(x_{1}AND{x}_2)+x_2=x_1+x_2=(x_{1}OR{x}_2)+(x_{1}AND{x}_2)<y+(x_{1}AND{x}_2)$$

证明无论怎么分配都会有k-1个盒子贡献了2的b次方

则b可以删掉

---

https://qoj.ac/problem/5504

考虑容斥贪心

但是限制二选一

2-SAT不是很好处理，不好保证n个0或1

考虑如何连边，同时线段树优化建图，然后缩点

上面限制如果一个没有满足，则要求下面全部满足

发现限制全部长成这个样子

对sx向sy连边，表示当sx是1时，sy也要是1

考虑建立DAG

在上面取点，分割实现一侧为0，一侧为1

枚举他的左边或右边，

让他的前驱或后驱为一半，剩余为另一半即可

考虑加边时的变化

如果一次变化中跳到了小于n或大于2n，则构造不成立

在使用拓扑序加点时，某次落入[n,2n]的区间即是合法解

---

https://www.luogu.com.cn/problem/CF1646F

注意到目标状态不一定要最优，

不能保证可以

考虑换一个目标结果，

将结果转化为每个人从1-n都拿一张

就不会出现已经凑齐了n张牌还必须要失去的结果了

显然不是等价的转化，

但是可以在多项式时间内求解，

接下来考虑贪心，只要一个人手中有重复的牌就往前送，

考虑一个值为一的牌移动多少次，牌和人相互匹配，必然存在一个循环移位，使结果合法

所以最多耗费n（n-1）/2次操作

每个操作有会用n次

所以操作数合法

---

https://qoj.ac/problem/895

一个趣味网络流题

证明一个充分条件

每个颜色最多有（m+1）/2个匹配

将这些1-n个加入到set’中

考虑这些set的大小，

每次只加入一个点，

左边m个点，表示m个颜色，右边n个点，表示要连n个边

每种颜色最多连一个边，边也只能连一个点，容量为一

左右连边，金星二分图匹配，

只要流满就成立

左边每个出度和右边每个入度都是m+1-n，

将右边最后一个拆成m’个，就是一个二分正则图，根据霍尔定理，一定存在完美匹配