Codeforces 709D AIM-Tech-Round-3-Div.2 Recover the String

题目链接: Recover the String

题意:

一个只包含01且不为空的字符串,在串中任意选两个不同的字符,可能产生的组合为’00’, ‘01’, ‘10’, ‘11’;
现在给你每个组合的个数a(00), a(01), a(10), a(11),在满足组合个数的条件下,构造这个串;
例如a(00) = 1, a(01) = 2, a(10) = 2, a(11) = 1, 满足条件的串可能有:0110,1001

题解:

  • 要构造'00', '11',分别只和串中的'0', '1'字符有关
    1. cnt0表示原串中’0’的个数,a(00) = (cnt0 * (cnt0 - 1)) / 2,当cnt0 = 1 或 cnt0 = 0,a(00) = 0
    2. cnt1表示原串中’1’的个数,同理
    3. 所以我们可以根据a(00), a(11),推导出cnt0, cnt1;
      若a(00) = 0,cnt0可能等于0或1,这时候要看a(01), a(10),若a(01)>0 或 a(10)>0,则cnt0 = 1
      也就是说,cnt0是可以被唯一确定的; 同理,cnt1也可以唯一确定
  • 构造’01’, ‘10’
    1. 现在问题等价于,在一个全0串中,插入cnt1个’1’字符
    2. 若在全0串的P位置插入一个’1’,则会产生P个'10'串,cnt0 - P个'01'串;也就是每插入一个'1',增加的'10','01'串个数和是cnt0;所以当所有’1’都插入全0串后,a(01) + a(10) = cnt0 * cnt1
    3. 从左到右遍历一次全0串,但’10’数量还不够时就插入一个’1’

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll limit = 10e9;
const ll limit_length = 10e5;
const int maxn = 1000100;

ll sum[maxn], cs, a[4];

void init() {
sum[0] = 0LL;
for (int i = 1; i < maxn; i++) {
sum[i] = sum[i-1] + i;
if (sum[i] > limit) {
cs = i;
break;
}
}
}

int main() {
init();
while (scanf("%lld%lld%lld%lld", &a[0], &a[1], &a[2], &a[3]) != EOF) {
ll *value0 = lower_bound(sum, sum + cs, a[0]);
ll *value3 = lower_bound(sum, sum + cs, a[3]);
if (*value0 != a[0] || *value3 != a[3]) {
puts("Impossible");
continue;
}

ll cnt0 = 0LL, cnt1 = 0LL;
if (*value0) {
cnt0 = value0 - sum + 1LL;
}
if (*value3) {
cnt1 = value3 - sum + 1LL;
}
if (!cnt0) {
if (a[1] || a[2]) cnt0 = 1LL;
}
if (!cnt1) {
if (a[1] || a[2]) cnt1 = 1LL;
}

if (cnt0 + cnt1 > limit_length) {
puts("Impossible");
continue;
}

// count of `01`+`10`
ll total = cnt0 * cnt1;
if (a[1] + a[2] != total) {
puts("Impossible");
continue;
}

//printf("cnt0=%lld\n", cnt0);
//printf("cnt1=%lld\n", cnt1);

if (!cnt0 && !cnt1) {
cnt0 = 1LL;
}

char *ans = new char[cnt0 + cnt1 + 1];
int length = cnt0 + cnt1, index = 0;
ll re10 = a[2], used1 = 0;
for (int i = cnt0; i >= 0; i--) {
while (re10 >= i && used1 < cnt1) {
ans[index++] = '1';
re10 -= i;
used1++;
}
if (!i) break;
ans[index++] = '0';
}
ans[length] = '\0';
printf("%s\n", ans);
}
return 0;
}
坚持原创分享,您的支持将鼓励我继续创作!