2022ICPC沈阳站训练补题记录

Chuanhua Yu 发布于

最后更新于

[TOC]

这里给出部分题解(个人结题记录，可能还有很多地方可以优化)，持续更新中，按对我个人的难度排序

记得用PyPy3.x交,比python3.x系列会快几倍

D、DRX vs. T1

签到题，按题意模拟即可

1
2
3
4
5
6
7
8
9
import sys

s = list(sys.stdin.readline().strip())
d, t = 0, 0
for i in range(len(s)):
    if s[i] == 'T': t += 1
    elif s[i] == 'D': d += 1
    if d ==3 or t == 3: break
print("T1" if t == 3 else "DRX")

点击并拖拽以移动

C、Clamped Sequence

简单题，分析可知区间限制在 [ l，r]只会使sum变小，所以我们要使 l 到 r 之间尽可能包含多的数，所以 r = l + d，每个 |ai − ai+1| 对答案的贡献是关于 l 的分段一次函数，可以枚举 O(n) 个关键的 l 和 r 计算答案，做到 O(n^2 ) 的复杂度，也可以使用扫描线维护做到 O(n logn) 的复杂度。

这里给出O(n^2)的代码：

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
import sys

n,d = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
ls = [0]*n
ans = -1
for j in range(n):
    l = a[j]
    r = l+d
    cnt = 0
    for i in range(n):
        if a[i] < l: ls[i] = l
        elif a[i] > r: ls[i] = r
        else: ls[i] = a[i]
    for i in range(n-1):
        cnt += abs(ls[i]-ls[i+1])
    ans = max(cnt, ans)
for j in range(n):
    r = a[j]
    l = r-d
    cnt = 0
    for i in range(n):
        if a[i] < l: ls[i] = l
        elif a[i] > r: ls[i] = r
        else: ls[i] = a[i]
    for i in range(n-1):
        cnt += abs(ls[i]-ls[i+1])
    ans = max(cnt, ans)
print(ans)

点击并拖拽以移动

L、Tavern Chess

一个模拟题，当时自己先统计不同结果的局数来模拟写的WA了比较蛋疼，后来直接在dfs中算概率AC了。酒馆战旗规则，所有随从都是初始生命等于攻击的水桶腰身材，可以发现任何两个随从对撞时至少有一个被击倒。 递归遍历所有可能的局面，遍历到的局面最多是 (7!)^2。

下面直接上ac代码吧，没分太多函数，可能写的比较累赘。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import sys
sys.setrecursionlimit(100000)

class Node:
    def __init__(self, ATK, HP, num = 0):
        self.atk = ATK
        self.hp = HP
        self.num = num    ##num为攻击次数
        self.live = True

n,m = map(int, sys.stdin.readline().split())
bob,alix,pj = 0,0,0
ls_a = list(map(int, sys.stdin.readline().split()))
ls_b = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    ls_a[i] = Node(ls_a[i], ls_a[i])
for i in range(m):
    ls_b[i] = Node(ls_b[i], ls_b[i])

def find(ls):
    """查找这次哪个随从攻击，返回下标"""
    min_ = 0
    idx = 0
    for i in range(len(ls)):
        if ls[i].live:
            min_ = ls[i].num
            idx = i
            break
    for i in range(len(ls)):
        if not ls[i].live: continue
        if ls[i].num == 0 or ls[i].num == min_-1:
            return i
    return idx

