原题: http://codeforces.com/contest/598/problem/A 题目大意: 给一个数字n, 求1…n的合, 其中如果遇到2的倍数的数,要当负数处理. 分析: 直接求O(n) 会超时, 所以会想到求和公式. 通过观察可以发现, 给一个n, 我们可以: 求1到n的合, 用等差数列求和公式. 找到1到n中,有多少个2的倍数, 用对数公式, 这里注意, 1也是, 所以求完log后要用flooring求包含几个2的倍数后, 要加上1. 用公式 减去两杯的上面公式的结果就是答案了. public class TaskA { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); for (int i = 0; i < n; i++) { out.printLine(solve(in.readLong())); } } public long solve(long […]

原题: http://codeforces.com/contest/581/problem/B 题目大意: 给n个数, 表示n层楼, 问从左向右, 加盖几层楼可以使得当前的楼比右边最高的楼还高. 分析:开始的时候直接写了一个O(n^2)的算法, i遍历每个楼, j遍历当前楼右边的楼找出最大. 后来超时了, 想想发现可以从右向左扫,记录一下max 如果当前楼比max矮, 则盖max-ary[i]+1层, 然后每次扫一个数都更新max. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = IOUtils.readIntArray(in, n); int max = 0; int[] result = new int[n]; for (int i = ary.length – 1; i >= 0; i–) { if (ary[i] […]

原题: http://codeforces.com/contest/581/problem/A 题目大意:  给两个数,n和m, 两个表示不同颜色的袜子, 每天都穿不同的袜子, 问几天能穿不同的袜子, 剩下的袜子能穿几天. 分析: 不同袜子就是两个数取最小, 剩下的袜子的数除以2就是剩下的袜子能穿几天 public void solve(int testNumber, InputReader in, OutputWriter out) { int red = in.readInt(); int blue = in.readInt(); int f = Math.min(red,blue); out.print(f); out.print(‘ ‘); int s = red > blue ? red – f : blue – f; out.print(s/2); }

原题: http://codeforces.com/contest/580/problem/C 题目大意: 给一个tree, tree上有几个mark的节点, 连续走m个mark的节点就不能继续往下走了. 问你能走到多少个leaf. leaf的定义是没有child的节点. 分析: 首先找出mark的节点的index, 存一下, 然后找到leaf的index, 存一下, 找leaf时, 看一下相邻的节点个数就可以判断出那个是leaf, 如果节点个数是1(只有父节点), 那么就是leaf. 然后从root dfs一下, 每次搜到一个mark的节点就计数, 达到m个就return, 然后遍历每个leaf节点, 如果这些节点都visited了, 那么就res++. int res = 0; ArrayList<Integer>[] g; ArrayList<Integer> leaf; int[] cat; int n; int m; boolean[] visited; public void solve(int testNumber, InputReader in, OutputWriter out) { n = in.readInt(); m = in.readInt(); g […]

原题:http://codeforces.com/contest/580/problem/B 题目大意: 给n,d两个整数,给n个pair<first,second>, 让你找second的合最大的pair组, 满足first之间的差值不大于d. 返回sum. 分析: 因为要满足的条件是pair中, first的差值不大于d, 所以首先我们要以first为基准, 排序n个pair. 其次,我们要找期中second的合最大的数组, 满足first的差不大于d, 这时, 我们已经知道, 答案在已排序的数组中, 并且是连续的子数组. 这时, 我们用双指针扫描. 第一个指针i扫整个pair组的每一个pair, 第二个指针j在i后边, 用来判断当前元素是否能满足abs(A[cur] .first – A[i].first) < d. 如果不满足, 要往前移动j,并且把A[j]从cur中踢除.. 然后每次取最大值. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int d = in.readInt(); Pair<Integer, Integer>[] ary = new Pair[n]; for (int […]

原题: http://codeforces.com/contest/580/problem/A 题目大意: 给一个数组, 找最大的连续非递减子数组. 分析: 这个…就扫一下, count一下每次有多少个连续的数是非递减的, 注意的是counter要从1开始. 因为如果一个数, 自己就是非递减的. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int max = 1; int cur = 1; int[] ary = IOUtils.readIntArray(in,n); for (int i = 1; i < ary.length; i++) { if (ary[i] >= ary[i-1]) cur++; else cur = 1; max […]

原题: http://codeforces.com/contest/579/problem/A 题目大意: 繁殖细菌, 细菌每天翻倍, 每天都可以添加任意个数的细菌. 问最后得到n个细菌, 需要加多少个细菌. 分析: 倍数增加, 就是二进制的1的个数, 每过一天, 前一天的细菌个数都增加 <<1 个, 所以找一下n中有几个1就可以了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); out.print(countOne(n)); } private int countOne(int x) { int count = 0; for (int i = 0; i <= 31; i++) { if ((x & (1 << i)) […]

原题: http://codeforces.com/contest/577/problem/B 题目大意: 给n个数, 问能不能找到其中的subsequence的合可以整除k. 分析: 额..这题开始做的时候考虑不周, 老是过不了, 后来加了个mod k 就过了. 看了答案后, 感觉思路差不多, 首先,当n>k时, 因为鸽巢原理, n个数,每个贡献1,肯定能找到合整除k的. 而当n<=k时, 我们可以通过记录数组当前数字与前一个数组合的模来判断是不是是否可以整除, 即: 如果合的模是0, 那么找到了答案返回YES. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int k = in.readInt(); int[] nums = IOUtils.readIntArray(in, n); boolean[] mod = new boolean[k]; for (int i = 0; i < n; […]