1103Div3-博弈#

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

A-数学#

题意：

对数组a中的每个元素增加b中对应的数值，目标是使a中每个元素都相等；

限制：b中的数值范围需满足[1,k]，找到最小的k

题解：

由于至少需要+1，所以最小的k即为max(a) + 1 - min(a)即可

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
        vector<int> h(n);
10
        for (int i = 0; i < n; i++) {
11
            cin >> h[i];
12
        }
13
        int mx = *max_element(h.begin(), h.end());
14
        int mn = *min_element(h.begin(), h.end());
15
        cout << mx + 1 - mn << "\n";
16
    }
17
    return 0;
18
}

B-数学-余数#

题意：

给定一个长度为n的01字符串，和一个整数k，进行如下操作：

选择一个整数i，并反转位置i和i+k上的字符

题解：

将字符串下标按模k的余数分组，每次操作只会影响同一个余数类中的两个字符，且反转后每个余数类中1的个数的奇偶性不会变换，因而每个余数类中1的个数必须为偶数

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    ios::sync_with_stdio(false);
5
    cin.tie(nullptr);
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        int n,k;
10
        cin >> n >> k;
11
        string s;
12
        cin >> s;
13
        vector<int> cnt(k,0);
14
        for(int i = 0;i < n;i++){
15
            if(s[i] == '1'){
16
                cnt[i%k]++;
17
            }
18
        }
19
        bool ok = true;
20
        for(int x:cnt){
21
            if(x&1){
22
                ok = false;
23
                break;
24
            }
25
        }
26
        cout << (ok ? "YES" : "NO") << endl;
27
    }
28
}

C-贪心+数学#

题意：

给定三个整数a,b,x

目标是使a==b

可以执行一下两种操作：

1.选择a,b中的一个并将其加上1

2.选择a,b中的一个便将其除以x并向下取值

题解：

把每个数所有可能的“连续除以x后得到的状态”全部列出来，最优策略一定是“若干次除法 + 最后若干次加法”，枚举两个数除法后的状态(v1,v2)，代价为：除法次数1+除法次数2+∣v1−v2∣

1
#include <iostream>
2
#include <vector>
3
#include <utility>
4
#include <cstdlib>
5
#include <algorithm>
6
using namespace std;
7
int main(){
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
    int t;
11
    cin >> t;
12
    while(t--){
13
        long long a,b,x;
14
        cin >> a >> b >> x;
15
        vector<pair<long long,int>>va,vb;
16
        long long cur = a;
17
        int step = 0;
18
        va.push_back({cur,step});
19
        while(cur > 0){
20
            cur /= x;
21
            step++;
22
            va.push_back({cur,step});
23
        }
24
        cur = b;
25
        step = 0;
26
        vb.push_back({cur,step});
27
        while(cur > 0){
28
            cur /= x;
29
            step++;
30
            vb.push_back({cur,step});
31
        }
32
        long long ans = llabs(a - b);
33
        for(auto & [v1,s1] : va){
34
            for(auto & [v2,s2] : vb){
35
                ans = min(ans,(long long)s1 + s2 + llabs(v1- v2));
36
            }
37
        }
38
        cout << ans << endl;
39

40
    }
41
    return 0;
42
}

D-博弈#

题目重述

给定一个数组 $a$ 和整数 $k$ 。

游戏规则如下：

第一次可以删除任意元素；
设上一次删除的元素值为 $x$ ；
下一次只能删除满足

0 \le y-x \le k

的元素。

即后续删除的数字必须：

不小于上一次删除的数字；
与上一次删除数字的差值不超过 $k$ 。

无法进行操作的玩家输掉游戏。

正常情况下 Dabir 先手。

现在 Arseniy 可以代替 Dabir 执行第一步。

之后按照：

1
Egor → Dabir → Egor → Dabir ...

继续进行。

问是否存在一种第一步，使得无论 Dabir 如何操作，Egor 都能够保证获胜。

题解思路

由于后续只能选择不小于当前值的数字，因此游戏过程中的数字一定是单调不下降的。

对于同一个数值 $v$ ：

1
v v v v v ...

这些元素之间永远可以互相选择。

因此同一个数值实际上形成一个独立的“堆”。

设其出现次数为：

cnt[v]

情况一：存在偶数次出现的数字

假设某个数字出现了偶数次：

1
v v v v

Arseniy 第一手删除一个 $v$ 。

剩余：

