Menu Sidebar
Menu

Codeforces

Codeforces Round #316 (Div. 2) B. Simple Game

原题: http://codeforces.com/contest/570/problem/B 题目大意: 给一个范围[1,n], 一个人取范围中的数字m, 问你如何取一个数字a, 可以让|c-a| < |c-m|的概率更高, where c 是一个[1,n]中的随机数 分析: 可以把范围看成一组数, 其中的m把这组数字分成了2组, [1,m)和(m,n]. 于是这个题就转化成问你, 找一个数字a,让a覆盖的数字比m覆盖的数字更大. 这个数字肯定在m+1或者m-1, 这时候, 需要比一下m和n/2, 看看m是在n的中间的左边还是右边, 如果是右边, 那么说明m左边的数字比右边的多, 所以我们选m-1, 相反同理. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); if (n == 1) { out.print(1); return; } if (m > n / […]

Codeforces Round #316 (Div. 2) C. Replacement

原题: http://codeforces.com/contest/570/problem/C 题目大意: 给一个string s, s有小写字母和’.’组成. 做m个query替换操作, 对于每个操作都要进行固定的处理, 这个处理是把s中的连续两个’.’. 替换成1个, 一次替换消除一对’.’ 问对每个query, 需要几次替换. 分析: 开始的时候以为能爆过….结果暴到test case7 过不去了…后来只能分情况讨论. 一上来先算下原始的s需要几次替换, 假设原始string s 需要n次替换.  这时, 对于m个query, 有两种情况可以改变n的值. 替换的字符是’.’ 但是当前字符不是, 有以下两种情况: 如果当前字符的前边是’.’, n++ 如果当前字符的后边是’.’, n++ 替换的字符是字母, 但是当前字符是’.’, 有以下两种情况: 如果当前字符的前边是’.’, n– 如果当前字符的后边是’.’, n– 最后别忘了把字符替换一下. public void solve(int testNumber, InputReader in, OutputWriter out) { int len = in.readInt(); int m = in.readInt(); […]

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

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

Codeforces Round #Pi (Div. 2) C. Geometric Progression

原题: http://codeforces.com/contest/567/problem/C 题目大意: 给一个n大小数组, 问其中的子序列(非连续)能组成多少个已p为公比的等比序列, 且长度为3. 分析: 这题卡了好久, 我用找等差数列的方法改的. 后来总是过不了test. 可是怎么看我的是O(nlgn)的复杂度, 所以过不了大的test case 肯定是有O(n)的. 于是开始想啊想啊….最后想到了是用等比中项的性质. 首先上一个过不了的code: public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int p = in.readInt(); IntPair[] nums = new IntPair[n]; for (int i = 0; i < nums.length; i++) { nums[i] = new IntPair(in.readInt(),i); } Arrays.sort(nums); int count […]

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++) { […]

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

Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes

原题:http://codeforces.com/contest/551/problem/C 题目大意: n堆箱子, m个学生要搬走箱子, 每个学生走过在箱子中间移动需要一秒, 移除一个箱子需要一秒, 问最少多少秒搬完. 分析: 这题有两个很tricky的地方. 一个是在搬走的时候, 不需要移动学生到别的地方. 所以如果学生在箱子上面, 在n秒内, 就能搬走n个箱子. 第二个是学生之间是同步进行搬箱子的. 解题的时候, 用的是穷举, 后来过不了TLE了. 看了答案才明白是二分搜索问题. 这里二分搜索用的是以下的原理: 如果在t秒内能完成任务, 那么肯定在大于t秒的时间内也能完成. 这就说明我们可以忽略那些大于t秒的情况.如何找到t呢. 因为题中告诉我们: at least one pile is non empty. 所以移动到这个non-empty pile需要1秒, 移动box 需要1秒, 所以我们的low bound是2. 那high bound是什么? 我们假设只有一个学生, 移动到n个地方需要n秒, 移除a1,a2…an个箱子需要a1+a2….+an秒, 所以high bound是(数组长度+box总数). 所以我们的range是在[2,Total(box+index)] 在每次搜索中,我们对m个学生依次分配任务, 从最后一个non-empty的pile开始移动尽可能多的箱子中. 因为我们已经知道时间是固定的, 所以问题转换成: 在已知时间内, 每个学生最多能拿多少箱子, 这里用贪婪的思想, 假设每个学生拿最多就可以. public void […]

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

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

Newer Posts
Older Posts

书脊

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

February 2025
M T W T F S S
 12
3456789
10111213141516
17181920212223
2425262728  
© 2025 书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.