蓝桥杯python基础练习-递归与递推

太久没练习了,省赛前夕刷一下基础练练手感

内容源自Acwing

很多时候板子比较长,实际代码不长就是了😶‍🌫️

92. 递归实现指数型枚举

暴力

代码

n=II()
path=[]

def f(i):
    if i==n:
        print(" ".join(map(str,path)))
        return
    f(i+1)
    path.append(i+1)
    f(i+1)
    path.pop()
f(0)

94. 递归实现排列型枚举

依然暴力,不过状压一手

现在发现可以用*path替换" ".join(map(str,path)),优雅多了

代码

n=II()


path=[]
def f(i,use=0):
    if len(path)==n:
        print(*path)
        return
    for i in range(n):
        if (use>>i)&1:
            continue
        path.append(i+1)
        f(i+1,use|(1<<i))
        path.pop()
f(0)

717. 简单斐波那契

递推

代码

@fstream
def solve():
    a,b=0,1
    n=II()
    for i in range(n):
        if not i:
            print(a,end=" ")
        else:
            print(b,end=" ")
            b,a=a+b,b
    return 0

95. 费解的开关

经典题目,贪心+二进制枚举

最重要的是贪心出的结论(只有第一行决定所有的状态)

注意多维数组复制要深拷贝

代码

def for_t(func):
    def wrapper():
        T=II()
        for _ in range(T):
            func()
    return wrapper

dire=[(0,0),(0,1),(1,0),(0,-1),(-1,0)]

@fstream
@for_t
def solve():
    a=[]
    for _ in range(5):
        p=I()
        b=[]
        for c in p:
            b.append(int(c))
        a.append(b[::])
    I()
    def do(li,i,j):
        for dx,dy in dire:
            x,y=i+dx,j+dy
            if 0<=x<5 and 0<=y<5:
                li[x][y]^=1
    def check(st):
        li=deepcopy(a)
        cnt=0
        for i in range(5):
            if (st>>i)&1:
                cnt+=1
                do(li,0,i)
        for i in range(1,5):
            for j in range(5):
                if li[i-1][j]==0:
                    cnt+=1
                    do(li,i,j)
        for j in range(5):
            if li[4][j]==0:
                return inf
        return cnt if cnt<=6 else inf
    ans=inf
    for st in range(1<<5):
        ans=min(ans,check(st))
    print(ans) if ans!=inf else print(-1)
    return 0

93. 递归实现组合型枚举

注意:

二进制运算符的优先级导致的错误
低版本python没有bit_count

二进制枚举+lowbit

import sys
from math import ceil,floor,fmod,gcd,sqrt,inf,log2
from bisect import bisect_left
from collections import defaultdict,Counter,deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from copy import deepcopy

limits = [100000, 10000, 5000, 2000]
for limit in limits:
    try:
        sys.setrecursionlimit(limit)
        break
    except:
        continue 

input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()
 
def II():
    return int(input())
 
def MII():
    return map(int, input().split())
 
def LI():
    return list(input().split())
 
def LII():
    return list(map(int, input().split()))

n,m=MII()

for i in range((1<<n)-1,(1<<m)-2,-1):
    ans=[]
    while i:
        lowbit=i&(-i)
        ans.append(n-int(log2(lowbit)))
        i-=lowbit
        if len(ans)>m:
            break
    else:
        if len(ans)==m:
            print(*ans[::-1])

暴搜

import re,os
from io import BytesIO, IOBase
import random
import sys
from math import ceil,floor,fmod,gcd,sqrt,inf
from bisect import bisect_left
from collections import defaultdict,Counter,deque,OrderedDict
from functools import cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from copy import deepcopy
from typing import *
from string import ascii_lowercase, ascii_uppercase
# 快读区块大小
BUFSIZE = 4096
# 判断是否本地
LOCAL="--open17" in sys.argv

# 可能会导致pypy产生TLE
# if "PyPy" in sys.version:
#     import pypyjit; pypyjit.set_param('max_unroll_recursion=-1')

# 调试递归极限
limits = [100000, 10000, 5000, 2000]
for limit in limits:
    try:
        sys.setrecursionlimit(limit)
        break
    except:
        continue 




class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 

