doge的个人site
0%

tea-1128

Posted on Edited on

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的时候的答案

推论:

  1. 由于异或和 = 0 意味着 i必须是个偶数(奇数的最后一位必然是1)
  2. 考虑$n$个数的二进制最低位, 有$j$个1, 从n个数里面取的有效方案数就是$C(n, j), j = 0,2,4,…$
  3. 去掉最低位后 其余位数元素和等于$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的起点来求

如何判断一个图是否含有奇数环(二分图)

  • 不能二分图的有环图就是有奇数环
  • 偶数环可以对角染色完成二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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