首页 > 代码库 > cf708B. Recover the String---（构造法）

cf708B. Recover the String---（构造法）

2024-08-10 23:55:03   216人阅读

题目链接：http://codeforces.com/problemset/problem/708/B

意思是给出四个参数 
a00表01串中00对的数量 
a01表01串中01对的数量 
a10表01串中10对的数量 
a11表01串中11对的数量

求出一个符合条件的01串，如果不存在输出Impossible；

 

根据a00和a11可以求出0和1的个数；把cnt1个1放在前面，cnt0个0放在后面，此时的01串为0，当把0往前移动一位是01的个数会增加一，所以可以根据a01的个数移动0的位置；

当然在当a00为0时0的个数可能是0个也可能是1个要看a01和 a10同样1的个数也是一样；有对应的串时应满足1的个数*0的个数 = a01+a10的；

 

技术分享
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <queue>#include <algorithm>typedef long long LL;#define INF 0x3f3f3f3f#define N 1000100using namespace std;int a[4];char ans[N];int main(){    for(int i=0; i<4; i++)        scanf("%d", &a[i]);    if(!a[0] && !a[1] && !a[2] && !a[3])    {        printf("0\n");        return 0;    }    int cnt0, cnt1;    if(!a[0] && !a[1] && !a[2]) cnt0 = 0;    else cnt0 = 1;    if(!a[3] &&!a[1] && !a[2]) cnt1 = 0;    else cnt1 = 1;    if(a[0]) cnt0 = (int)sqrt(a[0]*2) + 1;    if(a[3]) cnt1 = (int)sqrt(a[3]*2) + 1;    if(a[0]*2 != cnt0*(cnt0-1) || a[3]*2 != cnt1*(cnt1-1) || cnt0*cnt1 != a[1]+a[2])    {        puts("Impossible");        return 0;    }    int p = 0, r = 0;    while(a[1])    {        if(a[1] >= cnt1)        {            ans[p++] = ‘0‘;            a[1] -= cnt1;            r++;        }        else        {            int m = cnt1-a[1];            while(m) ans[p++] = ‘1‘, m--;            ans[p++] = ‘0‘, r++;            a[1] = 0;        }    }    int s = p-r;    while(cnt1-s) ans[p++] = ‘1‘, s++;    while(cnt0-r) ans[p++] = ‘0‘, r++;    puts(ans);    return 0;}
View Code

 

cf708B. Recover the String---（构造法）


联系
我们