1114Div3-①B-模拟②C2-贪心③D-构造#

Dashboard - Codeforces Round 1114 (Div. 3) - Codeforces

A-模拟#

题目#

爱丽丝、鲍勃和查理正在玩一个代币游戏。他们开始时分别有 a 、 b 和 c 个代币。

游戏分轮进行。在每一轮开始之前，他们都要检查每个人拥有的代币数：

如果任何两名玩家拥有的代币数量完全相同，游戏立即结束。
否则，一轮游戏开始时，三位玩家拥有的代币数量完全不同。拥有最多代币的玩家给拥有最少代币的玩家 1 个代币。

给定起始代币为 a 、 b 和 c ，请确定游戏到底要进行多少轮才会结束

模拟#

对a,b,c进行排序，假设a≤b≤c，每次操作使a+=1,c-=1，a和c都趋向于b，那么显然答案为min(b - a,c - b)

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    int t;
5
    cin >> t;
6
    while(t--) {
7
        vector<int> v(3);
8
        for(int &x : v) cin >> x;
9
        sort(v.begin(), v.end());
10
        cout << min(v[2] - v[1], v[1] - v[0]) << endl;
11
    }
12
}

B-模拟#

题目#

让 f(s) 成为字符串 s 的压缩版本，将每个最大连续字符块中的相同字符替换为该字符的单个副本。例如， f( “aabbcc” ) = “abc”。 “abc”。

让 |s| 表示字符串 s 的长度。接着， |f(s)| 表示压缩字符串的长度。例如

|f( “aabbcc” )|= 。 | “abc” | =3
如果字符串为空，其长度为 0 。

优素福给了您一个由 n 个小写拉丁字母组成的字符串 s 。您必须准确删除1个字符 si （ 2≤i≤n−1 ）以组成新字符串 s′ ，然后找出 |f(s′)| 的最小可能值。

注意不能删除 s1 或 sn 。

模拟#

在删除字符时，考虑该字符左侧和右侧的字符，若他们相同，则答案会减少2；否则答案减少1

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int t;
5
    cin >> t;
6
    while(t--){
7
        int n;
8
        cin >> n;
9
        string s;
10
        cin >> s;
11
        int ans = 1,x = 0;
12
        for(int i = 1;i < n;i++){
13
            if(s[i] != s[i-1]){
14
                ans++;
15
            }
16
            if(i == n - 1){
17
                break;
18
            }
19
            if(s[i] != s[i-1] && s[i] != s[i+1]){
20
                if(s[i-1] == s[i+1]){
21
                    x = 2;
22
                }
23
                else{
24
                    x = max(x,1);
25
                }
26
            }
27
        }
28
        cout << ans - x << endl;
29
    }
30
    return 0;
31
}

C1-贪心#

题目#

优素福给了你两个长度相同的二进制字符串 $a$ 和 $b$ 。

您可以执行以下任意操作：

在 $a$ 中选择一个与 $\texttt{001}$ 相等的子串 $^{\text{∗}}$ ，并替换为 $\texttt{100}$ ，反之亦然（即 $\texttt{001} \rightarrow \texttt{100}$ 或 $\texttt{100} \rightarrow \texttt {001}$ ）。
在 $a$ 中选择一个等于 $\texttt{110}$ 的子串，并将其替换为 $\texttt{011}$ ，反之亦然（即 $\texttt{011} \rightarrow \texttt{110}$ 或 $\texttt{110} \rightarrow \texttt {011}$ ）。

您的任务是确定是否可能用有限次的运算将字符串 $a$ 转换为字符串 $b$ 。

$^{\text{∗}}$ 如果通过删除开头的几个（可能是零个或全部）字符和结尾的几个（可能是零个或全部）字符，可以从 $b$ 得到 $a$ ，那么字符串 $a$ 就是字符串 $b$ 的子串。

贪心#

共有000,001,010,011,100,101,110,111等8种状态，对于可操作的四种状态种，等同于将 $a_i$ 和 $a_{i+2}$ 自由交换，显然的操作不会改变索引的奇偶性，对于不可操作的其余四种状态可以发现0和1的奇偶性不会改变，那么我们可以无休止地交换奇数索引处的字符（想换多少次就换多少次），因此我们可以将它们重新排列成我们想要的任何排列，而与偶数索引处的字符无关。

因此，如果 $a$ 中奇数位置上的元素与 $b$ 中奇数位置上的元素的1（或0）个数相同，那么它们就可以匹配。同样的方法也适用于偶数位置。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int t;
5
    cin >> t;
6
    while(t--){
7
        int n;
8
        cin >> n;
9
        string a,b;
10
        cin >> a >> b;
11
        int cnta[2] = {},cntb[2] = {};
12
        for(int i = 0;i < n;i++){
13
            cnta[i%2] += a[i] == '1';
14
            cntb[i%2] += b[i] == '1';
15
        }
16
        cout << (cnta[0] == cntb[0] && cnta[1] == cntb[1] ? "YES" : "NO") << endl;
17
    }
18
}

C2-贪心#

题目#

在C1的基础上求将a转化为b的最小操作次数，如果i无法转化输出-1

贪心#

对于同一奇偶性组：

