牛客周赛146-计数/哈希+子序列DP+博弈#

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

Easy：A、B

Mid：C、D、E

Hard：F

C-计数+哈希

题意：

给定平面上互不相同的n个点，选出三个构成三角形，满足：非退化的等腰三角行

题解：

枚举水平和垂直类似，下面是按Y坐标分组的讨论：

将相同y坐标的点，对其x坐标按照奇偶分类，对于每一类，计算其第三点坐标的x值，此情况下可构成的答案即为该x坐标对应的点的数量，需要剔除三点共线的情况

1
from collections import defaultdict
2
n = int(input())
3
xx = defaultdict(set)
4
yy = defaultdict(set)
5
for _ in range(n):
6
    x, y = map(int, input().split())
7
    xx[x].add(y)
8
    yy[y].add(x)
9
ans = 0
10
for y, xs in yy.items():
11
    even = []
12
    odd = []
13
    for x in xs:
14
        if x % 2 == 0:
15
            even.append(x)
16
        else:
17
            odd.append(x)
18
    for len_ in (even, odd):
19
        for i in range(len(len_)):
20
            x1 = len_[i]
21
            for j in range(i + 1, len(len_)):
22
                x2 = len_[j]
23
                mid_x = (x1 + x2) // 2
24
                if mid_x in xx:
25
                    cnt = len(xx[mid_x])
26
                    if y in xx[mid_x]:
27
                        cnt -= 1
28
                    ans += cnt
29
for x, ys in xx.items():
30
    even = []
31
    odd = []
32
    for y in ys:
33
        if y % 2 == 0:
34
            even.append(y)
35
        else:
36
            odd.append(y)
37
    for len_ in (even, odd):
38
        for i in range(len(len_)):
39
            y1 = len_[i]
40
            for j in range(i + 1, len(len_)):
41
                y2 = len_[j]
42
                mid_y = (y1 + y2) // 2
43
                if mid_y in yy:
44
                    cnt = len(yy[mid_y])
45
                    if x in yy[mid_y]:
46
                        cnt -= 1
47
                    ans += cnt
48
print(ans)

D-子序列DP

题意：

给定一个由数字构成的字符串，计算该字符串中有多少个子序列满足：将该子序列转化为10进制数，该十进制数是6的倍数

题解：

DP定义：

dp[r]表示处理到当前位置时，所有已构造的非空子序列中，数值模6等于r的结果

DP初始化：

dp = [0,0,0,0,0,0]

DP状态转移方程：

对于当前处理的数字d，新的DP值ndp由以下三部分组成：

1.不选当前字符：ndp[r] = dp[r]

2.新建只包含当前字符的子序列：ndp[d%6] += 1

3.将当前字符追加到已有子序列末尾：对于每个r∈(0,1,2,3,4,5,6)：ndp[(r*10 + d)%6] = ndp[(r*10 + d)%6] + dp[r]

1
MOD = 998244353
2
n = int(input())
3
s = input().strip()
4
dp = [0] * 6
5
ans = 0
6
for ch in s:
7
    d = int(ch)
8
    ndp = dp[:]
9
    ndp[d % 6] = (ndp[d % 6] + 1) % MOD
10
    for r in range(6):
11
        nr = (r * 10 + d) % 6
12
        ndp[nr] = (ndp[nr] + dp[r]) % MOD
13
    dp = ndp
14
print(dp[0] % MOD)

E-博弈

题意：

有n堆石头，每堆有若干个石子，用ai表示

x和y进行一场游戏，由x先手，选一个整数b，要求b不小于上一步操作所选的数值，之后选择任意一个至少含有b个石子的堆，从中拿走b个石子

如果轮到某人时，其无法操作，则判输

题解：

先手必胜策略：

先手找到出现奇次的堆，从中取走对应的石子，那么之后每当后手操作，先手在配对的堆中模仿即可

后手必胜策略：

所有堆出现的次数都是偶数，先手在任一堆取x，后手在配对堆也取x，每次操作所有石子频率保持偶数，先手最终面对全0状态

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int, input().split()))
4
    cnt = {}
5
    for x in a:
6
        cnt[x] = cnt.get(x, 0) + 1
7
    if all(v % 2 == 0 for v in cnt.values()):
8
        print("fang")
9
    else:
10
        print("red")

音乐

音乐

牛客周赛146-计数/哈希+子序列DP+博弈#

音乐

目录