Menu Sidebar
Menu

Codeforces

Codeforces Round #725 (Div. 3)F. Interesting Function

给两个数字l和r, 求从l加到r中间digit的变化个数是多少. 这题用的方法和D一样,就是先求R的答案, 然后减去L的答案, 具体的求法是通过观察: 比如21这个数, 从1->9 是9个1位改变, 9->10是1个2位, 10->19是9个1位改变, 19->20是2个1位改变. 20->21 是1个1位改变, 所以加起来就是21+2, 有次可推,数字123是123+12+1.

Codeforces Round #725 (Div. 3)D. Another Problem About Dividing Numbers

给三个数,a,b,k, 问a和b是不是能在k次(exactly) 下通过整除相等. 这个题情况比较多, 比如a和b互质, 比如k大于a和b. 反正就是交一次就对的都是大神. 这题思路是, 反正a和b一直和某数做整除, 最后就是1, 肯定相等啊, 所以只需要计算有多少质因子在a和b的和中.即可, 剩下就是各种corner cases.

Codeforces Round #725 (Div. 3)A. Stone Game

给一个数组, 可以从两端取数字, 取了就没了, 求最少多少步可以取了最大和最小值. 这题他妈的真费时间, 一共3种取法 (答案给的是四种), 反正我三种做的, 三种是: 从左往右取, 从右往左和两侧取. 这题给了最大值是n, 最小值是1, 所以1/2两种都很好做, 就是第三个, 需要找下两个值的坐标, 然后减去两端就行了.

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 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, 通过观察我们知道, 我们只需要遍历一半的数组就可以得到答案, 因为我们是通过”给数”的方法, 所以我们用一个循环遍历一半的数组. 通过再次观察不难发现, 比如数组 […]

Older Posts

书脊

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