老 K 的博客

link

link

垫底了

不知道该写THUWC2019还是THUWC2020，由于有一场THUWC2019了，于是就写THUWC2020算了

官方有些地方写的2019,有些地方写的2020

Day -?

听教练说THU只给未来的学生用电脑，于是我就没资格用了，只能带自己的电脑去。

果断的带上了机械键盘，血赚（

link

题意

有\(n\)个变色龙，初始都为蓝色，没吃过任何球。每次可以投入一个红球或一个蓝球，然后会有一只变色龙吃掉它。如果一只变色龙吃掉的红球比蓝球多，就会变为红色，如果蓝球比红球多，就会变为蓝色，如果一样多就不会变。

求有多少个长度为\(k\)的投球序列满足存在一种吃法使得最后每个变色龙都是红色。

\(n,k\le 5\cdot 10^5\) ### 题解 枚举投入的红球数\(r\)，蓝球数\(b\)，使得\(r+b=k\)。

如果\(r<b\)则显然不可能。

如果\(r=b\)则要求最后一个球是蓝球，且存在一种找出\(n\)对红球-蓝球的配对关系使得红球在蓝球左边，且每个球最多被选一次。

如果\(r>b\)则至少有\(r-b\)个变色龙不用考虑顺序，只需要找出\(max(n-(r-b),0)\)个一样的配对关系即可。

定义\(f(r,b,n)\)表示\(r\)个红球，\(b\)个蓝球，要找出\(n\)个配对关系的方案，那么\(r=b\)方案就是\(f(r,b-1,n-1)\)，\(r>b\)就是\(f(r,b,max(n-(r-b),0))\)。

考虑\(f(r,b,n)\)的求法。

发现如果可以选出配对关系，一定存在一种方案红球是前\(n\)个红球，蓝球是后\(n\)个蓝球。那么就是说第\(b-n+1\)个蓝球前一定有一个红球，\(b-n+2\)个蓝球前一定有2个红球\(\dots\)。

如果把选球的过程相当于从\((0,0)\)每次可以\(x+1\)或\(y+1\)，要求走到\((r,b)\)的方案数，那么一定不能经过\(y=x+(b-n+1)\)上方的部分。

对于经过了的情况，我们把第一次到达之后的\(x+1\)都变成\(y+1\)，\(y+1\)变成\(x+1\)，也就是关于这条直线对称，那么最后走到的点就是\((r,b)\)关于这条直线对称的点。

两个组合数算一下就可以了。

时间复杂度\(O(n+k)\)。

太妙了。

link

AFOed 2019.11.17.

问题

给定\(n,k,f_0\dots f_{k-1},a_1\dots a_{k}\)，定义\(f_n=\sum_{i=1}^k f_{n-i}a_i\)，求\(f_n\)。

link

题意

给定一张n+n的二分图，每条边有\(p_{i,j}\)的概率出现，求存在完美匹配的概率。

\(n\le 7,15s\)

Subtask: \(n\le 6,7s\)

题面

给定\(n\)个长度为\(k\)的置换，对于每个子段，求出通过使用零次或多次这些置换可以从初始排列\((1,2,\dots,k)\)得到的不同排列个数。

\(n\le 2\cdot 10^5,k\le 5\)