| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> Codeforces E. Game With String -> 正文阅读 |
|
[数据结构与算法]Codeforces E. Game With String |
大意: alice先手。问是否能让alice必胜。 思路: 惊奇地发现这是一个非公平博弈(bob占优势,可恶,可怜的alice!),一开始想着SG函数去做,打算用状压来处理情况的,但是思路乱的不行,还是放弃了。 发现每一段连续的"."都是互不干扰的,所以我们可以一段一段来看。 设连续的长度为len。 1.len<b: 很好,大家都没得玩,谁都放不了,不必考虑。 2.len>=b&&len<a: 只有bob能放。这时bob必赢,因为Alice能放的bob都能放,如果哪次bob除了这一段len已经没有选择了,就说明alice也同样没有选择了,那么bob只要放在这里游戏就结束了。 3.len>=a&&len<2*b: 大家都只能在这里放一次,一次性用品。 4.len>=2*b: 对bob来说算是很长的区间了。如果对于这个区间bob能够先手的话,他一定可以构造出一个2类区间,那他就赢了。所以只要有两个这样的区间,bob就同样一定赢了。如果0个的话,那大家就算公平竞争了,一人用一段3类区间,看谁倒霉刚好轮空就是了。(考虑3类区间的奇偶性).接下来就是只有一个4类的情况了。那么考虑alice先手:她会选择尽可能截断这个长区间,并且要保证两边的多出来的区间不是2类也不是4类(2类不用说了,如果有四类的话,那bob就可以构造出一个2类,那他也必胜),如果能做到这个的话,那她就能跟bob公平竞技了,同上,考虑3类的奇偶性。同时注意,还要加上alice截断后可能产生的3类区间。 (真是伤脑壳。。。)
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 | -2024/11/26 7:31:46- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |