6953专题

UVALive 6953 Digi Comp II(拓扑)

题意:    m个开关,n个球。每个开关有两个状态,左或右,左则滚到左边,右则滚到右边。每滚一个球状态则反转一次。问最后每个开关的状态是怎样的。 解题:   因为球数实在太多(10^18),一个一个模拟果断不行,而开关的最后状态只取决于滚过的球数和初始状态。所以计算出每个点球的流量并记录节点初始的状态即可。 注意:左右可以连同一个点!!!并且一开始不仅仅只有一为度数为零的