首页 > 代码库 > Codeforces 708B. Recover the String

Codeforces 708B. Recover the String

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

题意:

  给你四个数 a00, a01, a10, a11, 让你构造一个“01”字符串满足其中恰好有 a00 个 “00” 子串, a01 个 “01” 子串, a10 个 “10” 子串, a11 个 “11” 子串.如果不存在这样的字符串输出 “Impossible”.

思路:

  由于 K(K > 1) 个 ‘0’ 可以组成 K * ( K - 1) / 2 个 “00” 串, 则可以得到 a00 和 a11  应该是某些特殊的数的结论, 即存在一个数 n 使得 a00 = 1 + 2 + ... + n, 同时也存在一个数 m 使得 a11 = 1 + 2 + ... + m.否则不可能构造出来这个字符串.即 n 个 ‘0’ 将组成 a00 个 “00” 串, m 个 ‘1‘ 将组成 a11 个 “11” 串.当 n 和 m 确定存在后就要分情况讨论了:

  如果这里的 n = 0, 满足  a01 + a10 =  m, 则可以这么构造 1...1(a10个‘1’)01...1(a01个‘1’)

  如果这里的 m = 0,满足  a01 + a10 =  n,  则可以这么构造 0...0(a01个‘0’)10...0(a10个‘0’)

  如果这里的a01 = 1 或者 a10 = 1 且 m = n = 0, 则答案就是构造字符串 “01” 或者 “10”

以上三种是比较特殊的情况因为一个字符串中仅有 1 个或者 0 个 ‘0’ 其中的 “00” 串个数都为 0, 同理 一个字符串有 1 个或者 0 个 ‘1’  其 “11” 串的个数也为 0, 比如 “01111” “10000” “10” 这样.接下来就是比较一般的情况了:

  如果一个字符串中有 n 个 ‘0’ 以及 m 个 ‘1’ 则其中的 “01” 串的数量 a01 和 “10” 串的数量 a10 应该满足 a01 + a10 = n * m.其构造方法可以这样构造,从 “01” 串的数量开始构造, 假设 c = a01 / m, d = a01 % m, 则 c 个 ‘0‘ 和 m 个 ‘1’ 组成 c * m 个 “01” 串, 但是还少 d 个 “01” 串, 那么就在倒数第 d 个 ‘1’ 之前插入一个 ‘0’, 于是 “01” 串的个数就是 c * m + d, 其值恰为 a01 , 然后把剩余的 ‘0’ 添加到最后末尾.就可以满足 a10 个 “10” 串了.这里的前提是 m != 0, 如果 m = 0,则说明 a10 和 a01 也为 0,那么直接输出 n 个 ’0‘ 就好了.

代码:

 1 #include <bits/stdc++.h> 2  3 using namespace std; 4 typedef long long LL; 5 const int MAXN = 44721; 6  7 struct NODE { int cnt; int n; }; 8 NODE arv[MAXN + 7]; 9 10 int bsearch(int key) {11     int lo = 1, hi = MAXN;12     while(lo <= hi) {13         int mid = (lo + hi) >> 1;14         if(arv[mid].cnt == key) return arv[mid].n;15         else if(arv[mid].cnt > key) hi = mid - 1;16         else lo = mid + 1;17     }18     return -1;    // key值不合法19 }20 21 void pf(int n, char k){ for(int i = 0; i < n; i++) cout << k; }22 23 int main() {24     //freopen("output", "w", stdout)25     ios_base::sync_with_stdio(0); cin.tie(0);26     arv[1].cnt = arv[1].n = 0;27     for(int i = 2; i <= MAXN; i++) arv[i].cnt = i * (i - 1) / 2, arv[i].n = i; // 根据输入的 a00 a11 找出 0 和 1 的个数以及判断是否存在 a00 a1128     int a00, a01, a10, a11; cin >> a00 >> a01 >> a10 >> a11;29     int cnt0  = bsearch(a00), cnt1 = bsearch(a11);30     if( cnt0 != -1 && cnt1 != -1 ) { // 存在 cnt0 个 ’0‘ 组成 a00 个 ’00‘ 串,以及存在 cnt1 个 ‘1’ 组成 a11 个 ‘11’ 串31         if(a01 + a10 == cnt0 && cnt1 == 0) {// ’11‘ 串的个数为 0, 但是字符串中存在一个 ’1‘32             pf(a01, 0); pf(1, 1); pf(a10, 0);33         }34         else if(a01 + a10 == cnt1 && cnt0 == 0) {// ’00‘ 串的个数为 0, 但是字符串中存在一个 ’0‘35             pf(a10, 1); pf(1, 0); pf(a01, 1);36         }37         else if(a01 + a10 == 1 && cnt0 == 0 && cnt1 == 0) {// ’00‘ 串的个数为 0 且 ’11‘ 串的个数为 0,但存在一个 ’1‘ 和一个 ‘0’38             cout << (a01 == 1 ? "01" : "10");39         }40         else if(a01 + a10 == cnt0 * cnt1) {//这里特别注意 "a01 0 0 0" "0 0 0 a11“ 这样的数据41             if(cnt1 == 0) { pf(cnt0, 0); cout << endl;  return 0; }// 形如 "a01 0 0 0"的数据42             int zero = a01 / cnt1, inset = a01 % cnt1; // a01 = (a01 / cnt1) * cnt1 + a01 % cnt1;43             pf(zero, 0), cnt0 -= zero;44             pf(cnt1 - inset, 1), cnt1 = inset;45             if(cnt0 > 0) pf(1, 0), cnt0 -= 1; //在第倒数 inset 个 ‘1’ 之前插入一个 ‘0’46             pf(inset, 1), pf(cnt0, 0);47         }48         else cout << "Impossible";49     }50     else cout << "Impossible";51     cout << endl;52     return 0;53 }

 

Codeforces 708B. Recover the String