1099Div2#

Dashboard - Codeforces Round 1099 (Div. 2) - Codeforces

Easy：A

Mid：B

Hard-Mid：C

Hard：D(Gemini3.5Flash)

A-构造

题意：

给定一个整数n，构造出一个整数数组a1,…an，该数组具有如下性质：

数组中所有元素及相邻元素之和两两不同

题解：

一种较为愚蠢的做法是用一个set记录插入数组中的元素：

1
for _ in range(int(input())):
2
    n = int(input())
3
    ans = [0]*n
4
    s = set()
5
    j = 0
6
    i = 1
7
    while j < n:
8
        if i not in s:
9
            ans[j] = i
10
            j += 1
11
            i += 1
12
            s.add(i)
13
        else:
14
            i += 1
15
            continue
16
    print(*ans)

实际上，只需要数组中所有元素均为奇数即可

1
for tt in range(int(input())):
2
    n = int(input())
3
    ans = [2 * i + 1 for i in range(n)]
4
    print(*ans)

还有一种可行的构造是，该数组中的所有元素均不能被3整除，在这个数组中，相邻元素的和是可以被3整除的，模3的余数形成1，2，1，2的规律

B-贪心

题意：

给定一个数组，可以最多对该数组执行如下的一次操作：

选择一个整数 $k$ ，以及一个子序列 $b$ ，将 $k$ 加到该子序列的每个元素上

判断是否能够是数组按非递减顺序排序

题解：

当数组中相邻元素出现递减a[i] < a[i-1]时，如果a[i-1] < a[i-2]，那么显然，无法通过给定的操作实现非递减；反之，用一个maxadd = max(maxadd,a[i-1] - a[i])，记录最大的 $k$ 值

正向遍历数组，为每个a[i] < a[i-1]的a[i] += maxadd；

正向遍历数组，如果该数组中仍然出现递减，则无法通过指定操作实现目的。

1
# 对于下降的地方，记录需要添加的最小值，最大化这个最小值
2
# 为每个下降的地方加上这个最大化的最小值
3
# 对于连续下降的直接NO
4

5
t = int(input())
6
for _ in range(t):
7
    n = int(input())
8
    a = list(map(int, input().split()))
9
    ok = 1
10
    maxadd = 0
11
    for i in range(1,n):
12
        if a[i] < a[i-1]:
13
            # 如果连续下降，则一个无法完成
14
            if i - 1 > 0 and a[i-1] < a[i-2]:
15
                ok = 0
16
            maxadd = max(maxadd,a[i-1] - a[i])
17
    if not ok:
18
        print("NO")
19
    else:
20
        for i in range(1,n):
21
            if a[i] < a[i-1]:
22
                a[i] += maxadd
23
        for i in range(1,n):
24
            if a[i] < a[i-1]:
25
                ok = 0
26
        if ok:
27
            print("YES")
28
        else:
29
            print("NO")

1
#include<stdio.h>
2
#include<stdlib.h>
3
void solve(){
4
    int n;
5
    if(scanf("%d",&n) != 1){
6
        return;
7
    }
8
    long long *a = (long long *)malloc(n*sizeof(long long));
9
    for(int i = 0;i < n;i++){
10
        scanf("%lld",&a[i]);
11
    }
12
    int ok = 1;
13
    long long maxadd = 0;
14
    for(int i = 1;i < n;i++){
15
        if(a[i] < a[i-1]){
16
            if(i-1 > 0 && a[i-1] < a[i-2]){
17
                ok = 0;
18
            }
19
            long long diff = a[i-1] - a[i];
20
            if(diff > maxadd){
21
                maxadd = diff;
22
            }
23
        }
24
    }
25
    if (!ok){
26
        printf("NO\n");
27
    }
28
    else{
29
        for(int i = 1;i<n;i++){
30
            if(a[i] < a[i-1]){
31
                a[i] += maxadd;
32
            }
33
        }
34
        for(int i=1;i<n;i++){
35
            if(a[i] < a[i-1]){
36
                ok = 0;
37
            }
38
        }
39
        if(ok){
40
            printf("YES\n");
41
        }
42
        else{
43
            printf("NO\n");
44
        }
45
    }
46
    free(a);
47
}
48

49
int main(){
50
    int t;
51
    if(scanf("%d",&t) != 1){
52
        return 0;
53
    }
54
    while(t--){
55
        solve();
56
    }
57
    return 0;
58
}

C-模拟+思维

题意：

给定一个序列，选择一个元素进行如下操作：

1.如果所选的元素是偶数，则将其除以2

2.如果所选的元素是奇数，则将其加1

求出最小的操作次数，使得给定的序列中所有数都相等