def fstream(func):
    def wrapper(is_local):
        input_file = open('data.in', 'r', encoding='utf-8') if is_local else sys.stdin
        output_file = open('data.out', 'w', encoding='utf-8') if is_local else sys.stdout
        sys.stdin = IOWrapper(input_file)
        sys.stdout = output_file
        func()
        sys.stdin = sys.__stdin__
        sys.stdout = sys.__stdout__
        if is_local:
            input_file.close()
            output_file.close()
    return wrapper

input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()
 
def II():
    return int(input())
 
def MII():
    return map(int, input().split())
 
def LI():
    return list(input().split())
 
def LII():
    return list(map(int, input().split()))

def for_t(func):
    def wrapper():
        T=II()
        for _ in range(T):
            func()
    return wrapper


@fstream
# @for_t
def solve():
    n,m=MII()
    path=[]
    def f(i):
        if len(path)==m:
            print(" ".join(path))
            return
        if i==n+1:
            return
        for j in range(i+1,n+1):
            path.append(str(j))
            f(j)
            path.pop()
    f(0)
    return 0


solve(LOCAL)

1209. 带分数

注意只有1-9个数,所以暴搜即可

注意减个枝

代码

import re,os
from io import BytesIO, IOBase
import random
import sys
from math import ceil,floor,fmod,gcd,sqrt,inf
from bisect import bisect_left
from collections import defaultdict,Counter,deque,OrderedDict
from functools import cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from copy import deepcopy
from typing import *
from string import ascii_lowercase, ascii_uppercase
# 快读区块大小
BUFSIZE = 4096
# 判断是否本地
LOCAL="--open17" in sys.argv

# 可能会导致pypy产生TLE
# if "PyPy" in sys.version:
#     import pypyjit; pypyjit.set_param('max_unroll_recursion=-1')

# 调试递归极限
limits = [100000, 10000, 5000, 2000]
for limit in limits:
    try:
        sys.setrecursionlimit(limit)
        break
    except:
        continue 




class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 

def fstream(func):
    def wrapper(is_local):
        input_file = open('data.in', 'r', encoding='utf-8') if is_local else sys.stdin
        output_file = open('data.out', 'w', encoding='utf-8') if is_local else sys.stdout
        sys.stdin = IOWrapper(input_file)
        sys.stdout = output_file
        func()
        sys.stdin = sys.__stdin__
        sys.stdout = sys.__stdout__
        if is_local:
            input_file.close()
            output_file.close()
    return wrapper

input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()
 
def II():
    return int(input())
 
def MII():
    return map(int, input().split())
 
def LI():
    return list(input().split())
 
def LII():
    return list(map(int, input().split()))

def for_t(func):
    def wrapper():
        T=II()
        for _ in range(T):
            func()
    return wrapper


@fstream
# @for_t
def solve():
    n=II()
    cnt=0
    a=[0,0,0]
    used=[0]*10
    def f(i,t):
        if i==10:
            nonlocal cnt
            # print(a)
            if a[0]+a[1]/a[2]==n:
                # print(a)
                cnt+=1
            return
        for p in range(1,10):
            if used[p]:
                continue
            used[p]=1
            tmp=a[t]
            a[t]*=10
            a[t]+=p
            if t==0 and a[t]>n:
                a[t]=tmp
                used[p]=0
                return
            if t==2 and a[t]>a[t-1]:
                a[t]=tmp
                used[p]=0
                return
            if t!=2:
                f(i+1,t+1)
            if i+2-t<9 or t==2:
                f(i+1,t)
            a[t]=tmp
            used[p]=0
    f(1,0)
    print(cnt)
    return 0


solve(LOCAL)

116. 飞行员兄弟

看上去和费解的开关很像,不过费解开关只能改变相邻的,所以具有基于传递性的贪心策略,但是这里可以改变一整行和一整列

所以需要都枚举,即枚举16个

代码

import re,os
from io import BytesIO, IOBase
import random
import sys
from math import ceil,floor,fmod,gcd,sqrt,inf
from bisect import bisect_left
from collections import defaultdict,Counter,deque,OrderedDict
from functools import cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from copy import deepcopy
from typing import *
from string import ascii_lowercase, ascii_uppercase
# 快读区块大小
BUFSIZE = 4096
# 判断是否本地
LOCAL="--open17" in sys.argv

# 可能会导致pypy产生TLE
# if "PyPy" in sys.version:
#     import pypyjit; pypyjit.set_param('max_unroll_recursion=-1')

