Menu Sidebar
Menu

Codeforces

Codeforces Round #319 (Div. 2) B. Modulo Sum

原题: http://codeforces.com/contest/577/problem/B 题目大意: 给n个数, 问能不能找到其中的subsequence的合可以整除k. 分析: 额..这题开始做的时候考虑不周, 老是过不了, 后来加了个mod k 就过了. 看了答案后, 感觉思路差不多, 首先,当n>k时, 因为鸽巢原理, n个数,每个贡献1,肯定能找到合整除k的. 而当n<=k时, 我们可以通过记录数组当前数字与前一个数组合的模来判断是不是是否可以整除, 即: 如果合的模是0, 那么找到了答案返回YES.

Codeforces Round #319 (Div. 2) A. Multiplication Table

原题: http://codeforces.com/contest/577/problem/A 题目大意: 给两个数字,n和k, 找出等于k的个数在n*n的table中, table中每一位是i*j, where i and j are row and column 分析: 这个暴不了, 所以考的是观察. 观察题中给的example: 我们可以发现, 在一个n=6的表中, k=12 出现在6 4 3 2. 这些数字都是12的除数, 可是少了几个啊, 12本身也是除数,1 也是除数, 而且在n=10,k=5中, 我们发现答案是2(1和5). 那么上边的1和12 为什么不算? 因为 12/1 = 12 , 12不在表中. 所以我们得到另一个条件, 除完的余数要小于等于n.

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) C. Bear and Poker

原题: http://codeforces.com/contest/574/problem/C 题目大意: 给一个n个数的数组, 问这几个数能不能通过double或者triple得到一个相同的数. 分析: 几个数能通过double或者triple得到一个相同的数, 必然这几个数由2 或者(和) 3的倍数组成, 所以这几个数可以分解成2^a*3^b* rest, 所以我们先要把每个数的2的倍数和3的倍数都消去, 然后检查rest部分是不是相同, 即可判断是不是可以通过double和triple组成相同的数.

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) B. Bear and Three Musketeers

原题: http://codeforces.com/contest/574/problem/B 题目大意: 给一个无向图, 问你是不是有三个点互联, 并且算出所有三点互联情况下, 这三点的degree的合. 分析: 开始的时候, 看到4000的顶点数, 先想的就是直接暴, 后来发现第7个test case 过不了,  中间加了个简单的剪枝, 立刻就过了. 先把图建起来, 然后用个array存一下每个点的度, 最后用结果减去6(三个点互相连接的度), 就是这三点和其他点度的合.

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections

原题: http://codeforces.com/contest/574/problem/A 题目大意: 给一个n的数的数组, 问如何让第一个数拿最少数组中别的数字的数,使得第一个数变成这个数组最大的数. 分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是O(n2), 看来能有lgn的做法. 后来想想, 假设第一个数是数组中最大的数, 那么就可以不用拿别的数, 如果第一个数不是数组中最大的数, 那么它最多拿的数, 应该是数组中最大的数. 假设数组: 5 1 11 2 8. 第一个数5不是数组中最大的数字, 那么我们可以假设, 最坏情况下, 我们最多拿11(11为数组中最大的数字), 使得5变成数组中最大的数字, 当然这个情况是最坏情况. 其次, 上面例子中的5 1 11 2 8的结果是4, 那么我们可以证明, 任何大于4的数字都是可以的. 因此, 我们可以通过二分搜索的办法, 搜索这个数字. 复杂度是o(nlgn), n是每次检查搜索结果的正确性, lg是二分.

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) B. Order Book

原题: http://codeforces.com/contest/572/problem/B 题目大意: 对n个股票操作进行排序, 最后生成一个Order Book. 操作有两种, buy 和 sell, 后边是股票标号和价钱. 要求对相同操作的相同股票进行合并操作. 然后输出排序后前s个sell和buy的股票. 这里的排序要求是, 对于sell, 先对编号递增排序, 然后取前s (没有s个取所有). 然后再对编号递减排序. 对于buy直接递减排序即可. 分析: 用Java的TreeMap一下就出来了. 因为TreeMap本身就是有序的, 用Collections.reverseOrder()可以改变顺序. 然后取前s个的时候, 可以把set变成stream, 然后limit一下就可以

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) A. Arrays

原题: http://codeforces.com/contest/572/problem/A 题目大意: 给两个数组, 问是否能在第一个数组找到k个数,在第二个数组找到m个数, 使得所有在第一个数组找到的数小于第二个数组找到的数. 数组已排序. 分析: 因为数组已经排序, 所以如果在第一个数组前k个数字小于第二个数组后m个数字, 那么打印YES.如果不是, 打印NO

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

原题: http://codeforces.com/contest/570/problem/A 题目大意: 竞选问题, n个候选人, m个城市. 选取规则是,第一轮同城选最大,一样选最小index. 第二轮是城市间选最大, 一样选最小index. 分析: 没什么分析的…走一遍矩阵先行找最大, 然后记录下, 再列找最大…

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:

最后看了一下答案, 发现是用两个set保存当前数字为等比中项的前后序列, 然后记录一下相同项的个数. 第二次扫描的时候, 如果当前数字能整除公比, 那么找到j,i,k的个数,相乘就是答案. 这里注意要用long存. 难怪我test老挂 答案code:

 

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

原题:http://codeforces.com/contest/567/problem/B 题目大意: 一个计数器, +号代表一个人进入图书馆, -号代表一个人出去图书馆. 给一个log, 问这个log中能知道的这个图书馆最小的可能容量是多少, log是片段, 在program运行前可能图书馆已经有人, 在运行后也可能人还没出去? 分析: 因为log不能完全记录图书馆的信息, 有可能第一条就是-号,所以我们需要用个数组记录一下人来往的信息. 但是当发现有人出去但是没有进入的信息, 我们就知道在当前时候, 图书馆的容量应该比记录的容量多1. 换句话说, 当发现一个人走出来但是没有被记录进去, 我们只能认为这个人一直在图书馆里.

Newer Posts
Older Posts

书脊

倾城与倾国, 佳人难再得