Binary Prefix Divisible By 5
找了半天规律，发现没意思。直接破解了。然后submit发现有overflow，看了下输入是个数组，那真是大。立刻想到取模。取模有分配律，对答案无影响
math
Divisor Game
注意的是N % k == 0， 所以如果是偶数，那么Alice取个1就赢了。奇数就是Bob取个1，Alice取个1，然后就不能去了，因为k的取值范围是0 < k < N。因为可以取1，所以最后结束肯定是取不了数了才结束。比如5的话，Alice只能选1. 因为5不能整除2，3，4任何一个数，然后Bob对着4可以选2，但是他不选，他选1，这样4-1=3，Aice要面对3，他只能选1，然后Bob面对2选1，剩下1. Alice输了。 所以只需要判断奇偶即可
Two City Scheduling
这题可有点绕，开始直接想的就是动态规划，然后琢磨了一下，觉得easy应该有greedy的做法，于是想到比较两个人去A和B之间的差的abs，即B[1]-A[1]（去B点cost的差）和B[0]-A[0]（去A点的cost的差），然后排序，再求和。 最后翻了翻答案， 看到以下解法，真是更巧妙。 举例[[10,20],[30,200],[400,50],[30,20]]，因为只有A，B两个点，所以我们假设所有人都去一个点B，那么就是 20 + 200 + 50 + 20. 然后我们数组的两个数相减，得出如果去A，那么哪些人优先去？[20-10], [200-30], [50-400],[20-30] -> [10], [170], [-350], [-10], 然后排序，[170], [10], [-10], [-350]. 这个数组序列是按照最应该去A的人。最后是最巧妙的一点， 我们因为已知n个人要去A，所以只需取前两个，[170], [10].， 然后是我们如何加到最开始的数组？ 首先，我们把[170], [10] 还原成 [200-30], [20-10], 然后我们用20 + 200 + 50 + 20 – (200-30) – (20 – 10).就可以消去B并且加回A。
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的唯一. 所以答案先晒质数, 再求倍数. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] prime = new boolean[n+1]; Arrays.fill(prime, 2, n + 1, true); for (int i = 2; i * i <= n; i++) if (prime[i]) for (int j = […]
[SPOJ] FCTRL – Factorial
原题: http://www.spoj.com/problems/FCTRL/ 题目大意: 给一个数字n,问你n!后边有多少个0. 分析: 这就是Leetcode那个Factorial Trailing Zeroes 我们看n!是由多少个5的倍数组成的. 就知道后边有几个0. 纯数学题. 没意思 public class FCTRL { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int sum = 0; while(n != 0) { sum += n / 5; n = n / 5; } out.printLine(sum); } }
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组成相同的数. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = IOUtils.readIntArray(in,n); for (int i = 0; i < n; i++) { ary[i] = modify(ary[i]); } for (int i = 1; i < n; i++) { […]
Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) A. Arrays
原题: http://codeforces.com/contest/572/problem/A 题目大意: 给两个数组, 问是否能在第一个数组找到k个数,在第二个数组找到m个数, 使得所有在第一个数组找到的数小于第二个数组找到的数. 数组已排序. 分析: 因为数组已经排序, 所以如果在第一个数组前k个数字小于第二个数组后m个数字, 那么打印YES.如果不是, 打印NO public void solve(int testNumber, InputReader in, OutputWriter out) { int na = in.readInt(); int nb = in.readInt(); int k = in.readInt(); int m = in.readInt(); int[] naAry = IOUtils.readIntArray(in, na); int[] nbAry = IOUtils.readIntArray(in, nb); if (naAry[k – 1] >= nbAry[nb – m]) out.print(“NO”); […]
Ugly Number II
public int nthUglyNumber(int n) { int[] ugly = new int[n]; ugly[0] = 1; int m2 = 1; int m3 = 1; int m5 = 1; int f2 = 2; int f3 = 3; int f5 = 5; for(int i = 1; i < n; i++) { int min = Math.min(Math.min(f2,f3),f5); ugly[i] = min; if(min == […]
Ugly Number
public boolean isUgly(int num) { if(num == 0) return false; else if(num == 1) return true; else if(num % 2 == 0) return isUgly(num / 2); else if(num % 3 == 0) return isUgly(num / 3); else if(num % 5 == 0) return isUgly(num / 5); else return false; }