Codeforces Round #724 (Div. 2)A. Omkar and Bad Story
给一个数组, 问是否可以组成一个数组, 里面的元素包含其中任意两个元素相减的绝对值. 这题, 我上来以为是等差数列什么的呢…结果就是暴力求解..
Codeforces
Educational Codeforces Round 110 (Rated for Div. 2)B. Array Reodering
给一个数组, 可以reorder这个数组, 求最大数量的pair, 使得gcd(ary[i], ary[j] * 2) >1 where i < j. 这个题就是需要思考, 我暴力的求解了一下, 发现过不了. 这题求一个数和2个倍数的gcd的大于1(非互质)个数. 因为能无限制reorder, 所以主要看这个数是不是2的倍数, 即是否可以被2整除, 如果可以, 假如ary[i] = 4, 那么肯定和 ary[j] * 2的gcd>1, 无论ary[j]是多少. 所以把数字分成两类, 一类是2的倍数, 另一类是非2的倍数, 然后排序下, 找一边即可.
Educational Codeforces Round 110 (Rated for Div. 2)A. Fair Playoff
给四个数, 两两比大小, 求最后的结果是不是两个中较大的.
Educational Codeforces Round 3 D – Gadgets for dollars and pounds
链接: https://codeforces.com/contest/609/problem/D 这题好tricky, 好几个test都是c++的ll类型的, java做着好头疼. 首先根据题意可以看出来, 能在x天完成任务(从m中买到k个item), 在剩下的x+1天也能完成, 所以具有单调性, 可以在排序(根据买东西的实际价格排序, 这里的实际价格是第i天的汇率*单价). 其次我们的目标是买k个东西, 那么如果给定某天x, 如何用同样的钱(假设), 买更多的东西?, 肯定是先买便宜的啊. 所以是贪心算法. 既然是贪心算法, 我们就要找到算法的关键, 那就是如何在m天中的第i天买到更便宜的东西? 显然, 我们知道汇率和单价是乘法关系, 就要分别找到前i天的两种货币的最低汇率minD和minP, 然后我们要测试一下在cur天的时候, 我们能否买够所需的k个物品. 这里我们用minD和minP分别乘以m个物品, 然后得到的价格就是cur天实际价格, 然后通过排序并且提取前k个物品, 我们就可以测试能否在cur天购买到k个物品.
Educational Codeforces Round 3 C – Load Balancing
链接: https://codeforces.com/contest/609/problem/C 公式推导题, 先要排序ary, 然后算出数组的和sum. 然后可以观察到, 我们可以把相对大的数给相对小的数以便于达到平衡, 这种平衡有两个可能性, 一种是两数合为奇数, 比如数组 1 2 4, 4+1=5, 5是奇数, 这种情况下给完后的差是1, 即2 2 3, 3-2=1. 另外一种情况是两数合为偶数, 比如 1 2 3, 3+1=4, 4是偶数. 这种情况下给完后的差是0, 即2 2 2, 2-2=0. 所以可以证明这种先排序后两端互相给的方法, 是答案要的方法, 即miimize(Ma – Mb), where a is the most loaded server and b is the least loaded one. 最后我们需要找到平衡数组b, 通过观察我们知道, 我们只需要遍历一半的数组就可以得到答案, 因为我们是通过”给数”的方法, 所以我们用一个循环遍历一半的数组. 通过再次观察不难发现, 比如数组 […]
Educational Codeforces Round 3 B. The Best Gift
链接: https://codeforces.com/contest/609/problem/B 就是普通的排序问题, 从m个不同类的物品中, 抽取(不重复)2个不同的物品. 物品没有先后顺序. 第一个循环计算每种物品的个数, 第二个循环外边遍历每种物品, 里面遍历当前物品外的物品, 中间因为物品没有顺序所以是乘法
Educational Codeforces Round 3 A – USB Flash Drives
链接: https://codeforces.com/contest/609/problem/A 先排序一下, 然后从大往小用贪婪思想选数, 注意选的时候的两个情况有先后, 第二种情况 出现是选最后一个数的时候.
Educational Codeforces Round 2 E – Lomsat gelral
链接:https://codeforces.com/contest/600/problem/E 上面code的idea不是我自己想的, 是我看了答案后, 找到另一个人的解法, 然后优化出来的. 答案里写的方法有点太难了, 我看了另一个文章还有用dsu(union-find) in tree优化的. 题目边上的Problem tags里也有dsu. dsu在这里优化主要是用来减少dfs中合并子树中color count, 但是我感觉其实并不需要这样做: 首先, 用dsu就需要标记leaf和root, 然而我们的本意只是想找到leaf的color count, 然后合并, 所以其实只要记录并比较当前dfs节点上的count大小和我们记录下的与其相邻的节点大小, 就可以知道谁是leaf, 谁是root (dfs原理). 这样在dfs经过leaf的时候, 我们只需要记录当前的count就可以, 在dfs经过root的时候, 我们通过parent 这个变量, 就知道上次调用的节点数据. 其次, dsu合并的均摊是logn, 但是使用dsu需要维护另一个数组, 并且构图的时候也要多构造一个dsu. 而这里我们使用两个变量, sum和count, sum记录当前node下属所有节点的有最大count的color的合, count记录当前node下属所有节点的有最大count. 这里我们把这两个关键数据放在dfs的外侧, 作为闭包内的变量, 然后用totalColorCounts和totalColorSums记录全局数据. 这样我们在每次访问节点的时候, 就可以通过更新sum和count计算出当前节点的答案, 记录在 totalColorCounts和totalColorSums里. 这个题我觉得最难的是找到更新和维护connectedNodeColorCount和currentNodeColorCount, 一个是子节点的color和count数据, 另一个是这个子节点的父节点的color和count数据. 这两组数据决定了最后的total color和total sum. 另外, 语句connectedNodeColorCount.size() > currentNodeColorCount.size(), 确保了在当前节点为子节点的情况下, […]
Educational Codeforces Round 2 D – Area of Two Circles’ Intersection
链接: http://codeforces.com/contest/600/problem/D 这题不难,就是个公式, 但是Java的double不够精度, 需要用BigDecimal. 然而Java三角函数acos最多支持double, 不支持BigDecimal. 所以难点是要自己写acos(我是肯定不会写展开式的啊)…所以上面code是最高精度. Btw, 我搜了所有code, 基本都是c++…..c++的long double还是好用啊
Educational Codeforces Round 2 C. Make Palindrome
链接: http://codeforces.com/contest/600/problem/C 这题开始做的时候, 还是很费脑的, 首先要关注题中要求的回文问题, 不难看出是需要计算字符串中字频的奇偶, 然后可以想到, 回文只能有不能超过一种奇数的字符. 但是后边很难想的是, 如何修改才能满足 lexicographically (alphabetically) smallest palindrome(字典序下最小回文). 这时可以看到题中给出的回文都是lower case, 所以用双指针的方法, 前后两个指针扫描字频数组, 找到奇数字频的回文, 然后把字典序大的回文给字典序小的回文. 最后一个考点是重构回文, 这里需要注意的是, 我们上一步中已经通过交换的方式消灭了奇数字频的回文, 但是真的完全消灭了么? 其实不然, 回文是可以有一个奇数的字频的字符存在的, 这个字频的字符应该放在中间. 所以我们这里用odd_index, 起始值为-1(表示没有奇数字频), 如果上一步后odd_index不是-1, 这表示我们发现一个字频 这里有两个小技巧: 第一, 当重构回文的时候, 因为题中要求 If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. 我们需要从大的字符往小的字符扫描count数组重构回文, 因为我们想把大的字符放在中间, 把小的字符放到两边, 这种构建方法确保了构建后的回文是字典序最小的回文. […]