atcoder 上的一些题

可能要停更了，现在只是在AT上打ABC但是马上就打不了。 突然发现 atcoder 居然没有被关，知道这上面数据结构题很少，用到一些高难度算法的题目比较少，于是就随便刷了一些题。 $update$ on 10.18:学习了日记的方法，采用栈的形式。 持续更新。 ## D - Partition [Partition](https://atcoder.jp/contests/abc112/tasks/abc112_d) 题意就是将m分解成n个相加和为m的数，使这些数的最大公约数最大。 不能算是一道数学题，因为我们会发现这个最大的公约数一定是m的一个约数，所以直接跟号m枚举就完了。 [代码链接](https://atcoder.jp/contests/abc112/submissions?f.Task=abc112_d&f.LanguageName=&f.Status=&f.User=longdie) # AtCoder Beginner Contest 180 [比赛链接](https://atcoder.jp/contests/abc180) 这是在AtCoder打的第一场比赛，确实有点水，除了后三题的难度还可以，其他的就是入门级别的题。 打完这场就灰名了。 ## D - Takahashi Unevolved 比较简单的一道题，显然贪心选最优，但是这样选择会TLE，所以如果乘已经不优了，那么直接计算出需要几次加法，直接跳出。 反正这道题我不开 unsigned long long 是过不了的，当然也可以不用。 ## E - Traveling Salesman among Aerial Cities 个人感觉就是一个状压DP板子题，设 $f[i][j]$ 表示当前打通集合i，并且最后在j点时的最短路程，然后直接暴力转移就完了。 ## F - Unbranched [Unbranched](https://atcoder.jp/contests/abc180/tasks/abc180_f) 这道题算是比较难的一道了，应该是一道计数DP。 就是计算满足条件的一类图的个数。 这道题细节还是挺多的。 首先采用前缀和的形式，设最大的联通块不超过 l 的图的个数，然后直接减去 l-1 的就可以了。 设 $f[i][j]$ 表示用了i个点和j条边的方案数。 转移的时候分类枚举是环是链就可以了。 但是注意的是如果一个点的话是不分环和链的， 两个点的情况也需要特判。 再就是是n个不同的点所形成的链的个数，这个自己可以想。 最后就是最恶心的地方了，这样会算重方案，这种情况我们可以强制规定我必须选择当前未选的编号最小的那一个，这样就不会重复了。 给个[代码链接](https://atcoder.jp/contests/abc180/submissions?f.Task=abc180_f&f.LanguageName=&f.Status=&f.User=longdie) ## D - Robot Arms [Robot Arms](https://atcoder.jp/contests/abc111/tasks/arc103_b) 虽说是道ABC的题，但是这却是一道构造题，而且在洛谷上是道紫题，所以其实还是很难的。 题意不是很好说，这个可以在洛谷上看。 首先判无解，给出结论：如果坐标之和的奇偶性不同，那么无解。 这个其实不难想，因为你会发现一个数减一个偶数奇偶性不变（减偶数是因为折返），所以这样是无解的。 那么剩下的情况就是有解了，那么我们要如何构造，题目中说不能超过40条，要不我就可以一直放长度为一的了。 那么看了一下数据范围，我们只能考虑二进制拆分了（其实这种题一般都是二进制拆分）。 首先我们会发现用 $2^0-2^n$ 的数可以拼出 最长为 $2^n$ 的矩形里的奇数点。 然后我们会想到只要再加一条边就可以拼出所有的偶数点。 这样我们的前两问就做完了，后面我们考虑如何拼。 因为我们已经证明了一定可以拼出，那么我们直接贪心从大到小放，哪边差的多就往哪边放就完了。 然后给一篇[证明博客](https://blog.csdn.net/zxyoi_dreamer/article/details/82905515) 然后是[代码链接](https://atcoder.jp/contests/abc111/submissions?f.Task=arc103_b&f.LanguageName=&f.Status=&f.User=longdie) ## C - Skip 题目[Skip](https://atcoder.jp/contests/abc109/tasks/abc109_c?lang=ja) abc的一道题，似乎有点太水了，所以不想说了。 就是个n个数的 gcd。 给个[代码链接](https://atcoder.jp/contests/abc109/submissions?f.Task=abc109_c&f.LanguageName=&f.Status=&f.User=longdie) ## D - Median of Medians 链接[Median of Medians](https://atcoder.jp/contests/arc101/tasks/arc101_b) 这道题就是上一道题的下一道，难度似乎增加了不少。 看题目就应该可以猜出这道题是中位数的中位数。 大概就是给定一个长度为 n 的序列,对它的所有连续子区间拿出来求中位数(如果是偶数长度就取较大的那个),再将这些中位数排起来求中位数,问这个中位数是什么。 这道题是一道不错的题目吧，反正我没想出来，挺菜的。 直接考虑二分答案，然后我们可以进行操作，把小于等于 mid 的设为 -1，把大于它的设为 1，再求出前缀和，这样如果一个区间的和大于 0, 那么就是合法的。 注意二分答案的是区间的中位数为小于等于 mid 的区间有多少个。 然后考虑如何维护，其实可以用树状数组维护就行了。 代码不长，给个[链接](https://atcoder.jp/contests/arc101/submissions?f.Task=arc101_b&f.LanguageName=&f.Status=&f.User=longdie) ## C - Candles 一道2018年ARC的题目，比我想象的水多了。 给个链接[Candles](https://atcoder.jp/contests/arc101/tasks/arc101_a) 大概题意就是数轴上放有 n 根蜡烛,初始时站在 0 坐标,移动的速度是一个定值, 求最少用多少时间可以点亮 k 根蜡烛。 感觉一道很水的题目，考虑贪心，我们肯定是把这一段区间上的蜡烛全部点亮，所以直接枚举所有区间就可以了。 其实就是类似于尺取法的一道题目，直接暴力 $O(n)$ 枚举就可以了。 其实这道题应该也就差不多了。 给个[代码链接](https://atcoder.jp/contests/arc101/submissions?f.LanguageName=&f.Status=&f.Task=&f.User=longdie&orderBy=time_consumption) ## D - Make Them Even 题目[Make Them Even](https://atcoder.jp/contests/abc109/tasks/abc109_d?lang=ja) 是ABC中最难的一道，但是好像也很水。 题意概述：给定一个 H*W 的矩阵，每个格子中有一些硬币，每次可以从一个格子向与他四联通的任意一个格子移动一个硬币(只能移动一次)，使得最终的局面中有偶数个硬币的格子最多。 这个题之所以简单是因为它不要求你用最少的移动来实现最优解，这样只要扫一遍就行了，我们发现如果是偶数，一定不需要变动，如果是奇数，只要不是最后一个格子，就一定可以变成偶数，所以直接扫一遍就完了。 [代码链接](https://atcoder.jp/contests/abc109/submissions?f.Task=abc109_d&f.LanguageName=&f.Status=&f.User=longdie) 但是考虑一下进阶问题：1.用最少的步数实现。 2. 如何$O(1)$判断偶数个硬币的格子数是多少。 对于第二个问题很简单，直接把每个数加起来，如果为偶数，则全是，否则最后一个不是。 对于第一个问题，如果可以奇数转向奇数，显然比奇数变偶数更优，然后可以贪心解决（~~细节未考虑~~）。 ## D - Factorization 题目[Factorization](https://atcoder.jp/contests/abc110/tasks/abc110_d) 似乎ABC的最后一题还是有点思维的。 题目是分解的意思，和题意还是很贴切的。 当时我没想出来，其实主要用到的是数学知识。 首先我们可以把这个数质因子分解。 题目就被转化成了,将 m 的质因数排成一排,可以任意合并,求个数小于等于 n 的方案数.虽然题目说是等于 n ,然而不够时添 1 就可以了。 然后就可以把每个质因数分开考虑，这样就转化为了可以为空的**插板法**，然后就很简单了，直接乘起来就行了。 [代码链接](https://atcoder.jp/contests/abc110/submissions?f.Task=abc110_d&f.LanguageName=&f.Status=&f.User=longdie)