Menu Sidebar
Menu

math

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

Codeforces Round #319 (Div. 2) C. Vasya and Petya’s Game

原题: http://codeforces.com/contest/577/problem/C 题目大意: 给一个数字n, 一个人猜这个n是多少, 他可以提问: n是不是整除x, 问你最少提问多少次,问的是什么可以猜出n. 分析: 算术基本定理(https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). 可以证明,我们需要猜出每个n前边的的质数p, 对于每个p,我们还要猜出其不大于n的倍数, 才能确保n的唯一. 所以答案先晒质数, 再求倍数.

[SPOJ] FCTRL – Factorial

原题: http://www.spoj.com/problems/FCTRL/ 题目大意: 给一个数字n,问你n!后边有多少个0. 分析: 这就是Leetcode那个Factorial Trailing Zeroes 我们看n!是由多少个5的倍数组成的. 就知道后边有几个0. 纯数学题. 没意思

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) C. Bear and Poker

原题: http://codeforces.com/contest/574/problem/C 题目大意: 给一个n个数的数组, 问这几个数能不能通过double或者triple得到一个相同的数. 分析: 几个数能通过double或者triple得到一个相同的数, 必然这几个数由2 或者(和) 3的倍数组成, 所以这几个数可以分解成2^a*3^b* rest, 所以我们先要把每个数的2的倍数和3的倍数都消去, 然后检查rest部分是不是相同, 即可判断是不是可以通过double和triple组成相同的数.

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) A. Arrays

原题: http://codeforces.com/contest/572/problem/A 题目大意: 给两个数组, 问是否能在第一个数组找到k个数,在第二个数组找到m个数, 使得所有在第一个数组找到的数小于第二个数组找到的数. 数组已排序. 分析: 因为数组已经排序, 所以如果在第一个数组前k个数字小于第二个数组后m个数字, 那么打印YES.如果不是, 打印NO

Ugly Number II

因为定义的ugly number是2,3,5的倍数, 所以新的ugly number也是由他们的倍数组成. 每次找到三个数中最小的, 然后求它的倍数.

Ugly Number

Codeforces Round #316 (Div. 2) B. Simple Game

原题: http://codeforces.com/contest/570/problem/B 题目大意: 给一个范围[1,n], 一个人取范围中的数字m, 问你如何取一个数字a, 可以让|c-a| < |c-m|的概率更高, where c 是一个[1,n]中的随机数 分析: 可以把范围看成一组数, 其中的m把这组数字分成了2组, [1,m)和(m,n]. 于是这个题就转化成问你, 找一个数字a,让a覆盖的数字比m覆盖的数字更大. 这个数字肯定在m+1或者m-1, 这时候, 需要比一下m和n/2, 看看m是在n的中间的左边还是右边, 如果是右边, 那么说明m左边的数字比右边的多, 所以我们选m-1, 相反同理.

[LintCode] Fibonacci

[SPOJ] DIVSUM – Divisor Summation

原题: http://www.spoj.com/problems/DIVSUM/ 题目大意: 给一个数n,找到它所有的除数的合. 比如number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22. 分析: 第一次提交的时候, 老老实实找每个divisor, 结果tle了. 后来想想20/2 = 10, 一次可以把2和10都找到, 所以lgn就可以有. 先上第一次代码:

以上代码tle, 下面是二分代码:

另外注意的是, 1的结果是….0….

Older Posts

书脊

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

June 2019
M T W T F S S
« May    
 12
3456789
10111213141516
17181920212223
24252627282930