【codeforces 709D】Recover the String

【题目链接】:http://codeforces.com/problemset/problem/709/D

【题意】



给你一个序列;

给出01子列和10子列和00子列以及11子列的个数;

然后让你输出一个符合要求的序列;

【题解】



这里

00和11可以确定出序列中0和1的个数;

但有边缘数据

00如果为0代表什么?

->没有0或者是有1个0

11如果为0代表什么?

->没有1或者是有1个1

对这两种情况需要特判一下(两种情况的特判需要用到01和10的数量)

看代码吧。

然后这两种情况排除之后;

00和11就都大于0了;

则可以根据

00=a0*(a0-1)/2

11=a1*(a1-1)/2

来求出0的个数和1的个数;

具体的;

你需要对2*00开根号->x

同时你还有算一下

(x+1)*x/2是不是等于00

因为如果不是的话就表示没有符合要求的0的个数的序列满足要求;

那种情况也要输出无解;

1同理;

然后我们算出1的个数和0的个数;

把所有的1都放在最前面,然后0的放在后面;

这样a10等于0的个数乘1的个数;

然后可以验证你每把最右边那个1往右交换一个0,a10会减1,a01会加1;

则按照这个规则;

每次看看a10和输入的a10的差为多少rest

while(rest>=num0){

**把最右边那个1和最右边那个0交换;

**rest-num;

}

然后rest可能还有剩余

则把最右边那个1和这个1往右数rest个0交换位置;

就能再减去rest个10了;

根据上述规则可知;

如果输入的a10+a01!=1的个数*0的个数

则输出无解;



【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x) typedef pair<int, int> pii;
typedef pair<LL, LL> pll; const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 110; int a00, a01, a10, a11;
string s; void work(int num0, int num1){
s = " ";
rep1(i, 1, num1) s += '1';
rep1(i, 1, num0) s += '0';
if (a01 + a10 != num0*num1) puts("Impossible"),exit(0);
int ta10 = num1*num0;
int j = num1,i = 0;
LL rest = ta10 - a10;
while (rest>=num0)
{
swap(s[j], s[num1 + num0 - i]);
j--; i++;
rest -= num0;
}
swap(s[j], s[j + rest]);
s.erase(0, 1);
cout << s << endl;
exit(0);
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
rei(a00), rei(a01), rei(a10), rei(a11);
if (a00 == 0){
//no zero
if (a01 == 0 && a10 == 0){
int len = sqrt(2 * a11)+1;
if (len*(len - 1) == 2 * a11)
{
rep1(i, 1, len) printf("1");
return 0;
}
} //one zero
if (a11 == 0){
//no one
if (a10 == 0 && a01 == 0) return puts("0"), 0; //one one
if (a10 + a01 == 1){
if (a10 == 1) return puts("10"), 0;
if (a01 == 1) return puts("01"), 0;
}
}
else
if (a11 > 0) {
int len = sqrt(2 * a11) + 1;
if (len*(len-1)==2*a11)
work(1, int(sqrt(2 * a11) + 1));
}
puts("Impossible");
return 0;
}
if (a11 == 0)
{
//no one
if (a10 ==0 && a01 == 0) {
int len = sqrt(2 * a00) + 1;
if (len*(len - 1) == 2 * a00) {
rep1(i, 1, len) printf("0");
return 0;
}
} //one one
assert(a00 > 0);
int len = sqrt(2 * a00) + 1;
if (len*(len - 1) == 2 * a00)
work(int(sqrt(2 * a00) + 1), 1);
puts("Impossible");
return 0;
}
int len = sqrt(2 * a00) + 1, len1 = sqrt(2 * a11) + 1;
if (len*(len-1)==2*a00 && len1*(len1-1)==2*a11)
work(int(sqrt(2 * a00) + 1), int(sqrt(2 * a11) + 1));
puts("Impossible");
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
上一篇:【codeforces 707E】Garlands


下一篇:聊一聊全球加速GA的带宽包选择