RDC去省赛玩前の日常训练 Chapter 1

时间:2024-01-03 11:57:50

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

熊输出爆炸。

我觉得我是来搞笑的。全场划水(当然,苟老爷也是来搞笑的)

要思路没思路,要代码没代码,可以说很囍了