Menu Sidebar
Menu

Codeforces

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 || […]

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 […]

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

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

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 […]

Codeforces Round #311 (Div. 2) B. Pasha and Tea

原题:http://codeforces.com/contest/557/problem/B 题目大意: 一个大小为w的茶壶, 给n个男孩儿,n个女孩儿倒茶. 一共有2n个杯子, 每个杯子的容量都不一样. 所有女孩儿喝x量的茶, 所有男孩儿需要喝2x量的茶. 问怎么倒能倒最多的茶. 分析: 一看以为是Greedy的题, 后来看了下tag, 发现是sorting, 能sort的就只有茶杯了, 于是把茶杯按容量从小到大排序. 一共有2n个茶杯. cup[0]是妹纸中拿到的最小的茶杯, 因为所有妹纸都喝一样多的茶,  所以最小茶杯的茶杯bound住妹纸们喝的总量, 同理, cup[n]是汉子中拿到的最小的茶杯, 它bound住所有汉子喝的茶. 所以妹纸们喝的总量是cup[0]*n, 汉子们喝的总量是cup[n]*n. 那么先给汉子倒茶还是先给妹纸倒茶? 这个不一定的, 要看cup[0]和cup[n]的大小, 如果cup[0]*2 > cups[n] 那么就要给汉子先倒茶, 反过来就要先给妹纸倒茶. 最后注意一下倒的总量不能超过w. 如果超过了 那么就是w了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); long w = in.readLong(); long[] cups = […]

Codeforces Round #310 (Div. 2) A. Case of the Zeros and Ones

原题:http://codeforces.com/contest/556/problem/A 题目大意:给一个字符串,如果出现一个0和一个1就同时消除, 问最少剩下几个. 分析: – – 0和1的个数差几个就剩下几个啊.. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int res = 0; String s = in.readLine(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ‘0’) res ++; if (s.charAt(i) == ‘1’) res –; } out.print(Math.abs(res)); }

Codeforces Round #311 (Div. 2) A. Ilya and Diplomas

原题:http://codeforces.com/contest/557/problem/A 题目大意:给三个[min,max]格式的区间,A,B,C,分配n个东西, 问怎么分配在满足min的前提先, 按照满足A,B,C的先后顺序,最大分配. 分析:n个东西, 因为要满足B,C的min, 所以先拿出B的min和C的min, 剩下的就是n – min_B – min_C, 然后取min(max_A, n – min_B – min_C) 就是A的数量, 同理类推做B. 很水的题. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int min_1 = in.readInt(); int max_1 = in.readInt(); int min_2 = in.readInt(); int max_2 = in.readInt(); int min_3 = in.readInt(); int […]

Codeforces Round #312 (Div. 2) C. Amr and Chemistry

原题:http://codeforces.com/problemset/problem/558/C 题目大意: 给一个数组, 可以对每个数进行两个操作, *2 或者 /2. 每次操作算一步, 问一共多少步能让数组所有数都相同. 分析: 下面的code是答案, 我写的太复杂了. 一看答案那么短, 真是跪了. 答案的思路是BFS, 然后也没有什么技巧. 就是暴啊. 而且是全局暴.. 我自己的code还左移右移的写了一大堆. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] count = new int[100010];//记录从i点能走到其他点的总数 int[] visit = new int[100010];//防止环 int[] steps = new int[100010];//记录从i点走了多少步到其他点 int res = Integer.MAX_VALUE; for (int i = […]

Codeforces Round #312 (Div. 2) B. Amr and The Large Array

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

Newer Posts
Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

May 2024
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  
© 2024 书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.