CSP模拟 17

今天挂了 \(\text{85 \ pts}\)，谨记本地编译要开 \(\operatorname{O}_2\)，离线处理的题最后输出一定要再排序排回来。

A. 弹珠游戏

考虑用一个 01 串表示每个人的状态，表示每个人所拥有球的情况。

例如 R->100、G->010、B->001、RG->110、RB->101、BG->011。

考虑贪心，对于一个新的弹珠，优先给即将达到三种弹珠都有的人。

举个栗子，对于一个字符串 RGRB。

第一个 R 无所谓给谁，对于这个 G 我们还是给第一个得到 R 的人，第二个 R 不能给第一个已经有 R 的人。

对于 B，我们考虑前面两人产生贡献的区间，我们优先交给得到 RG 的人，就可以使得其贡献区间终结，减少多个贡献区间重叠的部分，以使得总的不满意度之和最小。

过程中记录每种状态的人数，随时乘起来就好。

Code

#include <bits/stdc++.h>

using namespace std;

const int Mod = 998244353;

int n;

string st;

int cnt[10];

long long ans = 1;
// R 100
// G 010
// B 001
// RG 110
// RB 101
// BG 011

int main() {
    cin >> n;
    cin >> st;
    
    cnt[000] = n;
    
    for(int i = 0;i < 3 * n; i++) {
        if(st[i] == 'R') {
            if(cnt[011]) {
                ans = (ans * cnt[011]) % Mod;
                cnt[111] ++;
                cnt[011] --;
            }
            else if(cnt[010]) {
                ans = (ans * cnt[010]) % Mod;
                cnt[110] ++;
                cnt[010] --;
            }
            else if(cnt[001]) {
                ans = (ans * cnt[001]) % Mod;
                cnt[101] ++;
                cnt[001] --;
            }
            else if(cnt[000]) {
                ans = (ans * cnt[000]) % Mod;
                cnt[100] ++;
                cnt[000] --;
            }
        }
        else if(st[i] == 'G') {
            if(cnt[101]) {
                ans = (ans * cnt[101]) % Mod;
                cnt[111] ++;
                cnt[101] --;
            }
            else if(cnt[001]) {
                ans = (ans * cnt[001]) % Mod;
                cnt[011] ++;
                cnt[001] --;
            }
            else if(cnt[100]) {
                ans = (ans * cnt[100]) % Mod;
                cnt[110] ++;
                cnt[100] --;
            }
            else if(cnt[000]) {
                ans = (ans * cnt[000]) % Mod;
                cnt[010] ++;
                cnt[000] --;
            }
        }
        else {
            if(cnt[110]) {
                ans = (ans * cnt[110]) % Mod;
                cnt[111] ++;
                cnt[110] --;
            }
            else if(cnt[100]) {
                ans = (ans * cnt[100]) % Mod;
                cnt[101] ++;
                cnt[100] --;
            }
            else if(cnt[010]) {
                ans = (ans * cnt[010]) % Mod;
                cnt[011] ++;
                cnt[010] --;
            }
            else if(cnt[000]) {
                ans = (ans * cnt[000]) % Mod;
                cnt[001] ++;
                cnt[000] --;
            }
        }
    }

    cout << ans;
    return 0;
}

B. 晚会

暴力思路是跑类似 Floyd 的方式多次，跑到出现合法状况为止，复杂度 \(\mathcal{O}(kn^3)\)，\(k\) 为未知常数。

考虑树的情况。

假设两棵树内部已经是连好的，那么考虑两棵树之间如何连边。

如果给出的边中有使这两个连通块相连的边，边权为 \(w\)，那么这两个连通块中任何两个点之间我们都可以连边权为 \(w\) 的边，这样使得不管两个连通块内部的边权为多少，都满足不会出现不友好情况。

如果给出的边没有使这两个连通块相连的边，也可以理解为最后连完边发现整张图不连通，那我们就可以把这些连通块直接的边都连为 \(1\)。既可以满足保持友好，也能够使得总和最小。

两个连通块之间的连边操作不是真的暴力去连，而是一个限制，未来判断无解的限制。

例如两个连通块之间的边都已经连为 \(5\) 了，那么如果后来出现在这两个连通块间边权为 \(3\) 的点就会产生无解情况。

然后我们发现，边权越小，对其他边的限制就越严格，所以我们跑一个类似最大生成树的操作，优先去连较大的边。

我们把相同边权的边存在一起，第一遍去判这些边是否合法，第二遍去连边，防止出现上一次产生的限制出锅导致判不出无解的情况。