题目现在好像还看不到,据说过段时间会挂出来
A. 简单来说就是求第n个catalan数 MOD m的值,n可能到10^6,m是10^9
B. 搜索题,据说是很裸的dancing link,不过我不懂
C. 处理两个list的运算,比较简单
D. 一堆窗口,一堆点击,每次点击就把点到的窗口拿到最上层,输出每次点击后位于最上层的是谁
E. dp,背包问题,不太难
F. 树型DP,在树上找一条长为L的链使得其它所有点到这个链的最近距离之和最小
G. 很有意思的题,后来我们讨论似乎可以用解方程组做
H. AC自动机+状态压缩BFS
I. 比较简单
J. 区间覆盖问题,贪心
一上来zdx跟我说A可能能做,我一看Catalan么,结果发现O(n)的递推式忘掉了-_-,我们一点关于组合数学的资料都没带,然后我就开始手推。小刘说I是水题,就上去写了。推了很久推出来了,突然才意识到里面有个除法,没办法直接取模的,当时就囧了,怪不得一直没人过呢。小刘的I题WA了,zdx说C题能写,她就上去写了,小刘自己找错,我开始读剩下的题,想找找有没有我所谓的“条件反射题”,结果越读越囧:A题这种我只知道一种理论上把m拆成互质的,然后分别算出逆元来,最后再用中国剩余定理合起来的方法,但是数论题我从来就不会做的,扔了;B题明显搜索,明显不敢写,扔了;D题一看数据规模就吓死人,几万个窗口,几十万次点击,扔了;E题想了一会儿,有点想法,但复杂度有点悬,扔了;F题感觉是状态转移超级恶心的树型DP,扔了;G题想出一个线性规划,扔了;H题没想到做法,扔了……这时候就傻了,怎么没有能做的题呢?本想跟跟风,扫遍全场只有CI两题,无奈了。
zdx的C也WA了,小刘的I又WA了一次后,我发现了她程序里一个小bug,12点应该显示成0点的,改了以后就过了。然后她跟我说了J题题意,说感觉是贪心,我一开始没想法,以为是dp,后来仔细想想确实可以贪心,正好这时候lx他们队有J球出来了,我就直接把一个O(n^2)的程序拍了上去(n是10000…当然加了一堆break在里面,后来我们分析加上一个剪枝后应该可能是线性的,但不知道我当时是怎么写的了),总之是y了……这时候zdx的C又WA了一次,她说找不出错了,让我重写一下。我仔细一想也不太复杂,重写也不花太长时间,于是重写一遍y了。这时候E过了很多,再加上有J题乱暴过了的信心,对这题的复杂度也就放心了。用了一个O(n*m)的预处理,然后二分答案再二分查找每个物品的花费,中间写卡了,大概花了40多分钟y了。然后又无所事事了……
当时的情况是,还有一个半小时,我们左边的队很诡异地过了当时好像全场唯一的D,右前方的复旦队过了个F,大概有3个H,还有1个A。因为看到有学校一个多小时就过了H,猜测这题可能结论性比较强或者是模版题,就决定先想想试试,如果不行只好冒个挂死的危险硬啃F。还好突然灵光一闪发现就是个自动机的变形,把自动机建起来以后用个BFS,用状态压缩记录一下状态就可以了。复杂度比较变态,我开了若干个几千万大小的数组……心惊胆颤地写完了,又调试了半天才过Sample,比较虚,又让小刘和zdx出了一些数据,果然又发现了bug,然后还好还是1y了……到那时为止我的所有提交都是Yes,发现和MM组队果然有好RP啊……
还有半个多小时,F题不敢开了,考虑到我们左边不太强的队过了D,心想或许能水过去,就开始乱水。结果水出来无数TLE,一直到比赛结束。结束以后问了问也过了这题的WHU,他们的做法是先离线读入所有点击的位置,然后再处理一下怎么怎么的,这题还没有仔细想。
后来回来的火车上小胖说了一下G的想法,我感觉挺强大的:其实我们可以把这个网络看成一个电路,那个S(u,v)其实就是两点间的电势差,这样当源汇点之间的电压一定时,电流也是一定的,故这个方程组的解实际上是唯一的,只不过可能同时放大或缩小一个比例而已。这样就不需要线性规划,只要解方程组出来,再把解缩放到恰好满足流量限制就可以了。如果当时能想到这个的话,半个多小时写个高斯消元还是有可能的,这样就6题了,嘿嘿,yy一下……
这次的题目出得很好,等题目挂出来以后建议大家都去看看。最后点评的时候,蔡老师说有点偏难了,实际上我感觉是因为大家基本都是临时凑的队伍,少有以磨合好的阵容参赛的,所以成绩偏低,我想如果这是一场regional的话,冠军肯定远不止6题。
另外,学到一种扑克新玩法。还有,拱猪拱了数晚上,我只输过两把,呼呼哈哈
Recent Comments