自动搬运

查看原文

来自洛谷，原作者为

	max67 bobo

搬运于2025-08-24 22:26:02，当前版本为作者最后更新于2022-09-24 20:58:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

感谢

指导

（看分类过程的可以看有灰色竖线的部分）

题解

设与男孩相邻的数量为 $a$，与女孩相邻的数量为 $b$。

首先可以凭感觉知道：这种既带构造又带环的题目，大多都要分类讨论。为了使我们讨论的顺畅一点，首先我们先特判一些特殊情况，创造出一些性质：

当 $a=0$ 时，注意到此时不能填 B，必须全填 G。容易算出此时的 $b$ 的值为 $n$。因此当且仅当 $b=n$ 时有解。$b=0$ 的情况同理。

那么此时满足答案里面至少有一个 G，至少有一个 B。分别考虑每个字符的贡献，注意到这仅与他两边的字符有关。

那么考虑把一段连续的字符缩成一个连续段，分别讨论每个连续段的贡献（假设这个连续段的字符都是 B）：

• 设这个连续段的长度为 $k$，首先可以观察出与这个连续段相邻的连续段的字符都是 G

• 当 $k=1$ 时，注意到他两边的字符都是 G，那么只有对 $b$ 有 $1$ 的贡献

• 当 $k>1$ 时，连续段两端的字符与 G 相邻，因此对 $b$ 有 $2$ 的贡献；连续段里的所有字符都与 B 相邻，对 $a$ 有 $k$ 的贡献。

• 注意连续段个数必须为偶数，若为奇数的话一定会有两个字符相同的连续段相邻,就会不合法。

由于上面的分类贡献比较复杂，因此考虑对于总数（$a+b$） 的贡献。当连续段的长度为 $1$ 时，对 $a+b$ 有 $1$ 的贡献；当连续段的长度为 $k>1$ 时，对 $a+b$ 有 $k+2$ 的贡献。

因此若有 $t$ 个大于 $2$ 的连续段，$a+b$ 的总数就为 $n+2t$。

因此 $2|t,t\ge 0$，所以若 $a+b<n$ 或 $2\nmid a+b-n$ 就无解。

现在，我们知道了 $t$ 的表达式：$t=\frac{a+b-n}{2}$。

然后似乎很难讨论，那么我们尝试挖掘 $a,b$ 和 $t$ 的性质。观察 $a,b$ 的定义可得

• 因为总人数小于等于 $n$，因此 $0\le a,b \le n$。

• 有 $n-b\le 0,n-a\le 0$，即 $\frac{a+(n-b)}{2}=t \le \frac{a}{2}$，变形一下有： $2\times t\le a$。

• 同理，有 $2\times t \le b$

但这样还不够，一个常见的构造想法是先构造出一个基础解，再在上面进行增添。那么一个朴素的思路就是往联通块里面插数。那么手模一下，有：

• 当一个连续段的个数大于 $1$ 时，假设字符为 B。往里面插一个相同的字符，只会使得 $a$ 的值增加 $1$。

那么我们可以首先创建 $t$ 个长度为 $2$ 的连续段。注意到上面的性质，也就是只要有一个连续段就能单独调整 $a$ 或 $b$，那么我们肯定保证要给每个字符至少一个连续段。

注意到 $a,b\ge 2t$，即当 $t>1$ 时是上面的想法可能的，那么我们先讨论这种情况。由于 $a,b \ge 2t$，一个暴力的想法是直接给 $a,b$ 分 $\frac{t}{2}$ 个上下浮动的连续段。

当 $2\nmid t$ 时，我们规定一个字符分到 $\frac{t+1}{2}$ 个段（设是字符 B），另一个字符分到 $\frac{t-1}{2}$（设是 G）。因为 $t$ 为奇数，还需要额外增加一个长度为 $1$ 的连续段（否则有两个连续段会合并），字符为分到连续段数小的那个（假设为 G）。那么我们现在对于 $a$ 已经有 $2t+1$ 的贡献，$b$ 已经有 $2t$ 的贡献。由于 $a,b\ge 2t$，也就是说若满足 $a>2t$ 。因此我们的当前构造不会不合法的。由于我们能任意增加 $a$ 或 $b$ 的值（往任意一个长度大于等于 $2$ 的连续段里面插数），因此构造是合法的。同理可以构造 $b>2t$。

考虑 $a=b=2t$ 的情况怎么办。推一下式子，有：$a=b=a+b-n,a=b=n$。由于 $t$ 为奇数，设 $t=2k+1$，那么 $n=2t=2(k+1)=4k+2$，即 $n$ 在模 $4$ 意义下的模数为 $2$。

那么考虑 $a,b$ 的定义，因为 $a=b=n$，一个字符最多产生 $2$ 的贡献，也就是说任意一个位置的相邻的两个字符都不同。假设答案中位置为 $i$ 的字符为 $v_i$。有 $v_1!=v_3,v_3!=v_5,v_1=v_5$，即 $v_1=v_{4k+1}=v{(4k+2)-1}=v_{n-1}$，而 $v_1!=v_{n-1}$，就导出了矛盾。