1
v v v

数量变成奇数。

之后无论双方如何选择，只要游戏进入这个数值，

这些相同数字会被轮流取走：

1
Egor
2
Dabir
3
Egor
4
...

因为数量为奇数，

最后一个 $v$ 一定由 Egor 取走。

因此：

如果存在某个数字出现次数为偶数，则答案一定为 YES。

情况二：所有数字出现次数均为奇数

此时无法利用上一种方法。

设所有不同数字升序排列：

b_1<b_2<\cdots<b_m

如果存在一对相邻不同数字满足：

b_{i+1}-b_i\le k

那么 Arseniy 可以先删除一个 $b_i$ 。

随后 Egor 立即选择：

b_{i+1}

由于两个数字之间可以相互连接，

Egor 能够抢占主动权并获得必胜局面。

因此：

如果存在相邻不同数字差值不超过 $k$ ，答案仍然是 YES。

情况三：所有频率均为奇数，且相邻数字差值均大于 k

即：

b_{i+1}-b_i>k

对于所有 $i$ 都成立。

此时：

不同数字之间完全无法转移；
每个数字形成独立块；
每个块大小均为奇数。

Arseniy 删除任意元素后：

该块大小变为偶数；
其余块仍为奇数。

此时 Dabir 总能通过最优策略获得最后一步。

因此：

不存在让 Egor 必胜的第一步。

答案为 NO。

判定条件

统计每个数字出现次数。

若存在：

cnt[v]\equiv0\pmod2

则直接输出：

1
YES

否则将所有不同数字排序。

若存在：

b_{i+1}-b_i\le k

则输出：

1
YES

否则输出：

1
NO

算法流程

使用哈希表统计每个数字出现次数；
若存在偶数频率，输出 YES；
对所有不同数字排序；
检查是否存在相邻数字差值不超过 k；
存在则 YES，否则 NO。

时间复杂度

统计频率：

O(n)

排序不同数字：

O(m\log m)

其中 $m$ 为不同数字个数，且：

m\le n

总复杂度：

O(n\log n)

满足题目要求。

1
from collections import Counter
2

3
for _ in range(int(input())):
4
    n, k = map(int, input().split())
5
    a = list(map(int, input().split()))
6

7
    cnt = Counter(a)
8

9
    ok = False
10

11
    for c in cnt.values():
12
        if c % 2 == 0:
13
            ok = True
14
            break
15

16
    if ok:
17
        print("YES")
18
        continue
19

20
    vals = sorted(cnt.keys())
21

22
    for i in range(len(vals) - 1):
23
        if vals[i + 1] - vals[i] <= k:
24
            ok = True
25
            break
26

27
    print("YES" if ok else "NO")

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7

8
    int T;
9
    cin >> T;
10

11
    while (T--) {
12
        int n, k;
13
        cin >> n >> k;
14

15
        map<int,int> cnt;
16

17
        for (int i = 0; i < n; i++) {
18
            int x;
19
            cin >> x;
20
            cnt[x]++;
21
        }
22

23
        bool ok = false;
24

25
        for (auto &p : cnt) {
26
            if (p.second % 2 == 0) {
27
                ok = true;
28
                break;
29
            }
30
        }
31

32
        if (ok) {
33
            cout << "YES\n";
34
            continue;
35
        }
36

37
        vector<int> vals;
38

39
        for (auto &p : cnt) {
40
            vals.push_back(p.first);
41
        }
42

43
        for (int i = 0; i + 1 < (int)vals.size(); i++) {
44
            if (vals[i + 1] - vals[i] <= k) {
45
                ok = true;
46
                break;
47
            }
48
        }
49

50
        cout << (ok ? "YES" : "NO") << '\n';
51
    }
52

53
    return 0;
54
}

D-DP#

状态转换

频率数组

题目保证：

1\le a_i\le n

因此统计每个数字出现次数：

1
freq[x]

例如：

1
1 1 2 2 2 4

对应：

1
freq[1]=2
2
freq[2]=3
3
freq[4]=1

DP定义

定义：

1
dp[i]

表示：

当前游戏来到数字 i 这一层时，当前操作者是否处于必胜态。

其中：

1
dp[i]=1

表示必胜态。

1
dp[i]=0

表示必败态。

为什么只考虑数字大小

由于后续操作满足：

0\le y-x\le k

因此数字只能越来越大。

游戏过程一定是：

1
小数字 → 大数字 → 更大的数字

