链接: http://codeforces.com/contest/600/problem/B 这题有个test20, 卡了最差时间, 所以只是sort不行, 需要先shuffle一下. 其他就是找upper bound, 如果用c++可以直接调用模板, java没有这个函数, 所以需要写一下. count函数就是c++的upper bound, 区别只是count返回index(个数) 而upper bound返回array的元素
链接: http://codeforces.com/contest/600/problem/A 就是普通的字符串处理, 非常烦的是有很多的corner cases. 比如 test 5的 ;;;;;真是变态
原题:http://codeforces.com/contest/598/problem/D 题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个. 分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是!@#@!#!, 于是记录一下每次请求的结果. 原想是用uf记录, 后来想了想有现成的k, 就用k记录了…一个hashmap来的比uf方便的多. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); int k = in.readInt(); char[][] map = new char[n][m]; int[][] visited = new int[n][m]; for (int i […]
原题: http://codeforces.com/contest/598/problem/B 题目大意: 给一个string, 给l,r,k三个数, l和r是其中的char的index(以1为底), 求k次右shift后的string 分析: 没有什么算法, 就是注意是以1为底, 然后特殊情况有两种, 一个是k比r-l+1大, 所以取余, 另一个是r==l, 别的都是照常实现就好. public class TaskB { public void solve(int testNumber, InputReader in, OutputWriter out) { String s = in.readLine(); char[] chars = s.toCharArray(); int n = in.readInt(); for (int i = 0; i < n; i++) { int l = in.readInt(); int r […]
原题: 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 […]
给一个int的array, 问你这个array是不是一个bst的preorder. 用stack做preorder遍历” 如果当前元素大于stack里的元素, 证明我们在遍历一个node的右节点, 这时,因为是preorder, 说明左节点已经遍历过了, 所以我们要把stack中所有小于当前元素的节点pop出来,并且用low记录最后的一个. 如果当前元素比low小, 证明循序有错误, 因为low是左子树中最小的元素. 然后每次把当前node放入stack, 最后stack中有元素也不影响判断是不是preorder public boolean verifyPreorder(int[] preorder) { int low = Integer.MIN_VALUE; Stack<Integer> st = new Stack<>(); for(int p : preorder){ if (p < low) return false; while (!st.empty()&& st.peek() < p) low = st.pop(); st.push(p); } return true; }
原题: 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 […]