22 | July | 2015

Codeforces Round #313 (Div. 2) D. Equivalent Strings

原题: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 || […]

Date July 22, 2015
Category Codeforces
Comments No Comments

Codeforces Round #313 (Div. 2) B. Gerald is into Art

原题: 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 […]

Date July 22, 2015
Category Codeforces
Comments No Comments

Codeforces Round #313 (Div. 2) A. Currency System in Geraldion

原题: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”); } }

Date July 22, 2015
Category Codeforces
Comments No Comments

[Google] Longest Arithmetic Sequence 求最长等差数列

这题是我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<>(); […]

Codeforces Round #310 (Div. 2) B. Case of Fake Numbers

原题: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] = […]

Date July 22, 2015
Category Codeforces
Comments No Comments

Codeforces Round #311 (Div. 2) C. Arthur and Table

原题:http://codeforces.com/contest/557/problem/C 题目大意: 一个桌子, n条腿, 每个腿的长度不同, 定义一个平衡状态为: 最长腿的个数 >= 总数 / 2. 每个腿去除要花费的能量都不一样, 问最少多少能达到平衡. 分析: 这题开始做的时候, 有点糊涂, 以为是贪婪+暴力, 然后第八个test case 各种过不去.仔细一看有10万个腿.我x,那是桌子么.. 然后想dp, 又想反了, 最开始想的是,自顶向下的, 后来发现remove的次数太多, 每次remove都重复了, 才知道应该是从下往上容易做. 具体的思路是: Sort一下所有的腿长, 从最短的开始, 建立Pre数组, 记录如果选择当前的腿, 所需要砍除的所有比它高的腿的能量花费的合,即: Sum( cur_max<=i<=Pre.length){腿[i]}.然后另一个窍门是, 一共能量的范围只有200多, 建一个count数组, 记录所有的energy cost, 然后从小往大找能删除的腿. 找到就加到sum. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int cost […]

Date July 22, 2015
Category Codeforces
Comments No Comments

Archive: July 22, 2015