codeforces708b// Recover the String //AIM Tech Round 3 (Div. 1)

时间:2024-12-07 00:03:01

题意:有一个01组成的串,告知所有长度为2的子序列中,即00,01,10,11,的个数a,b,c,d。输出一种可能的串。

先求串中0,1的数目x,y。

首先,如果00的个数a不是0的话,设串中有x个0,C(X,2)=a,那么x*(x+1)=2a,解方程(其实只要看sqrt(x)*(sqrt(x)+1)等不等于2a),x没有整数解就IMPOSSIBLE。同理得出1的个数y。如果00个数是0看01个数。

第二,如果x*y!=b+c则IMPOSSIBLE,具体自己举个例子就明白。

最后,先将所有的0组成一个串str,再从右边开始逐个加1。具体来说,在str最右加1个1,01数量增加x个,倒二位置加,增加x-1个......总共要b个01,先往最右增加b/x个1。然后还缺b1个01,在倒二位置加b1/(x-1)个......循环结束。

乱码。。。。。。

//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include <stack>
#include <list>
using namespace std;
const int SZ=,INF=0x7FFFFFFF;
typedef long long lon; int main()
{
std::ios::sync_with_stdio();
//freopen("d:\\1.txt","r",stdin);
lon a00,a01,a10,a11;
cin>>a00>>a01>>a10>>a11;
bool ok1=,ok2=;
lon sq1=sqrt(a00*),sq2=sqrt(a11*);
if(sq1*(sq1+)==*a00)ok1=;
if(sq2*(sq2+)==*a11)ok2=;
lon num0=sq1+,num1=sq2+;
if(a00==&&a01==&&a10==)num0=;
if(a11==&&a01==&&a10==)num1=;
if(num0==num1&&num0==)cout<<<<endl;
else if(ok1&&ok2)
{
if(a01+a10!=num0*num1)cout<<"Impossible"<<endl;
else if(num0==)
{
cout<<string(num1,'')<<endl;
}
else if(num1==)
{
cout<<string(num0,'')<<endl;
}
else
{
string str(num0,'');
lon right1num=a01/num0;
lon rem=num1-right1num;
str+=string(right1num,'');
lon stillneed01=a01-num0*(a01/num0);
for(int i=(int)str.size()-right1num-,j=;i>=;--i,++j)
{
lon cur0=num0-j;
if(cur0==)
{
str=string(rem,'')+str;
break;
}
int right1num=stillneed01/cur0;
str.insert(str.begin()+i,right1num,'');
stillneed01-=cur0*right1num;
rem-=right1num;
}
cout<<str<<endl;
}
}
else cout<<"Impossible"<<endl;
return ;
}