标签归档:STL

51nod 1786 数据流中的算法 – 众数

数据流统计功能上线后,为51nod提升用户体验做出了很大的贡献。但是新问题随之而来,夹克老爷还想知道在一个窗口内,访问次数最多用户(即窗口内的众数)。如果有多个众数,取用户ID最小的一个。(窗口的意思是一个固定长度的区间!)

(因为数据流是实时的、在线的,所以不允许使用离线算法^_^)
Input

Output

Input示例

Output示例

很早之前比赛做的一个题,翻51nod的时候发现挂了出来于是就A了一下。

就是每加入一个数的用map记录次数,set存一个<次数,ID>的pair,然后模拟一下就好了。

 

2015 ACM Amman Collegiate Programming Contest 做题记录


fls说我暑假需要给学弟们找点简单gym做,于是决定锻炼一下自己的代码能力,单挑了一场非常水的gym,然后做的时候各种心累,感觉真是写不完的感觉,主要是卡到了一道全场题,然后找李大爷当小黄鸭才发现了一个傻逼bug,最后也因此没有打成AK目标。不过最后那个题目不给我多点时间我肯定也是想不出来的。。。于是这个post就按照我做题的顺序记录吧。因为题目较短只写做法不写题意了。

A.Who Is The Winner

直接把数据读入,在这个过程中维护答案即可。时间复杂度:\(O(n)\)

 

B. Rock-Paper-Scissors

n的范围很小,考虑暴力枚举。因为出手的情况是三段,所以我们预处理出来每个位置处”剪刀石头布“这三种情况的得分前缀和,然后枚举断点即可。注意断点需要考虑没有某一种操作的情况。时间复杂度:\(O(n^{2})\)

C. Street Lamps

简单贪心,先把所有已知灯能影响到的格子全部标上’*’,那么接下来就贪心即可,出现一个’.’如果它后面紧跟着是’.’方格,那么就选择染后面的那个,因为这样会更优。记录染的次数即可。时间复杂度:\(O(n)\)

D. Alternating Strings

这个题和L一样,但是数据范围不一样。本题中n较小,可以暴力dp。\(dp[i]\)表示前i个数被分成的最小段数。然后根据限制条件转移即可。时间复杂度:\(O(n^{2})\)。

E. Epic Professor

限制加分后不能超过100,所以我们找到一个加分前最大分数即可确定加分,然后扫一遍即可。时间复杂度:\(O(n)\)

F. Travelling Salesman

寻找一棵生成树,使得其最大边最小就是最小瓶颈生成树,也就是最小生成树。时间复杂度可以认为是:\(O(mlogm+n)\)

K. Runtime Error

把数组排序后,把数字和位置组成一个pair插入到一个set里面,然后扫的过程中即可判断是否存在这个数。时间复杂度:\(O(nlogn)\)

J. Candy

确定顺序后贪心选择即可,当同等级的糖果小于当前等级学生时候舍去,否则分配即可。时间复杂度:\(O(nlogn)\)

G. Heavy Coins

状压一下暴力枚举删钱情况进行判断。时间复杂度:\(O(2^{n}*n)\)

H. Bridges

我们需要先求出所有的桥边,显然当一个连通的无向图我们把边双连通分量全部缩成点后,得到了一棵树,这棵树的边都是桥。那么加的那条边一定是直径的两个端点才最优。所以bfs几下就可以了。时间复杂度:\(O(n+m)\)

I. Bahosain and Digits

从大到小枚举操作长度\(K\)和最终结果,然后从左到右进行check即可。时间复杂度:\(O(k*n^{2})\)

L. Alternating Strings II

对于每个字符\(i\)都可以预处理出来一个位置\(len[i]\)表示从这个位置往后均为01交替串直到位置\(i\)。而且转移返程一直需要的都是前面的最大的那个dp值,所以维护一个单调递减的队列即可,状态数\(O(n)\),转移优化到\(O(1)\)。时间复杂度:\(O(n)\)。

 

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)做题记录


终于把这场补完了。。。最后一个题不知道为什么,我的写法貌似比别人的要慢一点。。。比赛的时候卡C卡了很久,后来旁边大爷说b数组没用只用找最小值就可以了,然后写了个mapT了。。后来发现原来是[]运算符的锅。。。E只剩十分钟的时候才会,写完交上去wa5,才发现是个重要的地方没有判断。。。实在遗憾。。。

A. Unimodal Array

三个while循环走一遍,如果最后位置不是最后就是错误的。

B. Keyboard Layouts

用map实现就好了。

C. Jury Marks

其实在之前写过了。一开始想的是n*k^2的暴力,但是其实我们可以通过枚举b序列最小值出现的位置,从而确定出起始值,然后带着算一遍check就好了,这样就是k^2的复杂度了。

D. Office Keys

题意:n个人要去一个地方p,给出每个人的坐标a[i],去这个地方需要一把钥匙,总共有k把钥匙,给出每把钥匙的坐标b[i],问n个人最后都到达了这个地方需要多少经过多少时间,每个人走一个单位距离需要一个单位时间。

可以贪心也可以dp。dp就是前i个人从前j把钥匙选择出i把的最大时间进行n^2的dp。

贪心就是发现最优的取钥匙方案一定是一段连续的区间(因为假如只有n把钥匙,一定是一一对应的是最优)。所以我们可以枚举区间起始点,然后O(n)扫一遍人序列求出时间,最后取个min就好了。

复杂度应该都是O(n^2)的。

E. Cards Sorting

题意:给出n张扑克牌,每次拿第一张牌如果他是当前序列中最小的,就把它扔掉,否则就放到最后,问最终需要操作多少次。N<=100000

用set存下来一个pair<卡牌数字,位置>,然后每次从set的第一个值确定出来当前需要选的数,但是会出现相同的数字不止一张的情况,所以我们还需要找到第一张在当前位置之后的这个数字的卡牌。然后计算的过程可以用树状数组加速。

F. Bamboo Partition

题意:给出n(n<=100)个竹子,以及一个限制长度k(k<=1e11),告诉你每个竹子nice的高度a[i]。竹子一开始的高度都是0,每天长1个高度,一个人每隔d天去check这些竹子,并且对于长度高于nice的竹子砍掉至a[i],并且这个竹子不会再生长。问最大的间隔d使得切下来的部分竹子之和不超过k。a[i]<=1e9。

一开始以为是有单调性的,但是后来发现傻逼了。

然后推式子:

随着d的增大这个函数实际上是一个分段的函数,在和式的值不变的情况下随着d增大,但当和式值变化的时候出现间断点。

那个和式根据余数之和那道题目的思想,最多有O(sqrt(a[i]))级别个。所以处理出来O(nsqrt(a[i]))个间断点,然后一个个带进去check好了。但是有个问题最后合法的一段可能只有最小值合法,最大值不合法,但最小值不一定是最大的。所以存一下和式的值,然后通过上式右边计算d就好了。

但是我写的常数好大的感觉= =