注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【构造】【数学】【游戏】 Codeforces #97 DIV2 Zero-One  

2011-12-13 16:24:38|  分类: ACM_数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目大意:
一个游戏,有一个01的串,有两个人A、B,A的每次都去掉这个串中的一个元素,使得剩下的串的十进制表示最大,B每次去掉这个串中的一个元素,使得剩下串的十进制表示最小,A先走,当只剩下两个元素的时候结束,
现在给出一个串,由0,1,?,组成,?可以替换成0或者1,输出A、B玩这个串的游戏的时候最后结束的时候,可能的剩下的串,按照字典序输出
数据量10^5

分析:
数据量比较大,不能模拟,需要找规律构造,感觉有点像我科ACM校内赛中的C题,
注意到结果只可能是00,01,10,11的组合,所以逐个分析什么情况下结果分别是00,01,10,11
多列几个例子就找到规律了,每次A都是去掉串中最左的1,B是去掉最左的0

假设一个串没有‘?’,那么设n0,n1分别为0,1的个数,
当n0 > n1时,结果是00,
当n1 > n0+1时,结果是11,
当n0 = n1 或者n0 +1 = n1 时,结果取决于串的末尾(设为last)
如果last = ‘0’ ,结果是10
如果last = '1',结果是01

考虑有'?'的情况
设x0,x1,w分别为串中0,1,?的个数,
如果last != ‘?’,则只需要判断方程
1)x0 + w - t = x1 + t,t表示w中1的个数,0<=t <= w
2)x0 + w - t + 1 = x1 + t
中一个是否有解,如果有表示可以出现n0 = n1 或n0 + 1 = n1 的情况,
判断方程是否有解的时候,因为转换成一个函数后,f(t) = 0是否有解,函数单调,只需要判断最大值>=0,并且最小值<= 0,即可

如果last = ‘?’,
分情况讨论
1) last = '1'时,x1 = x1 +1, w = w - 1,然后用last != ‘?’的方法计算
2) last = '0'时,x0 = x0 +1, w = w - 1,然后用last != ‘?’的方法计算


代码:
#include <cstdio>
#include <cstring>

using namespace std;

char data[100010];
bool ck1(int x0,int x1,int w)//判断方程1)是否有解
{
        return (x0-x1+w >= 0) && (x0-x1-w <=0);
}

bool ck2(int x0,int x1,int w)//判断方程2)是否有解
{
        return (x0-x1+w+1 >= 0) && (x0-x1+1-w <= 0);
}

void work()
{
        int x0,x1,w;
        x0 = x1 = w = 0;
        int len = strlen(data);
        bool b01,b10;
        b01 = b10 = false;
        char last;
        last = data[len-1];
        for(int i = 0;i < len;i ++)
        {
                if(data[i] == '1') x1 ++;
                if(data[i] == '0') x0 ++;
                if(data[i] == '?') w ++;
        }

        if(x0 + w > x1) puts("00");
        
        if(last != '?')
        {
                if(ck1(x0,x1,w) || ck2(x0,x1,w))
                {
                        if(last == '1') b01 = true;
                        if(last == '0') b10 = true;
                }
        }
        else
        {
                //0
                if(ck1(x0+1,x1,w-1) || ck2(x0+1,x1,w-1))
                        b10 = true;
                //1
                if(ck1(x0,x1+1,w-1) || ck2(x0,x1+1,w-1))
                        b01 = true;
        }
        
        if(b01) puts("01");
        if(b10) puts("10");
        if(x1 + w > x0 + 1) puts("11");
}

int main()
{
        scanf("%s",data);
        work();
        return 0;
}
  评论这张
 
阅读(156)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018