首页 > 代码库 > 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