「Codeforces Gym 101142B」Boys and Girls

题目链接:Codeforces Gym 101142B

Description

现在有$n$个小盆友围成一圈,已知两边是男生的小盆友有$x$个,两边是女生的有$y$个,让你构造这个序列。

如果构造不出,输出Impossible

Data Range

$2\leq n\leq 100000,0\leq x,y \leq n$

Solution

写的比较乱,简易自己画图边阅读。

考虑大力分类讨论。

首先记$C=x+y-n$,经过画图表示或者逻辑推理可得,这个代表的是区间形如$BBGG$,也就是两个及以上相同字符相连块之间的个数。

然后记$A=x-C,B=y-C$,分别表示只有一个$B$或者一个$G$的情况。

因为每一个交接点一定会对双方都必将且仅产生$1$的贡献,所以这个$C$一定是一个偶数,否则不存在。
或者如果$A,B,C$中其中有一个为负数,也不存在。

然后根据$C$进行讨论。

首先$C=0$也就是不存在两个及以上相同字符相连的块,所以只有可能是三种情况。

BBBBBBBB
GGGGGGGG
BGBGBGBG

这三种情况分别是$B=0,A=0,A=B$

然后讨论$C=n$的情况,所以全都是形如$BBGG$的块,但是每一个块一定是完整的,所以这个$n$一定是$4$的倍数,否则无解。

考虑$C=2$的情况比较特殊,因为只有一个$BBGG$块或者说是只有长度为$2$以下的BBGG

那么假设我们的序列为BBB...BGBGBG....BG,假设前面的有长度为$s$的$B$串,然后后面有$t$个$BG$串。

那么$A=s-2+t+1=s+t-1,B=t$,因为$s>=2$所以$A>B$,反之那么把$BG$交换一下同理构造,$A=B$,那么无解。

考虑长度为$C>2$继续分类讨论。

以下是$A>B$的情况

当$C$为$4$的倍数时,也就是可以构造出整数个$BBGG$的串

那么只需要再来$A+2$个$B$,再来$B+2$个$G$。

那么这些串可以给我们提供$4$个不同的性别,然后在后面构造上$C/2+1$个$BBGG$就可以了。

如果不是$4$的倍数,类似于偶数的构造方式,我们需要减少一个性别不同的孩子,那么就把最后一个$BBGG$串改成$BBG$串,这样我们就成功减少了一个$G$,因为减少了一个$G$,所以我们减掉一个$B$,也就是构造$A+1$个$B$和$B+2$个$G$,这样保证了个数的平衡。

反之$A<B$就把所有的$BG$交换就可以了。

大力讨论,可能有地方写错了,欢迎指出

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> void chkmax(T &x, T y) { x = x > y ? x : y; }
template <typename T> void chkmin(T &x, T y) { x = x < y ? x : y; }
template <typename T> void read(T &x) {
    x = 0; bool w = 0; char ch = 0;
    for (; !isdigit(ch); ch = getchar()) w |= ch == '-';
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= w ? -1 : 1;
}
template <typename T> void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T> void write(T x, char ch) {
    write(x); putchar(ch);
}
int n, x, y;
int A, B, C;
int main() {
    freopen("boysgirls.in", "r", stdin);
    freopen("boysgirls.out", "w", stdout);
    read(n); read(x); read(y); 
    if (x + y < n) {
        puts("Impossible");
        return 0;
    }
    C = x + y - n; 
    if (C % 2 == 1) {
        puts("Impossible"); 
        return 0; 
    }
    A = x - C; B = y - C; 
    if (C == 0) { // if there is no complete blocks between BG
        if (A == 0) {
            for (int i = 1; i <= n; i ++) printf("G"); 
            puts("");
            return 0; 
        }
        if (B == 0) {
            for (int i = 1; i <= n; i ++) printf("B"); 
            puts("");
            return 0; 
        }
        if (x == y) {
            for (int i = 1; i <= n / 2; i ++) printf("BG"); 
            puts("");
            return 0;
        }
        printf("Impossible\n");
        return 0;
    }
    if (C == n) {
        if (n % 4 != 0) printf("Impossible");
        else {
            for (int i = 1; i <= n / 4; i ++) printf("BBGG");
            puts("");
        }
        return 0; 
    }
    if (C == 2) {
        if (A == B) {
            printf("Impossible");
            puts("");
            return 0; 
        }
        if (A > B) { // B is more than G
            for (int i = 1; i < y; i ++) printf("BG");
            for (int i = 1; i <= n - (y - 1) * 2; i ++) printf("B");
            puts("");
            return 0; 
        }
        if (A < B) { // G is more than B
            for (int i = 1; i < x; i ++) printf("GB");
            for (int i = 1; i <= n - (x - 1) * 2; i ++) printf("G");
            puts("");
            return 0;  
        }
    }
    // blocks is more than 4
    if (A < B) {
        for (int i = 1; i < C / 4; i ++) printf("GGBB");
        if (C % 4 != 0) {
            for (int i = 1; i <= B + 1; i ++) printf("G");
            for (int i = 1; i <= A + 2; i ++) printf("B");
            puts("GGB");
        }
        else {
            for (int i = 1; i <= B + 2; i ++) printf("G");
            for (int i = 1; i <= A + 2; i ++) printf("B");
        }
    }
    else {
        for (int i = 1; i < C / 4; i ++) printf("BBGG");
        if (C % 4 != 0) {
            for (int i = 1; i <= A + 1; i ++) printf("B");
            for (int i = 1; i <= B + 2; i ++) printf("G");
            puts("BBG");
        }
        else {
            for (int i = 1; i <= A + 2; i ++) printf("B");
            for (int i = 1; i <= B + 2; i ++) printf("G");
            puts("");
        }
    }
    return 0;
}
最后修改:2019 年 07 月 29 日 09 : 57 PM
如果觉得我的文章对你有用,请随意赞赏

2 条评论

  1. ljc20020730

    C=0可以不用讨论

    1. chhokmah
      @ljc20020730

      要讨论的吧,可能是我写的比较丑。

发表评论