CF#734 div3

Posted on Edited on In Views:
Symbols count in article: 12k

（模拟赛）

题目 A B1 B2 C D1 D2 E F
通过情况 AC AC AC AC AC O AC O
难度 800 800 1400 1500 1700 2100 2000 2200

A. Polycarp and Coins

题面

略

解法

略

代码

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
/*
 * @题目: A. Polycarp and Coins
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 09:22:46
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 09:32:35
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#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;
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 cnt1, cnt2;
        cnt1 = cnt2 = n / 3;
        if (n % 3 == 1)
            cnt1++;
        else if (n % 3 == 2)
            cnt2++;
        printf("%d %d\n", cnt1, cnt2);
    }
    return 0;
}

B1. Wonderful Coloring - 1

题面

略

解法

统计字母出现次数即可，分类讨论

代码

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
/*
 * @题目: B1. Wonderful Coloring - 1
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 09:22:50
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 10:21:49
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#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;
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[100];
int cnt[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        scanf("%s", s + 1);
        memset(cnt, 0, sizeof(cnt));
        int n = strlen(s + 1);
        rep(i, 1, n)
            cnt[s[i] - 'a']++;
        int cnt1 = 0, cnt2 = 0;
        rep(i, 0, 25)
        {
            if (cnt[i] == 0)
                continue;
            if (cnt[i] >= 2)
                cnt2++;
            else if (cnt[i] == 1)
                cnt1++;
        }
        printf("%d\n", cnt1 / 2 + cnt2);
    }
    return 0;
}

B2. Wonderful Coloring - 2

题面

略

解法

把每种数字前$m\left( m\leqslant k \right) $次位置记录下来，由小到大染色即可（注意控制下染色的次数是$k$的倍数）

代码

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
/*
 * @题目: B2. Wonderful Coloring - 2
 * @算法: 数学
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 09:33:07
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 10:15:04
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#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;
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 col[maxn];
int ccnt[maxn];
int a[maxn];
vector<int> b[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read(), k = read();
        memset(a, 0, sizeof(a));
        rep(i, 1, n) b[i].clear();
        rep(i, 1, n)
        {
            int x = read();
            if (b[x].size() < k)
                b[x].push_back(i);
        }
        int m = 0;
        rep(i, 1, n)
        {
            m += b[i].size();
        }
        m -= m % k;
        int color = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < b[i].size(); j++)
            {
                color %= k;
                a[b[i][j]] = ++color;
                if (--m == 0)
                    break;
            }
            if (m == 0)
                break;
        }
        rep(i, 1, n) printf("%d ", a[i]);
        putchar('\n');
    }
    return 0;
}

C. Interesting Story

题面

给定$n$个由小写字母组成的字符串，选取其中$k$个字符串使得其中某个字母出现的次数大于其他字母出现次数的总和。输出最大的$k$，若没有输出$0$。

解法

对于输入的每一个字符串，进行预处理，单独计算每个字母的总和与其他字母出现次数总和之差。
对于每个字母，按照该字母的贡献对字符串进行排序，从大到小计算最多能选取的个数（见代码）。

代码

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
/*
 * @题目: C. Interesting Story
 * @算法: 暴力、排序
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 09:23:01
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 10:47:29
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 200010
#define maxm 400010
#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;
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[maxm];
int cnt[26][maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        rep(i, 0, n - 1)
        {
            scanf("%s", s);
            int m = strlen(s);
            rep(j, 0, 25) cnt[j][i] = -m;
            rep(j, 0, m - 1) cnt[s[j] - 'a'][i] += 2;
        }
        int ans = 0;
        rep(j, 0, 25)
        {
            sort(cnt[j], cnt[j] + n);
            int sum = 0, tot = 0;
            per(i, n - 1, 0)
            {
                sum += cnt[j][i];
                if (sum > 0)
                    tot++;
                else
                    break;
            }
            ans = max(ans, tot);
        }
        printf("%d\n", ans);
    }
    return 0;
}

D1. Domino (easy version)

题面

给定$n\times m$（$n\times m$为偶数）的矩形，判断用$k$个$1\times 2$个和$\frac{n m}{2}-k$个$2\times 1$的小矩形是否能刚好填满大矩形（不重叠）

解法

讨论两种情况
（1）n和m均为偶数，不难想到这时必须保证横着的和竖着的小矩形必须都是偶数个（组成小正方形）
（2）当n或m为奇数，只需要把多的一行或列用横着的或竖着的填上即可（易证如果填不上则无解），之后退化成情况（1）

代码

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
/*
 * @题目: D1. Domino (easy version)
 * @算法: 构造
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 09:23:07
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 11:14:30
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#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;
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(), m = read(), k1 = read();
        int k2 = n * m / 2 - k1;
        if (m % 2 == 1)
        {
            k2 -= n / 2;
            if (k2 < 0)
            {
                puts("NO");
                continue;
            }
        }
        else if (n % 2 == 1)
        {
            k1 -= m / 2;
            if (k1 < 0)
            {
                puts("NO");
                continue;
            }
        }
        if (k1 * k2 % 2 != 0)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}

D2. Domino (hard version)

题面

在D1的基础上输出图形

解法

D1的小扩展，构造一下即可

代码

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
100
101
102
/*
 * @题目: D2. Domino (hard version)
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 12:28:00
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 12:41:02
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#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;
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 mp[200][200];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read(), m = read(), k1 = read();
        int k2 = n * m / 2 - k1;
        if (m % 2 == 1)
        {
            k2 -= n / 2;
            if (k2 < 0)
            {
                puts("NO");
                continue;
            }
            rep(i, 0, n / 2 - 1)
            {
                mp[i << 1][m - 1] = mp[i << 1 | 1][m - 1] = (i & 1) ? 'x' : 'y';
            }
        }
        else if (n % 2 == 1)
        {
            k1 -= m / 2;
            if (k1 < 0)
            {
                puts("NO");
                continue;
            }
            rep(i, 0, m / 2 - 1)
            {
                mp[n - 1][i << 1] = mp[n - 1][i << 1 | 1] = (i & 1) ? 'x' : 'y';
            }
        }
        if (k1 * k2 % 2 != 0)
        {
            puts("NO");
            continue;
        }

        puts("YES");
        rep(i, 0, n / 2 - 1)
        {
            rep(j, 0, m / 2 - 1)
            {
                if (k1)
                {
                    k1 -= 2;
                    mp[i << 1][j << 1] = mp[i << 1][j << 1 | 1] = ((i + j) & 1) ? 'a' : 'b';
                    mp[i << 1 | 1][j << 1] = mp[i << 1 | 1][j << 1 | 1] = ((i + j) & 1) ? 'c' : 'd';
                }
                else
                {
                    mp[i << 1][j << 1] = mp[i << 1 | 1][j << 1] = ((i + j) & 1) ? 'e' : 'f';
                    mp[i << 1][j << 1 | 1] = mp[i << 1 | 1][j << 1 | 1] = ((i + j) & 1) ? 'g' : 'h';
                }
            }
        }
        rep(i, 0, n - 1)
        {
            rep(j, 0, m - 1)
            {
                putchar(mp[i][j]);
            }
            putchar('\n');
        }
    }
    return 0;
}

E. Fixed Points

题面

给定数列$a_1,a_2,…,a_n$，删除其中$n-m$个数变成$b_1,b_2,…,b_m$(每次删除后向左补齐)，求使得最终数列里$b_i=i$的个数为k个的最小删除次数，若不存在输出$-1$

解法

$dp[i][j]$表示前$i$个数里剩$j$个数时满足条件$b_i=i$的最大值，此时有递推式$\begin{cases}
f[i+1][j]=max\left( f[i+1][j],f[i][j] \right)\\
f[i+1][j+1]=max\left( f[i+1][j+1],f[i][j]+\left( a[i+1]==j+1?1:0 \right) \right)\\
\end{cases}$

代码

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
/*
 * @题目: E. Fixed Points
 * @算法: 线性DP
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 11:20:19
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 11:25:19
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 2010
#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;
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 f[maxn][maxn];
int a[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read(), k = read();
        rep(i, 1, n) a[i] = read();
        rep(i, 0, n) rep(j, 0, i) f[i][j] = 0;
        rep(i, 0, n)
        {
            rep(j, 0, i)
            {
                f[i + 1][j] = max(f[i + 1][j], f[i][j]);
                f[i + 1][j + 1] = max(f[i + 1][j + 1], f[i][j] + (a[i + 1] == j + 1 ? 1 : 0));
            }
        }
        int ans = -1;
        per(i, n, 0)
        {
            if (f[n][i] >= k)
            {
                ans = n - i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

F. Equidistant Vertices

题面

给定一棵树并在树上选k个点，使得这k个点中两两树上距离相等。

求选点方法数。

解法

当$k=2$时,显然树上任意两点满足条件，答案为$C_{n}^{2}$

当$k\geqslant 3$时，不难得出满足条件的点的距离必然经过相同的顶点，并且①顶点与点集中的各点距离相等②该点是点集中任意两点的公共祖先

这样，我们遍历树上的所有点作为顶点，统计子树中各层点的数量。对于每棵子树，$dp[i][j]$表示在深度为i层中选择满足条件的j个点的选取方法数，则有递推式$dp[i][j] = dp[i][j] + dp[i][j - 1] * cnt[i]$，最后将各层的dp[i][k]累加即为该顶点的方法数（通俗理解为将$LN$棵子树的每一层点进行组合）

具体实现见代码

代码

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
100
101
102
103
104
105
106
107
108
/*
 * @题目: F. Equidistant Vertices
 * @算法: 树形DP
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-06 14:19:30
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-06 15:27:10
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 110
#define maxm 210
#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;
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;
}
const int mod = 1e9 + 7;
struct edge
{
    int v, nxt;
} e[maxm];
int cnt[maxn], head[maxn], tot;
void init()
{
    tot = 0;
    memset(e, 0, sizeof(e));
    memset(head, 0, sizeof(head));
}
void add(int u, int v)
{
    e[++tot].v = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
void dfs(int u, int fu, int d)
{
    cnt[d]++;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fu)
            continue;
        dfs(v, u, d + 1);
    }
}
int dp[maxn][maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read(), k = read();
        init();
        rep(i, 1, n - 1)
        {
            int u = read(), v = read();
            add(u, v), add(v, u);
        }
        if (k == 2)
        {
            printf("%lld\n", n * (n - 1ll) / 2 % mod);
            continue;
        }
        ll ans = 0;
        for (int u = 1; u <= n; u++)
        {
            memset(dp, 0, sizeof(dp));
            for (int i = 1; i < n; i++)
                dp[i][0] = 1;
            for (int i = head[u]; i; i = e[i].nxt)
            {
                memset(cnt, 0, sizeof(cnt));
                int v = e[i].v;
                dfs(v, u, 1);
                for (int i = 1; i < n; i++)
                {
                    if (cnt[i] == 0)
                        break;
                    per(j, k, 1)
                    {
                        dp[i][j] = 1ll * (dp[i][j] + dp[i][j - 1] * cnt[i]) % mod;
                    }
                }
            }
            for (int i = 1; i <= n; i++)
                ans = (ans + dp[i][k]) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}