Acwing 周赛143 解题报告 | 珂学家 | 状压DP
前言
整体评价
被这个T2难住了, 幸好最后磨出来了，感觉蛮头痛的。T3是道状压题，这个反而容易写。
A. 时间
思路: 模拟
取模，但是对0要改成12
n = int(input())r = n % 12print (12 if r == 0 else r)
B. 数对推理
思路: 按题意模拟
如果一组存在歧义，则必为-1
需要从A，B两人分别去匹配
n, m = list(map(int, input().split()))arr = list(map(int, input().split()))
brr = list(map(int, input().split()))from collections import Countercnt = Counter()bad = Falsefor i in range(0, n * 2, 2):t1, t2 = arr[i], arr[i + 1]tmpCnt = Counter()for j in range(0, m * 2, 2):c1, c2 = brr[j], brr[j + 1]if t1 == c1 and t2 == c2:passelif t1 == c2 and t2 == c1:passelif t1 == c1 and t2 != c2:tmpCnt[t1] += 1elif t1 == c2 and t2 != c1:tmpCnt[t1] += 1elif t1 != c1 and t2 == c2:tmpCnt[t2] += 1elif t1 != c2 and t2 == c1:tmpCnt[t2] += 1if len(tmpCnt) >= 2:bad = Trueelif len(tmpCnt) == 1:cnt[list(tmpCnt.keys())[0]]+=1for i in range(0, m * 2, 2):t1, t2 = brr[i], brr[i + 1]tmpCnt = Counter()for j in range(0, n * 2, 2):c1, c2 = arr[j], arr[j + 1]if t1 == c1 and t2 == c2:passelif t1 == c2 and t2 == c1:passelif t1 == c1 and t2 != c2:tmpCnt[t1] += 1elif t1 == c2 and t2 != c1:tmpCnt[t1] += 1elif t1 != c1 and t2 == c2:tmpCnt[t2] += 1elif t1 != c2 and t2 == c1:tmpCnt[t2] += 1if len(tmpCnt) >= 2:bad = Trueelif len(tmpCnt) == 1:cnt[list(tmpCnt.keys())[0]]+=1if bad:print (-1)
else:if len(cnt) >= 2:print (0)elif len(cnt) == 1:print (list(cnt.keys())[0])else:print (-1)
C. 铺瓷砖
思路: 状压
只能说非常典的状压题
grid = []
for _ in range(2):grid.append(input())n = len(grid[0])dp = [0] * 4# 状压
def f(ch):return ord(ch) - ord('0')dp[f(grid[0][0]) + (f(grid[1][0]) << 1)] = 0for i in range(1, n):dp2 = [0] * 4mask1 = f(grid[0][i - 1]) + (f(grid[1][i - 1]) << 1)mask2 = f(grid[0][i]) + (f(grid[1][i]) << 1)for s1 in range(4):if (mask1 & s1) != mask1:continuefor s2 in range(4):if (mask2 & s2) != mask2:continuep2 = s2 - mask2if (s1 & 1) == 0 and p2 == 3:dp2[s2] = max(dp2[s2], dp[s1] + 1)if (s1 & 2) == 0 and p2 == 3:dp2[s2] = max(dp2[s2], dp[s1] + 1)if s1 == 0 and p2 == 1:dp2[s2] = max(dp2[s2], dp[s1] + 1)if s1 == 0 and p2 == 2:dp2[s2] = max(dp2[s2], dp[s1] + 1)if p2 == 0:dp2[s2] = max(dp2[s2], dp[s1])dp = dp2res = max(dp)
print (res)