01trie树

基本介绍

01Trie树其实就是Trie树的一种运用,普通的Trie树只是用来存储和查找字符串,而01Trie树只是将存储的字母变成了数组的二进制每一位,即0和1.

01Trie树主要是用来求解异或最值问题。

01Trie树特点如下:

1、一般01Trie树最多只有32层,因为最多31位二进制位,其中每个节点的两条边都表示某一位是0还是1,某条路径从根节点到叶子结点就得到了一个二进制数。

2、从上到下分别为某个数二进制的最高位和最低位。

3、可通过贪心的策略来寻找与x异或结果最大(最小)的数,即优先找和x的二进制的未处理的最高位值不同(相同)的边对应的点,这样保证结果最大。

阅读更多...

SG函数

在讲解SG函数之前先了解一下必胜点和必败点,也就是所谓的必胜态和必败态。

P点(必败点):当你处于这个情况的时候,无论进行怎样的操作,对方都能取胜。

N点(必胜点):当你处于这个情况的时候,你能进行恰当的操作,保证一定能取胜。

必胜点和必败点的性质:

1、所有终结点是必败点P。(一般都是以此为基本前提进行推理,换句话说,我们以此为假设)。

2、从任何必胜点N操作,至少有一种方式可以进入必败点P。

3、无论如何操作,必败点P都只能进入必胜点N。

阅读更多...
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信