也打了不少比赛了。总结一下。上海市赛contestboard还有两题是签到题。然后 6 题低罚时就能金牌。A. 学术造假对于矩阵两列存在≥ k \ge k≥k的子区间差值相同则称这两列造假。求造假对数。等价于判断有无差分子区间一致。考虑字符串哈希。然后枚举两列枚举某一列子区间 set 判重。时间复杂度O ( n 3 log n ) O(n^3 \log n)O(n3logn)。recordB. 啥博弈Alice Bob 轮流移动棋子获取网格上的数值相邻数值不同。问先手是否必胜。Sol博弈论圣经没后继的状态都是必败态。必败态走到的都是必胜态。只能走到必胜态的就是必败态。任何局面下的最大值一定是必败态。其邻居一定为必胜态。进入下一局面。复杂度O ( n 2 log n ) O(n^2 \log n)O(n2logn)瓶颈在排序。recordD. 收集符文给定矩阵初始全 0。每次操作一个格子让其吸取旁边格子的能量。求最小每个格子满足要求的步数。tm诈骗题。recordF. 神话子序列给定一串数字选最长的一个子序列使得任意子串都不是 9 的倍数。首先任意子串不是 9 的倍数等价于不存在相同前缀和模 9 意义下。那么子序列长度至多为8 88这个前缀序列最多8 ! 8!8!种。考虑枚举前缀序列得到子序列在原串中检查是否存在。预处理一个f i , j f_{i,j}fi,j表示原串中从第i ii位开始下一个j jj的位置。预处理复杂度O ( n ) O(n)O(n)枚举 check 复杂度O ( 8 ! ⋅ 8 ) O(8! \cdot 8)O(8!⋅8)。recordThe 2024 ICPC Asia Nanjing Regional ContestcontestB - Birthday Gift0 , 1 , 2 0,1,20,1,2的串相邻两个0 / 1 0/10/1可以消掉2 22可以变0 / 1 0/10/1求最小长度。考虑奇偶性。为什么要考虑呢 ACM 总结
也打了不少比赛了。总结一下。上海市赛contestboard还有两题是签到题。然后 6 题低罚时就能金牌。A. 学术造假对于矩阵两列存在≥ k \ge k≥k的子区间差值相同则称这两列造假。求造假对数。等价于判断有无差分子区间一致。考虑字符串哈希。然后枚举两列枚举某一列子区间 set 判重。时间复杂度O ( n 3 log n ) O(n^3 \log n)O(n3logn)。recordB. 啥博弈Alice Bob 轮流移动棋子获取网格上的数值相邻数值不同。问先手是否必胜。Sol博弈论圣经没后继的状态都是必败态。必败态走到的都是必胜态。只能走到必胜态的就是必败态。任何局面下的最大值一定是必败态。其邻居一定为必胜态。进入下一局面。复杂度O ( n 2 log n ) O(n^2 \log n)O(n2logn)瓶颈在排序。recordD. 收集符文给定矩阵初始全 0。每次操作一个格子让其吸取旁边格子的能量。求最小每个格子满足要求的步数。tm诈骗题。recordF. 神话子序列给定一串数字选最长的一个子序列使得任意子串都不是 9 的倍数。首先任意子串不是 9 的倍数等价于不存在相同前缀和模 9 意义下。那么子序列长度至多为8 88这个前缀序列最多8 ! 8!8!种。考虑枚举前缀序列得到子序列在原串中检查是否存在。预处理一个f i , j f_{i,j}fi,j表示原串中从第i ii位开始下一个j jj的位置。预处理复杂度O ( n ) O(n)O(n)枚举 check 复杂度O ( 8 ! ⋅ 8 ) O(8! \cdot 8)O(8!⋅8)。recordThe 2024 ICPC Asia Nanjing Regional ContestcontestB - Birthday Gift0 , 1 , 2 0,1,20,1,2的串相邻两个0 / 1 0/10/1可以消掉2 22可以变0 / 1 0/10/1求最小长度。考虑奇偶性。为什么要考虑呢