【题解】Codeforces Round 758 (Div.1 + Div.2)

更新于 分类于 ， 阅读次数： 本文字数： 6.5k 阅读时长 ≈ 6 分钟

Codeforces Round #758 (Div.1 + Div. 2) A-D题解，即CF1608A-CF1608D，两道思维题，一道涉及图论的建模，一道涉及组合数学的计算

CF1608A

题意

多组数据，构造一个长为 nn 的数列，数字范围 [1,109][1,10^9] ，使得数列中除第一项的每一项都无法整除前一项

分析

2,3,4,5,6...2,3,4,5,6... 的数列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cout << i + 2 << ' ';
    cout << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

CF1608B

题意

tt 组数据，输入 n,a,bn,a,b ，尝试构造一个 1...n1...n 的排列使排列中恰好有 aa 个极大值和 bb 个极小值，t∈[1,104],n∈[2,105]t\in[1,10^4],n\in[2,10^5]

分析

分析略复杂细心就行，但代码写起来非常恼火

极小极大值最多构造个数

考虑最多能构造的极大极小值个数，一定是按以下排列（高矮代表数的大小），即最小-最大-次小-次大…或反过来：

如果 nn 是奇数，最多能构造 ⌊n2⌋,⌊n2⌋−1\lfloor \frac{n}{2}\rfloor,\lfloor \frac{n}{2}\rfloor-1 个极大极小值，若以最小开头则极大值比极小值多 11 个，反之以最大开头极大值比极小值少

如果 nn 是偶数，最多能构造 ⌊n2⌋\lfloor \frac{n}{2}\rfloor 个极大值和极小值

极小极大值构造个数差值

考虑极大极小值的个数最多能差几个

上面分析已经说明可以差一个了，尝试构造差两个：

可以发现，为了出现两个极大值，中间一定会有一个极小值出现，因此极大极小值个数差不可能超过 11

要求极大极小值个数没有达到上限

考虑不能将整个排列都构造成极值连续的情况：

如果极大值比极小值多 11 个（选择最小开头），在最后一个需要的极大值出现之后将剩下的数字降序排列即可：

如果极小值比极大值多 11 个（选择最大开头），在最后一个需要的极小值出现之后将剩下的数字升序排列即可：

如果极大值极小值个数相同（最大最小开头都可，这里用最小开头），在极大值极小值都出现完之后按顺序（如果最小开头就是升序，否则降序）输出剩下的数字即可：

代码

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
void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    int x = min(a, b);
    if (abs(a - b) > 1) {
        cout << "-1\n";
        return;
    }
    if ((n & 1) && ((a == b && min(a, b) > n / 2 - 1) || (a != b && max(a, b) > n / 2))) {
        cout << "-1\n";
        return;
    }
    if ((!(n & 1) && max(a, b) > n / 2 - 1)) {
        cout << "-1\n";
        return;
    }
    if (!a && !b) // 无极值
        for (int i = 1; i <= n; i++)
            cout << i << ' ';
    else if (a == b) // 同等个数
    {
        for (int i = 1; i <= a; i++)
            cout << i << ' ' << n - i + 1 << ' '; // 构造a个极大极小值组
        for (int i = a + 1; i < (n - a + 1); i++)
            cout << i << ' '; // 剩下的升序输出
    } else if (a > b) // 需要的极大值更多
    {
        for (int i = 1; i <= b + 1; i++)
            cout << i << ' ' << n - i + 1 << ' '; // 多输出一个极大值
        for (int i = n - (b + 1); i > b + 1; i--)
            cout << i << ' ';
    } else {
        for (int i = 1; i <= a + 1; i++) // 多输出一个极小值
            cout << n - i + 1 << ' ' << i << ' ';
        for (int i = a + 2; i < (n - (a + 1) + 1); i++)
            cout << i << ' ';
    }
    cout << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

CF1608C

题意

tt 组数据。有地图 11 和地图 22 ，共 nn 个人，在两张地图上的战斗力分别为 ai,bia_i,b_i ，每一张图上各人的战斗力没有重复的值，战斗力高的一定能战胜战斗力低的。每比赛一场，淘汰输的一方，主办方可以随意搭配每一场的对战人员和地图。问每个人是否都能赢得最后的胜利（利用不同的对战顺序）

分析

这题要看到战斗力高的一定能战胜战斗力低的，所以能力最高的可以一路打败所有人，两张图随意挑选，要想到（我当时并没有想到）每两个人之间是一条单向边，连出来的有向图中能走遍所有点的节点一定可以取胜（同时也是对战的顺序）

所以思路就是建图、缩点、重构图的同时记录入边，找到重构图中没有入边的点（原图中的强连通分量）（因为这里是一条链上继续加边，因此重构图有且仅有一个点没有入边），里面所有的人都是可以取胜的，其他人都不可以

代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
pii a[N], b[N];
vector<int> G[N], G2[N];
set<int> G2check[N];
int dfn[N], dfntot, low[N];
int st[N], top;
bool instack[N];
int scc[N], sc;
bool vst[N];
int n;

void init()
{
    for (int i = 1; i <= n; i++) {
        a[i].second = b[i].second = i;
        G[i].clear();
        dfn[i] = 0;
    }
    sc = dfntot = top = 0;
}

