P8819 [CSP-S 2022] 星战
考虑本题需要判断的是每个点的出度是否都为 。
首先每个状态时总边数时容易计算的。那么接下来只要判断是否每个节点的出度都是奇数。
每个元素的奇偶性的判断,容易想到哈希。对每一个点赋一个随机权值,统计当前状态下所有出度的权值异或和,这也是容易的。
如果异或和不等于所有点的权值异或和,那么答案是 NO
。
考虑本题需要判断的是每个点的出度是否都为 。
首先每个状态时总边数时容易计算的。那么接下来只要判断是否每个节点的出度都是奇数。
每个元素的奇偶性的判断,容易想到哈希。对每一个点赋一个随机权值,统计当前状态下所有出度的权值异或和,这也是容易的。
如果异或和不等于所有点的权值异或和,那么答案是 NO
。
作者:Enucai
文章链接:http://enucai.github.io/2022/12/01/hash-random-P/
版权声明:本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 协议。转载请注明出处!