CF135C Zero-One

传送门

码农题

本题的数据范围很大，暴力会TLE，所以是一道结论题，但是细节很多，考虑一定要周全。

规律

设 1 的数量 $x_1$，0的数量 $x_0$，问号的数量 $x_x$。

最优取

通过题目不难发现，若保持结果尽量大，就会从左向右取 0；若保持结果尽量小，就会从左向右取 1。

例 1：1010

最后要剩两位数所以会取掉一个 0 和 1。若取右边的 1，那么最后一定是 10，但若取左边的 1，有可能会剩 01，所以从左向右会更优；若取右边的 0，会使结果变成 01，而取左边的 0，结果会是 10，所以从左向右取 0 更优。

我们会发现在 $x_1=x_0$ 时，结果由最后一位影响。

最后一位的影响

在 $x_1=x_0$ 时，因为最优取是从左向右的，而结束时取得数量是相同的，且最后一位一定不会被取，所以 $x_1=x_0$ 时结果的第二位是原序列的最后一位，结果的第一位是原数列的最后一位的相反的值。

先手优势

因为先取 1，所以在判断的时候要特殊注意一下。

例 2：11100

例 3：1100

根据最优取我们发现例 2 例 3 的结果都是 10，这就体现出先手的优势了，所以在判断时要特判 $x_1=x_0+1$ 情况的出现。

两种数的数量不同

例 4：1000

例 5：1110

我们可以发现如下的结论：当 $x_1>x_0+1$ 是结果必是 11，当 $x_1<x_o$ 时结果必是 00。

问号的情况

本题最大的困难就是对问号的处理。问号的存在使判断过程变得复杂，但既然是结论题，一定还是有规律的。

根据最优取，我们知道当 $x_1=x_0$ 时，结果由最后一位影响，而再根据先手情况，我们才有更全面的结论：当 $x_1=x_0$ 或 $x_1=x_0+1$ 时，结果由最后一位影响。

而问号的出现，可以用来判断是否有可能出现某种情况，所以我们只要判断是否会出现对应的情况即可。

不难发现，当 $x_0+x_x>x_1$ 时结果会出现 00 的情况，当 $x_1+x_x-1>x_0$ 时会出现 11 的情况。

而当 $x_x>=x_0-x_1$ 且 $x_0>=x_1$ 或 $x_x>=x_1-x_0-1$ 且 $x_1>=x_0+1$ 时，问号就可以使 $x_1=x_0$ 或 $x_1=x_0+1$ 的情况出现了。而这时就可以用最后后一位的结论代入即可。

代码

#include<cstring>
#include<iostream>
#include<string>
#include<map>
using namespace std;
int x_1,x_0,x_x;
string s_s;
map<string ,int>mp;//用来判断结果是否有出现的可能
int main(){
  cin>>s_s;//读入序列 
  for(int i=0;i<s_s.length();i++)//统计 x_1 x_0 x_x 
    if(s_s[i]=='0')x_0++;
    else if(s_s[i]=='1')x_1++;
    else x_x++;
  mp["11"]=0;mp["10"]=0;mp["01"]=0;mp["00"]=0;//清空 
  if(x_1+x_x-1>x_0)mp["11"]=1;
  if(x_0+x_x>x_1)mp["00"]=1;
  if(((x_x>=x_0-x_1)&&x_0>=x_1)||(x_x>=x_1-x_0-1&&x_1>=x_0+1)){//问号使 x_1=x_0 和 x_1=x_0+1 的情况出现 
    if(s_s[s_s.length()-1]=='1')mp["01"]=1;//最后一位判断
    else if(s_s[s_s.length()-1]=='0')mp["10"]=1;//最后一位判断
    //最后一位是问号的判断 
    else if((x_x>(x_1-x_0)&&x_1>=x_0||x_x>(x_0-x_1)+1&&x_0>=x_1+1)&&x_x>1)mp["01"]=mp["10"]=1;//当问号为1或没有时，最多只会出现01和10的一种情况 
    else {
      if(x_1>x_0)mp["10"]=1;
      else mp["01"]=1;
    }
  }
  //输出 
  if(mp["00"])cout<<"00"<<endl;
  if(mp["01"])cout<<"01"<<endl;
  if(mp["10"])cout<<"10"<<endl;
  if(mp["11"])cout<<"11"<<endl;
  return 0;
}