题解：

注意到，对一个数进行上次多次操作后，该数会达到1，随后在进行操作，数在[1,2,1,2…]变换，

因此只需要保留该数在达到1之前的前缀部分即可

用一个字典reach记录数组中所有数字经过操作后得到的数字，包括两个字段：某个演变出的数字num有[went, steps]，分别代表有多少个原始数组中的元素经过操作可以到达num；所有可到达该数的总操作次数

最后比较所有went == n的情况下，最小的steps

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int,input().split()))
4
    reach = {}
5
    for num in a:
6
        went_to = set()
7
        step = 0
8
        while num not in went_to:
9
            went_to.add(num)
10
            if num not in reach:
11
                reach[num] = [1,step]
12
            else:
13
                reach[num][0] += 1
14
                reach[num][1] += step
15
            if num%2 == 0:
16
                num //= 2
17
            else:
18
                num += 1
19
            step += 1
20
    ans = float('inf')
21
    for went,step in reach.values():
22
        if went == n and step < ans:
23
            ans = step
24
    print(ans)

1
from collections import defaultdict
2
for _ in range(int(input())):
3
    n = int(input())
4
    a = list(map(int,input().split()))
5
    reach = defaultdict(lambda: [0, 0])
6
    for x in a:
7
        step = 0
8
        s = set()
9
        while x not in s:
10
            s.add(x)
11
            reach[x][0] += 1
12
            reach[x][1] += step
13
            if x % 2 == 0:
14
                x//=2
15
            else:
16
                x+=1
17
            step += 1
18
    ans = float('inf')
19
    for cnt,tot in reach.values():
20
        if cnt == n and tot < ans:
21
            ans = tot
22
    print(ans)

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <string.h>
4

5
#define INF 1000000000000000000LL
6

7
typedef struct {
8
    long long key;
9
    long long went;
10
    long long step_sum;
11
    int is_used;
12
} ReachNode;
13

14
#define REACH_SIZE 5000005
15
ReachNode reach[REACH_SIZE];
16

17

18
int used_slots[REACH_SIZE];
19
int used_slots_cnt = 0;
20

21
void reset_reach_fast() {
22
    for (int i = 0; i < used_slots_cnt; i++) {
23
        reach[used_slots[i]].is_used = 0;
24
        reach[used_slots[i]].key = 0;
25
        reach[used_slots[i]].went = 0;
26
        reach[used_slots[i]].step_sum = 0;
27
    }
28
    used_slots_cnt = 0;
29
}
30
unsigned int hash_p68(unsigned long long key) {
31
    key ^= key >> 33;
32
    key *= 0xff51afd7ed558ccdULL;
33
    key ^= key >> 33;
34
    return key % REACH_SIZE;
35
}
36

37
void add_to_reach(long long num, long long step) {
38
    unsigned int hash = hash_p68((unsigned long long)num);
39
    while (reach[hash].is_used && reach[hash].key != num) {
40
        hash = (hash + 1) % REACH_SIZE;
41
    }
42

43
    if (!reach[hash].is_used) {
44
        reach[hash].key = num;
45
        reach[hash].went = 1;
46
        reach[hash].step_sum = step;
47
        reach[hash].is_used = 1;
48
        used_slots[used_slots_cnt++] = hash;
49
    } else {
50
        reach[hash].went += 1;
51
        reach[hash].step_sum += step;
52
    }
53
}
54

55
#define SET_SIZE 205
56
long long went_to[SET_SIZE];
57
int set_used[SET_SIZE];
58

59
void reset_set() {
60
    memset(set_used, 0, sizeof(set_used));
61
}
62

63
int check_and_add_set(long long num) {
64
    unsigned long long hash = (unsigned long long)num % SET_SIZE;
65
    while (set_used[hash] && went_to[hash] != num) {
66
        hash = (hash + 1) % SET_SIZE;
67
    }
68

69
    if (set_used[hash]) {
70
        return 1;
71
    }
72

73
    went_to[hash] = num;
74
    set_used[hash] = 1;
75
    return 0;
76
}
77

78
void solve(){
79
    int n;
80
    if (scanf("%d", &n) != 1) return;
81

82
    long long *a = (long long *)malloc(n * sizeof(long long));
83
    for (int i = 0; i < n; i++) {
84
        scanf("%lld", &a[i]);
85
    }
86

87
    reset_reach_fast();
88

89
    for (int i = 0; i < n; i++) {
90
        long long num = a[i];
91
        reset_set();
92
        long long step = 0;
93

94
        while (check_and_add_set(num) == 0) {
95
            add_to_reach(num, step);
96
            if (num % 2 == 0) {
97
                num /= 2;
98
            } else {
99
                num += 1;
100
            }
101
            step += 1;
102
        }
103
    }
104

105
    long long ans = INF;
106
    for (int i = 0; i < used_slots_cnt; i++) {
107
        int idx = used_slots[i];
108
        if (reach[idx].went == n && reach[idx].step_sum < ans) {
109
            ans = reach[idx].step_sum;
110
        }
111
    }
112

113
    if (ans == INF) {
114
        printf("-1\n");
115
    } else {
116
        printf("%lld\n", ans);
117
    }
118

119
    free(a);
120
}
121

