企业官网建设流程全解析

也打了不少比赛了。总结一下。

上海市赛

contest

board

还有两题是签到题。然后 6 题低罚时就能金牌。

A. 学术造假

对于矩阵两列，存在≥ k \ge k≥k的子区间差值相同，则称这两列造假。求造假对数。

等价于判断有无差分子区间一致。考虑字符串哈希。然后枚举两列，枚举某一列子区间 + set 判重。时间复杂度O ( n 3 log ⁡ n ) O(n^3 \log n)O(n3logn)。

record

B. 啥博弈

Alice Bob 轮流移动棋子，获取网格上的数值（相邻数值不同）。问先手是否必胜。

Sol：

博弈论圣经：

• 没后继的状态都是必败态。
• 必败态走到的都是必胜态。
• 只能走到必胜态的就是必败态。

1. 任何局面下的最大值一定是必败态。
2. 其邻居一定为必胜态。
3. 进入下一局面。

复杂度O ( n 2 log ⁡ n ) O(n^2 \log n)O(n2logn)，瓶颈在排序。

record

D. 收集符文

给定矩阵，初始全 0。每次操作一个格子让其吸取旁边格子的能量。求最小每个格子满足要求的步数。

tm，诈骗题。

record

F. 神话子序列

给定一串数字，选最长的一个子序列，使得任意子串都不是 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)。

record

The 2024 ICPC Asia Nanjing Regional Contest

contest

B - Birthday Gift

0 , 1 , 2 0,1,20,1,2的串，相邻两个0 / 1 0/10/1可以消掉，2 22可以变0 / 1 0/10/1，求最小长度。

考虑奇偶性。（为什么要考虑呢？）