不会回头。

所以可以从大到小进行 DP。

连通块思想

设当前处理数字 i。

若最近出现过的数字为：

1
last

并且：

last-i>k

说明：

1
i 无法转移到 last

两者属于不同连通块。

此时：

1
last=-1

重新开始计算一个新的独立游戏块。

代码：

1
if last != -1 and last - i > k:
2
    last = -1

一个新块的情况

如果：

1
last == -1

说明当前数字是一个新块的最大数字。

此时只有：

1
freq[i]

个相同数字。

游戏退化成：

1
i i i i ...

双方只能轮流拿。

因此：

奇数个 → 先手赢
偶数个 → 先手输

即：

1
dp[i] = freq[i] % 2

代码：

1
dp[i] = v % 2

状态转移

假设：

1
dp[i+1]

已经求出。

当前数字出现：

1
v = freq[i]

次。

情况1：v为奇数

若：

1
v % 2 == 1

则当前玩家最终会把操作权交给对手。

因此状态发生翻转。

如果后继是必败态：

1
dp[i+1] == 0

则当前一定能赢：

1
dp[i] = 1

代码：

1
if v % 2 == 1 and dp[i+1] == 0:
2
    dp[i] = 1

情况2：v为偶数

若：

1
v % 2 == 0

双方在这一层拿完后，

操作权不会改变。

因此：

1
dp[i] = dp[i+1]

当后继是必败态时：

1
dp[i]=0

代码：

1
elif v % 2 == 0 and dp[i+1] == 0:
2
    dp[i] = 0

情况3：后继是必胜态

若：

1
dp[i+1] == 1

说明已经存在一种策略使当前玩家获胜。

于是：

1
f = True
2
break

说明 Arseniy 已经找到了一个第一步。

代码：

1
elif dp[i+1] == 1:
2
    f = True
3
    break

为什么答案是 f

变量：

1
f

表示：

是否存在一个位置，能让删除一个元素后， Egor 面对的是必胜局面。

一旦找到：

1
f=True

即可立即结束。

最后：

1
print("YES" if f else "NO")

算法流程

统计每个数字出现次数；
从大到小扫描数字；
按照差值是否超过 k 划分连通块；
维护 dp[i] 表示当前数字开始是否为必胜态；
一旦发现存在可行第一步则输出 YES；
否则输出 NO。

时间复杂度

统计频率：

O(n)

DP扫描：

O(n)

总复杂度：

O(n)

空间复杂度：

O(n)

满足：

\sum n \le 2\times10^5

的要求。

1
import sys
2
input = lambda: sys.stdin.readline().strip()
3

4
for _ in range(int(input())):
5
    n, k = map(int, input().split())
6
    nums = list(map(int, input().split()))
7

8
    freq = [0] * (n + 1)
9

10
    for v in nums:
11
        freq[v] += 1
12

13
    dp = [0] * (n + 2)
14

15
    last = -1
16
    f = False
17

18
    for i in range(n, -1, -1):
19
        v = freq[i]
20

21
        if v == 0:
22
            dp[i] = dp[i + 1]
23
            continue
24

25
        if last != -1 and last - i > k:
26
            last = -1
27

28
        if last == -1:
29
            last = i
30
            dp[i] = v % 2
31

32
            if dp[i] == 0:
33
                f = True
34
                break
35
        else:
36
            last = i
37

38
            if v % 2 == 1 and dp[i + 1] == 0:
39
                dp[i] = 1
40

41
            elif v % 2 == 0 and dp[i + 1] == 0:
42
                dp[i] = 0
43

44
            elif dp[i + 1] == 1:
45
                f = True
46
                break
47

48
    print("YES" if f else "NO")

E-枚举#

题目重述

给定一个长度为 $n$ 的数组 $a$ 。

需要从中选出：

两个 不重叠
且 长度相同
的子段

记长度为 $L$ 。

要求两个子段都满足：

可以重排成一个数列，使得相邻差为 1

并且拼接后整体仍满足该性质。

1. “好数组”的本质

一个数组可以重排为：

b_i - b_{i-1} = 1

等价于：

子段内所有不同值必须构成一个连续整数区间

即：

\max - \min = \text{distinct} - 1

2. 子段合法性条件

对于一个区间 $[i, j]$ ：

记：

$\min = \min(a_i \dots a_j)$
$\max = \max(a_i \dots a_j)$
$len = j - i + 1$

