2025.11.1
括号生成
向右或向上走，不能超过对角线。
Catalan数枚举。
class Solution:def generateParenthesis(self, n: int) -> list[str]:ans=[]def dfs(l,res,r):if(l<r):returnif(l+r==2*n-1):ans.append(res+')')returnif(l<n):dfs(l+1,res+'(',r)if(l>r):dfs(l,res+')',r+1)dfs(1,"(",0)return ans
print(Solution().generateParenthesis((3)))
N 皇后
class Solution:def solveNQueens(self, n: int) -> list[list[str]]:y=[0]*nz=[0]*(2*n+1)w=[0]*(2*n+1)ans=[]def dfs(x,res):if(x==n):tmp=[]for i in range(n):t='.'*res[i]+'Q'+'.'*(n-1-res[i])tmp.append(t)ans.append(tmp)returnfor i in range(n):if(y[i]==0 and z[i+x]==0 and w[i-x+n]==0):y[i]=1z[i+x]=1w[i-x+n]=1temp=res.copy()temp.append(i)dfs(x+1,temp)y[i]=0z[i+x]=0w[i-x+n]=0dfs(0,[])return ans
print(Solution().solveNQueens(4))
熄灯问题
根据题目提示，枚举第一行的所有情况，然后一行行往下推，直到遇到刚好全部关闭的情况。
二维数组的深拷贝需用copy库中的deepcopy().
from copy import deepcopy
a=[]
a.append([0]*8)
for i in range(5):t=list(map(int,input().split()))t.insert(0,0)t.append(0)a.append(t)
a.append([0]*8)
qaq=deepcopy(a)
ans=[[0 for _ in range(8)]for _ in range(7)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def button(i,j):for k in range(4):x0 = i + dx[k]y0 = j + dy[k]a[x0][y0] ^= 1a[i][j] ^= 1ans[i][j] ^= 1
def change():for i in range(2,6):for j in range(1,7):if(a[i-1][j]==1):button(i,j)
for i in range(1<<6):a=deepcopy(qaq)ans = [[0 for _ in range(8)] for _ in range(7)]# if(i==37):# for j in range(1,6):# print(" ".join(map(str, a[j][1:7])))# print("TEST")for k in range(6):if(i&(1<<k)):button(1,k+1)# if(i==37):# for j in range(1,6):# print(" ".join(map(str, a[j][1:7])))# print("TEST")change()if(sum(a[5][1:7])==0):for j in range(1, 6):print(" ".join(map(str,ans[j][1:7])))break# if(i==37):# for j in range(1,6):# print(" ".join(map(str, a[j][1:7])))# print("TEST")# for j in range(1,6):# print(" ".join(map(str, ans[j][1:7])))
2025.11.4
马走日
t=int(input())
dx=[-2,-1,1,2,2,1,-1,-2]
dy=[1,2,2,1,-1,-2,-2,-1]
ans=0
def dfs(x,y,step):global ansif(step==m*n):ans+=1returnfor i in range(8):x0=x+dx[i]y0=y+dy[i]if(0<=x0<n and 0<=y0<m and vis[x0][y0]==0):vis[x0][y0]=1dfs(x0,y0,step+1)vis[x0][y0]=0
for i in range(t):n,m,x,y=map(int,input().split())vis=[[0 for _ in range(m)]for _ in range(n)]vis[x][y]=1ans=0dfs(x,y,1)print(ans)
排列
1.康托展开+逆康托展开。还原的过程中使用小根堆。阶乘使用math库中的factorial.
康托展开
2.
from math import factorial
import heapq
m=int(input())
for p in range(m):n,k=map(int,input().split())a=list(map(int,input().split()))ans=[]t=0count=[0]*nfor i in range(n):for j in range(i,n):if(a[j]<a[i]):count[i]+=1for i in range(n):t+=factorial(n-1-i)*count[i]t+=kt=(t+1)%(factorial(n))-1for i in range(n):temp=t//factorial(n-1-i)ans.append(temp)t=t-temp*factorial(n-1-i)res=[]nums=[]heapq.heapify(nums)for i in range(1,n+1):nums.append(i)for i in range(n):qwq=nums[ans[i]]res.append(qwq)nums.remove(qwq)print(" ".join(map(str,res)))