原题: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); […]
原题: http://codeforces.com/contest/556/problem/C 题目大意: 俄罗斯套娃, 给n个套娃, 套成k组, 每组用数字表示, 大的数字套小的数字, 问怎么把它们套在一起. 分析: 这题想了好久哇. 因为开始读题不仔细, 所以开始想的时候各种WA. 我以为: 1 2 3 4 5 6 这种情况只需要一秒. 但是仔细看题才发现, 这个需要先把6拆下来, 然后把5 套在4上, 然后把6套在5上, 所以是三步. 这个地方卡了好久. 剩下的思路很明确: 首先找到最小的套娃1, 然后往后扫, 看看按照1 2 3 4 ….n这个顺序有几个. 因为把n个套娃套上需要n-1秒,所以坏情况, 就是我们拆下所有的套娃用n-1秒, 然后套上去, 用n-1秒, 这里的-1的原因是编号1的套娃不用动. 所以最坏下是n-1+n-1 = 2n-2秒. 然后我们用排除法, 这里需要把拆开和组装分开记录,一种是 一个链子中为: 1 2 3 4 5 …. 这种情况下, 我用变量b记录了有多少个不用组装的套娃. 第二种是, […]
原题:http://codeforces.com/contest/556/problem/B 题目大意: n个数字组成的数组, 如果是已经排序的0.1.2.3…n 返回yes, 如果不是, 偶数的数变大,奇数的数变小, 不管大小, 都绕着n转,问能否转出来0.1.2.3..n 分析: n才1000, hash一下放hashset里. 转的时候, 多一步+n再取模, 防止负数 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = IOUtils.readIntArray(in, n); HashSet<Long> hashSet = new HashSet<>(); int[] ary = new int[n]; for (int i = 0; i < n; i++) { ary[i] = […]
原题:http://codeforces.com/problemset/problem/558/B 题目大意: 给一个数组, 找出其中的子数组,并且要求原数组中出现最多次数的数字在在子数组中.最多次数的数字可以不唯一. 所以答案也不一定唯一 分析: 暴啊暴啊…先按照频率排序,然后找同频率下所有的数字间隔在原数组中间隔最小的. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int nums[] = IOUtils.readIntArray(in, n); HashMap<Integer,Item> map = new HashMap<>(); // <num, item> for (int i = 0 ; i < nums.length; i++) { int x = nums[i]; if (!map.containsKey(x)) map.put(x,new Item(i,i,1)); else { Item […]
原题:http://codeforces.com/problemset/problem/558/A 题目大意: 坐标轴上, 每个坐标上有一颗苹果树, 坐标的值代表的值是苹果的数量, 人从0开始走, 可以往左,也可以往右, 当遇到一个苹果树时, 人必须往反向走, 问:最多拿多少个的苹果? 分析: 无非开始往左or往右, 两种情况, 当遇到另一边没有树的时候, 停止, 所以最多拿max([left+1,right],[right+1,left]).left,right 原点左右的树的数量. 建个Pair<Integer,Integer>, 前边是index, 后边是value, 然后sort下 加一下就出来了. public void solve(int testNumber, Scanner in, PrintWriter out) { int n = in.nextInt(); ArrayList<Pair<Integer,Integer>> pos = new ArrayList<Pair<Integer,Integer>>(); ArrayList<Pair<Integer,Integer>> neg = new ArrayList<Pair<Integer, Integer>>(); for (int i = 0; i < n; i++) […]