122
int main(){
123
    int t;
124
    if (scanf("%d", &t) != 1) return 0;
125
    while (t--) {
126
        solve();
127
    }
128
    return 0;
129
}

D-构造+贪心+模拟(Gemini3.5Flash)

题意：

给定一个长度为 $n$ 的原数组 $a$ ，我们定义：

前缀和数组 $b$ ： $b_i = \sum_{j=1}^{i} a_j$
前缀最大值数组 $c$ ： $c_i = \max(b_1, b_2, \dots, b_i)$

现在，原数组 $a$ 的部分元素丢失了。输入会给你一个二进制字符串 $s$ 和不完整的数组 $a$ ：

如果 $s_i = 1$ ，说明 $a_i$ 没丢，给你的是它的真实值。
如果 $s_i = 0$ ，说明 $a_i$ 丢失了（此时输入给出的 $a_i = 0$ 作为占位符），你可以将其填入任意整数。

另外，完整的前缀最大值数组 $c$ 是保存完好的。

你的任务： 判断能否通过合理地填补 $s_i=0$ 的那些 $a_i$ ，来恢复出一个满足前缀最大值刚好为 $c$ 的原数组 $a$ 。如果能，输出Yes并打印出完整的 $a$ 数组；否则输出No。

题解：

代码的核心切入点在于利用 $c_i = \max(c_{i-1}, b_i)$ 的性质。

1. 核心观察与关键推导

前缀最大值数组 $c$ 具有天然的单调递增性。当 $c_i$ 发生变化时，即 $c_i > c_{i-1}$ ，这意味着 $b_i$ 刷新了历史最高纪录。因此：

\text{当 } c_i \neq c_{i-1} \text{ 时，必然有 } b_i = c_i

一旦 $b_i$ 的确切值被固定了，我们可以往前逆推。如果 $s_i = '1'$ 且 $s_{i-1} = '1'$ ，那么根据前缀和关系，有 $b_{i-1} = b_i - a_i$ 。以此类推，只要前面连续的 $s$ 都是'1'，那么这一段的 $b$ 链条全部可以被唯一确定。

2. 代码变量的职责

b[i]：代表推导出的前缀和 $b_i$ 的确切值。
d[i]：状态标记布尔数组。d[i] = 1表示 $b_i$ 的值已经被唯一锁定了；d[i] = 0表示 $b_i$ 的值目前还是未知的（可以由 $s_i=0$ 的空位来调整）。

3. 双阶段逻辑拆解

第一阶段：贪心逆推锁定（从前向后遇到突变，向后逆推）

遍历整个数组，一旦发现 $c_i \neq c_{i-1}$ ：
1. 如果 $c_i < c_{i-1}$ ，不符合前缀最大值的单调性，直接判定为No。
2. 否则，令 $b_i = c_i, d[i] = 1$ 。然后从 $i$ 开始往左回溯：只要 $s[j] == '1'$ ，说明这一步的变换贡献 $a_j$ 是已知的，因此 $b_{j-1}$ 也随之被唯一锁定为 $b_j - a_j$ 。
3. 冲突检查：如果在左推过程中发现 $b_{j-1}$ 早已被另一个链条锁定过（即d[j-1] == 1），且新算出的值不等于旧值，说明产生逻辑悖论，直接判定为No。
第二阶段：正向顺推填补与合法性检验
1. 从 $1$ 到 $n$ 正向遍历。如果 $s[i] == '1'$ 且前一步的 $b_{i-1}$ 是已知的，那么当前位置也可以顺推出来： $b_i = b_{i-1} + a_i$ 。
2. 如果到某一步 $d[i] == 0$ （即 $b_i$ 还没有被强制规定），说明这是一个“自由位”，由于它不影响 $c_i$ 刷新，为了最大安全化，我们把它设为一个极小值（代码里用了 $-10^{16}$ ），使其不干扰后续的最大值。
3. 终极校验：根据补全后的 $b$ 数组还原出最终的 $a_i = b_i - b_{i-1}$ 。并检查每一个位置是否满足 $c_i = \max(c_{i-1}, b_i)$ 。如果完全吻合，则构造成功输出Yes；否则输出No。

