OI - RGB Balls(AtCoder) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - RGB Balls(AtCoder)

发表于 更新于 分类于 Valine：

思路倒是挺不错
找到了一道比较奇怪的利用了“费用提前计算”方法的题目

Part1. 题面

有 3 种球，分别标记为 R,G,B。每种球各有 n 个，这 3n 个球排成一行。

现在将这 3n 个球分成 n 组，使得每一组中每种球恰有一个。每个分组的代价为该组球中相隔最远的两个球的距离。

问有多少种不同的分组方式，使得分组的总代价最小（两种方式被考虑为不同当且仅当至少有一个组中有不同的球）。

数据规模：$1\le n\le10^5$。

Part2. 题解

Part2/1. 怎样计算最小值

要知道最小值的方案数，首先要知道最小值怎么算。不妨考虑一种非常暴力的 DP：dp[i][a][b][c][d][e][f] 表示：前 i 个球中，3 种球各有 a,b,c 个没有配对（已经被分到组中的球就叫“已配对”），(R,G) 配对了 d 对，(R,B) 配对了 e 对，(G,B) 配对了 f 对。

但是我们发现这样似乎不能转移，因为我们不知道未配对的球的位置，也就无法计算距离。其实是可以转移的，这里就要用到“费用提前计算”了，转移分为三种（不妨设当前考虑的球为 R，对应的数量是 a；其他两种情况是一样的）：

  1. 不配对：

    dp[i][a+1][b][c][d][e][f]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)

    后面的 a+b+c+d+e+f 就是费用提前计算了——这已经存在的 a+b+c 个球和 d+e+f 对球仍未完成分组，必然会增加 1 的花费。

  2. 与 G 配对：

    dp[i][a][b-1][c][d+1][e][f]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)

    与 B 配对是类似的。

  3. 与一对 (G,B) 配对：

    dp[i][a][b][c][d][e][f-1]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)

以上只是帮助理解贪心的正确性，代码实现中并不会体现这一段——不难发现，我们要 让 a+b+c+d+e+f 尽可能小 才可能使 dp 值更优。因此，当我们拿到一个 R 球，如果有一对未配对的 G,B 球，一定会配对成一组；如果有单个未配对的 G 或 B，一定会与它组成一对，即固定为分在同一组中。

Part2/2. 贪心

于是就有了一个非常easy的贪心：记录 3 种球在之前有多少个未完成分组，显然不会同时有 3 种球未完成分组。

考虑当前这个球，如果能够和之前未配对的球配对，那就配对了。又因为推导这个贪心结论时，我们是利用动态规划的“费用提前计算”，所以当前的球具体与前面的哪两个球配对并不重要，因此组合数算一算即可。

如果无法配对，那就更改未配对的球的数量。

这样扫一遍 $O(n)$，可以 AC 了。（其实难点在证明这个贪心是正确的）

Part3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5,MOD=998244353;

int n;
char str[3*N+3];

struct MODNUM{
    int num;
    MODNUM(){}
    MODNUM(int _n):num(_n){}
    MODNUM operator *(const MODNUM B){return 1ll*num*B.num%MOD;}
    MODNUM operator +(const MODNUM B){return (1ll*num+B.num)%MOD;}
    MODNUM operator -(const MODNUM B){return ((1ll*num-B.num)%MOD+MOD)%MOD;}
    MODNUM operator +=(const MODNUM B){return *this=(*this)+B;}
    MODNUM operator *=(const MODNUM B){return *this=(*this)*B;}
    MODNUM operator -=(const MODNUM B){return *this=(*this)-B;}
}ans,num[4][4];

int main(){
    // freopen("legend.in","r",stdin);
    // freopen("legend.out","w",stdout);
    scanf("%d%s",&n,str+1);
    for(int i=1;i<=3*n;i++){
        if(str[i]=='R') str[i]='1';
        if(str[i]=='G') str[i]='2';
        if(str[i]=='B') str[i]='3';
    }
    ans=1;
    for(int i=1;i<=3*n;i++){
        int ano1,ano2,thi=str[i]-'0';
        if(str[i]=='1') ano1=2,ano2=3;
        if(str[i]=='2') ano1=1,ano2=3;
        if(str[i]=='3') ano1=1,ano2=2;
        if(num[ano1][ano2].num) ans*=num[ano1][ano2],num[ano1][ano2]-=1;
        else if(num[ano1][0].num) ans*=num[ano1][0],num[ano1][0]-=1,num[min(ano1,thi)][max(ano1,thi)]+=1;
        else if(num[ano2][0].num) ans*=num[ano2][0],num[ano2][0]-=1,num[min(ano2,thi)][max(ano2,thi)]+=1;
        else num[thi][0]+=1;
    }
    for(int i=1;i<=n;i++) ans*=i;
    printf("%d\n",ans);
    return 0;
}

The End

Thanks for reading!

啊哈？又完成一篇 blog 了呢！