Menu Sidebar
Menu

Codeforces

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 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数组重构回文, 因为我们想把大的字符放在中间, 把小的字符放到两边, 这种构建方法确保了构建后的回文是字典序最小的回文. […]

Educational Codeforces Round 1 D. Igor In the Museum

原题:http://codeforces.com/contest/598/problem/D 题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个. 分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是[email protected]#@!#!, 于是记录一下每次请求的结果. 原想是用uf记录, 后来想了想有现成的k, 就用k记录了…一个hashmap来的比uf方便的多.

 

Educational Codeforces Round 1 B. Queries on a String

原题: http://codeforces.com/contest/598/problem/B 题目大意: 给一个string, 给l,r,k三个数, l和r是其中的char的index(以1为底), 求k次右shift后的string 分析: 没有什么算法, 就是注意是以1为底, 然后特殊情况有两种, 一个是k比r-l+1大, 所以取余, 另一个是r==l, 别的都是照常实现就好.

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

October 2019
M T W T F S S
« Sep    
 123456
78910111213
14151617181920
21222324252627
28293031