把 a 中该组所有 1 的位置按顺序排列：posA[0], posA[1], ...
把 b 中该组所有 1 的位置按顺序排列：posB[0], posB[1], ...
最优匹配就是按顺序一一对应

对于每个匹配对 (posA[i], posB[i])：

移动距离是 |posA[i] - posB[i]| / 2

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int t;
5
    cin >> t;
6
    while(t--){
7
        int n;
8
        cin >> n;
9
        string a,b;
10
        cin >> a >> b;
11
        long long ans = 0;
12
        bool ok = true;
13
        for(int k = 0;k < 2;k++){
14
            vector<int>p1,p2;
15
            for(int i = k;i < n;i += 2){
16
                if(a[i] == '1'){
17
                    p1.push_back(i);
18
                }
19
                if(b[i] == '1'){
20
                    p2.push_back(i);
21
                }
22
            }
23

24
            if(p1.size() != p2.size()){
25
                ok = false;
26
                break;
27
            }
28
            for(int i = 0;i < p1.size();i++){
29
                ans += abs(p1[i] - p2[i]);
30
                }
31

32
        }
33

34

35
        if(!ok){
36
            cout << -1 << endl;
37
        }
38
        else{
39
            cout << ans/2 << endl;
40
        }
41

42
    }
43
    return 0;
44
}

D-构造#

题目#

尤塞夫有一个由 $n$ 个严格正整数组成的秘密数组 $a$ 。

对于每个元素 $a_i$ 来说，它的影子 $b_i$ 是 $a$ 中所有严格小于 $a_i$ 的元素之和。形式上

b_i = \sum_{\substack{1 \le j \le n\\ a_j \lt a_i}} a_j

给你一个阴影数组 $b$ 。你的任务是重构一个由满足上述条件的严格正整数组成的逻辑上最小的有效数组 $a$ 。如果不存在这样的数组，则输出 $-1$ 。

构造#

给定影子数组 b，其中 b_i 等于数组 a 中所有严格小于 a_i 的元素之和。

我们需要构造字典序最小的正整数数组 a，若不存在则输出 -1。

将 a 中所有不同值从小到大排序：

$v_1 < v_2 < \cdots < v_m$

对应出现次数为 $c_1, c_2, \dots, c_m$ 。
对于值为 $v_i$ 的元素，它的影子值等于：

$S_{i-1} = \sum_{j=1}^{i-1} c_j \cdot v_j$

这是严格小于它的所有元素之和。
因此，所有等于 $v_i$ 的位置，其 b 值必须相同，且等于 $S_{i-1}$ 。

不同 b 值必须严格递增，且最小的 b 值一定是 0（因为最小的 $v_1$ 没有更小的元素）。
将 b 中所有不同值排序：

$x_1 < x_2 < \cdots < x_m$

其中 $x_1 = 0$ ，且每个 $x_i$ 的出现次数就是 $c_i$ 。
由前缀和关系：

$x_{i+1} = S_i = S_{i-1} + c_i \cdot v_i = x_i + c_i \cdot v_i$

所以：

$v_i = \frac{x_{i+1} - x_i}{c_i}$

必须为正整数，并且必须满足 $v_i > v_{i-1}$ （ $v_0 = 0$ ）。
最后一组 $v_m$ 没有后继约束，为了字典序最小，取：

$v_m = v_{m-1} + 1$
如果所有条件满足，则根据原 b 的顺序，将每个 b_i 映射到对应的 $v$ ，即为答案。

否则输出 -1。

1
from collections import Counter
2
for _ in range(int(input())):
3
    n = int(input())
4
    b = list(map(int, input().split()))
5
    cnt = Counter(b)
6
    val = sorted(cnt.keys())
7
    if val[0] != 0:
8
        print(-1)
9
        continue
10
    m = len(val)
11
    if m == 1:
12
        print(" ".join(["1"] * n))
13
        continue
14
    a = {}
15
    pre = 0
16
    ok = True
17
    for i in range(m - 1):
18
        x = val[i]
19
        xn = val[i + 1]
20
        dif = xn - x
21
        if dif % cnt[x] != 0:
22
            ok = False
23
            break
24
        v = dif // cnt[x]
25
        if v <= pre:
26
            ok = False
27
            break
28
        a[x] = v
29
        pre = v
30
    if not ok:
31
        print(-1)
32
        continue
33
    xend = val[-1]
34
    a[xend] = pre + 1
35
    ans = [str(a[x]) for x in b]
36
    print(" ".join(ans))

音乐

音乐

1114Div3-①B-模拟②C2-贪心③D-构造#

A-模拟#

题目#

模拟#

B-模拟#

题目#

模拟#

C1-贪心#

题目#

贪心#

C2-贪心#

题目#

贪心#

D-构造#

题目#

构造#

文章分享

音乐

目录

音乐

音乐

[算法训练] 1114Div3-①B-模拟②C2-贪心③D-构造

1114Div3-①B-模拟②C2-贪心③D-构造#

A-模拟#

题目#

模拟#

B-模拟#

题目#

模拟#

C1-贪心#

题目#

贪心#

C2-贪心#

题目#

贪心#

D-构造#

题目#

构造#

文章分享

音乐

目录