题目来源：https://www.acwing.com/activity/content/2869/

亲戚

题意

并查集裸题

题解/坑点

用python的input会TLE

from sys import stdin

stdin.readline().strip().split()

代码

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

N,M = (int(_) for _ in stdin.readline().split(" "))
fa = [i for i in range(N+1)]

def find(x):
    if x!=fa[x]:
        fa[x] = find(fa[x])
    return fa[x]

for i in range(M): 
    x,y = (int(_) for _ in stdin.readline().split(" "))
    fx = find(x)
    fy = find(y)
    fa[fa[x]] = fa[y]
    

Q = int(stdin.readline())

for i in range(Q):
    x,y = (int(_) for _ in stdin.readline().split(" "))
    fx = find(x)
    fy = find(y)
    if fx == fy:
        print("Yes")
    else:
        print("No")

连通块中点的数量

题意

1
2
3
4
5
现在要进行m个操作，操作共有三种：

C a b，在点 a 和点 b 之间连一条边，a和b可能相等；
Q1 a b，询问点 a和点 b是否在同一个连通块中，a和b可能相等；
Q2 a，询问点a所在连通块中点的数量；

题解/坑点

在并查集之外维护cnt[]，合并时进行更新，只有当下标为代表结点时，cnt[i]才有效

代码

略

笨拙的手指

题意

给一个二进制串，一个三进制串。分别修改一位，使得它们的值相等

题解/坑点

python 进制转换：

二进制 bin() 十进制 int() 八进制 oct() 十六进制 hex()
  • int(‘1010’, 2) 表示 1010B的十进制值
  • int(‘1210’, 3) 1210在三进制下的十进制值
  • bin(int( n , x )) 表示字符串n，在x进制下的二进制值

一般的dict访问不存在的下标会报错

from collections import defaultdict

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict

b, bt = list(input()), ['0', '1']
t, tt = list(input()), ['0', '1', '2']
st = defaultdict(bool)

for i in range(len(b)):
    for change in bt:
        if b[i]!=change:
            b1 = b[:] #相当于深拷贝
            b1[i] = change
            st[int(''.join(b1),2)]=True

for i in range(len(t)):
    for change in tt:
        if t[i]!=change:
            t1 = t[:]
            t1[i] = change
            if st[int(''.join(t1),3)]:
                print(int(''.join(t1),3))
                break

滑动窗口

题意

题解/坑点

注意细节

input().strip().split(' ')

不加strip()会报错！！！！！

代码

1
2
3
4
5
6
7
8
9
10
11
12
(n,k) = map(int,input().strip().split(' '))
a = list(map(int,input().strip().split(' ')))
q = [0 for i in range(n)]
tt=-1
hh=0

for i in range(n):
    if hh<=tt and i-q[hh]+1>k:hh+=1
    while hh<=tt and a[q[tt]]>=a[i]:tt-=1
    tt+=1
    q[tt] = i
    if i>=k-1:print(a[q[hh]],end=' ')

烽火传递

题意

1
2
3
在某两个城市之间有n 座烽火台，每个烽火台发出信号都有一定的代价。
为了使情报准确传递，在连续m个烽火台中至少要有一个发出信号。
现在输入n,m和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

题解/坑点

dp[i]表示点亮第i个烽火台，且能传递信号的最小花费。

暴力做法O(nm)，但每次只需考虑大小为m的窗口的最小值即可

用单调队列优化

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(n,k) = map(int,input().strip().split(' '))
a = list(map(int,input().strip().split(' ')))
a = [0]+a
q = [0 for i in range(n+2)]
dp = [1<<60 for i in range(n+2)]
dp[0] = a[0]
tt = -1
hh = 0
            
for i in range(n):
    if tt>=hh and i-q[hh]+1 > k:hh+=1
    while tt>=hh and dp[q[tt]] >= dp[i]:tt-=1
    tt+=1
    q[tt] = i
    dp[i+1] = a[i+1]+dp[q[hh]]

ans = 1<<60
for i in range(n-k+1,n+1):
    ans =min(ans,dp[i])
    
print(ans)

微博转发

题意

1
2
3
当用户在微博上发布帖子时，他/她的所有关注者都可以查看并转发他/她的帖子，然后这些人的关注者可以对内容再次转发…
现在给定一个社交网络，假设只考虑L层关注者，请你计算某些用户的帖子的最大可能转发量。
如果B是A的关注者，C是B的关注者，那么A的第一层关注者是B，第二层关注者是C

题解/坑点

BFS模板题，注意py中的deque的用法

代码

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
from collections import deque

N,L = map(int,input().strip().split())
li = [[] for i in range(N+2)]
for i in range(1,N+1):
    tp = list(map(int,input().strip().split()))
    tp.pop(0)
    for j in tp:
        li[j].append(i)

Q = list(map(int,input().strip().split()))

