2018-Sp55-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.2.jpg,600px)]]
[/wiki/2018-team3 返回Helianthus]
[https://ac.nowcoder.com/acm/contest/296#question]
== 流水账 ==
== 总结 ==
=== LYK ===
zimpha题，好楠楠。
=== Heltion ===
=== Jhguai ===
== 题解 & 补题 ==
* D ：先确定决策，x->y，从高到低位，如果相同则不变，否则考虑是否把x的1去掉，如果去掉后x仍然大于y则去掉，否则把之后x的所有1都去掉再-1，再把多余的1去掉。可以发现这样计数的答案是变化位及之前的x去掉的1的个数（x=1,y=0），和变化位之后x中1的个数和y中0的个数。这个东西可以通过O(N）的数位DP来统计（以前只会统计单个变化量，每个变化量贡献为1的数位DP...）。[i][j][l][p]状态表示取到i位，j表示y是否等于n，l表示x是否等于y，p表示现在是变化位之前(0)，在变化位后且之后位上x=y(1)，在变化位后且之后位上x>y(2)，需要维护f,g两个数组，表示x,y的方案数和最终答案总和。 [wiki:helianthus-Sp55-D 代码]
* C : Hackenbush-graph 转换成边权为1的树上删边游戏。当边为1，子树sg=原sg+1；当边为偶数，子树sg=原sg异或1；当边为奇数，子树sg=原sg。原树sg=子树sg异或和。 DFS时用一个该子树sg理论值，能使得先手必胜。
[/wiki/2018-team3 返回Helianthus]
https://ac.nowcoder.com/acm/contest/296#question
流水账
总结
LYK
zimpha题，好楠楠。
Heltion
Jhguai
题解 & 补题
- D ：先确定决策，x->y，从高到低位，如果相同则不变，否则考虑是否把x的1去掉，如果去掉后x仍然大于y则去掉，否则把之后x的所有1都去掉再-1，再把多余的1去掉。可以发现这样计数的答案是变化位及之前的x去掉的1的个数（x=1,y=0），和变化位之后x中1的个数和y中0的个数。这个东西可以通过O(N）的数位DP来统计（以前只会统计单个变化量，每个变化量贡献为1的数位DP...）。[i][j][l][p]状态表示取到i位，j表示y是否等于n，l表示x是否等于y，p表示现在是变化位之前(0)，在变化位后且之后位上x=y(1)，在变化位后且之后位上x>y(2)，需要维护f,g两个数组，表示x,y的方案数和最终答案总和。 代码
- C : Hackenbush-graph 转换成边权为1的树上删边游戏。当边为1，子树sg=原sg+1；当边为偶数，子树sg=原sg异或1；当边为奇数，子树sg=原sg。原树sg=子树sg异或和。 DFS时用一个该子树sg理论值，能使得先手必胜。