2015 ACM/ICPC EC-Final

2016年12月8日1,2421

A. Boxes and Balls

题意:有不超过n个球放在若干袋子里,每次操作拿一个新的袋子,从现有的所有袋子中各拿一个求放进新的袋子里,去掉空袋子

问最多可以放多少个球,使得每次操作之后,所有袋子球数构成情况不变

 

容易发现,恒定不变的状态为1,12,123…

B.Business Cycle

题意:给定一个n个结点的环,编号0~n-1,每个点有一定的权值,从点0出发沿编号走,到达某一个节点则把目前总权值加上这个节点的权值,如果结果小于0则变成0。现在给你最多可以走的步数P和最大需要到达的权值大小G,问你需要的最小的初始权值为多少,能在P步内能够产生的最大权值大于等于G

 

初始权值越大,经过同样步数之后得到的权值越大,考虑二分,但是步数太大无法模拟

如果走第一圈的时候在某一点上x变成0,等价于初始权值为0,接着从x开始,每走一圈的变化值是相同的

否则每走一圈的变化值都相同

D.Change

题意:现有一台售货机,要破开一张人民币,目标是一张更小面值的人民币

每次可以买任意价值的东西,返还币值类型随机,问至少花多少钱一定能获得想要的面值

 

结论:若B为0.01,0.1,1,10且A不等于2B,答案0.02,否则答案0.01

考虑B=0.01,那么花0.01,则一定会找回一张0.02,再把0.02破成0.01即可

其余类似

F.Hungry Game of Ants

题意:有n只蚂蚁排列在数轴的1到n,第i只蚂蚁重量为i

每只蚂蚁运动速度为1,两种蚂蚁相遇时,体重大的蚂蚁吃掉小的(体重相同时左侧蚂蚁获胜),体重增量为所食蚂蚁的体重,运动到边界的蚂蚁折返

蚂蚁的初始朝向有2^n种可能,问其中有多少种使得第K只蚂蚁最终存活

 

第K只蚂蚁一定初始方向朝左,否则一定会被吃

考虑K的左侧,设离K最近的向左的蚂蚁为x,\([x+1,K-1]\)的所有蚂蚁依次被K吃掉,1到x最终会合成一只体重为\((1+x)*x/2\)的向右的蚂蚁

那么要满足条件\((1+2+…+x)\leq [(x+1) + (x+2) + … + K]\)

考虑K的右侧,设右侧的所有向左的蚂蚁为\(x_1,x_2…x_m\),要符合在K吃完其左侧的所有蚂蚁后

\([K+1,x_1]\)的所有蚂蚁会合成一只后被K吃掉,接着\([x_1+1,x_2]\)的所有蚂蚁被K吃掉,以此类推

故右侧用一个简单的dp,\(F(i)\)表示前i只蚂蚁都被K吃掉的方案数,用前缀和优化转移

J.Dome and Steles

题意:有n个同宽的长方体,可以调换长方体的顺序,使得能用一个尽量小的半球包含所有的长方体

问最小半径

 

二分答案,计算每个长方体可以放置的横坐标范围,排序贪心

L.Multiplication Table

题意:给一张无限大的表格

1 2 3 4 …

2 4 6 8 …

给定一个R*C的表格(可能有些非确定元素),问其是否可能是原表的一部分

 

拿一个确定的元素x,考虑它的所有约数d,x元素可能在原表的第d行第x/d列

根据其它元素与它的相对位置,check一下选定的d是否合适

由于每个元素只符合于一个d,所以复杂度是O(TRC)

M.November 11th

题意:有一个R*S的电影院,B个损坏的座椅

两个人不会并排坐在一起,问至多能坐下多少人?至少坐多少人以后不能再坐下更多的人?

 

连续n张座椅,至多可以坐(n+1)/2人,至少(n+2)/3人

每一行是独立的,依次处理即可