void dfs(int rt)
{
    low[rt] = dfn[rt] = ++dfntot;
    st[++top] = rt;
    instack[rt] = true;
    for (auto v : G[rt]) {
        if (!dfn[v]) {
            dfs(v);
            low[rt] = min(low[rt], low[v]);
        } else if (instack[v])
            low[rt] = min(low[rt], dfn[v]);
    }
    if (dfn[rt] == low[rt]) {
        ++sc;
        while (st[top] != rt) {
            scc[st[top]] = sc;
            instack[st[top]] = false;
            top--;
        }
        scc[st[top]] = sc;
        instack[st[top]] = false;
        top--;
    }
}

void rebuild()
{
    for (int i = 1; i <= sc; i++) {
        G2[i].clear();
        G2check[i].clear();
        vst[i] = false;
    }
    for (int i = 1; i <= n; i++)
        for (auto v : G[i])
            if (scc[v] != scc[i] && !G2check[scc[i]].count(scc[v])) {
                G2[scc[i]].push_back(scc[v]);
                G2check[scc[i]].insert(scc[v]);
                vst[scc[v]] = true;
            }
}

void solve()
{
    cin >> n;
    init();
    for (int i = 1; i <= n; i++)
        cin >> a[i].first;
    for (int i = 1; i <= n; i++)
        cin >> b[i].first;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i < n; i++) {
        G[a[i + 1].second].push_back(a[i].second);
        G[b[i + 1].second].push_back(b[i].second);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            dfs(i);
    rebuild();
    for (int i = 1; i <= sc; i++)
        if (!vst[i]) {
            for (int j = 1; j <= n; j++)
                cout << (scc[j] == i ? '1' : '0');
            break;
        }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

CF1608D

题意

一个东西有左面右面，可以涂黑/白色，nn 个这些东西可以任意顺序排列，要求一个东西的右面与它右边的那个东西的左面颜色不同，第一个和最后一个以成环来处理

一组数据，有 nn 个东西，给出已经涂的颜色 W 、 B ，没有涂的用 ? 代替，求所有合法的涂色方案数 mod  998244353\mod 998244353

分析

由前一个的右面和下一个的左面颜色不同（且整个是个环）可以知道合法的方案里黑白的个数是相等的，设黑的个数为 ww，白的个数为 bb，则所有的涂色方案数（只考虑个数合法）为 C(2n−w−b,n−b)C(2n-w-b,n-b)，其中 w,b<=nw,b<=n

每个东西的涂色共有 44 种情况：WW, WB, BW, BB，可以发现有一个WW，个数合法方案必有一个BB（否则黑白个数不等）

考虑相邻的搭配：WW和BB相邻搭配就可以合法；WB有两种合法，一种是全是WB，另一种是WB夹在BB和WW之间，没有别的情况了；BW同理

所以：

序列中只要有BB和WW一定是合法的，无论怎么天色，有WB和BW有就WBWB…和BWBW…顺次排好插BB和WW中间，因此设一个标志位 flag 记录原序列中是否有这两个中的一个，如果有答案就是上面那个组合数；

序列中没有BB和WW的情况下，只有全WB和全BW的序列是合法的。原序列中的B+?和W+?被填成BW和WB的情况先全部删除，方案数是 1×1×1...=11\times 1\times 1...=1 ，原序列中??被填成BW和WB的方案数为 2×2×2...2\times 2\times 2...，二者乘起来作为容斥删除的非法方案数。容斥加回多删了的全WB和全BW序列，如果B?或?W，和W?或?B同时在原序列中出现了，那么就不可能填出全WB或全BW的合法序列，不需要容斥加回；只出现其中一类可以填出一个合法序列，容斥加回一种方案；两种都没出现则可以填出两个合法序列，容斥加回两个方案

代码

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
60
const ll mod = 998244353;

int fac[N], inv[N];
ll qpow(ll m, ll n)
{
    ll ans = 1;
    while (n) {
        if (n & 1)
            ans = (ans * m) % mod;
        m = (m * m) % mod;
        n >>= 1;
    }
    return ans;
}
void init(int n)
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
int C(int x, int y)
{
    if (x < y || y < 0)
        return 0;
    return 1ll * fac[x] * inv[x - y] % mod * inv[y] % mod;
}
int main()
{
    int n;
    cin >> n;
    init(n << 1);
    string s;
    bool flag = false, bw = false, wb = false; // 原序列中是否出现了BB/WW、B?/?W、W?/?B
    ll qq = 0, b = 0, w = 0; // 原序列中出现的??个数、b个数、w个数
    for (int i = 0; i < n; i++) {
        cin >> s;
        b += (s[0] == 'B') + (s[1] == 'B');
        w += (s[0] == 'W') + (s[1] == 'W');
        if (s[0] == s[1]) {
            if (s[0] == '?')
                qq++;
            else
                flag = true;
        } else {
            bw |= (s[0] == 'B') | (s[1] == 'W'); // 是否出现B?/?W
            wb |= (s[0] == 'W') | (s[1] == 'B'); // 是否出现W?/?B
        }
    }
    ll ans = C(2 * n - w - b, n - b);
    if (!flag) // 需要容斥
    {
        ans = (ans - qpow(2ll, qq) + mod) % mod; // 容斥删除没有WW和BB的所有序列
        ans = (ans + (bw ^ 1) + (wb ^ 1)) % mod;
    }
    cout << ans;
    return 0;
}