IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: 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

url

大意:
alice和bob进行博弈。给定一个字符串由X和.组成,每个人每次进行一次操作为将连续数量的"."变成"X",其中alice每次要求的连续数量为a,bob为b,且a>b.

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类区间。

(真是伤脑壳。。。)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k;
ll t;
char s[300010];
ll a,b;
bool solve()
{
	bool c33=0;
	ll len;
		    ll c1=0,c2=0,c3=0;
	for(int l=1,r=1;l<=n;l=r+1,r=l)
	    {
	    	if(s[r]=='X') continue;
	    	while(r<n&&s[r+1]=='.') r++;//分段 
	    	ll d=r-l+1;
	    	if(d<b) continue;
	    	if(d>=b&&d<a)
	    	{
	    		
	    		return 0;
	    		continue;
			}
			if(d>=a&&d<2*b)//一人一个 
			{
				c2++;
				continue;
			}
			if(d>=2*b)
			{
				c3++;
				len=d;
				continue;
			}
	    	//printf("%lld\n",d);
		}
		//cout<<c1<<" "<<c2<<' '<<c3<<endl;
		if(c2%2) c33=1;//是奇数,所以要先手去抢一个来 ,先手一定先拿这个,那么结果是
		//全部拿完c3后轮到bob行动 
		if(c3>=2)
		{
			//cout<<"NO"<<endl;//可以拥有c1类,bob必胜 
			return 0;
		}
		if(c3==0)
		{
			if(c33==1)
			{
			    //cout<<"YES"<<endl;
				return 1;
			} 
			else
			{
			//	cout<<"NO"<<endl;
				return 0;
			}
		} 
		ll num=0;
		if(c3==1)
		{
			bool fsd=0;//是否可以截成不包括c2,c4; 
			for(int i=0;i<=len-a;++i)
			{
				ll llen=i;ll rlen=len-a-i;
				if(llen>=b&&llen<a) continue;
				if(rlen>=b&&rlen<a) continue;
				if(llen>=2*b) continue;
				if(rlen>=2*b) continue;
				fsd=1;
				num=(llen>=a&&llen<2*b)+(rlen>=a&&rlen<2*b);
				if((c2+num)%2==0) return 1;
			}
			
		} 
		return 0;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    scanf("%lld",&t);
    while(t--)
    {
    	scanf("%lld%lld",&a,&b);
	    scanf("%s",s+1);
	    n=strlen(s+1);
	    if(solve()) printf("YES\n");
	    else printf("NO\n");
	}
	return 0;
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-26 12:01:52  更:2022-04-26 12:06:26 
 
开发: 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-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码