J - Jumbled String（构造01串）

原题： https://cn.vjudge.net/problem/Gym-101933J

题意： 有a个00子顺序串，b个01，c个10，d个11，构造01串

解析：

可以从a推出0的数量，b推出1的数量$:(x-1)\ast x/2=a$，然后判断$b+c$是否等于$C_{x+y}^2-C_x^2-C_y^2=x\ast y$，如果是，则说明一定可以。相当于在x个0中插y个1，插在k个0的后面，会得到k个01，x-k个10，直接模拟即可

当然，需要特判ad=0时的情况，因为1个0或0个0，a都是0

#include<bits/stdc++.h> using namespace std; #define LL long long LL o(LL x){ x*=2; LL i; for(i=1ll;;i++){ if(i*(i-1)>x)break; } i--; if(i*(i-1)==x)return i; return -1; } bool cmp(LL a,LL b){ return a>b; } int main(){ LL a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); if(!a&&!b&&!c&&!d)return 0*printf("0\n"); LL x=o(a),y=o(d);//x 0 y 1 if(x==-1||y==-1)return 0*printf("impossible\n"); if(x==1&&y==1){ if(b&&c)printf("impossible\n"); else if(b==1)printf("01\n");//不等于1也不行 else if(c==1)printf("10\n"); else if(b==0&&c==0) printf("0\n"); else printf("impossible\n"); return 0; } else if(x==1){ if(b==0&&c==0)x=0; } else if(y==1){ if(b==0&&c==0)y=0; } LL all=x*y; if((b+c)!=all)return 0*printf("impossible\n"); string s(x,'0'); LL _01=b,_10=c; vector<LL>Insert; while(y--){ LL pos=min(x,_01); _01-=pos;_10-=x-pos; s.insert(pos,"1"); } cout<<s<<endl; }