A. Same Difference#

Description#

给定一个长度为 $n$ 的字符串 $s$ ，由小写字母组成。

在一次操作中，你可以选择一个整数 $i$ ，满足 $1 \leq i<n$ ，并将 $s_i$ 改为 $s_{i+1}$ 。

使所有字符相同所需的最少操作次数是多少？可以证明这是始终可行的。

Solution#

显然， $s_n$ 是不可被修改的，所以只能修改前面的 $n-1$ 个数，使得其全部与 $s_n$ 相同。所以只需要对每个不等于 $s_n$ 的字符做一次操作。

时间复杂度： $O(n)$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
    string s;
17
    cin>>N;
18
    cin>>s;
19
    char ss=s[s.size()-1];
20
    int sum=0;
21
    for(int i=0;i<s.size()-1;i++){
22
        if(s[i]==ss){
23
            continue;
24
        }
25
        sum++;
26
    }
27
    cout<<sum<<endl;
28
}
29
signed main()
30
{
31
#ifdef NOI_IO
32
    freopen(".in", "r", stdin);
33
    freopen(".out", "w", stdout);
34
#endif
35
    ios::sync_with_stdio(0);
36
    cin.tie(nullptr), cout.tie(nullptr);
37
#ifdef MULTI_CASES
38
    cin >> T;
39
    while (T--)
40
#endif
41
        Solve();
42
    return 0;
43
}

B. Tab Closing#

Description#

你已盯着电脑屏幕太久，是时候休息一下，去触摸一下草地了。

你的屏幕长度为 $a$ ，上面显示着 $n$ 个标签页。你希望通过点击它们右端的“x”来关闭所有标签页。

每个标签页是一个长度为 $\textrm{len}=\min(b,\frac{a} {m})$ 的线段，其中 $m$ 表示剩余标签页的数量。标签页总是紧密地从左端点开始顺序排列；也就是说，标签页的“x”位置分别在距离左端点 $\textrm{len}, 2 \cdot \textrm{len}, 3 \cdot \textrm{len}, \ldots, m \cdot \textrm{len}$ 的位置。请注意，随着你关闭标签页，它们的长度会发生变化。

现在你的光标位于屏幕的左端点。你想知道，关闭所有标签页，最少需要移动鼠标的次数“次”。

如果你对题意理解有困难，可以参考浏览器标签页的可视化示意，或点击这里。

Solution#

观察样例，发现所有的答案都是 $1$ 或 $2$ 。

手动模拟一下这一过程，可以发现，如果 $\frac{a}{m}<b$ ，也就是当标签页铺满整个屏幕的情况下，只需要移动到屏幕的最右侧，一直点击清除即可。

反之，如果 $\frac{a}{m}\geq b$ ，也就是每个标签页可以完全展开到长度 $b$ 的情况下，只需要在第一个标签页的位置一直点击清除即可。

总操作次数 $ans\le 2$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
// int a[MaxN];
14
int a,b;
15
inline void Solve()
16
{
17
    cin>>a>>b>>N;
18
    int m=a/b;
19
    if(N>m&&a!=b){
20
        cout<<2<<endl;
21
    }
22
    else{
23
        cout<<1<<endl;
24
    }
25
}
26
signed main()
27
{
28
#ifdef NOI_IO
29
    freopen(".in", "r", stdin);
30
    freopen(".out", "w", stdout);
31
#endif
32
    ios::sync_with_stdio(0);
33
    cin.tie(nullptr), cout.tie(nullptr);
34
#ifdef MULTI_CASES
35
    cin >> T;
36
    while (T--)
37
#endif
38
        Solve();
39
    return 0;
40
}

C. Cyclic Merging#

Description#

你被赋予了 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ，它们在一个环上排列。对于每个 $1 \le i < n$ ， $a_i$ 和 $a_{i+1}$ 是相邻的； $a_1$ 和 $a_n$ 也是相邻的。

你需要恰好执行以下操作 $n-1$ 次：

选择环上任意一对相邻的元素，设它们的值为 $x$ 和 $y$ ，并将它们合并为一个值为 $\max(x,y)$ 的元素，合并的代价也是 $\max(x,y)$ 。

请注意，该操作会使环的大小减一，并相应更新相邻关系。

请计算将环合并为一个元素的最小总成本。

Solution#

考虑贪心，每次操作优先删除代价最小的。同时，每个数与其左侧的数合并等价于其左侧的数与这个数合并。所以只需要统计一个数向右合并的代价并从小到大排序，然后取其前 $n-1$ 个即可。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
int a[MaxN];
14
int b[MaxN];
15
inline void Solve()
16
{
17
    cin>>N;
18
    for(int i=1;i<=N;i++){
19
        cin>>a[i];
20
    }
21
    for(int i=1;i<=N;i++){
22
        int j=i+1;
23
        if(j==N+1)j=1;
24
        b[i]=max(a[i],a[j]);
25
    }
26
    sort(b+1,b+N+1);
27
    int ans=0;
28
    for(int i=1;i<N;i++){
29
        ans+=b[i];
30
    }
31
    cout<<ans<<endl;
32
}
33
signed main()
34
{
35
#ifdef NOI_IO
36
    freopen(".in", "r", stdin);
37
    freopen(".out", "w", stdout);
38
#endif
39
    ios::sync_with_stdio(0);
40
    cin.tie(nullptr), cout.tie(nullptr);
41
#ifdef MULTI_CASES
42
    cin >> T;
43
    while (T--)
44
#endif
45
        Solve();
46
    return 0;
47
}
48
// 1 1 4 5 1 4 1
49
// 1 4 5 5 4 4 1
50
// 1 1 3 2
51
// 1 3 3 2

