贪心——cf708b

先求0,1的个数,然后贪心输出01即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll a,b,c,d,tot1,tot0;
int main(){
    cin>>a>>b>>c>>d;
    //a=0,b=0的情况优先考虑
    if(!a && !b && !c && !d){
        puts("0");return 0;
    }
    //判断a=0的情况 
    if(!a&&!b&&!c)tot0=0;else tot0=1;
    //判断d==0的情况
    if(!d&&!b&&!c)tot1=0;else tot1=1;
    
    if(a)tot0=(int)(sqrt(a*2))+1;
    if(d)tot1=(int)(sqrt(d*2))+1;
     
    if(tot0*(tot0-1)/2!=a || tot1*(tot1-1)/2!=d || tot0*tot1!=b+c){
        puts("Impossible");return 0;
    }
    
    while(b){
        if(b>=tot1){
            cout<<0;
            b-=tot1;
            tot0--;
        }
        else if(c>=tot0){
            cout<<1;
            c-=tot0;
            tot1--;
        }
    }while(tot1)cout<<1,tot1--;
    while(tot0)cout<<0,tot0--;
    
}

 

上一篇:【UOJ567】【IOI2020】Biscuits(DP)


下一篇:SEERC 2020 题解