开福区网站建设论坛,专门做微信小程序的公司,怎么制作个人作品网站,建设银行衡阳市分行网站前言 整体评价
好绝望的牛客周赛#xff0c;彻底暴露了CF菜菜的本质#xff0c;F题没思路#xff0c;G题用置换环骗了50%, 这大概是唯一的亮点了。 A. 小红的字符串生成
思路: 枚举
a,b两字符在相等情况下比较特殊
a, b input().split()
if a b:print (2)print (a)pri…
前言 整体评价
好绝望的牛客周赛彻底暴露了CF菜菜的本质F题没思路G题用置换环骗了50%, 这大概是唯一的亮点了。 A. 小红的字符串生成
思路: 枚举
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)B. 小红的非排列构造
思路: 脑筋急转弯
如果合法就是0
如果不合法就把第1项改为n1排列外的数
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)C. 小红的数字拆解
思路: 贪心
从高位到低位贪心即可
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:j1])i j 1arr.sort(keylambda x: (len(x), x))print (*arr, sep\n)D. 小红的陡峭值
思路: 构造
这题是限制性很强的题 绝对差值总和为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[i1])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)E. 小红的树形 dp
思路: 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] ddeq.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 pdeq.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))F. 小红的矩阵构造
思路: 异或特性
贴一下皮神的代码
代码即是说服力
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)G. 小红的元素交换
思路: 置换环 找规律
假如这题没有交换颜色的限制那这题就是裸的置换环
但是实际上这题的核心框架依旧是 置换环 置换环 置换环
具体情况需要分类讨论 同一置换环(a个元素)中存在两种颜色, 则交换一定为a-1 同一置换环(a个元素)中只存在1种颜色, 则需要借助外部的非同色这样为a-12a1
但是这样做只能对大致50%
为啥呢
因为对于纯色R的置换环和纯色W的置换环其实可以互相借调因此这一组合可以减少2次不必要的交换。
因此在原先的基础上需要优化减掉 m i n ( 纯色 R 的群数纯色 W 的群数 ) ∗ 2 min(纯色R的群数纯色W的群数) * 2 min(纯色R的群数纯色W的群数)∗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)写在最后