D. Marble Council#

Description#

你得到一个多重集 $a$ ，它由 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 组成。你希望通过以下步骤生成一个新的多重集 $s$ ：

将 $a$ 分割成任意数量的非空多重集 $x_1,x_2,\ldots,x_k$ ，每个元素恰好属于其中一个多重集。
最初， $s$ 为空。对每个 $x_i$ ，从其众数 $^{\text{∗}}$ 中选择一个并将其插入 $s$ 。

请计算通过该过程能生成的不同多重集 $s$ 的个数，结果对 $998\,244\,353$ 取模。

请注意，统计的是不同多重集的数量，这意味着元素的顺序不重要，但每个元素的个数很重要，即 $\{1,1,2\}$ 、 $\{1,2\}$ 、 $\{1,1,2,2\}$ 都被视为不同的。

$^{\text{∗}}$ 多重集的众数定义为出现次数最多的元素；若多个元素并列为最大值，则它们都被视为众数。

Solution#

首先，题目给定的 $a$ 是一个多重集合，也就是无序的。所以答案只与每个元素出现的频率 $c_i$ 有关。

考虑多重集合 $S$ ，如果 $a_i$ 在 $S$ 中出现了 $t_i$ 次，也就意味着划分出的子序列中，有 $t_i$ 个序列的众数是 $a_i$ 。那么 $S$ 可以表示为 $S=\{i|a_i^{t_i}\}$ 。

之后考虑如何判定 $S$ 合法，可以得出结论：

\sum_{i\in S}c_i\geq \max_{j\notin S}c_j

考虑 $i\in S$ 的部分，如果 $i\in S$ ，也就意味着 $a_i$ 至少是一个子序列的众数。那么根据众数的定义，在这一子序列中， $a_i$ 出现的次数必须大于等于其他数出现的次数。那么我们将这些数先填入子序列。

之后考虑 $j\notin S$ 的部分，如果 $j\notin S$ ，也就意味着 $a_j$ 在每个子序列都不被作为众数。那么为了将这部分填入子序列，一定需要满足子序列中一定存在一个 $a_i$ 出现次数大于等于 $a_j$ 。

所以问题就转化为：求出所有合法的子序列的乘积和，一个子序列合法当且仅当元素之和不小于 $\max{c_i}$ 。

之后通过背包DP求解即可。设 $f_{i,j}$ 表示前 $i$ 个元素，已选择的元素之和为 $j$ 时的答案。

f_{i,j}=f_{i-1,j}+f_{i-1,j-c_i}\cdot c_i

复杂度 $O(n^2)$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 5100;
10
const int INF = 1e9;
11
const int mod = 998244353;
12
int T = 1, N, M;
13
int a[MaxN];
14
int sum[MaxN];
15
int dp[MaxN][MaxN];
16
inline void Solve()
17
{
18
    cin >> N;
19
    memset(sum, 0, sizeof sum);
20
    int maxn = 0;
21
    for (int i = 1; i <= N; i++)
22
    {
23
        cin >> a[i];
24
        sum[a[i]]++;
25
        maxn = max(maxn, sum[a[i]]);
26
    }
27
    dp[0][0] = 1;
28
    for (int i = 1; i <= N; i++)
29
    {
30
        for (int j = 0; j <= N; j++)
31
        {
32
            if (j < sum[i])
33
            {
34
                dp[i][j] = dp[i - 1][j];
35
            }
36
            else
37
            {
38
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - sum[i]] * sum[i]) % mod;
39
            }
40
        }
41
    }
42
    int ans = 0;
43
    for (int i = maxn; i <= N; i++)
44
    {
45
        (ans += dp[N][i]) %= mod;
46
    }
47
    cout << ans << endl;
48
}
49
signed main()
50
{
51
#ifdef NOI_IO
52
    freopen(".in", "r", stdin);
53
    freopen(".out", "w", stdout);
54
#endif
55
    ios::sync_with_stdio(0);
56
    cin.tie(nullptr), cout.tie(nullptr);
57
#ifdef MULTI_CASES
58
    cin >> T;
59
    while (T--)
60
#endif
61
        Solve();
62
    return 0;
63
}

Codeforces Round 1064 (Div. 2）题解

A. Same Difference#

Description#

Solution#

Code#

B. Tab Closing#

Description#

Solution#

Code#

C. Cyclic Merging#

Description#

Solution#

Code#

D. Marble Council#

Description#

Solution#

Code#