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}?\frac{1}{(1?x{)}^2}$$

將 $x$ 恢復為 ${\left(\frac{n?i}{n}\right)}^{j?1}$，得到最終結果：

$$\frac{i}{n}?\frac{1}{{\left(1?\left(\frac{n?i}{n}\right)\right)}^2}=\frac{i}{n}?\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’個，就是一個二分正則圖，根據霍爾定理，一定存在完美匹配