1
for _ in range(int(input())):
2
    n = int(input())
3
    s = ' ' + input().strip()
4
    a = [0] + list(map(int,input().split()))
5
    c = [0] + list(map(int,input().split()))
6
    b = [0] * (n + 1)
7
    d = [0] * (n + 1)
8
    d[0] = 1
9
    b[0] = 0
10
    c[0] = -10 ** 18
11
    ok = True
12

13
    # 第一阶段：逆推锁定
14
    for i in range(1, n + 1):
15
        if c[i] != c[i - 1]:
16
            if c[i] < c[i - 1]:
17
                ok = False
18
                break
19

20
            b[i] = c[i]
21
            d[i] = 1
22
            j = i
23
            while j >= 0:
24
                if s[j] == '1':
25
                    if d[j - 1] and b[j - 1] + a[j] != b[j]:
26
                        ok = False
27
                        break
28
                    d[j - 1] = 1
29
                    b[j - 1] = b[j] - a[j]
30
                    j -= 1
31
                else:
32
                    break
33
            if not ok:
34
                break
35

36
    if not ok:
37
        print("No")
38
        continue
39

40
    # 第二阶段：正向顺推与最终检验
41
    for i in range(1, n + 1):
42
        if s[i] == '1':
43
            b[i] = b[i - 1] + a[i]
44
            d[i] = 1
45
        if not d[i]:
46
            b[i] = -10 ** 16
47

48
        a[i] = b[i] - b[i - 1]
49

50
        if max(c[i - 1], b[i]) != c[i]:
51
            ok = False
52
            break
53

54
    if not ok:
55
        print("No")
56
    else:
57
        print("Yes")
58
        print(' '.join(map(str, a[1:n + 1])))

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <string.h>
4

5
#define N 500005
6
long long a[N], c[N], b[N], d[N];
7
char s[N];
8

9
long long max_ll(long long x, long long y) {
10
    return x > y ? x : y;
11
}
12

13
void solve() {
14
    int n;
15
    if (scanf("%d", &n) != 1) return;
16

17
    // 读入字符串并存放在 s[1] 开始的位置
18
    scanf("%s", s + 1);
19

20
    d[0] = 1;
21
    for (int i = 1; i <= n; i++) {
22
        scanf("%lld", &a[i]);
23
        d[i] = 0;
24
    }
25
    for (int i = 1; i <= n; i++) {
26
        scanf("%lld", &c[i]);
27
    }
28

29
    c[0] = -1000000000000000000LL; // -1e18
30
    b[0] = 0;
31

32
    // 第一阶段：逆推锁定
33
    for (int i = 1; i <= n; i++) {
34
        if (c[i] != c[i - 1]) {
35
            if (c[i] < c[i - 1]) {
36
                printf("No\n");
37
                return;
38
            }
39
            b[i] = c[i];
40
            d[i] = 1;
41
            for (int j = i; j >= 0; j--) {
42
                if (s[j] == '1') {
43
                    if (d[j - 1] && b[j - 1] + a[j] != b[j]) {
44
                        printf("No\n");
45
                        return;
46
                    }
47
                    d[j - 1] = 1;
48
                    b[j - 1] = b[j] - a[j];
49
                } else {
50
                    break;
51
                }
52
            }
53
        }
54
    }
55

56
    // 第二阶段：正向顺推与最终检验
57
    for (int i = 1; i <= n; i++) {
58
        if (s[i] == '1') {
59
            b[i] = b[i - 1] + a[i];
60
            d[i] = 1;
61
        }
62
        if (!d[i]) {
63
            b[i] = -10000000000000000LL; // -1e16
64
        }
65
        a[i] = b[i] - b[i - 1];
66
        if (max_ll(c[i - 1], b[i]) != c[i]) {
67
            printf("No\n");
68
            return;
69
        }
70
    }
71

72
    printf("Yes\n");
73
    for (int i = 1; i <= n; i++) {
74
        printf("%lld%c", a[i], (i == n) ? '\n' : ' ');
75
    }
76
}
77

78
int main() {
79
    // 优化标准 C 的输入输出性能
80
    setvbuf(stdin, NULL, _IOFBF, 16384);
81
    setvbuf(stdout, NULL, _IOFBF, 16384);
82

83
    int t;
84
    if (scanf("%d", &t) == 1) {
85
        while (t--) {
86
            solve();
87
        }
88
    }
89
    return 0;
90
}

音乐

音乐

1099Div2#

音乐

目录

音乐

音乐

1099Div2-构造+模拟+贪心

1099Div2#

音乐

目录