(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）
T1 codeJan与***
可以根据 codeJan 的位置，将方格矩阵分成四个子矩阵分别考虑。对于每个子矩阵如果存在边长为 0的话，就不用考虑。如果存在边长小于 K 那一定不能完成任务，否则依次按照行列炸毁。因为要炸毁所有区域且允许重复炸一个区域，所以对于 a ∗ b 的子矩阵行上需要
可以想象的是如果 m 足够大，codeJan 最后肯定会选择在相邻的两个城市来回走。所以可以枚举两个相邻的城市(实际上应该是距离最小的两个城市)。并且直接” 奔向” 这两个城市的应该是最吼的！但是还要考虑，可能先往后退到 一个城市，再” 奔向” 枚举的城市。
举个例子就明白了：n = 3,m = 10, p = 2，三个城市的位置是 1 10 14。那么应该先退回到 1，然后再在 10 和 14 之间来回走。时间复杂度：O(n)
T3 小Q与氪金游戏
如果x>=y，直接枚举氪金单数进行计算，否则不同的抽卡次数会对应不同的氪金单数，可以直接枚举抽卡次数进行计算，只需要枚举足够多项即可达到要求的精度，标程枚举了 10^6项。
T4 codeJan与青蛙
先把所有的青蛙按照位置从小到大排序。下面用“代价”代称听到的 WA 次数。dp[i][j] 表示用 j 个黑洞收集前 i 个位 置青蛙的最小代价。枚举第 j 个黑洞的放置位置k，可以得到状态转移方程：
其中 cost[k][i] 表示第 k 到 i 位置的青蛙全部被放在 k 位置上的黑洞收集的代价。 如果我们定义:
因此可以通过
T5 珂朵莉与GCD
从一个点 r 开始往左端的 gcd 最多只会变化 logv 段先预处理出每个点到一端的所有 gcd 变化的位置然后把询问离线扫描线右端点，维护所有左端点的答案即可总复杂度 O( mlognlogv + nlogv )
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
全部评论
(1) 回帖