原题: 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/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 = […]
原题: 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; […]
原题: http://codeforces.com/contest/577/problem/A 题目大意: 给两个数字,n和k, 找出等于k的个数在n*n的table中, table中每一位是i*j, where i and j are row and column 分析: 这个暴不了, 所以考的是观察. 观察题中给的example: 我们可以发现, 在一个n=6的表中, k=12 出现在6 4 3 2. 这些数字都是12的除数, 可是少了几个啊, 12本身也是除数,1 也是除数, 而且在n=10,k=5中, 我们发现答案是2(1和5). 那么上边的1和12 为什么不算? 因为 12/1 = 12 , 12不在表中. 所以我们得到另一个条件, 除完的余数要小于等于n. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int k […]
原题: 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++) { […]
原题: http://codeforces.com/contest/574/problem/B 题目大意: 给一个无向图, 问你是不是有三个点互联, 并且算出所有三点互联情况下, 这三点的degree的合. 分析: 开始的时候, 看到4000的顶点数, 先想的就是直接暴, 后来发现第7个test case 过不了, 中间加了个简单的剪枝, 立刻就过了. 先把图建起来, 然后用个array存一下每个点的度, 最后用结果减去6(三个点互相连接的度), 就是这三点和其他点度的合. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); int[] h = new int[n+1]; boolean[][] g = new boolean[n+1][n+1]; for (int i = 0; i < m; i++) […]
原题: http://codeforces.com/contest/574/problem/A 题目大意: 给一个n的数的数组, 问如何让第一个数拿最少数组中别的数字的数,使得第一个数变成这个数组最大的数. 分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是O(n2), 看来能有lgn的做法. 后来想想, 假设第一个数是数组中最大的数, 那么就可以不用拿别的数, 如果第一个数不是数组中最大的数, 那么它最多拿的数, 应该是数组中最大的数. 假设数组: 5 1 11 2 8. 第一个数5不是数组中最大的数字, 那么我们可以假设, 最坏情况下, 我们最多拿11(11为数组中最大的数字), 使得5变成数组中最大的数字, 当然这个情况是最坏情况. 其次, 上面例子中的5 1 11 2 8的结果是4, 那么我们可以证明, 任何大于4的数字都是可以的. 因此, 我们可以通过二分搜索的办法, 搜索这个数字. 复杂度是o(nlgn), n是每次检查搜索结果的正确性, lg是二分. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] […]
原题: http://codeforces.com/contest/572/problem/B 题目大意: 对n个股票操作进行排序, 最后生成一个Order Book. 操作有两种, buy 和 sell, 后边是股票标号和价钱. 要求对相同操作的相同股票进行合并操作. 然后输出排序后前s个sell和buy的股票. 这里的排序要求是, 对于sell, 先对编号递增排序, 然后取前s (没有s个取所有). 然后再对编号递减排序. 对于buy直接递减排序即可. 分析: 用Java的TreeMap一下就出来了. 因为TreeMap本身就是有序的, 用Collections.reverseOrder()可以改变顺序. 然后取前s个的时候, 可以把set变成stream, 然后limit一下就可以 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int s = in.readInt(); int cb = 0; int cs = 0; Map<Integer, Integer> BMap = […]
原题: 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”); […]