P7032 [NWRRC2016]Boys and Girls

· · 题解

前言

感谢 @Umbrella_Leaf 大佬的指导

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

题解

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

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

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

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

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

由于上面的分类贡献比较复杂，因此考虑对于总数（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 的定义可得

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

那么我们可以首先创建 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。虽然说两个构造方法不同，但是分类讨论的痛苦是相同的。