则：

\text{合法} \iff \max - \min = len - 1

并且必须保证：

所有数互不重复（等价于 distinct = len）

我们需要找到：

两个不重叠的合法区间，长度相同且尽可能大

转化为“窗口枚举问题”

Step 1：枚举所有合法区间

固定左端点 i，向右扩展 j：

维护：

当前最小值 minval
当前最大值 maxval
用 visit 数组判重

只要满足：

1
maxval - minval == j - i

则说明当前区间是一个“连续排列区间”。

Step 2：记录每个长度的区间位置

我们维护两个数组：

1
minimum[x][len] = 最小右端点
2
maximum[x][len] = 最大左端点

含义：

对于值域起点 x：

存所有长度为 len 的合法区间
记录最左 / 最右覆盖情况

Step 3：本质优化

我们不直接存区间，而是：

记录“值域区间 + 长度”对应的最极端位置

即：

最靠左的起点
最靠右的终点

用于快速判断是否能选出两个不重叠区间。

Step 4：判断是否能选两个区间

枚举长度 L：

对于所有值域起点 x：

检查是否存在：

1
区间1：[x, x+L-1]
2
区间2：[x+L, ...]

并且：

两个区间都存在合法子段
且不重叠

判断条件：

1
minimum[x][L] < maximum[x+L][L]
2
or
3
minimum[x+L][L] < maximum[x][L]

1. 一个长度 L 的“好数组”

对应的是一个：

值域长度 = L 的连续排列段

2. 两个数组拼接仍合法

说明：

两个值域区间必须“无冲突”，即：

不能交错
必须能够拼成更大连续块

因此只需检查：

两个长度 L 的连续块是否能在数组中找到“互不重叠实例”

Step 1：枚举所有子段

双指针 + hash 判重：

min/max
是否重复
是否满足 max-min=len-1

Step 2：记录区间信息

更新：

1
minimum[minval][len] = min(minimum[minval][len], j)
2
maximum[minval][len] = max(maximum[minval][len], i)

Step 3：枚举答案

从大到小枚举 L：

对于每个起点 x：

检查是否存在两个合法区间且不重叠

复杂度分析

枚举子段：

最坏：

O(n^2)

判重优化：

利用 s[val] = i 防止重复扩展

平均接近：

O(n^2 / \text{amortized})

总复杂度：

在 $n \le 6000$ 下可通过。

1
t = int(input())
2
for _ in range(t):
3
    n = int(input())
4
    a = list(map(int, input().split()))
5
    max_len = n // 2 + 2
6
    INF = 10**9
7
    minimum = [[INF] * max_len for _ in range(n + 1)]
8
    maximum = [[-1] * max_len for _ in range(n + 1)]
9
    vis = [0] * (n + 5)
10
    for i in range(n):
11
        minv = a[i]
12
        maxv = a[i]
13
        tag = i + 1
14
        for j in range(i, n):
15
            v = a[j]
16
            if vis[v] == tag:
17
                break
18
            vis[v] = tag
19
            minv = min(minv, v)
20
            maxv = max(maxv, v)
21
            length = j - i + 1
22
            if maxv - minv == length - 1 and length < max_len:
23
                minimum[minv][length] = min(minimum[minv][length], j)
24
                maximum[minv][length] = max(maximum[minv][length], i)
25
    ans = 0
26
    for L in range(n // 2, 0, -1):
27
        ok = False
28
        for x in range(1, n - 2 * L + 2):
29
            if minimum[x][L] < maximum[x + L][L] or minimum[x + L][L] < maximum[x][L]:
30
                ok = True
31
                break
32
        if ok:
33
            ans = L
34
            break
35
    print(ans)

子段“好数组” ⇔ 值域连续（max-min = len-1）
预处理所有合法子段
记录“值域 + 长度”的最极端位置
枚举长度 L 判断是否能找到两个不重叠合法块

先找所有“值域连续的子段”，再用二维记录其左右边界，最后判断是否存在两个同长度且不重叠的合法块。

音乐

音乐

1103Div3-博弈#

A-数学#

B-数学-余数#

C-贪心+数学#

D-博弈#

D-DP#

E-枚举#

音乐

目录

音乐

音乐

1103Div3-①博弈②DP③哈希枚举

1103Div3-博弈#

A-数学#

B-数学-余数#

C-贪心+数学#

D-博弈#

D-DP#

E-枚举#

音乐

目录