4/3
技能点
A. 生成树的计数
论文:周冬《生成树的计数及其应用》(看不懂 pending)
一个栗子:Codeforces 719D
两个做法
- Matrix-Tree + 高斯消元,把这棵树Ctrl+C,Ctrl+V到完全图里n-1次就可以建立一个线性方程组,然后高斯消元就OJBK了。
- Pufer序列 + DP,我投降!
B. 归纳(瞎猜)
宝具Excavation的真名,也许不应该是数据挖掘,而应是数学归纳!
1.博弈
注:Warning! Warning! 前方将出现大量伪证&乱证! v(´ʘ‿ʘ`)v
- Gym101669J 很有意思的博弈!然而并不会,先给个伪证。
先看两个Basic State
(1)每堆石子的个数全为1,那答案很简单,如果n%3=0,Lose,否则Win。
(2)恰有一堆石头个数大于1,Chomp Game, 选手1 Win!
轮到2号选手操作,如果有一堆石头>=3, 或者两堆石头>=2,1号选手就GG了。
(3->0), (3->1), (3->2)
(2,2)->(1,1), (2,2)->(0,1), (2,2)->(0,0)
在模3系下存在3种后继,成功控场!得证!【嘘!小声点,别被发现了】
(3)当有2堆石头>=3时 或者 3堆石头>=2时,选手1 Lose!
(4)像A,2,1,1,1,.... (A>=2)这样的,显然n%3 = 2先手Lose, else Win。
- ARC091 求SG函数,然后归纳分析。
- Anti-Nim: 证明比起Gym101669J这个暴恐分子简单多了。分成 [SG 是否 0] [max 是否大于 1]这四种情况。归纳一下就好。注意:如果最大值大于1,次大值等于1,Chomp Game!
- Bash-Nim: 普通的Nim是模2系下的,BashNim则是模k+1系下的。可以类比。
- 砍树博弈: $sg(u) = (sg(v_1) + 1) XOR (sg(v_2) + 1) $
- 翻硬币模型: 利用了膜2系的特征,很惊人地发现正面朝上的硬币居然互不相干!
- EC-Final的那道SOS题,难证成智障!
2.GCD
- Hiho1584: 我们发现路程\(s\) = \(lcm(w,h)\),然后">"与"v"有且仅有一个交点,所以可以求出有几个点被经过两次。
4/4
啊啊啊啊,挂了一天的机
技能点
A. Alpha-Beta剪枝
划了一天水,DFS死循环,我投降!
B. 不平等的博弈
看不懂,无法理解Surreal Number这种东西,我逃跑!
4/5
施展了NCPC2017
熊输出爆炸。
我觉得我是来搞笑的。全场划水(当然,苟老爷也是来搞笑的)
要思路没思路,要代码没代码,可以说很囍了