因此 $a=b=2t$ 的情况不合法。对于 $2|t$ 的情况，同理讨论即可。

当 $t>1,2\mid t$ 时，初始设置 $t$ 个长度为 $2$ 的连续段，其中 $\frac{t}{2}$ 个连续段的颜色为 B，$\frac{t}{2}$ 个连续段的字符为 G。那么对于 $a,b$ 的贡献已经为 $2t$

其次我们往其中一个字符为 B 的连续段放入 $a-2t$ 个字符，往其中一个字符为 G 的连续短放入 $b-2t$ 个字符。

当 $t>1,2\nmid t$ 时，若 $a=b=2t$，不合法，否则设 $a>b$，设置长度为 $2$ 的连续段 $t$ 个， $\frac{t+1}{2}$ 个连续段的字符为 B，$\frac{t-1}{2}$ 个连续段的字符为 G。再增加一个长度为 $1$ 的连续段，字符为 G。然后分给其中一个字符为 B 的连续段 $a-2t-1$ 个字符，分给其中一个字符为 G 的连续短 $b-2t$ 个字符。

然后分类讨论 $t=0,1$ 的情况。

当 $t=0$ 时，那么每个连续段的长度为 $1$，因此若 $n$ 为奇数，则至少为出现一个长度为 $2$ 的连续段，无解。那么 $n$ 为偶数，分配了 $\frac{n}{2}$ 个 B 和 G。易得 $a=b=\frac{n}{2}$ 时合法，否则不合法。

当 $t=1$ 时，设一共有 $2x$ 个连续段。其中 $x$ 个连续段的字符为 B，另外的为 G。假设 $a> b$，那么抽出其中一个字符为 B 的连续段，加入一个字符。那么此时对 $a$ 的贡献为 $x+2$，对 $b$ 的贡献为 $x+1$。由于 $a> b= x+1$，有 $a\ge x+2$。因此合法。当 $a<b$ 时同理。

当 $a=b$ 时，由于上面的构造是唯一解，所以不合法。（注意数据没有这个情况）

然后这题就做完了 QAQ。

代码

注意一下优先级：

1?putchar('B'),putchar('B'):putchar('G'),putchar('G')

的输出为 BBG。

#include<bits/stdc++.h>
#define pc putchar
using namespace std;
const int N=1e5+1e3;
int n,a,b;
void print(){puts("Impossible");exit(0);}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    // a 个孩子站在一个男孩旁边
    // b 个孩子站在一个女孩旁边
    if(a+b<n||((a+b-n)&1))print();
    if(a==0||b==0)
    {
        if(a+b!=n)print();
        if(a==0)for(int i=1;i<=n;i++)pc('G');
        if(b==0)for(int i=1;i<=n;i++)pc('B');
        exit(0);
    }
    int t=a+b-n>>1;
    if(t==0)
    {
        if(n%2||a!=n/2||b!=n/2)print();
        for(int i=1;i<=n;i++)pc(i&1?'G':'B');
        exit(0);
    }
    if(t==1)
    {
        if(a==b)print();
        if(a>b)
        {
            for(int i=1;i<=a-b+1;i++)pc('B');
            for(int i=1;i<=n-(a-b+1);i++)pc(i&1?'G':'B');
        }
        if(a<b)
        {
            for(int i=1;i<=b-a+1;i++)pc('G');
            for(int i=1;i<=n-(b-a+1);i++)pc(i&1?'B':'G');
        }
        exit(0);
    }
    if(t%2==0)
    {
        a-=2*t;b-=2*t;
        for(int i=1;i<=a+2;i++)pc('B');
        for(int i=1;i<=b+2;i++)pc('G');
        for(int i=1;i<=t-2;i++)pc(i&1?'B':'G'),pc(i&1?'B':'G');
        exit(0);
    }
    a-=2*t;b-=2*t;
    if(!a&&!b)print();
    if(a)
    {
        for(int i=1;i<=a+1;i++)pc('B');
        for(int i=1;i<=b+2;i++)pc('G');
        for(int i=1;i<=t-2;i++)pc(i&1?'B':'G'),pc(i&1?'B':'G');
        pc('G');
        exit(0);
    }
    if(b)
    {
        for(int i=1;i<=b+1;i++)pc('G');
        for(int i=1;i<=a+2;i++)pc('B');
        for(int i=1;i<=t-2;i++)pc(i&1?'G':'B'),pc(i&1?'G':'B');
        pc('B');
        exit(0);
    }
    return 0;
}

后记

在写题时，突然想起了 P6892 [ICPC2014 WF]Baggage。虽然说两个构造方法不同，但是分类讨论的痛苦是相同的。