2021年软件类第十二届蓝桥杯第二场省赛 python组 F-J题解

'''
比较简单就是枚举即可
'''
cnt = 0
n = int(input())
for i in range(1,n):
    if (i*i)%n <= n/2:
            cnt += 1
print(cnt)

'''
利用一种分解质因数的方法来计算
'''
from collections import Counter
h = Counter() # 计数，质因数的个数
n = int(input())
for i in range(2,int(n**0.5)+1): # 循环遍历
    while n%i==0: # 进行分解质因数
        n = n//i
        h[i] += 1 # 计算质因数个数
x = 1
for i in h:
    if h[i]%2 == 1: # 如果质因数的个数为奇数，就乘x
        x = x*i 
if x == 1:
    print(n) # 本身是一个质数，不用分解，打印自身
else:
    print(x) # 得到分解质因数后的值

import heapq
heap = []
n,m = map(int,input().split()) # 计算机数和任务数
v = list(map(int,input().split())) # 计算机的资源
v = [0] + v
for i in range(m):
    # a为时刻，b为机器，c为耗费时间，d为算力资源
    a,b,c,d = map(int,input().split())
    # 判断优先队列是否存有资源
    while heap:
        x = heap[0]
        if x[0] <= a: # 判断释放资源的时间 是否小于等于 当前时刻
            v[x[1]] += x[2] # 释放资源
            heapq.heappop(heap)
        else:
            break 
    # 判断是否有资源，如果有资源就分配，并加入优先队列 
    if v[b] >= d:
        v[b] -= d
        heapq.heappush(heap,(a+c,b,d))
        print(v[b]) # 打印剩余算力 
    else:
        print(-1)

'''
主要思路就是利用状压dp来解决
如果直接用我们的dfs应该是必会超时的
因为我们的行数和列数和马的数不是一样的
'''
# 计算二进制中1的个数，也就是计算当前列增加了多少个棋子
def lowbit(x):
    res = 0
    while x:
        # print(bin(x))
        res += 1
        x -= x&-x # 减去最低位的1
    return res
n,m,k = map(int,input().split())
# f[i][a][b][t] i 代表前i列，a代表前列，b代表当前列的状态集合，t代表已经用过多少个棋子
# f[n][m][m][k]
f = [[[[0]*(k+1) for _ in range(1<<n)] for _ in range(1<<n)] for _ in range(m+1)]
f[0][0][0][0] = 1 # 初始化为1
MOD = int(1e9+7)
for i in range(1,m+1):  # 循环枚举列，二进制枚举行的情况
    for a in range(1<<n): # 前一列
        for b in range(1<<n): # 当前列
            if (b>>2) & a or (b<<2) & a: continue
            for c in range(1<<n): # 前前列
                if (c<<2) & a or (c>>2) & a: continue # 与上一列发生冲突
                if (c<<1) & b or (c>>1) & b: continue # 与当前列发现冲突
                t = lowbit(b)  # 当前列放了 t 匹马
                for j in range(t,k+1): # 状态转移，也就是背包计数
                    f[i][a][b][j] = (f[i][a][b][j] + f[i-1][c][a][j-t]) % MOD
# 放了m列，当前状态为b，上一个状态为a，总共放了k 匹马的方案数
res = 0
for a in range(1<<n):
    for b in range(1<<n):
        res = (res + f[m][a][b][k]) % MOD
print(res)