2019-Sp1-team4

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest Information ==
[http://codeforces.com/group/H7nsMkHC7I/contest/244112]
[[Image(20190518.png,700px)]]


== 流水账 ==
== 总结 ==

'''sui'''
全场英语最菜读了最多的题，谢谢队友给了我练习读题的机会。开场没有意识到die是色子的意思懵逼了一会儿才开了A题，之后趁金天wa F题的时候跟zx讨论出G题。之后读了B题跟zx简单说了下（端茶倒水读题选手）。之后博弈大师jt上线写掉了H和F，我跟zx讨论J题，后来发现题意理解有点问题（说来你可能不信，都是题目没说清楚）。之后按位做掉了。E题后缀数组归我，中间因为板子用的有点问题耽误了一段时间。（此处小故事，上周用这个板子刚过了一道题，调的时候坚信板子没错，错的是这个世界，于是到现在我都不明白上周那题凭什么没bug）。最后终于因为数组忘记加倍成功贡献罚时。最后看着zx一发过了D之后开始垂zi死bao挣zi扎qi。


'''zx2018'''
有点摸感觉，J题意读错想了半天，F题没转过来，D倒是知道是AC自动机+高斯，一开始觉得有点烦，后面写起来发现还好（很久没写AC自动机了，还现场学习了一下fail 菜菜。假博弈G有点飘，想到了分色还是好做，真博弈H的sg这一套感觉不是很懂，博弈有点欠缺，全靠躺，有待加强。后缀数组的板子debug没帮上忙，帮jt看了个F数组越界的bug。
最后的两个题，一个I想太多了，没有去更多地挖掘题目性质，后面sui想了个不断从边界放桌子的想法，感觉比较可行。还改锻炼下模拟题C这种，后期能上场来一发。新队伍的一训，有卡壳的地方，导致后面两题没太多时间了。



== 补题 ==

== 题解 ==
'''A''' 签到

'''B''' 无脑宽搜

'''C'''

'''D'''
用AC自动机对所有字符串建树。对每个节点（状态）维护一下到这个点之后期望还需要抛几次硬币才会结束。很显然所有这些值有等式关系。对于一个点，如果有H/T边，那么直接连，否则一直沿着fail走到有H/T的地方，建方程高斯消元后，根节点的值即为答案。

'''E''' 
因为不限数量所以按字典序从小到大依次覆盖，直到完全覆盖就可以了。
字典序只需要倍长字符串之后跑后缀数组就可以了。(数组加倍，sb又忘记了）
覆盖的话我用了一个set维护，记录当前已经覆盖了多少个点。每次插入找到set里维护的前驱后继位置计算本次多覆盖了几位更新维护的值就可以了。

'''F''' 
当B从0到(1<<n)-1增加时，C的值是在一个范围的。相当于问一个区间内的（考虑最高位进位）数在二进制下有k个1的有多少个，可以数位dp；也能直接从高位到低位通过组合数相加，分两段即可。

'''G'''

马在棋盘上的走法是可以染色的，每次颜色相同走一步一定颜色不同，颜色不同一步之后颜色会相同。最后结束一定颜色相同（同一个点) 所以检查起点颜色是否相同就可以了。

'''H'''


'''I'''


'''J'''
显然能够一位一位做(题意原来是每次单独跑最后求收益总和啊……)。每一位跑一个dfs，把树上的每一个连通块的收益相加，sigma{C(num,2) * (1<<k)}。

Contest Information

http://codeforces.com/group/H7nsMkHC7I/contest/244112

流水账

总结

sui

全场英语最菜读了最多的题，谢谢队友给了我练习读题的机会。开场没有意识到die是色子的意思懵逼了一会儿才开了A题，之后趁金天wa F题的时候跟zx讨论出G题。之后读了B题跟zx简单说了下（端茶倒水读题选手）。之后博弈大师jt上线写掉了H和F，我跟zx讨论J题，后来发现题意理解有点问题（说来你可能不信，都是题目没说清楚）。之后按位做掉了。E题后缀数组归我，中间因为板子用的有点问题耽误了一段时间。（此处小故事，上周用这个板子刚过了一道题，调的时候坚信板子没错，错的是这个世界，于是到现在我都不明白上周那题凭什么没bug）。最后终于因为数组忘记加倍成功贡献罚时。最后看着zx一发过了D之后开始垂zi死bao挣zi扎qi。

zx2018

有点摸感觉，J题意读错想了半天，F题没转过来，D倒是知道是AC自动机+高斯，一开始觉得有点烦，后面写起来发现还好（很久没写AC自动机了，还现场学习了一下fail 菜菜。假博弈G有点飘，想到了分色还是好做，真博弈H的sg这一套感觉不是很懂，博弈有点欠缺，全靠躺，有待加强。后缀数组的板子debug没帮上忙，帮jt看了个F数组越界的bug。

最后的两个题，一个I想太多了，没有去更多地挖掘题目性质，后面sui想了个不断从边界放桌子的想法，感觉比较可行。还改锻炼下模拟题C这种，后期能上场来一发。新队伍的一训，有卡壳的地方，导致后面两题没太多时间了。

补题

题解

A 签到

B 无脑宽搜

C

D

用AC自动机对所有字符串建树。对每个节点（状态）维护一下到这个点之后期望还需要抛几次硬币才会结束。很显然所有这些值有等式关系。对于一个点，如果有H/T边，那么直接连，否则一直沿着fail走到有H/T的地方，建方程高斯消元后，根节点的值即为答案。

E

因为不限数量所以按字典序从小到大依次覆盖，直到完全覆盖就可以了。

字典序只需要倍长字符串之后跑后缀数组就可以了。(数组加倍，sb又忘记了）

覆盖的话我用了一个set维护，记录当前已经覆盖了多少个点。每次插入找到set里维护的前驱后继位置计算本次多覆盖了几位更新维护的值就可以了。

F

当B从0到(1<

G

马在棋盘上的走法是可以染色的，每次颜色相同走一步一定颜色不同，颜色不同一步之后颜色会相同。最后结束一定颜色相同（同一个点) 所以检查起点颜色是否相同就可以了。

H

I

J

显然能够一位一位做(题意原来是每次单独跑最后求收益总和啊……)。每一位跑一个dfs，把树上的每一个连通块的收益相加，sigma{C(num,2) * (1<

附加文件