大学生活混起来很快,不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆,因此今年我主动去报了名(上次是被人给拖去的)。今年有点装怪,题目数量不变,但时间缩短为4个小时。原计划是从8:00做到12:00,结果可能是因为我们所在的7号机房迟迟没有开门,时间临时改成了8:15到12:15。总的来说,今年的题目比去年要糟糕得多,但也不乏一些精彩的题目。
和去年一样,第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格,你在最左下角的位置(即(0,0)点),你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次,且不允许左转(题目背景让这个条件顺理成章:街道靠右行,左转不方便),问合法的路线共有多少种。题目难点就是你不一定要走最近的路,完全允许你绕上一大圈;这破坏了有序性,很难构造出递推公式或动态规划模型。稍微画一下图,我们发现了一些显然但很有启发性的规律:每一次右转后,你左手边方向的所有区域都不能再走了,这很可能产生出规模更小的子问题来。另外,所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走,这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁,我猜不少队伍都卡在这儿了吧。
后来我完全打翻前面的全部思路,猛然想到了一个具有决定意义的想法:街道的选取唯一地决定了整个路线。例如,假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的,其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此,我们可以用排列组合直接计算出答案来。向上走的路是五选二,向右走的路是七选三,向下走的路是四选三,向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是,计算所有的路线数只需要从小到大枚举拐弯的次数,每一次计算都是常数的,总复杂度是O(n)的;整个算法的瓶颈反倒是O(n^2)的组合数预处理,不过这个复杂度完全可以承受。
另一道题也很不错。有n只猫猫排成一排,初始时每只猫猫都没有花生。定义三种操作:给第i只猫猫一颗花生,令第i只猫猫吃掉它所有的花生,交换猫猫i和猫猫j的花生。给出长度不超过k的操作序列,输出循环执行m次操作序列后的结果。数据规模n≤100,k≤100,m≤1 000 000 000。看到这道题我们立马会想到矩阵乘法。如果能为每种操作构造出一个矩阵,m再大二分下来也能承受。我们可以先把序列中的k个操作乘起来,再利用二分自乘m次就可以了。
但这一思路碰到了一些困难:交换和清零操作都好办,但加一操作怎么弄?我们可以借用这里的第一题的思路,在猫猫向量的最后面加一个额外的“1”,从而解决了加一操作的难题。
这道题最后TLE了,而我们没有充足的时间去优化它,最终残念离去。算法的瓶颈就是把k个操作乘起来的过程,它的复杂度是O(k·n^3),也就是100的四次方,最坏情况下铁定会超时。不知道用O(n^2.81)的矩阵乘法是否可以AC。网上还有人提到,由于矩阵很稀疏,做乘法时写成if(a[i][k]&&b[k][j])c[i][j]+=a[i][k]*b[k][j]会大幅度提高效率。下来跟外校参赛选手512MM交流了一下,她告诉我一个操作序列的最终结果可以用O(k·n)的复杂度直接构造出来,这样就可以保证AC。另外,同队的leimiaos还提出了一个完全不同的算法:把交换操作看作置换群,然后把单个操作序列的交换操作分解成若干个循环。每个循环都将在100次序列重复以内产生周期性状态,而不同循环之间又互不干扰,问题即迎刃而解。
今年的题目确实没有去年的精彩。D题和G题都是很纯粹的数学题。D题是说有n个木块排成一行(n≤10^9),你可以给每个木块涂红蓝绿黄中的一种颜色,要求最后红木块和绿木块都有偶数个,问染色方案共多少种。leimiaos用满满一页草稿纸推出来公式4^(n-1) + 2^(n-1),大家也可以试试看。G题更干脆,题目描述压缩了就一句话,给定圆锥的表面积,求最大体积。作为根正苗红的理科生,同队的徐谷子MM和leimiaos都赶在我想出圆锥表面积怎样算并准备操键盘写二分之前飞快地算出了公式解。这两道题分别有108支队和160支队做出来,而走路题和猫猫题的AC数分别只有9和11。
其余的题目绝大多数都是比较复杂的模拟,几乎没人去做。这次比赛第一名AC了6道题,第二、三、四名AC了4道题,接下来有十几支队伍AC了3道题,然后就是不计其数的只搞出两道数学题的队伍。不管怎样,这次比赛再一次勾起了我做算法题的欲望。最近打算没事时稍微练练手,到时候大家在百度之星和有道难题上见!
那两个比赛我也报名啦
沙发
啊……是不是沙发?
啊……其实我一个小时前页面就打开了……
那三个矩阵乘法不是O(n)就能做好了吗。。。
一个是交换相应的两行,一个是把一行每个数都设成0,一个是把一行每个数都加1
干吗老老实实算啊。。。
第一页。。。
第一题好像GDOI08的某题啊
看了你的文章再一次勾起了我做算法题的欲望,CS大三算法盲飘过…
猫猫那道题,置换的话由于只有可能产生两个循环和三个循环,因此但从循环角度考虑的话六次置换为一个周期。因此,经过六次变换(a,b,c)->(k1*a+l1,k2*b+l2,k3*c+l3);ki取0或1,li就是常数。。。
小声说我们其实是7题@_@
另外,欢迎你来给POJ月赛出题啊,平时一题200块,校内赛一题500块~~
我还是喜欢数学题和算法题,不喜欢那种特殊情况多的题(比如candy之类的)
喵了= =。。。。。。
我昨天的访问量增了一倍……简单写了下做过的题的报告了:)
话说刚参加玩自己学校的程序设计大赛,题还比较简单~ 做出3/10道题~
这道题。。一直残念中。。大牛们帮忙看下这道题~~
http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1564
btw,我也去参加那两个竞赛去~~
话说pku的大牛们都是喜欢出数学题的啊~~
我觉得14楼的那题可以这样做:
2^200 = 1.60693804 × 10^60
所以说我们可以先把前两百位的表现形式写出来。
然后对输入的数变成二进制,再套用前两百位的表示形式即可。
火星一下,,这个BLOG是怎么回事-_-http://www.matrix67.com/yanyang/
>到时候大家在百度之星和有道难题上见!
哈哈,转载一下,这个题目估计会考到一柴兄弟,,
楼主是用啥软件画的图????
to 17:: 那是情侣博客 请搜索 本人正式脱光 那篇文章。。。
请问Matrix67是用啥画的图……
楼层: 地壳 | 2009-05-18 21:26 | fengzi 说:
第一题好像GDOI08的某题啊
….本来就是…..
猫的那题,我认为可以这样:把k个矩阵分成三个矩阵ABC的乘法,首先,把所有的清零操作,认为是一开始把某行清零,然后这个操作之前的所有对这行的加法操作disable,把所有的清零操作放到矩阵A里去,然后,对于所有的加法操作,那么它一定是有意义的了,然后在放到矩阵B里去,最后把所有的置换放到C里去,再做一个ABC的乘法,就求出了循环节。
这样的复杂度:对于每个操作,都要向前跟踪前面的所有操作,所以复杂度是O(k^2),最后ABC的合并是O(n^3)的,这样应该是可以接受的
Orz…
楼层: 23楼 | 2009-05-24 16:34 | ghk 说:
楼层: 地壳 | 2009-05-18 21:26 | fengzi 说:
第一题好像GDOI08的某题啊
….本来就是…..
是类似GDKOI2008的题~~
加一…难道没人用过OpenGL吗??
令猫向量是(k1,k2,…,kn,1)T,加一操作用(n+1)阶矩阵
IA
BC
左乘这个向量.其中I是单位矩阵,A是向量(0,0,…,0,1,0,..,0)T,其中第i只小猫要加一的话,第i行为1,B是一行0向量,C是1.
楼层: 14楼 | 2009-05-19 17:54 | flyink 说:
话说刚参加玩自己学校的程序设计大赛,题还比较简单~ 做出3/10道题~
这道题。。一直残念中。。大牛们帮忙看下这道题~~
http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1564
================================================
打表存掉2^0~2^60的最终表达方法,一个高精减+高精比较,完事。
@14楼
那道题存下2^0到2^60的最终表达式与值,从中找<=余值的最大的一个,记录,减掉,不断重复,直到余值为零。
路过
我有道难题挂了 欺负我不会cha
哈哈!我们最后排名刚好比你们高两位~
D题不就是VIJOS克隆龙这道题么
残念啊
我的结论是M67你要多写写程序了
貌似是这样
猫那个没次循环后没只猫最后的食物只有两种情况:1.原来是谁的增加了多少;2.是多少(被清0过)。这个应该O(k)就能解决
之后最终结果也许动态规划比矩阵要快… 猜测
仔细想想不是动态规划问题。因为有n只猫,食物经过的路径n次循环内必然经过同一只猫,或者被清空。于是就是O(n^2)的最坏情况… 如果我没想错的话。
34楼,我得出的结论跟你不一样。。。我得出的结论是M67要系统地学习数学了。。。给定表面积/周长算体积/总面积是有一定的方法的,公式是必须的,二分法太多余了。。。
M67能发点一看就懂的吗。好深奥哦
话说D题只要一条多重求和式就好了,满满一页的草稿纸是什么情况……