文档库

最新最全的文档下载
当前位置:文档库 > acm_趣题集

acm_趣题集

//missing_趣题、

1.歌唱王国(Modified)
字母表中有若干个字母,从空串出发每次等概率随机选择一个字母添加在当前串的末尾。
另给若干停止串,若当前串中出现了这些停止串则停止扩展。求串扩展的期望长度~!

2.水管局长
SC省MY市有着庞大的地下水管网络,嘟嘟是MY市的水管局长(就是管水管的啦),嘟嘟作
为水管局长的工作就是:每天供水公司可能要将一定量的水从x处送往y处,嘟嘟需要为供
水公司找到一条从A至B的水管的路径,接着通过信息化的控制中心通知路径上的水管进入
准备送水状态,等到路径上每一条水管都准备好了,供水公司就可以开始送水了。嘟嘟一
次只能处理一项送水任务,等到当前的送水任务完成了,才能处理下一项。在处理每项送
水任务之前,路径上的水管都要进行一系列的准备操作,如清洗、消毒等等。嘟嘟在控制
中心一声令下,这些水管的准备操作同时开始,但由于各条管道的长度、内径不同,进行
准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径,路径上
的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择
路径的系统,以满足供水公司的要求。另外,由于MY市的水管年代久远,一些水管会不时
出现故障导致不能使用,你的程序必须考虑到这一点。
-----------------------------------------------
最小生成森林LCA + 反向加边优化。

3.Frequent values
给一个有序序列,你的任务是对于每个询问Q(i, j),输出[i, j]中出现频率最高的次数。
-1 -1 1 1 1 1 3 10 10 10
-----------------------------------------------
转换为:2 4 1 3,辅助sum数组二分查找:2 6 7 10。RMQ

4.与众不同
A是某公司的CEO,每个月都会有员工把公司的盈利数据送给A,A是个与众不同的怪人,A不
注重盈利还是亏本,而是喜欢研究“完美序列”:连续的互不相同的序列。A想知道区间[L,R]
之间最长的完美序列。
-----------------------------------------------
st[i]:=max(st[i-1],last[a[i]]+1)
len[i]:=i-st[i]+1
由st的非递减性对于[L, R]可二分找到一个最大M使得st[M]<=L,
则Q(i, j) = max(M-L+1, RMQ(M+1, R));

5.程序复杂度(模拟)
给出一段程序,计算它的时间复杂度。这段程序只有三种语句:
–OP :执行一条时间耗费为x 的指令。这里的x 为不超过100 的正整数。
–LOOP :与END 配套,中间的语句循环x 次,其中x 可以为规模n,也可以是不超过100 的正整数。
–END:与LOOP 配套,循环终止。
注意:OP 语句的参数不能为变量n,而LOOP 语句的参数可以为变量n,但不允许有其他名字的变量。
这样

,整个程序的时间复杂度应为n 的多项式。你的任务就是计算并显示出这个多项式。
Sample In
OP 1
LOOP n
LOOP 10
LOOP n OP 7 END
OP 1
END
END
Sample Out
70n^2+10n+1

6.序列和的前n小元素
给你两个长度为n的数组A,B,从A,B中任选一个元素,可得到n*n个和,回答询问Q(i),表示第i小和的值(1<=i<=n)。
-----------------------------------------------
n路归并、heap

7.轮廓线
a).每一个建筑物用一个三元组(L, H, R), 表示左边界, 高度和右边界。
轮廓线如此给出:x1-H1-x2-H2-x3-H3-x4-0(x1b).求总面积。
-----------------------------------------------
离散化,每个区间找最大值。与求矩形面积相似,
a)快排后线性heap求解区间最大值。
b)线段树……