# 调试递归极限
limits = [100000, 10000, 5000, 2000]
for limit in limits:
    try:
        sys.setrecursionlimit(limit)
        break
    except:
        continue 




class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 

def fstream(func):
    def wrapper(is_local):
        input_file = open('data.in', 'r', encoding='utf-8') if is_local else sys.stdin
        output_file = open('data.out', 'w', encoding='utf-8') if is_local else sys.stdout
        sys.stdin = IOWrapper(input_file)
        sys.stdout = output_file
        func()
        sys.stdin = sys.__stdin__
        sys.stdout = sys.__stdout__
        if is_local:
            input_file.close()
            output_file.close()
    return wrapper

input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()
 
def II():
    return int(input())
 
def MII():
    return map(int, input().split())
 
def LI():
    return list(input().split())
 
def LII():
    return list(map(int, input().split()))

def for_t(func):
    def wrapper():
        T=II()
        for _ in range(T):
            func()
    return wrapper


@fstream
# @for_t
def solve():
    a=[]
    dic={"+":0,"-":1}
    for _ in range(4):
        c=I()
        b=[]
        for i in c:
            b.append(dic[i])
        a.append(b)
    # 110100001101
    def get(st):
        cnt=0
        li=[]
        for i in range(4):
            for j in range(4):
                if (st>>(i*4+j))&1:
                    li.append((i,j))
                    cnt+=1
        return li,cnt
    def f(st):
        p=[[0 for _ in range(4)] for _ in range(4)]
        li,cnt=get(st)
        for (i,j) in li:
            for x in range(4):
                if x!=i:
                    p[x][j]^=1
                if x!=j:
                    p[i][x]^=1
            p[i][j]^=1
        for i in range(4):
            for j in range(4):
                if a[i][j]^p[i][j]==0:
                    return li,inf
        return li,cnt
    ans=inf
    ans_li=None
    for st in range(1<<16):
        tmp,res=f(st)
        if res<ans:
            ans=res
            ans_li=tmp            
    print(ans)
    for p in ans_li:
        print(p[0]+1,p[1]+1)
    return 0


solve(LOCAL)

1208. 翻硬币

贪心结论: 不一样就反转,模拟一遍

代码

import re,os
from io import BytesIO, IOBase
import random
import sys
from math import ceil,floor,fmod,gcd,sqrt,inf
from bisect import bisect_left
from collections import defaultdict,Counter,deque,OrderedDict
from functools import cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from copy import deepcopy
from typing import *
from string import ascii_lowercase, ascii_uppercase
# 快读区块大小
BUFSIZE = 4096
# 判断是否本地
LOCAL="--open17" in sys.argv

# 可能会导致pypy产生TLE
# if "PyPy" in sys.version:
#     import pypyjit; pypyjit.set_param('max_unroll_recursion=-1')

# 调试递归极限
limits = [100000, 10000, 5000, 2000]
for limit in limits:
    try:
        sys.setrecursionlimit(limit)
        break
    except:
        continue 




class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 

def fstream(func):
    def wrapper(is_local):
        input_file = open('data.in', 'r', encoding='utf-8') if is_local else sys.stdin
        output_file = open('data.out', 'w', encoding='utf-8') if is_local else sys.stdout
        sys.stdin = IOWrapper(input_file)
        sys.stdout = output_file
        func()
        sys.stdin = sys.__stdin__
        sys.stdout = sys.__stdout__
        if is_local:
            input_file.close()
            output_file.close()
    return wrapper

input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()
 
def II():
    return int(input())
 
def MII():
    return map(int, input().split())
 
def LI():
    return list(input().split())
 
def LII():
    return list(map(int, input().split()))

def for_t(func):
    def wrapper():
        T=II()
        for _ in range(T):
            func()
    return wrapper


@fstream
# @for_t
def solve():
    a=I()
    b=I()
    flag=cnt=0
    dic={"*":0,"o":1}
    for i in range(len(a)):
        x=dic[a[i]]^flag
        y=dic[b[i]]
        if x!=y:
            cnt+=1
            flag=1
        else:
            flag=0
    print(cnt)
    return 0


solve(LOCAL)

92. 递归实现指数型枚举 ​

94. 递归实现排列型枚举 ​

717. 简单斐波那契 ​

95. 费解的开关 ​

93. 递归实现组合型枚举 ​

1209. 带分数 ​

116. 飞行员兄弟 ​

1208. 翻硬币 ​