牛客周赛 Round 34 解题报告 | 珂学家 | 构造思维 + 置换环

思路: 枚举

a,b两字符在相等情况下比较特殊

a, b = input().split()
if a == b:print (2)print (a)print (a + a)
else:print (4)print (a)print (b)print (a + b)print (b + a)

思路: 脑筋急转弯

如果合法，就是0

如果不合法，就把第1项改为n+1（排列外的数）

n = int(input())
arr = list(map(int, input().split()))si = set()
for v in arr:if 1 <= v <= n:si.add(v)
if len(si) != n:print (0)
else:print (1)print (1, n + 1)

思路: 贪心

从高位到低位贪心即可

s = input()arr = []i = 0
while i < len(s):j = iwhile j < len(s):p = ord(s[j]) - ord('0')if p % 2 == 0:breakj += 1arr.append(s[i:j+1])i = j + 1arr.sort(key=lambda x: (len(x), x))print (*arr, sep='\n')

思路: 构造

这题是限制性很强的题， 绝对差值总和为1

对于不满足条件数组，可以立马返回 -1.

难点在于

$$如何构造合法数组$$

假定0元素(左右两侧都存在非0值)，和左侧元素保持一致（反证法使得该假设一定成立）

那就剩下一侧有非0值的0值，如何讨论呢？

• 如果绝对差值总和为1
  • 那就和左侧/右侧的那个非0值，保持一致
• 如果绝对差值总和为0
  • 那就选一边构造一个比左侧/右侧刚好大1的数

n = int(input())
arr = list(map(int, input().split()))if arr == [0 for _ in range(n)]:if len(arr) == 1:print (-1)else:print (*([1] + [2] * (n - 1)), sep=' ')
else:# 计算当前的差值综合brr = [v for v in arr if v > 0]diff = 0for i in range(len(brr) - 1):diff += abs(brr[i] - brr[i+1])if diff > 1:print (-1)else:first, last = -1, -1for i in range(n):if arr[i] != 0:if first == -1:first = ilast = i # 填充中间的值pre = arr[first]for i in range(first + 1, last):if arr[i] == 0:arr[i] = preelse:pre = arr[i]# 填充两端的值if diff == 1:# 需要两端保持绝对值差值为0for i in range(first):arr[i] = arr[first]for i in range(last + 1, n):arr[i] = arr[last]print (*arr, sep=' ')else:# 需要两端构建出一个绝对值差值1if first > 0:for i in range(first):arr[i] = arr[first] + 1for i in range(last + 1, n):arr[i] = arr[last]print (*arr, sep=' ')elif last + 1 < n:for i in range(last + 1, n):arr[i] = arr[last] + 1print (*arr, sep=' ')else:print (-1)

思路: BFS + 验证

属于诈骗题，因为题目一直再诱导你往树形DP上去靠

其实从bfs出发，进行交叉染色

然后对边上两点进行验证，如果存在同色，即不合法

n = int(input())
s = input()
ss = list(s)g = [[] for _ in range(n)]for _ in range(n - 1):u, v = list(map(int, input().split()))u -= 1v -= 1g[u].append(v)g[v].append(u)from collections import dequedeq = deque()
for i in range(n):if ss[i] != '?':deq.append((i, ss[i]))# 需要补充这种特殊情况
if len(deq) == 0:ss[0] = 'd'deq.append((0, ss[0]))# BFS流程
while len(deq) > 0:idx, ch = deq.popleft()for v in g[idx]:if ss[v] == '?':ss[v] = 'd' if ch == 'p' else 'p'deq.append((v, ss[v]))# 验证逻辑
ok = True
for i in range(n):ch = ss[i]if ch == '?':ok = Falsebreakfor v in g[i]:if ch == 'd' and ss[v] != 'p':ok = Falsebreakif ch == 'p' and ss[v] != 'd':ok = Falsebreakif not ok:print (-1)
else:print (''.join(ss))

思路: 异或特性

贴一下皮神的代码

代码即是说服力

n, m, x = map(int, input().split())res = [[0] * m for _ in range(n)]if x % 4 == 0:res[0][0] = res[0][1] = res[1][0] = res[1][1] = x // 4for ls in res:print(*ls)
elif x == 2:print(-1)
else:res[2][0] = res[2][1] = 1res[1][0] = res[1][2] = 1res[0][1] = res[0][2] = 1for i in [0, -1]:for j in [0, -1]:res[i][j] += (x - 6) // 4for ls in res:print(*ls)

思路: 置换环 + 找规律

假如这题没有交换颜色的限制，那这题就是裸的置换环

但是实际上，这题的核心框架依旧是

$$置换环$$

具体情况需要分类讨论

• 同一置换环(a个元素)中存在两种颜色, 则交换一定为a-1

• 同一置换环(a个元素)中只存在1种颜色, 则需要借助外部的非同色，这样为a-1+2=a+1

但是这样做，只能对大致50%+

为啥呢？

因为对于纯色R的置换环，和纯色W的置换环，其实可以互相借调，因此这一组合，可以减少2次不必要的交换。

因此在原先的基础上，需要优化减掉

$$min(纯色R的群数，纯色W的群数)\ast 2$$

n = int(input())
arr = list(map(int, input().split()))
s = input()from collections import Counterif [i + 1 for i in range(n)] != arr and len(Counter(s)) == 1:print(-1)
else:res = 0white, red = 0, 0for i in range(n):if arr[i] == i + 1:continueelse:# 置换环核心逻辑state = 0tmp = 0while arr[i] != i + 1:p1, p2 = i, arr[i] - 1arr[p1], arr[p2] = arr[p2], arr[p1]tmp += 1state |= 2 if s[p1] == 'R' else 1state |= 2 if s[p2] == 'R' else 1# 分类讨论置换环的纯色情况if state == 3:res += tmpelse:# 纯色，需要借调外部力量res += tmp + 2if state == 1:white += 1else:red += 1print(res - min(white, red) * 2)