博弈论

arc-116

 2021.03.28 21:54  2023.09.01 18:14  ACM  DP  博弈论 󰈭 523字

自以为A了一道精妙的DP题结果被第二道同样思想的DP卡死 D 总和给定下进行NIM必败态计数给出n、m，表示总共有n堆可空石堆$ {a_i}$，要求满足$\sum a_i = m, \bigoplus a_i=0$，查询这样的序列的个数。感觉上可以称之为非常经典的题目。设置dp状态：dp[i]表示n堆石子和为i，异或和为0的序列数量。 ...

2019-SWERC

 2020.10.17 00:09  2023.09.01 18:14  ACM  最短路  卡特兰数  分段打表  博弈论 󰈭 3196字

参考博客： https://www.cnblogs.com/heyuhhh/p/12941654.html K 图上的路径存在问题(?) ->建反图进行染色建反图，用rot的每个邻点去对整张图染色，被染色的点就意味着可以走到该颜色所代表的邻点。我们允许每个点最多被染色两次，这是因为rot的邻点一旦被超过一个点染色，那么就一定不合法；所以对图中每个点而言，如果其被染色次数大于等于2，那么其出边所对应的一系列点的更新也已经都完成，再次染色增加染色次数没有任何意义，并不会改变“不合法”这一性质。 ...