Recover the String

题目链接：

构造

这题乍一看很难构造，但是如果知道了整个字符串中'0'和'1'的个数n0和n1，就很好构造了：

1.将整个字符串填满'1'，在所有的1右边填x个'0'，那么'10'就有x*n1个了，一直填到还需要'10'的个数t1小于n1个；

2.再从右边数n1-t1个'1'并在它前面添加一个'0'；

3.删去多余的'1'.

如此看来，构造并不困难，难的是判断何时Impossible.我们可以看到a1和a4必须是(1+n)*n/2的形式，而a2+a3肯定等于n0*n1（对于每一个'1'，若左边有x个'0'，那么右边有n0-x个'0'）。但是这样直接交还会WA，还有一种情况没有考虑：只有'1'或只有'0'的情况，这种情况特判就好啦。

代码如下：

1 #include
     
       2 #include
      
        3 using namespace std; 4 int a,b,c,d; 5 char s[1000005]; 6 int main(void){ 7     scanf("%d%d%d%d",&a,&b,&c,&d); 8     if(a+b+c+d==0){ 9         printf("1\n");10         return 0;11     }12     int n0=(int)sqrt(2*a)+1;13     if(n0*(n0-1)/2!=a){14         printf("Impossible\n");15         return 0;16     }17     int n1=(int)sqrt(2*d)+1;18     if(n1*(n1-1)/2!=d){19         printf("Impossible\n");20         return 0;21     }22     if(n0+n1>1000000){23         printf("Impossible\n");24         return 0;25     }26     if(c+b+d==0){27         for(int i=0;i
       
        =0;--i){49         if(k==n1-t1){50             s[i]='0';51             break;52         }53         if(s[i]=='1')k++;54     }55     for(;i>=0;--i){56         if(s[i]=='1')k++;57         if(k>n1)s[i]='0';58     }59     printf("%s\n",s);60 }