Codeforces 708B. Recover the String

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

题意:

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

思路:

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

　　如果这里的 n = 0, 满足 a₀₁ + a₁₀= m, 则可以这么构造 1...1_{(a₁₀个‘1’)}01...1_{(a₀₁个‘1’)}

　　如果这里的 m = 0,满足 a₀₁ + a₁₀= n, 则可以这么构造 0...0_{(a₀₁个‘0’)}10...0_{(a₁₀个‘0’)}

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

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

　　如果一个字符串中有 n 个 ‘0’ 以及 m 个 ‘1’ 则其中的 “01” 串的数量 a₀₁ 和 “10” 串的数量 a₁₀ 应该满足 a₀₁ + a₁₀ = n * m.其构造方法可以这样构造,从 “01” 串的数量开始构造, 假设 c = a₀₁/ m, d = a₀₁% m, 则 c 个 '0' 和 m 个 ‘1’ 组成 c * m 个 “01” 串, 但是还少 d 个 “01” 串, 那么就在倒数第 d 个 ‘1’ 之前插入一个 ‘0’, 于是 “01” 串的个数就是 c * m + d, 其值恰为 a_{01 ,}然后把剩余的 ‘0’ 添加到最后末尾.就可以满足 a₁₀个 “10” 串了.这里的前提是 m != 0, 如果 m = 0,则说明 a₁₀和 a₀₁ 也为 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 a11
28     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 }