def dfs(first, p, num_a, num_b):   ##num_a,num_b 为a,b当前的存活人数
    global bob, alix, pj
    if first:                 #a->b
        first = not first
        idx = find(ls_a)
        for i in range(m):
            if not ls_b[i].live: continue
            ls_a[idx].num = ls_a[idx].num + 1
            ls_a[idx].hp -= ls_b[i].atk
            ls_b[i].hp -= ls_a[idx].atk
            p /= num_b
            if ls_a[idx].hp <= 0:
                ls_a[idx].live = False
                num_a -= 1
            if ls_b[i].hp <= 0:
                ls_b[i].live = False
                num_b -= 1
            if num_a == 0 or num_b == 0:
                if num_a == 0 and num_b == 0: pj += p
                elif num_b == 0 and num_a != 0: alix += p
                elif num_a == 0 and num_b != 0: bob += p
                if ls_a[idx].live == False:
                    ls_a[idx].live = True
                    num_a += 1
                if ls_b[i].live == False:
                    ls_b[i].live = True
                    num_b += 1
                ls_a[idx].hp += ls_b[i].atk
                ls_b[i].hp += ls_a[idx].atk
                p *= num_b
                ls_a[idx].num = ls_a[idx].num - 1
                continue
            dfs(first, p, num_a, num_b)
            if ls_a[idx].live == False:
                ls_a[idx].live = True
                num_a += 1
            if ls_b[i].live == False:
                ls_b[i].live = True
                num_b += 1
            ls_a[idx].hp += ls_b[i].atk
            ls_b[i].hp += ls_a[idx].atk
            p *= num_b
            ls_a[idx].num = ls_a[idx].num - 1
    else:
        first = not first
        idx = find(ls_b)
        for i in range(n):
            if not ls_a[i].live: continue
            ls_b[idx].num = ls_b[idx].num + 1
            ls_a[i].hp -= ls_b[idx].atk
            ls_b[idx].hp -= ls_a[i].atk
            p = p/num_a
            if ls_a[i].hp <= 0:
                ls_a[i].live = False
                num_a -= 1
            if ls_b[idx].hp <= 0:
                ls_b[idx].live = False
                num_b -= 1
            if num_a == 0 or num_b == 0:
                if num_a == 0 and num_b == 0: pj += p
                elif num_b == 0: alix += p
                elif num_a == 0: bob += p
                if not ls_a[i].live:
                    ls_a[i].live = True
                    num_a += 1
                if not ls_b[idx].live:
                    ls_b[idx].live = True
                    num_b += 1
                ls_a[i].hp += ls_b[idx].atk
                ls_b[idx].hp += ls_a[i].atk
                ls_b[idx].num = ls_b[idx].num-1
                p *= num_a
                continue
            dfs(first, p, num_a, num_b)
            if not ls_a[i].live:
                ls_a[i].live = True
                num_a += 1
            if not ls_b[idx].live:
                ls_b[idx].live = True
                num_b += 1
            ls_a[i].hp += ls_b[idx].atk
            ls_b[idx].hp += ls_a[i].atk
            ls_b[idx].num = ls_b[idx].num - 1
            p *= num_a

first = True if n > m else False
if n != m: dfs(first, 1, n, m)
elif n == m:
     dfs(False, 0.5, n, m)
     dfs(True, 0.5, n, m)
ans = alix+bob+pj
print(f'{alix/ans:.15g}\n{bob/ans:.15g}\n{pj/ans:.15g}')

点击并拖拽以移动

F、Half Mixed

这题是到构造题，我们可以推出子矩形数量是 n(n+1)/2 * m(m+1)/2，如果子矩形数量是奇数则显 然无解，否则 n(n+1)/2 和 m(m+1)/2 至少有一个是偶数。我们只需要处理一行或一列即可。假设m(m+1)/2 为偶数，则一开始交替放0和1有m个纯子矩阵，我们要让纯子矩阵等于总数的一半即m(m+1)/4，令cnt = m(m+1)/4 - m，为纯子矩阵还差多少，再可以推出每加 k 个相同的数字，纯子矩阵增加 ∑ x (x from 1 to k) = k(k+1)/2，所以只需要贪心的选择最大的k直到cnt为0为止。

上ac代码：

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
import sys

t = int(sys.stdin.readline())
while t > 0:
    t -= 1
    n,m = map(int, sys.stdin.readline().split())
    num = n * (n+1) * (m+1) * m// 4
    if num % 2 != 0:
        print("No")
    else:
        print("Yes")
        if n*(n+1)%4 == 0:
            cnt = n*(n+1)//4 - n
            k,f = 1, 1
            ans = [1]
            for i in range(n-1):
                if cnt >= k:
                    ans.append(f)
                    cnt -= k
                    k += 1
                else:
                    k = 1
                    f = 0 if f else 1
                    ans.append(f)
            for i in range(n):
                for j in range(m):
                    print(ans[i], end = ' ' if j != m-1 else '\n')
        else:
            cnt = m*(m+1)//4 - m
            k,f = 1, 1
            ans = [1]
            for i in range(m-1):
                if cnt >= k:
                    ans.append(f)
                    cnt -= k
                    k += 1
                else:
                    k = 1
                    f = 0 if f else 1
                    ans.append(f)
            for i in range(n):
                print(*ans)

点击并拖拽以移动

smile是对你的礼貌

smile是对你的礼貌

在思维的迷宫里，有的人凭天生的灵感直奔终点； 有的人以持久的勤勉，铸造出适合自己的罗盘！

33
2
13
NOTICE

这是我的个人博客，主要发布一些算法竞赛相关题解和人工智能相关的技术与知识，页面最下面可以访问我的Github和知乎，可以通过下面链接访问我的CSDN https://blog.csdn.net/smile__everydays?spm=1000.2115.3001.5343

CATEGORYS
TAGS
DP Machine Learning XCPC div2 python模板 介绍 图匹配 图论 技术部寒假算法培训 最小生成树 牛客竞赛 蓝书 题目汇总