原题: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/554/problem/B 题目大意: 给个n x n的binary矩阵, 只能翻转(0->1,1->0)列, 问如何翻转, 让全是1行的总数最大. 分析: 因为每次翻转列的时候, 每个行都要翻转, 所以只要找到最大数目的相同的行. 就可以了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); HashMap<String, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { String s = in.readString(); if (!map.containsKey(s)) map.put(s,0); map.put(s,map.get(s)+1); } int max = 0 […]
原题: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); }
原题: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 […]
原题:http://codeforces.com/contest/560/problem/D 题目大意: 给字符串a和b, 定义a和b是等价的,如果: a和b相等. a等分成a1,a2,b等分成b1,b2, (a1==b1 && a2==b2) || (a2==b1 && a1==b2) 分析: 就暴呗…我也不知道为什么我暴就报错, 是因为java的原因么, 我看人家同样码用c++, 都飞快的. public void solve(int testNumber, InputReader in, OutputWriter out) { String a = in.readString(); String b = in.readString(); if (solve(a,b)) out.print(“YES”); else out.print(“NO”); } private boolean solve(String a, String b) { if (a.length() % 2 != 0 || […]
原题: http://codeforces.com/problemset/problem/560/B 题目大意:给三个矩形ABC,问能否把B和C放到A里 分析: 这题做了有40分钟, 生怕考虑不周. 其实就是从从ABC各挑出一条边,如果B,C相加小于A,并BC的另一条边分别小于A另一条边的长度. 那么就能放下. 别的放不下. 所以共2*2*2 = 8种情况. public void solve(int testNumber, InputReader in, OutputWriter out) { int[] a = IOUtils.readIntArray(in, 2); int[] b = IOUtils.readIntArray(in, 2); int[] c = IOUtils.readIntArray(in, 2); Arrays.sort(a); Arrays.sort(b); Arrays.sort(c); if (a[0] >= b[0]+c[0] && a[1] >=b[1] && a[1] >= c[1]) { out.print(“YES”); return; } else if […]
原题:http://codeforces.com/problemset/problem/560/A 题目大意: 一个国家, 发行n个不同面值的货币, 问他们国家能不能用这些货币找开所有的钱, 能返回-1, 不能返回最小的不能找开的钱的价值. 分析: 唉, 脑筋急转弯. 坑了我10分钟啊. 只要发行1元, 就能找开所有钱, 没有发行1元,1元本身就是最小的找不开的钱. 这次round的时间是特殊时间,估计是没睡醒.啃着面包做的. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = IOUtils.readIntArray(in,n); Arrays.sort(nums); if (nums[0] == 1){ out.print(“-1”); return; }else { out.print(“1”); } }
这题是我3年前面G家的原题.所以就写上google, 估计这么简单的题g家再也不会问了. 前几天朋友面G家, 已经上模拟退火了, 我也不知道当场白板模拟退火是什么感觉. 不过听说某神牛能IOI就当场写神经网络, 我也就感叹人和牛的差距比人和人的差距都大. 这题其实就是3-sum问题, code改了改就可以了. 所以想想g家onsite,出个3sum, 刷Leetcode的孩子们不要太高兴了, 是不是很良心. 不过写出来代码还是很容易bug的, 然后问时间复杂度,因为求的不是最长的长度, 而是数列, 所以是3-sum-hard 问题. 必然O(n2), 前几天听说有人破了这个hard bound, 不知道是不是真的. 也没关注. 具体思路就是从前往后扫, 如果没排序, 先排序一下,扫的时候, 让游标i在中间, 前边是j, 后边是k, 所以满足, 0<= j < i < k < Array.length, 然后i从1开始往后扫到Array.length-2, 因为j和k是从i初始化的, 每次i走一步, j往后扫,k往前扫, 所以总体的复杂度是O(n2) 代码: public static ArrayList<Integer> longestArith (int[] items) { ArrayList<Integer> res = new ArrayList<>(); […]
原题: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] = […]