AIM Tech Round 3 (Div. 2) D. Recover the String 构造、贪心、多坑、WA162

My Solution

构造、贪心、多坑、WA162

首先用杨辉三角求组合数打个表， 然后匹配一下找出 cnt11, cnt00，也就是1、0的个数   //这个做法比较暴力了嘿嘿 -_-||

然后如果 (a01 + a10 != cnt00*cnt11) 则没有答案

否则 初始是 000000111111这样的

然后每次if(a10 >= lef0){
cout<<1;
lef1--;
a10 -= lef0;
}
else{
cout<<0;
lef0--;
}

这样就是优先搞出大的10， 因为这个时候后面的0比较多 第一次 a10 >= lef0 就把 一个1提到最前面 a10 -= lef0， 否则是0 lef0--， 然后考虑下一位

此外就是  0 0 0 0, 0 1 0 0, 0 1 1 0, 1 0 0 0, 0 0 0 1这些数据的特殊处理了， 当统计出的cnt11 == -1 是 1的个数可能是1也可能是0 根据 a10 和 a01而定， cnt00 == -1同理

0 1 1 0 没有考虑， Wrong answer on test 162 呵呵哒 WA的最远的一次了 开心

复杂度O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;
const LL Hash = 1e9 + 7;

inline LL mod(LL a)
{
    return a - (a/Hash)*Hash;
}

LL C[maxn][6];
inline void getC()
{
    memset(C, 0, sizeof C);
    for(int i = 0; i < maxn; i++){
        C[i][0] = 1;
        for(int j = 1; j <= min(2, i); j++){ C[i][j] = mod(C[i-1][j-1] + C[i-1][j]); } } } string s; int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("o.txt", "w", stdout); int T = 3; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); getC(); LL a00, a01, a10, a11, cnt00 = -1, cnt11 = -1, lef1 = 0, lef0 = 0; cin>>a00>>a01>>a10>>a11;
    for(int i = 2; i < maxn; i++){
        if(a00 == C[i][2]){
            cnt00 = i;
            break;
        }
    }
    for(int i = 2; i < maxn; i++){
        if(a11 == C[i][2]){
            cnt11 = i;
            break;
        }
    }

    if((a00 != 0 && cnt00 == -1) || (a11 != 0 && cnt11 == -1)) {cout<<"Impossible"<<endl;}
    else{
        //cout<<cnt00<<" "<<cnt11<<endl;
        if(cnt00 == -1){
            if(cnt11 == -1){                                           //WA17   0 0 1 0
                if(a10 == 0 && a01 == 0) cout<<0<<endl;
                else if(a10 == 0){
                    if(a01 == 1) cout<<"01"<<endl;
                    else cout<<"Impossible"<<endl;
                }
                else if(a01 == 0){
                    if(a10 == 1) cout<<"10"<<endl;
                    else cout<<"Impossible"<<endl;
                }
                else cout<<"Impossible"<<endl;                        //WA162  0 1 1 0
                return 0;
            }

            if(a10 == 0 && a01 == 0){

                for(int i = 0; i < cnt11; i++) cout<<"1";
                cout<<endl;
                return 0;
            }
            cnt00 = 1;
        }
        if(cnt11 == -1){

            if(a10 == 0 && a01 == 0){
                for(int i = 0; i < cnt00; i++) cout<<"0";
                cout<<endl; return 0; } cnt11 = 1; } /* if(a10 > cnt00 * cnt11) cout<<"Impossible"<<endl; else if(a01 > cnt00 * cnt11) cout<<"Impossible"<<endl;
            */
        if(a10 + a01 != cnt00 * cnt11) cout<<"Impossible"<<endl;
        else{

            lef0 = cnt00; lef1 = cnt11;
            for(int  i = 0; i < cnt00 + cnt11; i++){ if(a10 >= lef0){
                    cout<<1;
                    lef1--;
                    a10 -= lef0;
                }
                else{
                    cout<<0;
                    lef0--;
                }
            }
            cout<<endl;
        }
    }

    #ifdef LOCAL
    cout<<endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx