11.30 ARC 136B - Triple Shift #
https://atcoder.jp/contests/arc136/tasks/arc136_b
给定两个数组A和B, 长度为都是$N \ge 3$
对于两数组中任意相邻的三个元素$a[i], a[i+1], a[i+2]$, 可以执行以下操作任意次:
- 交换$a[i], a[i+1], a[i+2]$, 得到 $a[i+2], a[i], a[i+1]$
问是否可能让A和B相同?
解法 #
-
$x,y,z = z,x,y = y,z,x$ 可以发现这样的一个规律(三个元素必然可以排序第一个)
-
$N$个元素序列必然可以排序前$N-2$个元素
于是第一点我们可以直接排序A,B数组, 看构成是否一样?
构成不一样直接No, 否则继续观察内部元素
-
如果存在重复的元素, 那么必然可以把重复元素放到一起(所以肯定可以实现排序)
-
如果没有, 就要看最终前N-2排完序后最终是否一致了(因为不能出现x,z,y)这种顺序 (这里可以借助逆序对的奇偶性来反映这一点)
12.1 ARC 116D - I Wanna Win The Game #
https://atcoder.jp/contests/arc116/tasks/arc116_d
解法 #
- n个非负整数
- 所有数的和为m
- 所有数的异或和为0 $A_1\oplus A_2 \oplus ⋯ \oplus A_N=0$
- $1 \le n,m \ge 5000$
所以每个元素取值在5000以内
对于异或和=0问题, 等价于观察每个比特为1出现的次数是否是偶数
对于相加和等于m, 等价于一个背包问题
用这样一个数组f[5000][32][2] 表示状态
f[x][y][z] 表示取得数字和为x, 比特位y上的1出现次数为z的方案数
每一轮更新 滚动数组, 因为5000 < 8192 所以只会用到前几个比特位(2^13) 所以只有0-13这14个比特位有效
时间就是O(14NM) = 14 * 25 * 1E6 =
空间就是O(NM) #
定义 $f[i]$为 n个元素和为i的时候的答案
推论:
- 由于异或和 = 0 意味着 i必须是个偶数(奇数的最后一位必然是1)
- 考虑$n$个数的二进制最低位, 有$j$个1, 从n个数里面取的有效方案数就是$C(n, j), j = 0,2,4,…$
- 去掉最低位后 其余位数元素和等于$i - j$, 再进行右移, 考虑$f[(i-j)/2]$
得到了一个递推关系式$f[i] = \sum_j f[(i-j)/2] \ctimes C(n,j), \ j=0,2,4,…$ 初始状态 $f[0] = 1$
所求的就是$f[m]$
12.02 ARC 077B #
https://atcoder.jp/contests/abc066/tasks/arc077_b
计算一下发现只需要关注两个唯一出现的重复位置带来的影响即可 靠左边一侧的重复元素位置记作$x$, 右边一侧的元素记作$y$
那么对于给定长度$k$, 会产生重复计数的序列数是多少?
- 数左边的时候, 会再在右边数到一次
- 左侧$x - 1$个, 右侧$n - y - 1$个, 从这些里面选$k-1$个得到的序列都是重复的
- 可以预处理这一段
组合数计算+逆元 可以参考模板
LC322 将节点分成尽可能多的组 #
被图论暴打了(悲) https://leetcode.cn/problems/divide-nodes-into-the-maximum-number-of-groups/
贴一个周赛的T4做法
由于是一个普通图, 我们可以拆分成多个连通分量 下面假设是一个连通图
- 考虑图的性质 发现如果是一个树(无环连通图), 那么始终可以满足题目要求
- 否则, 如果这个图存在奇数环就一定不行;
- 偶数环的连通图是可以完成分层操作的.
然后所求的答案就是每个连通分量内可以达到的最大分层数量, 这个我们不知道图的形状所以只能通过枚举BFS的起点来求
如何判断一个图是否含有奇数环(二分图)
- 不能二分图的有环图就是有奇数环
- 偶数环可以对角染色完成二分
class Solution:
def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
"""
|y - x| = 1
对于同一个点y
从某个节点x到达y
每一跳的组只能差1
所以不同路径的长度差距一定是偶数(路径长度都是奇数/偶数)
"""
g = [[] for _ in range(n)]
for e in edges:
a, b = e[0] - 1, e[1] - 1
g[a].append(b)
g[b].append(a)
# 时间戳判定BFS顺序
time = [0] * n
clock = 0
def bfs(start):
dep = 0
nonlocal clock
clock += 1
time[start] = clock
q = [start]
while q:
tmp = q
q = []
for x in tmp:
for y in g[x]:
if time[y] != clock:
time[y] = clock
q.append(y)
dep += 1
return dep
color = [0] * n
def is_bipartite(x, c):
color[x] = c
nodes.append(x)
for y in g[x]:
if color[y] == c or (color[y] == 0 and not is_bipartite(y, -c)):
return False
return True
ans = 0
for i, c in enumerate(color):
if c != 0: continue
nodes = []
# 存在奇数环
if not is_bipartite(i, 1): return -1
ans += max(bfs(x) for x in nodes)
return ans