题解 P7338 【『MdOI R4』Color】

· · 题解

B. Color

我验BF姐姐出的题，BF 姐姐验我出的题，我和 BF 贴贴/qq

这题的题目背景是 yummy 第一次尝试歌词集句呢，接得不是很顺，大家凑合着看哈。

字非常的丑，但是也只能这样，至少能识别。

这些歌都来自 Grace VanderWaal，第一次知道她是在 Stargirl 这部电影里面呢。

Subtask 1

手玩。首先 1 超过 n 个显然可以直接输出++。

考虑 1 不超过 n 个的情况，n=1\operatorname{or} 2 时显然输出RP。

对于n=3 的情况，观察发现，应该输出++，当且仅当有一个 1 的周围全都是 1。

Subtask 2

显然这道题换一种说法就是：

在 2 行 n 列的方格纸中，对于每个 1 找一个相邻 0，且每个 1 对应的 0 互不相同。

那么 n\le10 的方法就很显然了。首先，当 1 多于 n 个时，直接输出++。

接下来，对于每一个 1，暴力枚举它对应哪一个相邻的 0，然后进行判断。

每个 1 对应的 0 的可能不超过 3 种，故总时间复杂度 O(Tn3^n)，在 n\le 10 时稳。

Subtask 3

读题分。由于其中一行不作要求，故对于每个 1 ，选取这一列的 0 即可。故答案必为RP。

Subtask 4

手玩。第一步仍然是“如果一个 1 的周围全是 1 则直接 ++”。

相比于 Subtask 1，这个 Subtask 需要多进行的一个特判就是形如样例第 2 组数据这样的形状。

Subtask 5

我觉得可能有二维 DP 做法，但是目前没有想到。

该 Subtask 是为了照顾大常数选手，以及 Subtask 6 写假了的选手。

Update：根据赛时情况发现还有匈牙利二分图匹配的选手和网络流大常数选手。

Subtask 6&7

我们从左往右一列一列满足。

假设前 i-1 列的 1 都找到了 0，考虑第 i 列的 1 怎么找 0。

首先，若这个 1 的左边是没被占用的 0，则优先选择这个 0，因为从第 i+1 列开始，这个 0 是不会被用到的。

如果左边不是没被占用的 0，那么我们应该优先选择同一列的 0，因为同一列的 0 从第 i+2 列开始就不会被用到，但是右边的 0 从第 i+3 列开始才不会被用到。

如果某一个 1 的左边，同一列和右边都无法选择，那么输出++；如果最后一列也成功选择，那么输出 RP。

时间复杂度 \Theta(Tn)，常数较小。

Subtask 7 是赛后添加的，目的是让假的算法（如一些细节未考虑）通不过。

然后我发现这个 Subtask 有一个副作用就是直接 memset 的同学会 TLE，但 TLE 的似乎比WA多。

但是我相信随着时间的推移TLE会变少，因为后来的应该不会直接交比赛代码吧。

std

这题题面简洁，代码清新，是不可多得的贪心入门题，为良心出题人点赞！

(请注意 std 的数组从 0 开始。）

#include<bits/stdc++.h>
using namespace std;
int t,n;
char up[100005],down[100005];
bool cup(int x){//尝试给上面这行第x个位置染色
    if(up[x]!='0')return 1;
    up[x]='2';return 0;}
bool cdown(int x){//尝试给下面这行第x个位置染色
    if(down[x]!='0')return 1;
    down[x]='2';return 0;}
int main(){
    for(scanf("%d",&t);t;t--){
        scanf("%d%s%s",&n,up,down);
        bool flag=1;
        if(up[0]=='1'&&cdown(0)&&cup(1)||down[0]=='1'&&cup(0)&&cdown(1))//对于第0列因为没有上一列我们需要特判
            flag=0;
        for(int i=1;i<n;i++)
            if(up[i]=='1'&&cup(i-1)&&cdown(i)&&cup(i+1)||down[i]=='1'&&cdown(i-1)&&cup(i)&&cdown(i+1)){
            //利用&&的短路特性，即&&前面的语句为false就会不执行后面的语句，而且&&是右结合的
                flag=0;break;
            }
        if(flag)puts("RP");
        else puts("++");
    }
    return 0;
}

Further More

这题在行数 h\ge 3 时怎么做呢？

由于我一开始一直准备的贪心解法，所以我顺延贪心思想，一直觉得这题需要状压 DP。

具体地，dp(S,k) 表示当前在讨论第 k 列，这列 h 个格子（是 (1) 不是 (0) 未占用的 0）能否满足。

对于这一列的每个格子：

状态有 n\cdot 2^h 种，而总复杂度就是每个状态中（ 1 左移 010 子串的数量）的和。

我们可以将其近似地看作 1 左移 \min(\text{0 的个数,1 的个数})，计算得复杂度为 O(n\cdot 3^h)。

但是赛场上，我发现有些人使用了一种比正解码量大很多的算法：二分图最大匹配。

具体地，考虑对于所有的 1，向有公共边的所有 0 连一条边，然后使用Dinic跑二分图最大匹配。

由于此时边数和格子数同阶，故总时间复杂度为 \Theta(Tn\sqrt{n})，10\times 10^5\times\sqrt{10^5}=3.16\times 10^8。

再加上很难卡满，所以实际上也是可以过的。而且这可以用于 h\ge 3 的情况。

yummy 并不打算搞加强版，因为这个非常套路，不管状压还是网络流都接近板子。