[toc]

A. 日期统计 cpp组

不小心做到cpp这组了，用python的datetime库还是挺方便的

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
str = "5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3"
##
##
##print(str.replace( ,,))
from datetime import timedelta,date

str1 = [5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3]

## print(str.replace( ,","))
print(len(str1))
##
##
d1 = date(2023,1,1)
d2 = date(2023,12,31)

cnt = 0

while d1 <= d2:
    date = d1.strftime("%Y%m%d")
    #print(date)
    num = 0
    for i in range(len(str1)):
        if num == 8:
            cnt+=1
            break
        if str1[i] == int(date[num]):
            num+=1
            print(num)
    d1 += timedelta(days=1)
    
print(cnt)

A 2023

这题读题仔细一点应该不会做错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
str1 = "2023"


# print(str1 in str2)
cnt = 0
for i in range(12345678,98765432+1):
    ii = str(i)
    tmp = 0
    for j in range(len(ii)):
        if ii[j] == str1[tmp]:
            tmp+=1
        if tmp == 4:
            break
    if tmp!=4:
        cnt+=1

        
print(cnt)

B 硬币兑换

暴力枚举

1
2
3
4
5
6
7
res = [0]* 5000

for i in range(1,2024):		#
    for j in range(i+1,2024):
        res[i+j] += i		# 取决于最小个数
        
print(max(res))

C 松散子序列

  1. 不选 s[i]：则 dp[i] = dp[i-1]。
  2. 选 s[i]：则不能选 s[i-1]，因此 dp[i] = dp[i-2] + value(s[i])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
s = input().strip()
n = len(s)
if n == 0:
    print(0)
    exit()

# 初始化dp数组
dp = [0] * (n + 1)
dp[1] = ord(s[0]) - ord('a') + 1  # 第一个字符的价值

for i in range(2, n + 1):
    # 当前字符的价值
    current_value = ord(s[i-1]) - ord('a') + 1
    # 状态转移
    dp[i] = max(dp[i-1], dp[i-2] + current_value)

print(dp[n])

D 管道 二分+合并区间

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
import sys
import heapq
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().strip()

n,lens = map(int,input().split())

lis = []
for _ in range(n):
    a,b = map(int,input().split())
    lis.append((a,b))
    


    
def check(time):  
    cur = []  
    for l,s in lis:
        tmp = time - s
        #print(tmp)
        if tmp >= 0:
            cur.append([l-tmp,l+tmp])
 
    cur.sort()
    #print(cur)
    pos = cur[0][1] # 右端点
    for i in range(1,len(cur)):
        if cur[i][0] - pos <= 1:
            pos = max(cur[i][1],pos)
        else:
            break
    #print(pos)
    return pos>=lens

ll = 0
rr = 10**9

ans = 0
#print(ll,rr)
while ll<=rr:
    mid = (ll +rr)//2
    #print(mid)
    if check(mid):  
        ans = mid
        rr = mid-1
    else:
        ll = mid+1
print(ans)

E 保险箱

dp没有想象中那么难, 按以下三种状态考虑

  • 0：不传递进位
  • 1：向上传递进位（当前位+1）
  • 2：向下传递进位（当前位-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
n = int(input())
s1 =  input()[::-1]
s2 =  input()[::-1]

a = []
b = []
for i in range(n):
    a.append(int(s1[i]))
    b.append(int(s2[i]))

dp = [[0]* 3 for i in range(n+1)]


dp[0][0] = abs(a[0] - b[0])
dp[0][1] = b[0] + 10 - a[0]
dp[0][2] = a[0] + 10 - b[0]

for i in range(1,n):
    dp[i][0] = min(dp[i-1][0] + abs(a[i] -b[i]), dp[i-1][1] + abs(a[i] + 1 - b[i]), dp[i-1][2] + abs(a[i] - 1 - b[i]))    
    dp[i][1] = min(dp[i-1][0]+ b[i] + 10 - a[i], dp[i-1][1] + b[i] + 9 - a[i],      dp[i-1][2] + b[i] + 11 - a[i])
    dp[i][2] = min(dp[i-1][0] + a[i] + 10 -b[i], dp[i-1][1] + a[i] + 11 -b[i],      dp[i-1][2] + a[i] + 9 -b[i] )
print(min(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

H 独一无二

dijiestra + dp

1

K 异或和

我的题解（一个都过不了Qwq）

对于dfs的理解还是不够深入

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

n,m = map(int,input().split())

li = [0] + list(map(int,input().split()))

graph = {}
for i in range(n-1):
    a,b = map(int,input().split())
    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)
   
        
st = [False] * (n+5)
def dfs(x):
   # findroot = False
    xor = li[x]
    for i in graph[x]:
        if st[i] == False : 
            st[x] = True
            xor ^= dfs(i)
            st[x] = False
    
    return xor
res = []

for i in range(m):
    l = list(map(int,input().split()))
    if l[0] == 1:
        li[l[1]] = l[2]
    else:
        # st[l[1]] = True
        root = l[1]
        print(dfs(l[1]))
        #st[l[1]] = False


正确题解(能过但是感觉不太对)

只存储单向边，保证不会向上遍历（数据集树的点从上到下依次递增）

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

import os
import sys

from collections import deque
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
f=[[] for _ in range(n+1)]



for _ in range(n-1):
    u,v=map(int,input().split())
    f[min(u,v)].append(max(u,v))    # 把小节点指向大节点
for _ in range(m):
    dos=list(map(int,input().split()))
    if dos[0]==1:
        a[dos[1]]=dos[2]
    elif dos[0]==2:
        ans = 0
        q = deque()
        q.append(dos[1])
        while len(q)!=0:
            p = q.popleft()
            for i in f[p]:
                q.append(i)
            ans = ans ^ a[p]
        print(ans)

J 混乱数组

我的题解

混到几分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x = int(input())

if x==1:
    print(1)

for n in range(2,1*9):
    if n*(n-1)//2 >= x:
        leng = n
        break
res = []
if x== leng*(leng-1)//2:    
    for i in range(leng,0,-1):
        res.append(str(i))
     

print(" ".join(res))