8.赛车
有n辆赛车从各不相同的地方以各种速度(0描述(位置xi, 速度vi)。输出超车总数以及按时间顺序的前m个超车事件(ti, ai, bi->ti时间ai超过bi)。
------------------------------------------------
注意时间是浮点型,用heap模拟过程保存每辆车的前车与后车及超越时间。超越时间的比较用整数乘法……

9.可怜的奶牛
农夫John有n(n≤100000)头奶牛,可是由于它们产的奶太少,农夫对它们很不满意,决定每天把产奶最少的
一头做成牛肉干吃掉。但还是有一点舍不得,John打算如果不止有一头奶牛产奶最少,当天就大发慈悲,放过
所有的牛。由于John的奶牛产奶是周期性的,John在一开始就能可以了解所有牛的最终命运,不过他的数学很
差,所以请你帮帮忙,算算最后有多少头奶牛可以幸免于难。每头奶牛的产奶周期Ti可能不同,但不会超过10。
在每个周期中,奶牛每天产奶量不超过200。(输入一个T,表示John想知道T天后的奶牛数(T<=10^5)。待测试)
-------------------------------------------------
按周期分组,然后对每个周期中的每天维护一个heap,模拟天数。

10.黑匣子
我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻,黑匣子为空且i等于0。
这个黑匣子执行一序列的命令。有两类命令:
ADD(x):把元素x放入黑匣子;
GET +/-:(+:i增1的同时,-:i减1的同时)输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的
元素以非降序排序后位于第i位的元素。(如果i超出整数序列的个数范围,你应该输出NoElement。)
-------------------------------------------------
两个heap,一个大根堆维护输出的第i小值,一个小根堆,维护下一个将添加到大根堆里的元素值。

11.代码等式
由元素0和1

组成的非空的序列称为一个二进制代码。一个代码等式就是形如x1x2..xl=y1y2..yr,这里xi和yj是二进制
的数字(0或1)或者是一个变量(如英语中的小写字母)。每一个变量都是一个有固定长度的二进制代码,它可以在
代码等式中取代变量的位置。我们称这个长度为变量的长度。对于每一个给出的等式,计算一共有多少组解。
例: a,b,c,d,e的长度分别是4,2,4,4,2, 则1bad1 = acbe有16组解
--------------------------------------------------
并查集求解。先解析等式,把字母代表的二进制位用一个整数表示,即a,b,c,d,e的二进制位可从2标号到17。然后并
查集求解变量集合个数n。答案为2^n。

12.如下定义:朋友的朋友是朋友,敌人的敌人是敌人~!给你若干关系,判断最多有多少关系是正确的,如果一个关系与
前面的关系矛盾,我们认为它是错误的,就不要。
--------------------------------------------------有问题,值得思考。
想到了,感觉是个好东西……还是并查集。对每个人有两个集合:朋友集合及敌人集合。先确认一个事实:在(a,b,c)关
系中,如果a,b为朋友而a,c为敌人则b,c的关系只能是陌生人。所以对于每个输入(a,b)应该先判断没有一个c使得a,c为朋
友,b,c为敌人,或者相反。为了快速的进行上面的判断,我的策略是将每个人的朋友集合代表元和敌人代表元hash成一
个整数,由上面的关系知,如果F(a)+E(b)或F(b)+E(a)可以在hash表中找到就说明(a, b)应该是陌生人,不能有任何关系。
然后对于每次合并都需要修改hash表。我是先初始化a的敌人和朋友都是a,则hash表中有n个值F(i)+E(i) = i+i。每次合
并必然是删除一个值和添加一个值,所以可以在内存不增加的情况下保存不可能的值。hash查找近似O(1)。

13.合并队列
初始时n个数1~n各在单独的一列中, 需要执行两个操作
–Move(i, j): 把i所在列接到j所在列的尾部
–Check(i, j): 询问i和j是否在同一列, 如果是, 输出二者之间的元素个数
---------------------------------------------------
并查集....

14.数字序列
给定一个整数序列 a1 , a2 , … , an,求一个不下降序列 b1≤b2≤…≤bn,使得数列 {ai} 和 {bi} 的各项之差的绝对值之和
|a1 - b1| + |a2 - b2| + … + |an - bn| 最小。(数据规模:1≤n≤106, 0≤ai≤2*10^9 )
----------------------------------------------------
假设数列 a1,a2, … ,ak 的最优解为 b1,b2, … ,bk。合并 {bi} 中相同的项,得到 m 个区间和数列 s1,s2, … ,sm
显然,si 为数列 a 中,下标在第 i 个区间内的各项的中位数。若ak+1>sm,直接令sm+1=ak+1,得到前k+1项的最优解;
否则,将ak+1并入第m个区间,并更新sm不断 检查最后两个区间的解 sm-1

和 sm,若sm-1≥sm,合并最后两个区间,并令新区间的
解为该区间内的中位数。 左偏堆实现。

http://www.wendangku.net/doc/52829968b4daa58da0114aec.htmlaco Jan09 Safe Travel
格雷姆林最近在农场里泛滥,这些丑陋的东西会阻止牛从农庄(牛棚1)走到其他的牛棚(第i头牛的目的是牛棚i),每个格雷姆林i都
只认识牛i并且知道牛i一般走到牛棚i的最短路径(时间最少的路径)。所以每个格雷姆林i都会在牛i到牛棚i的最短路径的最后一条
路上等牛i。当然牛不愿意遇到格雷姆林,所以准备找一条稍微不同的路径从牛棚1走到牛棚i。所以,请你为每一头牛i找出避免格
雷姆林的最短路径的长度。农场中有M条双向道路,N个编号1..N的牛棚。第i条路连接牛棚ai、bi,且需要ti时间通过(两点间最多存
在一条路)。牛i到牛棚i的最短路唯一且存在。N<=100,000;M<=200,000
图论, 难题。SPT + 左偏树 + 从下至上。


16.块状链表
有一列整数,共n个。每次可以对这些整数操作,有两种操作:
1 第i个到第j个整数分别加上数p
2 询问这些数中比t小的数的个数。