A

签到

n = int(input())
print((n+1)//2)

B

贪心，遇到11，修改后面的1为0

n = int(input())

s = list(input().strip())

res = 0
for i in range(1,n):
    if s[i-1] == s[i] == '1':
        res += 1
        s[i] = '0'
print(res)

C

dp，第i位(i >=k)相当于拼接1或者拼接0

n,k = map(int,input().strip().split())
dp = 1
for i in range(k,n+1):
    dp *= 2
    dp %= 1_000_000_007
print(dp)

D

bfs找规律

n,k = map(int,input().strip().split())
res = 0
visit = [False] * (n+1)
from collections import deque
# 存储关了的灯
que = deque()
que.append(0)
visit[0] = True
while que:
    zero = que.pop()
    one = n - zero
     
    res += myComb(n,zero)
    res %= MAX_NUM 
    # 枚举t个0反转    
    for t in range(zero+1):
        if t > k:
            break
         
        nz = zero - t
        if k - t <= one:
            nz += k - t
        else:
            continue
        if visit[nz]:
            continue
        visit[nz] = True
        que.appendleft(nz)
         
for z in range(n+1):
    if visit[z]:
        print(z)

可以发现：

• n == k，只有两种
• k为奇数，可以灭[0,n]盏灯
• k为偶数，可以灭偶数盏灯 最终代码结合逆元组合数学，解决k为偶数的情况：

# 预处理阶乘以及其逆元
max_n = int(1*1e5)
fac = [1] * (max_n+1)
facinv = [1] * (max_n+1)
MAX_NUM = int(1e9+7)
 
for i in range(1,max_n+1):
    fac[i] = fac[i-1] * i % MAX_NUM
    # python自带快速幂
    facinv[i] = pow(fac[i],MAX_NUM-2,MAX_NUM)
 
def myComb(n,m):    
    if m < 0 or n < m:
        return 0
    return fac[n] * facinv[m] * facinv[n-m] % MAX_NUM
 
n,k = map(int,input().strip().split())
mod = int(1e9+7)
if n == k:
    print(2)
    exit()
if k&1:
    print(pow(2,n,mod))
    exit()
           
res = 0
t = 0
while t <= n:
    res += myComb(n,t)
    t += 2
    res %= MAX_NUM 
print(res)

E

贪心，若当前位为0：

• 若左右相邻都为0，则都变成1
• 若上下相邻都为0，则都变成1
• 若存在左右，则进行操作
• 若存在上下，则进行操作
• 否则，return -1

n,m = map(int,input().strip().split())
grid = []
for _ in range(n):
    s = map(int,list(input().strip()))
    grid.append(list(s))

t = 0
res = []
for i in range(n):
    for j in range(m):
        if grid[i][j]:
            continue
        if i + 1 < n and not grid[i+1][j]:
            res.append((i,j,i+1,j))
            grid[i+1][j] = 1
            t += 1
            continue
        
        if j + 1 < m and not grid[i][j+1]:
            res.append((i,j,i,j+1))
            grid[i][j+1] = 1
            t += 1
            continue
        
        if i + 1 < n:
            res.append((i,j,i+1,j))
            grid[i+1][j] = 0
            t += 1
            continue
        
        if j + 1 < m:
            res.append((i,j,i,j+1))
            grid[i][j+1] = 0
            t += 1
            continue
        print(-1)
        exit()
print(t)
for a,b,c,d in res:
    print(a+1,b+1,c+1,d+1)

F

树形dp，返回三个值：

• 当前节点为开状态的最小操作数
• 当前节点为关状态，且没有借时，的最小操作数
• 当前节点为关状态，且有借时，的最小操作数

所谓借，就是先关闭，回到父节点时，再还回来，即同时关闭父节点.

n = int(input())
from collections import defaultdict
road = defaultdict(list)
for _ in range(n-1):
    x,y = map(int,input().strip().split())
    road[x].append(y)
    road[y].append(x)

from types import GeneratorType 
def bootstrap(f, stack=[]):   #yield
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

# 当前节点，开，关不欠，关欠
@bootstrap
def dfs(node,last):
    a,b,c = 0,0,1
    dmn = float("inf")
    tmpe,tmpc = 0,float("inf")
    
    for nxt in road[node]:
        if nxt == last:
            continue
        
        la,lb,lc = yield dfs(nxt,node)
        # a开，子节点都关闭
        a += lb
        
        # b关不欠，要选一个lc
        '''
        le1 = min(la,lb)
        le1 + lc2 < lc1 + le2
        lc2 - le2 < lc1 - le1
        '''
        le = min(la,lb)
        c += le
        d = lc - le
        
        if d < dmn:
            dmn = d            
            tmpe,tmpc = le,lc
        b += le
        
    b -= tmpe
    b += tmpc
    return (yield a,b,c)

a,b,c = dfs(1,0)
print(min(a,b))

G

同F，树形dp，但要增加mem数组，来记录dp的上一个转移位置，从而来获取路径。

mem = [[[] for _ in range(3)] for _ in range(n+1)]:

• mem[node][0] 相当于当前节点为开状态时，走的所有子节点状态
• mem[node][1] 当前节点为关状态，且没有借时，走的所有子节点状态
• mem[node][2] 当前节点为关状态，且有借时，走的所有子节点状态

n = int(input())
from collections import defaultdict
road = defaultdict(list)
for _ in range(n-1):
    x,y = map(int,input().strip().split())
    road[x].append(y)
    road[y].append(x)
 
from types import GeneratorType 
def bootstrap(f, stack=[]):   #yield
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
 
# 记录每个节点走的路
mem = [[[] for _ in range(3)] for _ in range(n+1)]
# 当前节点，开，关不欠，关欠
@bootstrap
def dfs(node,last):
    a,b,c = 0,0,1
    dmn = float("inf")
    tmpe,tmpc = 0,float("inf")   
    tmpnxt = 0
    for nxt in road[node]:
        if nxt == last:
            continue      
 
        la,lb,lc = yield dfs(nxt,node)
        # a开，子节点都关闭
        mem[node][0].append((nxt,1))
        a += lb
        # b关不欠，要选一个lc
        '''
        le1 = min(la,lb)
        le1 + lc2 < lc1 + le2
        lc2 - le2 < lc1 - le1
        '''
        # le = min(la,lb)
        if la <= lb:
            le = la
            mem[node][1].append((nxt,0))
            mem[node][2].append((nxt,0))
        else:
            le = lb
            mem[node][1].append((nxt,1))
            mem[node][2].append((nxt,1))    
        b += le
        c += le
         
        d = lc - le       
        if d < dmn:
            dmn = d            
            tmpe,tmpc = le,lc
            tmpnxt = nxt
             
    b -= tmpe
    b += tmpc
    mem[node][1].append((tmpnxt,2))
    return (yield a,b,c)
 
a,b,c = dfs(1,0)
print(min(a,b))

最后再根据mem的路径依赖，走多一次dfs，从而获取关上了哪些灯：

@bootstrap
def getRes(node,i):
    # 当前节点开
    if i != 1:
        for nxt,ni in mem[node][i]:
            yield getRes(nxt,ni)
    # 当前节点关
    else:
        tmpnxt,tmpi = mem[node][i][-1]
        print(node,tmpnxt)
        for nxt,ni in mem[node][i]:
            if nxt == tmpnxt and ni != tmpi:
                continue
            yield getRes(nxt,ni)
    yield None
'''
for node in range(1,n+1):
    print(node,mem[node])
print(a,b)
'''
if a <= b:
    getRes(1,0)
else:
    getRes(1,1)

最后

就ac了最后两题，然后就没做了，现在补上其它题，D题花的时间还挺多。。。