CF-738-div2

Posted on Edited on In Views:
Symbols count in article: 9.6k
题目 A B C D1 D2 E
通过情况 AC AC AC AC O O
难度 800 800 1100 1300 1500 1900

A. Mocha and Math

题面

略

解法

对所有数做与运算后直接输出

代码

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
/*
 * @题目: A. Mocha and Math
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-15 22:23:32
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-15 22:38:46
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        int ans = read();
        rep(i, 2, n)
        {
            int tmp = read();
            ans &= tmp;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Mocha and Red and Blue

题面

略

解法

贪心

代码

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
/*
 * @题目: B. Mocha and Red and Blue
 * @算法: 贪心
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-15 22:23:35
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-15 22:46:08
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 210
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
char s[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        scanf("%s", s + 1);
        int pre = 0;
        rep(i, 1, n)
        {
            if (s[i] == '?')
            {
                if (s[pre] != '?')
                    pre = i;
                continue;
            }
            else
            {
                if (s[pre] == '?')
                {
                    per(j, i - 1, pre)
                        s[j] = s[j + 1] == 'R' ? 'B' : 'R';
                }
            }
        }
        if (s[pre] == '?')
            rep(i, pre, n) s[i] = s[i - 1] == 'R' ? 'B' : 'R';
        puts(s + 1);
    }
    return 0;
}

C. Mocha and Hiking

题面

略

解法

简单分析可知，一定可以构造出来可行解，只需要找到以下三种情况之一：
①$n+1\rightarrow 1$
②$n\rightarrow n+1$
③$i\rightarrow n+1\rightarrow i+1,i<n$

代码

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
/*
 * @题目: C. Mocha and Hiking
 * @算法: 图
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-15 22:23:38
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-15 22:58:19
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int a[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        rep(i, 1, n) a[i] = read();
        int f = 0;
        a[n + 1] = 1;
        rep(i, 1, n + 1) if (a[i] == 1 && a[i - 1] == 0) f = 1;
        if (f == 0)
        {
            puts("-1");
            continue;
        }
        rep(i, 1, n)
        {
            if ((a[i - 1] == 0 && a[i] == 1) && f)
            {
                printf("%d ", n + 1);
                f = 0;
            }
            printf("%d ", i);
        }
        if (f)
            printf("%d", n + 1);
        puts("");
    }
    return 0;
}

D1. Mocha and Diana (Easy Version)

题面

向两个图（无环路）中在相同位置加树边，直到不能继续加边

解法

使用并查集判断两点是否在同一个图中，枚举所有边，时间复杂度$O(n^2)$（$O\left( n\alpha \left( n \right) \right) $）

代码

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
/*
 * @题目: D1. Mocha and Diana (Easy Version)
 * @算法: 并查集
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-15 22:23:43
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-15 23:10:57
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int par1[maxn], par2[maxn];
int ans[maxn][2];
int find1(int x)
{
    return x == par1[x] ? x : par1[x] = find1(par1[x]);
}
int find2(int x)
{
    return x == par2[x] ? x : par2[x] = find2(par2[x]);
}
int main()
{
    int n = read(), m1 = read(), m2 = read();
    rep(i, 1, n) par1[i] = par2[i] = i;
    rep(i, 1, m1)
    {
        int u = read(), v = read();
        u = find1(u), v = find1(v);
        par1[u] = v;
    }
    rep(i, 1, m2)
    {
        int u = read(), v = read();
        u = find2(u), v = find2(v);
        par2[u] = v;
    }
    int cnt = 0;
    rep(i, 1, n)
    {
        rep(j, i + 1, n)
        {
            int u1 = find1(i), v1 = find1(j);
            int u2 = find2(i), v2 = find2(j);

            if (u1 != v1 && u2 != v2)
            {
                par1[u1] = v1;
                par2[u2] = v2;
                ans[cnt][0] = i, ans[cnt][1] = j;
                cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    rep(i, 0, cnt - 1) printf("%d %d\n", ans[i][0], ans[i][1]);
    return 0;
}

D2. Mocha and Diana (Hard Version)

题面

同D1

解法

可以证明，必然有一个图最后会形成树（有$n-1$条边）
先将1和其他点尝试进行连边，那么图中所有点必属于以下三种集合之一：
①在两个图中均与1相连的点集$S$
②在图1中与1相连，在图2中不与1相连点集$T_1$
③在图1中不与1相连，在图2中与1相连点集$T_2$
分属$T_1$和$T_2$中任意两点之间必然可以加边（否则不满足条件），所以接下来只需将$T_1$和$T_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
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
/*
 * @题目: D2. Mocha and Diana (Hard Version)
 * @算法: 并查集
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-15 22:23:46
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-18 23:34:06
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 1000010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int par1[maxn], par2[maxn];
int ans[maxn][2];
int s1[maxn], s2[maxn], p1, p2;
int find1(int x)
{
    return x == par1[x] ? x : par1[x] = find1(par1[x]);
}
int find2(int x)
{
    return x == par2[x] ? x : par2[x] = find2(par2[x]);
}
int main()
{
    int n = read(), m1 = read(), m2 = read();
    rep(i, 1, n) par1[i] = par2[i] = i;
    rep(i, 1, m1)
    {
        int u = read(), v = read();
        u = find1(u), v = find1(v);
        par1[u] = v;
    }
    rep(i, 1, m2)
    {
        int u = read(), v = read();
        u = find2(u), v = find2(v);
        par2[u] = v;
    }
    int cnt = 0;

    rep(i, 2, n)
    {
        int u1 = find1(1), v1 = find1(i);
        int u2 = find2(1), v2 = find2(i);

        if (u1 != v1 && u2 != v2)
        {
            par1[u1] = v1;
            par2[u2] = v2;
            ans[cnt][0] = 1, ans[cnt][1] = i;
            cnt++;
        }
    }
    rep(i, 2, n)
    {
        int u1 = find1(1), v1 = find1(i);
        int u2 = find2(1), v2 = find2(i);
        if (u1 != v1)
            s1[p1++] = i, par1[u1] = v1;
        else if (u2 != v2)
            s2[p2++] = i, par2[u2] = v2;
    }
    printf("%d\n", cnt + min(p1, p2));
    rep(i, 0, cnt - 1) printf("%d %d\n", ans[i][0], ans[i][1]);
    rep(i, 0, min(p1, p2) - 1) printf("%d %d\n", s1[i], s2[i]);
    return 0;
}

E. Mocha and Stars

题面

给定$n,m$，求满足以下条件的方案数:
①$a_i\in \left[ l_i,r_i \right] ,1\leqslant i\leqslant n$
②$\sum_{i=1}^n{a_i\leqslant m}$
③$gcd\left( a_1,…,a_n \right) =1$
答案对$998244353$取模

解法

设$f(a_1,a_2,…,a_n)$为满足前两个条件的方案数，然后用莫比乌斯反演对第三个条件化简
$\begin{aligned}
&\sum_{a_1=l_1}^{r_1}{\sum_{a_2=l_2}^{r_2}{\cdots}}\sum_{a_n=l_n}^{r_n}{[}\mathrm{gcd(}a_1,a_2,…,a_n)=1]f(a_1,a_2,…,a_n)\\
=&\sum_{a_1=l_1}^{r_1}{\sum_{a_2=l_2}^{r_2}{\cdots}}\sum_{a_n=l_n}^{r_n}{f}(a_1,a_2,…,a_n)\sum_{d\mid \mathrm{gcd(}a_1,a_2,…,a_n)}{\mu}(d)\\
=&\sum_{a_1=l_1}^{r_1}{\sum_{a_2=l_2}^{r_2}{\cdots}}\sum_{a_n=l_n}^{r_n}{f}(a_1,a_2,…,a_n)\sum_{d\mid a_1,d\mid a_2,…,d\mid a_n}{\mu}(d)\\
=&\sum_{d=1}^m{\mu}(d)\sum_{a_1=\lceil \frac{l_1}{d} \rceil}^{\lfloor \frac{r_1}{d} \rfloor}{\sum_{a_2=\lceil \frac{l_2}{d} \rceil}^{\lfloor \frac{r_2}{d} \rfloor}{\cdots}}\sum_{a_n=\lceil \frac{l_n}{d} \rceil}^{\lfloor \frac{r_n}{d} \rfloor}{f}(a_1,a_2,…,a_n)\\
\end{aligned}$
接下来对于每一个d用前缀和+背包计数即可

代码

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
/*
 * @题目: E. Mocha and Stars
 * @算法: 莫比乌斯反演、背包DP
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-21 14:49:44
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-21 15:01:56
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 100010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int mod = 998244353;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int prim[maxn], mu[maxn], cnt;
bool vis[maxn];
void get_mu(int n)
{
    mu[1] = 1;
    rep(i, 2, n)
    {
        if (!vis[i])
        {
            mu[i] = -1, prim[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * prim[j] <= n; j++)
        {
            vis[i * prim[j]] = 1;
            if (i % prim[j] == 0)
                break;
            mu[i * prim[j]] = -mu[i];
        }
    }
}
int n, m;
int l[maxn], r[maxn];
int nl[maxn], nr[maxn];
int dp[maxn], f[maxn];
int main()
{
    n = read(), m = read();
    get_mu(1e5);
    rep(i, 1, n) l[i] = read(), r[i] = read();
    ll ans = 0;
    rep(d, 1, m)
    {
        if (mu[d])
        {
            rep(i, 1, n) nl[i] = (l[i] + d - 1) / d, nr[i] = r[i] / d;
            int sum = m / d;
            rep(i, 0, sum) dp[i] = 1;
            rep(i, 1, n)
            {
                rep(j, 1, sum) f[j] = 0;
                rep(j, nl[i], sum)
                {
                    f[j] = dp[j - nl[i]];
                    if (j - nr[i] - 1 >= 0)
                        f[j] = (f[j] - dp[j - nr[i] - 1] + mod) % mod;
                }
                dp[0] = 0;
                rep(j, 1, sum) dp[j] = (dp[j - 1] + f[j]) % mod;
            }
            ans = (ans + dp[sum] * mu[d] + mod) % mod;
        }
    }
    printf("%lld", ans);
    return 0;
}