for i in range(1,Q[0]+1):
    st = set()
    cnt = 0
    qu = deque()
    qu.append((Q[i],0))
    st.add(Q[i])
    while len(qu):
        tp = qu.popleft()
        if tp[1] >= L: continue
        # print(li[tp[0]])
        for nx in li[tp[0]]:
            if nx not in st:
                st.add(nx)
                qu.append((nx,tp[1]+1))
    print(len(st)-1)

全球变暖

题意

岛屿，如果一块陆地上下左右四个相邻像素中有海洋，就会被淹没

求有几个岛屿会被淹没

题解/坑点

bfs模板题。有个坑：如果一个岛被淹成了两个岛，答案不会-1

bfs的时候给岛屿上的点编号即可

使用stdin.readline()一定要strip()

代码

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
from collections import deque
from sys import stdin
import copy

def bfs(li,i,j,st,cnt):
    dx,dy = [0,1,0,-1],[1,0,-1,0]
    qu = deque()
    qu.append((i,j))
    st[(i,j)]=cnt
    while len(qu):
        tp = qu.popleft()
        for i in range(4):
            x, y = tp[0] + dx[i] ,tp[1] + dy[i]
            if  x < 0 or y<0 or x>=len(li[0]) or y>=len(li[0]): continue
            if (x,y) in st:continue
            if li[x][y] == '.':continue
            st[(x,y)] = cnt
            qu.append((x,y))

def fun(li,st):
    cnt = 0
    for i in range(len(li[0])):
        for j in range(len(li[0])):
            if li[i][j] == '.':
                continue
            if (i,j) not in st:
                cnt+=1
                bfs(li,i,j,st,cnt)
    return cnt

N = int(input())
li = [[] for i in range(N+2)]
li2 = [[] for i in range(N+2)]
for i in range(N):
    li[i] = list(map(str,input()))
    li2[i] = copy.deepcopy(li[i])

stt = set()
dc = dict()
cnt = fun(li,dc)

for i in range(len(li[0])):
    for j in range(len(li[0])):
        if li[i][j]=='#':
            if li[i+1][j] == '.' or li[i][j+1] == '.' or\
               li[i-1][j] == '.' or li[i][j-1] == '.' :
                li2[i][j] = '.'
            else:
                stt.add(dc[(i,j)])
                
print(cnt - len(stt))

不同路径数

题意

题解/坑点

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
from collections import deque
from sys import stdin
import copy

n,m,k = map(int,stdin.readline().strip().split())

li = [[] for i in range(n)]
for i in range(n):
    li[i] = list(map(int,stdin.readline().strip().split()))

st = set()
def dfs(i,j,res,s):
    global st
    global li
    if res==0:
        st.add(s)
        return
    
    dx,dy = [0,1,0,-1],[-1,0,1,0]
    for _ in range(4):
        x,y = i+dx[_],j+dy[_]
        if 0<= x < len(li) and 0<= y < len(li[0]):
            dfs(x,y,res-1,s+str(li[x][y]))

for i in range(n):
    for j in range(m):
        dfs(i,j,k,str(li[i][j]))

print(len(st))

小猫爬山

题意

1
2
3
4
5
6
7
8
翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W，而N只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
1≤N≤18,
1≤Ci≤W≤10e8

题解/坑点

N很小，W很大，用搜索来做

注意剪枝和优化：

  1. cost >= ans直接返回
  2. 先从大到小排序 sort(reverse = True)

代码

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
N,w = map(int,input().strip().split())
C = []
p = [0] * 20
ans = 999
for i in range(N):
    x = int(input())
    C.append(x)

C.sort(reverse = True)

def dfs(u,cost):
    global ans
    if cost >= ans:return

    if  u == N:
        ans = min(ans,cost)
        return
    
    for i in range(1,cost+1):
        if p[i]+C[u] <= w:
            p[i]+=C[u]
            dfs(u+1,cost)
            p[i]-=C[u]

    p[cost + 1] = C[u]
    dfs(u + 1, cost + 1)
    p[cost + 1] = 0

dfs(0,0)
print(ans)

带分数

题意

题解/坑点

先dfs弄一个全排列，再n^2枚举i j

代码

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
import sys
sys.setrecursionlimit(1000000)
def check():
    global ans
    a , b, c = 0 ,0,0
    s = ''.join(str(i) for i in path)
    for i in range(1,9):
        a = int(s[:i])
        if a > n:break
        for j in range(8,i,-1):
            b = int(s[i:j])
            c = int(s[j:])
            if b<c:break
            if b%c:continue
            if a+b/c == n:
                ans += 1
                
def dfs(u):
    if u==9:
        check()
        return
    for i in range(1,10):
        if not st[i]:
            st[i] = True
            path.append(i)
            dfs(u+1)
            path.pop()
            st[i] = False

n = int(input())
ans = 0
st = [False]*10
path = []
dfs(0)
print(ans)