implementation

Codeforces Round #316 (Div. 2) A. Elections

原题: http://codeforces.com/contest/570/problem/A 题目大意: 竞选问题, n个候选人, m个城市. 选取规则是,第一轮同城选最大,一样选最小index. 第二轮是城市间选最大, 一样选最小index. 分析: 没什么分析的…走一遍矩阵先行找最大, 然后记录下, 再列找最大… public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); int[] count = new int[n]; for (int i = 0; i < m; i++) { int[] nums = IOUtils.readIntArray(in,n); int maxIndex = selection(nums); count[maxIndex]++; } out.print(selection(count)+1); […]

Date August 13, 2015
Category Codeforces
Comments No Comments

Codeforces Round #315 (Div. 2) A. Music

原题: http://codeforces.com/contest/569/problem/A 题目大意: 下载一个T秒音乐, 当S秒的时候开始播放, 如果播放到没有下载的地方, 就重新播放, 下载速度是q/q-1, 问播放几次能下载完毕. 分析: 呵呵, 居然不会做, 我看了半天没明白为什么是q-1没有用到. 比赛的时候还有个解释, 说下载速度是q/q-1, 即 q是现实时间, q-1就是下载track时间. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); int s = in.readInt(); int q = in.readInt(); int n = 0; while ( s < t) { s *= q; n++; } out.print(n); }

Date August 10, 2015
Category Codeforces
Comments No Comments

[LintCode] strStr

/** * Returns a index to the first occurrence of target in source, * or -1 if target is not part of source. * @param source string to be scanned. * @param target string containing the sequence of characters to match. */ public int strStr(String source, String target) { //write your code here if(target == […]

Date August 9, 2015
Category LintCode
Comments No Comments

[LintCode] Compare Strings

public boolean compareStrings(String A, String B) { // write your code here int[] count_A = new int[26]; for(int i = 0; i < A.length(); i++) count_A[A.charAt(i)-‘A’]++; int[] count_B = new int[26]; for(int i = 0; i < B.length(); i++) count_B[B.charAt(i)-‘A’]++; for(int i = 0 ; i < 26; i++) { if(count_A[i]<count_B[i]) return false; } return […]

Date August 9, 2015
Category LintCode
Comments No Comments

[LintCode] Two Strings Are Anagrams

public boolean anagram(String s, String t) { // write your code here s = s.toLowerCase(); t = t.toLowerCase(); int[] count_s = new int[26]; for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == ‘ ‘) continue; count_s[s.charAt(i)-‘a’]++; } int[] count_t = new int[26]; for(int i = 0; i < t.length(); i++){ if(t.charAt(i) == ‘ ‘) […]

Date August 9, 2015
Category LintCode
Comments No Comments

Codeforces Round #Pi (Div. 2) B. Berland National Library

原题:http://codeforces.com/contest/567/problem/B 题目大意: 一个计数器, +号代表一个人进入图书馆, -号代表一个人出去图书馆. 给一个log, 问这个log中能知道的这个图书馆最小的可能容量是多少, log是片段, 在program运行前可能图书馆已经有人, 在运行后也可能人还没出去? 分析: 因为log不能完全记录图书馆的信息, 有可能第一条就是-号,所以我们需要用个数组记录一下人来往的信息. 但是当发现有人出去但是没有进入的信息, 我们就知道在当前时候, 图书馆的容量应该比记录的容量多1. 换句话说, 当发现一个人走出来但是没有被记录进去, 我们只能认为这个人一直在图书馆里. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] t = new boolean[1000010]; int cap = 0; int cur = 0; for (int i = 0; i < n; i++) { […]

Date August 5, 2015
Category Codeforces
Comments No Comments

Codeforces Round #Pi (Div. 2) A. Lineland Mail

原题: http://codeforces.com/contest/567/problem/A 题目大意: 给一个数组, n个数, 有正有负, 已经排序好了, 让你输出每个数和数组中其他数的最大差和最小差. 分析: 已经排好, 所以遍历一遍,最小就是比较当前数字的左边或右边的差的绝对值, 最大就是比较当前数字和数组的头和数组的尾的差的绝对值, 就可以了, 注意第一个数和最后一个数没有左边或者右边. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = IOUtils.readIntArray(in, n); out.printLine(Math.abs(ary[1] – ary[0]) + ” ” + Math.abs(ary[0] – ary[ary.length – 1])); for (int i = 1; i < ary.length-1; i++) { out.printLine(Math.min(Math.abs(ary[i] – […]

Date August 5, 2015
Category Codeforces
Comments No Comments

Codeforces Round #307 (Div. 2) B. ZgukistringZ

原题: http://codeforces.com/contest/551/problem/B 题目大意: 给3个string,a,b,c. 问用a的字母通过交换,最多可以得到多少个b或者c? 分析: 本来感觉是dp的题, 后来想想不用那么复杂, 先用三个26个字符数组, 存下三个字符串的字频, 然后用三个变量,num, nums_a, nums_b存下对应a,b,c的个数. 然后暴力破解就可以, 因为题目是求最多b或者c. 我们假设从0个b开始,一步步递增. 看看最多能有多少个. 这里需要注意的是, b的取值应该是从[0,count_b[j]*i > count_a[j]](0个b, 到i个b的第j个字母超过了i个a的第j个字母). 最后输出的时候, 先输出b,再是c, 最后把a剩下的字符输出就行了 public void solve(int testNumber, InputReader in, OutputWriter out) { String a = in.readString(); String b = in.readString(); String c = in.readString(); int[] ca = new int[26]; int nums = 0; int […]

Date July 27, 2015
Category Codeforces
Comments No Comments

Codeforces Round #307 (Div. 2) A. GukiZ and Contest

原题: http://codeforces.com/contest/551/problem/A 题目大意: 给n个人, 每个人都有rank, rank最高的人是1, 同一个rank的人得分一样, 不同rank的人,得分是前边rank人数的合, 问返回的数组是什么. 分析: 我看题目是sorting, 我没sort唉. 一共rank才2000, 用个count数组记录一下, 然后从后往前(从大rank到小rank)扫数组,每次扫都取合传给下一个rank. 然后再走一般数组打印出来对应的rank就行了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] count = new int[2005]; int[] nums = new int[n]; for (int i = 0; i < n; i++) { int t = in.readInt(); count[t]++; nums[i] = […]

Date July 26, 2015
Category Codeforces
Comments No Comments

Codeforces Round #308 (Div. 2) B. Vanya and Books

原题:http://codeforces.com/contest/552/problem/B 题目大意: 给个数字n, 求这n个数字的digits个数的合分析: 比如1234, digit是1的区间是[1,9], 一共9个, 2的区间是[10,99]一共90*1个digit, 3的区间是[100,999]一共900*2个digit, n的区间是[10^n,10^(n+1)-1]一共10^(n+1) – 10^(n)*(n-1)个digit. 那么1234 落在区间4, [1000,9999]中. 可以用1234-1000+1得到4个digit的数字的个数, 然后乘以4,得到digit为4的digit数, 然后与前边的区间的合相加, 就是答案第一次写: public void solve(int testNumber, InputReader in, OutputWriter out) { long n = in.readLong(); long t = n; long res = 0; int digits = 1; while (n / 10 != 0) { res += (9 […]

Date July 25, 2015
Category Codeforces
Comments No Comments