7
这个区忘了 ST 表,导致 S 初赛被周飞,所以只有 J 打了。
标题何意味.
由于和上一篇训练目的不同,所以单开。
9.24
拜谢 FM 大佬,开始刷题单棍母和棍母
P7909
时候不早了,随便挑个橙玩玩。
因为要找到最大的 kmod nk \mod nkmodn,如果 l,rl,rl,r 除以 nnn 的商下取整相等,则在满足 L≤k≤RL \le k \le RL≤k≤R 的情况下 kkk 越大越好,于是我们取 k=Rk=Rk=R。否则,kmod nk \mod nkmodn 最大值明显为 n−1n-1n−1,直接输出 n−1n-1n−1 即可。
代码
复杂度分析
略
9.25
中秋快乐各位。
13 天假期必须好好补一补 whk 了,也(打算)报了洛谷的课程。但先玩几天(
在酒店看一会 J/S 的题目讲解
9.26
是谁写了一沙滩的毕导。
晚上帮 cchu 调代码,顺便讲一下吧。题目是今晚 ABC 的 D。
这种类型的题目 ABC 似乎出烂了,AtCoder 你只是怕了。
显然 lazy tag 优化,直接线性创飞了。
然后你会收到 AC18,WA13 的好成绩。
下面给一组 hack:
相信大家都知道错在哪了,如果直接去判断当前格子的染色状态会很麻烦,复杂度也会炸。也就是说正着维护很难。
触发关键词了。
没错,正难则反。我们反着去处理查询,每次只要找到这个格子最后一次的有效染色即可。
代码
略
复杂度分析
略
9.28
florr 玩破防了,老实滚回来写题。
P1182
唔,一个简单的二分答案,所以我们确定三个点:
1. check 函数
2. 二分边界
3. 二分内容
二分内容不难想,题目要求我们求最小最大值,所以我们二分这个值。边界也比较简单,显然当我分为 n−1n-1n−1 段时答案最小,为 max(a1,...,an)\max(a_1,...,a_n)max(a1 ,...,an );不分段时最大,为 ∑i=1nai\sum_{i=1}^{n} a_i∑i=1n ai ,那么边界就没问题了。
来看 check 函数。我们要在保证答案为 midmidmid 的情况下,所分段数不超过 mmm。考虑 O(n)\mathcal{O}(n)O(n) 求分段数,若当前这一段大小超过 midmidmid,则划分新的一段。由于我们需要 O(1)\mathcal{O}(1)O(1) 维护静态区间和,所以使用前缀和数组。
那就做完了。
代码:
复杂度分析
比较简单的分析,二分复杂度 O(logk)\mathcal{O}(\log k)O(logk),check 函数复杂度 O(n)\mathcal{O}(n)O(n),总复杂度 O(nlogk)\mathcal{O}(n \log k)O(nlogk)。其中 kkk 为 ∑i=1nai−max(a1,...,an)\sum_{i=1}^{n} a_i -\max(a_1,...,a_n)∑i=1n ai −max(a1 ,...,an )。
P14247
好神奇的题。
乍一看感觉条件三很难,尝试找规律。
看了一眼样例,没有给我们不合法的情况,猜测都是可以的。
从 n=2n=2n=2 开始看,发现随便填都符合条件,当时推到这就开智了。
显然我们构造的这个矩阵中只要包含一个 2×22\times 22×2 的由 1,2,3,41,2,3,41,2,3,4 组成的子矩阵即可满足条件三。
发现条件 333 要满足“恰有”,看看怎么放可以不出现第二个如上的子矩阵。我们假设 n=3n=3n=3,在上述条件下,我们可以在右侧与下侧全部填 555,右下角填 666,构造出来的矩阵是这样的:
那怎么往下扩展呢,看看 n=4n=4n=4 的情况,按照上述方法构造,矩阵如下:
发现,若 (n−1)×(n−1)(n-1) \times (n-1)(n−1)×(n−1) 是一个合法的构造,考虑在其右,下侧最后一列(排)放入 2x−12x-12x−1,最右下角放 2x2x2x。不管怎么圈,除了最左上角的子矩阵外,总是有且只有两个数重复。这样就满足了“恰有”这个条件,进而满足了所有条件。
代码
略
复杂度分析
显然为 O(n2)\mathcal{O}(n^2)O(n2)
10.1
P17288
高速上写的,脑子不清醒写了个石山。
直接模拟即可,思路不讲诗人都会吧。
代码
复杂度
O(max(∣a∣,∣n∣))\mathcal{O}(\max(|a|,|n|))O(max(∣a∣,∣n∣)),证明略
有帮助,赞一个