math

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, 相反同理. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); if (n == 1) { out.print(1); return; } if (m > n / […]

Date August 14, 2015
Category Codeforces
Comments No Comments

[LintCode] Fibonacci

public int fibonacci(int n) { // write your code here int first = 0; if(n == 1) return first; int second = 1; if(n == 2) return second; int third = 0; for(int i = 3; i <=n; i++) { third = first+ second; first = second; second = third; } return third; }

Date August 10, 2015
Category LintCode
Comments No Comments

[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就可以有. 先上第一次代码: public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int […]

Date August 8, 2015
Category SPOJ
Comments No Comments

[SPOJ] FACVSPOW – Factorial vs Power

原题:http://www.spoj.com/problems/FACVSPOW/ 题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n 分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); double power = 0; double fact = 0; int cur = 2; double temp = Math.log(n); while (true) { fact += Math.log(cur); // power = temp * cur; if (fact […]

Date July 30, 2015
Category SPOJ
Comments No Comments

Codeforces Round #308 (Div. 2) B. Vanya and Books

原题:http://codeforces.com/contest/552/problem/B 题目大意: 给个数字n, 求这n个数字的digits个数的合分析: 比如1234, digit是1的区间是[1,9], 一共9个, 2的区间是[10,99]一共90*1个digit, 3的区间是[100,999]一共900*2个digit, n的区间是[10^n,10^(n+1)-1]一共10^(n+1) – 10^(n)*(n-1)个digit. 那么1234 落在区间4, [1000,9999]中. 可以用1234-1000+1得到4个digit的数字的个数, 然后乘以4,得到digit为4的digit数, 然后与前边的区间的合相加, 就是答案第一次写: public void solve(int testNumber, InputReader in, OutputWriter out) { long n = in.readLong(); long t = n; long res = 0; int digits = 1; while (n / 10 != 0) { res += (9 […]

Date July 25, 2015
Category Codeforces
Comments No Comments

Codeforces Round #308 (Div. 2) A. Vanya and Table

原题:http://codeforces.com/contest/552/problem/A 题目大意: 给[1,100]个格子, n个矩阵, 问n个矩阵覆盖格子的合是多少? 分析: 乘一下就出来了 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int res = 0; for (int i = 0; i < n; i++) { int x1 = in.readInt(); int y1 = in.readInt(); int x2 = in.readInt(); int y2 = in.readInt(); res += (x2-x1+1) * (y2-y1+1); […]

Date July 25, 2015
Category Codeforces
Comments No Comments

Codeforces Round #309 (Div. 2) A. Kyoya and Photobooks

原题:http://codeforces.com/contest/554/problem/A 题目大意: 给一个string,表示一个相册页, 左右都能放photo, 问几种方法. 分析: n个相册夹, 左右都能放, n+1种地方, 26种photo, (n+1)*26, 当然会有重复, 重复是n个. 减去重复的就是答案 public void solve(int testNumber, InputReader in, OutputWriter out) { String s = in.readString(); int n = s.length(); out.print((n+1)*26 – n); }

Date July 23, 2015
Category Codeforces
Comments No Comments

Codeforces Round #309 (Div. 1) A. Kyoya and Colored Balls

原题:http://codeforces.com/contest/553/problem/A 题目大意: k个颜色, n个球, 球之间没区别. 问怎么放能至少让一个i个颜色的球排在i+1的颜色的球的前边. 分析:这题目看起来是很拗口, 我看着发愣了一会儿才明白. 颜色是有顺序的.第i+1颜色的前边至少要有一个i颜色的球, 这个i不是固定的. 1<=i<=k-1, 所以题目也可以解释成,至少一组球是有序的, 这个有序不一定是连续的球. 因为i表示的颜色是个范围, 所以要用dp来做, 假设i = 1, 这时候就一种颜色, 因为球和球之间无区别, 所以答案是1. i = 2的时候, 因为要保持以上的条件, 所以我们选一个颜色为2的球,放到最后, 然后其他的无所谓. (点一下,有清楚的图) public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = IOUtils.readIntArray(in,n); int max = 1002; long[][] bio = new long[max][max]; for (int […]

Date July 23, 2015
Category Codeforces
Comments No Comments