mydcwfy's Blog

CF Round#758

Posted on
Symbols count in article: 4.3k Reading time ≈ 9 mins.

比赛记录：ABC Accepted，Scores：1645，Rank #727（似乎有点巧，Fly727，Rating 829 -> 1239。

改题进度：ABCD Accepted。

比赛位置

本身应该出校吃东西的，但是因为 18:05 要一次难得的 CF 比赛，于是放弃了吃饭。

赛时

一开始看 A，发现是签到题，2 min 水完。

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    int n, t;
    cin >> t;
    while (t --)
    {
        cin >> n;
        for (int i = 1; i <= n; ++ i) printf("%d ", i + 1);
        puts("");
    }
    return 0;
}

看到 B，发现有一些神奇的题。

发现按照波峰波谷直接构造就可以了，但是有些难写，一直到了 45 min，还错了一发，终于过了。

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
while (t --)
    {
        scanf("%d %d %d", &n, &a, &b);
        if (abs(a - b) > 1) noans();
        if (a == b)
        {
            if ((a + 1) * 2 > n) noans();
            int st1 = a + 2, st2 = a + 1;
            for (int j = n, t = 0; t <= a; t ++, j -= 2)
                ans[j] = st1 ++, ans[j - 1] = st2 --;
            for (int i = 1; i <= n - ((a + 1) << 1); i ++) ans[i] = i;
            for (int i = n - ((a + 1) << 1) + 1; i <= n; ++ i) ans[i] += n - ((a + 1) << 1);
        }
        else if (a == b + 1)
        {
            if (a * 2 + 1 > n) noans();
            int st1 = a + 1, st2 = a + 2;
            for (int j = n, t = 0; t <= b; t ++, j -= 2)
                ans[j] = st1 --, ans[j - 1] = st2 ++;
            ans[n - ((b + 1) << 1)] = 1;
            for (int i = 1; i <= n - (a << 1) - 1; i ++) ans[i] = i;
            for (int i = n - (a << 1); i <= n; ++ i) ans[i] += n - (a << 1) - 1;
        }
        else if (a == b - 1)
        {
            if (b * 2 + 1 > n) noans();
            int st1 = b * 2 + 1, st2 = 1;
            for (int j = 1, t = 0; t <= a; ++ t, j += 2)
                ans[j] = st1 --, ans[j + 1] = st2 ++;
            ans[b * 2 + 1] = b + 1;
            for (int i = (b + 1) << 1; i <= n; ++ i) ans[i] = i;
        }
        for (int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
        puts("");
    }

看到 C 题，感觉是一个二维偏序问题，和 Dyd 讨论了一会，发现可以先排序，后一个向前一个连一条边表示可以战胜，是一个 Tarjan 可以快速搞完，就可以了。但是确实如果是我自己想的话，大概率是想不出来的。

但是开黑就是好。

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
48
49
50
51
52
53
54
55
56
57
58
59
bool cmpa(const Item &k1, const Item &k2){return k1.a < k2.a;}
bool cmpb(const Item &k1, const Item &k2){return k1.b < k2.b;}
 
void tarjan(int x)
{
    dfn[x] = low[x] = ++ tot;
    stk[++ top] = x, ins[x] = true;
    for (auto j : g[x])
        if (!dfn[j])
        {
            tarjan(j);
            low[x] = min(low[x], low[j]);
        }
        else if (ins[j]) low[x] = min(low[x], dfn[j]);
    if (low[x] != dfn[x]) return;
    int now;
    cnt ++;
    do{
        now = stk[top --];
        bel[now] = cnt;
        scc[cnt].push_back(now);
        ins[now] = false;
    }while (now != x);
}
 
int main()
{
    int t;
    cin >> t;
    while (t --)
    {
        scanf("%d", &n);
        tot = cnt = top = 0;
        for (int i = 1; i <= n; ++ i) g[i].clear(), scc[i].clear();
        for (int i = 1; i <= n; ++ i) k[i].id = i, dfn[i] = low[i] = 0, ins[i] = ok[i] = false, deg[i] = 0;
        for (int i = 1; i <= n; ++ i) scanf("%d", &k[i].a);
        for (int i = 1; i <= n; ++ i) scanf("%d", &k[i].b);
        sort(k + 1, k + n + 1, cmpa);
        for (int i = 1; i < n; ++ i) g[k[i + 1].id].push_back(k[i].id);
        sort(k + 1, k + n + 1, cmpb);
        for (int i = 1; i < n; ++ i) g[k[i + 1].id].push_back(k[i].id);
        for (int i = 1; i <= n; ++ i)
            if (!dfn[i]) tarjan(i);
        for (int x = 1; x <= n; ++ x)
            for (auto j : g[x])
                if (bel[j] != bel[x]) deg[bel[j]] ++;
        int deg0 = 0;
        for (int x = 1; x <= cnt; ++ x) deg0 += !deg[x];
        if (deg0 == 1)
            for (int x = 1; x <= cnt; ++ x)
                if (deg[x] == 0)
                    for (auto j : scc[x]) ok[j] = 1;
        for (int x = 1; x <= n; ++ x)
            if (ok[x]) putchar('1');
            else putchar('0');
        putchar('\n');
    }
    return 0;
}

看到 D 题，才 70 min。发现只有两种可能，一种是神仙 DP 题，另一种是构造 + 组合题。

但是我和 Dyd 想了很久的 DP 还是没有想出来。我们想了很久拆开一个多米诺骨牌，然后重新组合，但是和题目求的东西不一样。

一直到最后 5 min，我才发现似乎组合是更靠谱的，但是苦于时间过短，没有想出构造的方案。

赛后 System Tests，还是有些紧张，但幸好没有挂分。

看到评论，发现一堆人吐槽 Pretests too weak，说 C、D 的题的 Pretests 几乎等于没有。

然后好多人都是挂了，排名略微靠前。

赛后

D

开始改 D，发现是一个神仙的构造题。

首先，必须保证 B 的个数一定是 $n$。可以考虑排列组合，是 ${2 * n - b - w \choose n - b}$。注意判断无解。

如果有 BB 或 WW 的话，一定可以构造：一定 BB 和 WW 的个数是一样的，然后我们可以构造成 BB WW BB WW...，然后如果是 BW 的话，直接丢在 WW BB 中间，否则丢在 BB WW 中间。注意丢进去后还是 WW BW BB，仍然可以继续放 BW，WB 同理。

那么我们就减去没有 BB WW 的。让每一个都是 WB / BW，统计个数（$0\sim 2$）计入答案。

但是我们发现还有特例：都是一种颜色的话，是可以满足条件的。判断一下要加上。

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
bool check(char c, char cmp){return c == '?' || c == cmp;}
 
int main()
{
    init();
    flag1 = flag2 = true, ext = 1;
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%s", op);
        cntb += op[0] == 'B', cntb += op[1] == 'B';
        cntw += op[0] == 'W', cntw += op[1] == 'W';
        ext *= ((check(op[0], 'B') & check(op[1], 'W')) + (check(op[0], 'W') & check(op[1], 'B')));
        ext %= Mod;
        flag1 &= check(op[0], 'B') & check(op[1], 'W');
        flag2 &= check(op[0], 'W') & check(op[1], 'B');
    }
    if (cntb > n || cntw > n)
    {
        puts("0");
        return 0;
    }
    // cout << cntb << ' ' << cntw << ' ' << ext << endl;
    ans = fact[2 * n - cntw - cntb] * infact[n - cntb] % Mod * infact[n - cntw] % Mod;
    ans = (ans - ext + flag1 + flag2 + Mod) % Mod;
    cout << ans << endl;
    return 0;
}