WC2015总结&解题报告(伪)

这次三道题:k小割,混淆与破解,未来程序。

先看“k小割”:啥啥啥这都是啥……
然后看“混淆与破解”:范浩强居然真敢把讲课内容出出来……但是问题①GL算法的后半部分完全没听懂②即使听懂了算法显然也做不出来,不过没准前40分(m=1)的可做
“未来程序”:去年是给程序和输出凑输入,今年直接给程序(源代码都给了)和输入求输出?
不管了第一题10分暴力走你┏ (゜ω゜)=☞,方法是2^m枚举边集然后O(n+m)判断是否是割集
然后玩提答。
program1:这难道是传说中的快速乘?然后愉快地码了一个出来,用计算器验算正确
program2:让它算了几个小数据,发现是……Fibonacci数列的平方和?目测可以用某种矩阵乘法搞,然后开始构造矩阵,但构造了一小会发现不对劲啊!标程就是线性的啊!那用矩阵乘法直接加速标程的线性变换不就行了吗!(就是直接把a,b,c作为行向量的三个元素,不用管什么Fibonacci了)
program3:0~4次方和……0~3我都还记得公式,都很快算了出来。但4怎么办呢……想了一下突然发现可以直接用矩阵乘法搞啊!行向量前五个元素存i^0~i^4,后五个元素存0~4次方和(其实只需要4次方和,但反正可以一下搞出来为何不用呢),然后矩阵乘法一揽子搞定。所以刚才为什么要弄半天公式……
program4:count1是C(K,2),其中K是矩阵中1的个数。count2是:求每个格到最近0的曼哈顿距离。那直接建一个超级源,到所有0连长度为零的边,一遍SPFA搞定。
program5:这是求所有全1子矩阵个数。用单调栈目测能搞,不过好像要写很久的样子,总之40分已到手,看看前两题吧……
然后准备先想一小会T1,然后就去写T2的40分,然后继续搞提答。
T1的40分是:有n个位置(小n!不是代表整张图中点数的大N!),每个位置有两个档:b-a,b(分别代表割权值较大的边和割掉两条边)。一个方案是:在n个位置中任意选出若干个(可以不选),选出的要么取第一档要么取第二档。求权值前K小的方案(赛后听说这道题是K短路,不过俞鼎力论文中的做法非常复杂,另外我当时也根本没想到K短路)。
这种“k小”的题基本都是建一个堆,每次取出堆顶元素并塞进常数个元素(就是堆顶的后继)。
当时我错误地认为每个位置只有一挡,所以是这么想的:在每个方案的基础上,都可以再选。假如该方案选择的最后一个位置是x,那么在其基础上可以再选x+1~n,这O(n)个衍生方案都是它的儿子。那如果用左儿子右兄弟表示法,就可以成功变成常数个儿子了。而一个方案(堆中一个元素)其实只需要O(1)的空间存储,因为我们只关心该方案选择的“最后一个位置”。
然后对拍了一下发现有问题(每个位置有两档),最后还是改对了。
做法是:堆中元素是一个class,内含三个量:方案权值s,方案选择的“最后一个位置”p,该位置选择的档位lv(0~1)。
一个方案最多有三个后继:
①把p从第0档变成第1档,要求lv=0且p>=1(p=0代表什么都没选)
②在此基础上选中p+1的第0档,要求p
③不选p,换成p+1的第0档,要求p>=1且p
这样就能不重不漏地逐步扩展出k个最小方案了。
这样T1共50分到手,开始对拍并且写T2.
T2的前40分看上去比较好做。方法是:既然最终结果一定是”b+a*xi1^xi2^xi3^xi4……”这样一个式子(其中a是系数),那我逐个检测x1~xn是否在这个式子中即可。假设我们想要检测x1是否在其中,方法是:循环100次,每次给x2~xn都随机赋值,然后分别让x1=0和x1=1进行计算。假如x1确实“有用”,那么x1=0和x1=1算出的两个值有很大概率不相等。如果100次测试中大多数的结果都是“不相等”,我们就认为x1确实有用。
这样得出所有有用的变量。然后把它们全赋0,其余变量随机100次,看结果是0多还是1多。再把一个赋1,其余随机100次,看结果0多还是1多。这样就得出了要求你输出的那个结果表。
但总感觉这个算法太naive了……测了两组很小的p=0数据(复杂的我也构造不出来),能正常运行。
ps:这里100是脸滚键盘得出的一个常数,可以改。
然后T1和T2正式弃疗。继续玩提答。
program5:方法基于单调栈:先对每个格处理出来“向上能延伸几格”,然后逐行扫描。扫描过程是维护一个单调栈(栈中一个元素代表从某位置开始的‘高度限制’是什么,USACO中貌似有几道这种题),“以某格为右下角的全1子矩阵个数”就是当前单调栈所代表的一个阶梯状图形下的面积,在对单调栈进行改动时维护之。
program6:啥啥啥这都是啥……弃疗了
program7:一直以为是拉丁方,考试结束后才发现是数独……不过不影响,给的程序不是没剪枝吗?把它那个check改成“同一字母只能出现一次”,剪个枝,跑出前三个点。后面的死活跑不出来,就让它在那跑着,结果直到考试结束还是没跑出来。
program8:第一个大概也许似乎是个排列数?写个程序算了一下,不过最后发现谜之算错了。
program9:哈哈哈惊现CLJ头像。第一届NOI是1984年(论背笔试题的重要性),最常用六位密码是123456,那个人叫chenlijie,其余都不会了,弃疗……
program10:啥啥啥这都是啥……GUIDE打开程序都卡的不行。弃疗了
然后就没剩下多长时间了,余下时间一直在花式搞数独和试图看出8的规律,不过没搞出来。
最终第一题50,第二题40,第三题的1~5都得10分,7和9各得3分,共56.
总成绩50+40+56=146.
第一题的正解大致是把所有割集分成带e和不带e两类,那么只需要求出这两类中的次优解,再求次优解中的次优……比较复杂,不过中间那些n=m=100的点可以用A*骗分。
第二题的正解就是那个Goldreich-Levin算法……
第三题正解:
program6:暴力找循环节……这居然也行……
program7:贪心直接过……有人说可以把矩阵倒过来搜,也能直接过
program8:好像就是各种奇怪的组合数摞起来……
program9:出题人在前面某个题中给出了一个词典,可以按着词典暴搜
program10:把函数调用建成拓扑图

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注