card
需要一块很大的空间(>2m*2m),需要4-8人,需要懂数学中的二进制,需要会异或,需要了解字典序。
如果您们已具备了这些条件,那就让我们在01Trie上行走玩耍吧!
\1. 二进制:一种只采用0和1两个数码,逢二进位的计数法。
\2. 异或:在二进制上的不进位加法,俩个数进行异或,则在相同的二进制位上0⊕0=0、0⊕1=1、1⊕0=1、1⊕1=0。
\3. 字典序:对于一些序列进行排序,不同序列的先后关系是从左到右逐个比较对应的数字的先后来决定的的排序。
\4. Trie树:
Trie****树的简介
Trie这个名字取自“retrieval”,检索,因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。
Trie树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
此外Trie树也称前缀树(因为某节点的后代存在共同的前缀,比如pan是panda的前缀)。
它的关键字都为字符串,能做到高效查询和插入,时间复杂度为O(k),k为字符串长度,缺点是如果大量字符串没有共同前缀时很耗内存。
它的核心思想就是通过最大限度地减少无谓的字符串比较,使得查询高效率,即「用空间换时间」,再利用共同前缀来提高查询效率。
Trie****树的特点
假设有5个字符串,它们分别是:Code,Cook,Five,File,Fat。现在需要在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这5个字符串依次进行字符串匹配,那效率就比较低,有没有更高效的方法呢?
如果将这5个字符串组织成下图的结构,从肉眼上扫描过去感官上是不是比查找起来会更加迅速。
Trie树
· 通过上图,可以发现Trie树的三个特点:
· 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
· 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
· 每个节点的所有子节点包含的字符都不相同。
· Trie****树的插入操作
· Trie树的插入操作很简单,其实就是将单词的每个字母逐一插入Trie树。插入前先看字母对应的节点是否存在,存在则共享该节点,不存在则创建对应的节点。比如要插入新单词Cook,就有下面几步:
· 插入第一个字母c,发现Root节点下方存在子节点c,则共享节点c。
· 插入第二个字母o,发现c节点下方存在子节点o,则共享节点o。
· 插入第三个字母o,发现o节点下方不存在子节点o,则创建子节点o。
· 插入第三个字母k,发现o节点下方不存在子节点k,则创建子节点k。
· 至此,单词cook中所有字母已被插入Trie树中,然后设置节点k中的标志位,标记路径root->c->o->o->k这条路径上所有节点的字符可以组成一个单词Cook。
Trie****树的应用
事实上Trie树在日常生活中的使用随处可见,具体来说就是经常用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
1、人数:4-8人。
2、空间:>2m*2m。
3、前置知识:二进制、异或、字典序、01Trie的树形结构。
4、卡牌:
(1)、足够多的0和1的数码块。
(2)、带有1-511的数字及其二进制表示的基本牌。
(3)、带有符号“<<”“>>”“~”“I”“C”的技能牌。
(4)、用以计分的二进制滑块板。
(5)、用以记录击败次数的标记:权;死亡标记:亡;金奖标记、银奖标记和铁奖标记。
**注:**1.请玩家自行决定博弈次数,最后将金奖数目作为第一关键字,银奖数目作为第二关键字,铜奖数目作为第三关键字,铁奖数目作为第四关键字进行排名,决定最后的名次与获胜者。
2.玩家人数用n来表示。
3.从开始博弈到结束博弈,任何一个人的任何一枚权都可以随时转让给他人。
4.⌊⌋表示向下取整。
5.此过程必须在打出技能牌之前进行,所以原有2张技能牌,新摸一张,然后立即打出是不合法的,必须先弃置一张,再决定是否使用。
6.见详细讲解。
(一)****、博弈前:
1、每位玩家发一个初始值为100(1100100)的用以计分的二进制滑块板。
2、取n(注2)张带有“<<”符号的技能牌,2n张带有“>>”符号的技能牌,n张带有“~”符号的技能牌,n张带有“I”符号的技能牌和2n张带有“C”符号的技能牌洗乱,作为技能牌堆。
(二)****、博弈中:
1、开局:
(1)、将1-31的数字牌洗乱,每位玩家随机抽取一张纸牌,作为自己的初始数值。
(2)、将每位玩家的初始数值插入由01数码和一个无意义的根构成的十一层01Trie树中,并摆出一条全为0的路径表示0。
(3)、将剩余所有数字牌洗乱,作为基本牌堆。
(4)、随机从基本牌堆中抽出⌊n/2⌋张牌(不再放回去),在01Trie上其最高位的1的位置与次高位的1的位置分别放置一个亡标记。
(5)、选取在构造的01Trie上高度最高的1最低的一位玩家(若有多位则任选一位)作为起始玩家,由起始玩家开始,顺时针摸牌,每人首先摸2张基本牌作为起始手牌。
2、游戏进行时:
(1)、由起始玩家开始,顺时针的每位玩家轮流坐庄,开始自己的回合前可摸两张基本牌牌。
(2)、每玩家每回合首先必须打出一张基本牌,并自行选择用以异或自己在01Trie上的序列或用以异或公共序列(初始为0的序列)。
(3)、若某位玩家在进行完基本操作后,他选择操作的序列(自己的或者公共的)上有两个1的位置放置有两个亡标记,则这位玩家被淘汰,但所有分数保留不变。同时拿下这两个亡标记,该玩家获得一枚权(注3)。
(4)、若某位玩家在01Trie上的序列的1为第5-9层的第一个1,则获得(i(层数)-4)*100的分数。
(5)、若某位玩家在01Trie上的序列的1为第5-9层的第二个1,则获得(i(层数)-4)*75的分数。
(6)、若某位玩家在01Trie上的序列的1为第5-9层的第三个1,则获得(i(层数)-4)*50的分数。
(7)、若某位玩家在01Trie上的序列的1为第5-9层的第四个1,则获得(i(层数)-4)*25的分数。
(8)、每玩家每回合其次可决定是否获取技能牌,若想要获取技能牌,则打出一张手牌,并翻开基本牌堆最上面的一张牌作为判定牌,计算打出的牌、判定牌以及玩家在01Trie上的序列的异或和,若此异或和中各二进制位上1的个数>⌊2/3*该玩家在01Trie上的序列忽略前导零的序列个数⌋(注4),则可以从技能牌堆上摸1张技能牌,并且同时扣除50分,并将技能牌正面朝上置于计分板前。
(9)、若该位想要获取技能牌的玩家手中有权,也可以打出一张权直接获得一张技能牌。
(10)、由于每位玩家手中的技能牌数上限为2张,所以,若原有2张技能牌,又重新获取一张后必须弃掉一张(注5)。
(11)、每玩家每回合最后可以选择是否打出一张技能牌,打出后,询问所有玩家是否使用“C”技能抵消。若有玩家使用“C”技能抵消则此技能牌与打出的“C”技能牌均作废;若没有玩家使用,则对于自己在01Trie上的序列或公共序列触发对应技能(注6)。
(12)、若在玩家a的某次对于自己的序列的操作后两位玩家(a,b)在01Trie上序列的最高的1处于同一位置,则若在接下来的b的回合结束后依然处于同一位置,则比较两者的次高的1的高度(次高相同则平局)。若a高于b,则淘汰b,a增加一枚权且分数增加b分数的⌊1/3⌋,b的分数减少为现在的⌊2/3⌋。若b高于a ,则淘汰a,b增加一枚权且分数增加a分数的⌊1/3⌋,a的分数减少为现在的⌊2/3⌋。
(13)、若在玩家a的某次对于公共序列的操作后公共序列与b玩家在01Trie上序列的最高的1处于同一位置,则若在接下来的b的回合结束后依然处于同一位置,则比较b与公共序列的次高的1的高度(次高相同则平局)。若公共序列高于b,则淘汰b,a增加一枚权且分数增加b分数的⌊1/3⌋,b的分数减少为现在的⌊2/3⌋。反之,则不进行操作。
(14)、每玩家每回合结束时只允许保留两张基本牌作为自己的手牌,其余的基本牌必须全部弃置。
\3. 游戏结束时:
(1)、若公共序列中有1达到最高层,则该次博弈结束。
(2)、若玩家a的序列中有1达到最高层,则该位玩家获得666分,并且该次博弈结束。
(三)****、博弈后:
\1. 每次博弈后每位玩家的总分等于计分板上的分数+手中的权的数量*100,每次博弈按得分高低排名,得分最高者获金奖,得分次高者获银奖,得分第三高者获铜奖,其余玩家获铁奖。
\2. 见注1。
(一)****、计分滑块板:
十竖列01滑块均可上下滑动,以红色框内的数字构成二进制分数。
e.g.100(1100100):
(二)****、技能牌:
1、“<<”:读作“左移”。
作用:将01Trie上的二进制数数位均向上移动一位,最下方用0补齐。
2、“>>”:读作“右移”。
作用:将01Trie上的二进制数数位均向下移动一位,最上方用0补齐。
3、“~”:读作“取反”。
作用:将01Trie上二进制序列最高的1及其以下数位进行01取反。
4、“I”:读作“插入”(Insert)。
作用:将01Trie上二进制序列中某个1的相邻的0改为1。
5、“C”:读作“清除”(Clear)。
作用:阻止他人使用技能或清除01Trie上二进制序列中某个1。