4
8
2015
0

论逗逼的自我修养之TCO2014

做了TCO2013之后感觉TCO的题真的是挺好的..所以索性开个新坑做一下TCO2014(好吧其实真相是在策爷博客里看到了整套的题解)

[4.22]最近也是浪的飞起...(说好的贤者模式呢)不过总算断断续续的做完了...之后应该会补一些今年的省选题?也可能会开始做TCO2012的题吧...不能再这么浪下去了QAQ

现在做了几题

39

【TCO14 Round 1A 250】EllysSortingTrimmer 显然每一次排序之后字典序一定不会上升,所以就从后往前做[tex]len-L[/tex]次操作,剩下的字符串就是答案。

【TCO14 Round 1A 500】EllysScrabble 每一位从小到大贪心的取,然后判断是否存在可能的合法方案也是从左到右贪心的放。

【TCO14 Round 1A 1000】EllysLamps 挺简单的1000分。首先考虑如果知道了每一个开关的状态,怎么求解答案。发现每一位的决策最多只会影响到自己和前后的位置,所以可以状压[tex]f_{i,j}[/tex]表示考虑了前[tex]i[/tex]个开关,第[tex]i[/tex]和第[tex]i+1[/tex]盏灯的开关状态为[tex]j[/tex]时前[tex]i[/tex]盏灯中最少有多少盏是打开的,然后DP一遍就可以得到答案。现在不知道每一个开关的状态,考虑再套一层DP,[tex]g_{i,j}[/tex]表示[tex]f_i[/tex]是否可能为[tex]j[/tex],用一个map存一下跑一遍就好了。

【TCO14 Round 1B 200】SpamChecker 按照题面说的翻译成代码就好了。

【TCO14 Round 1B 600】WolvesAndSheep 爆枚一维的状态,剩下一维贪心,直到不能不放的时候再放围栏。

【TCO14 Round 1B 900】EagleInZoo [tex]dp_{i,j}[/tex]表示有[tex]j[/tex]只老鹰进入以[tex]i[/tex]为根的子树时最后一只停留在这颗子树上的概率,然后转移就枚举最后一只老鹰进入哪一个孩子,有多少只老鹰进入这个孩子,组合数算算就好了。

【TCO14 Round 1C 250】Unique 直接扫一遍。

【TCO14 Round 1C 450】FizzBuzzTurbo 算一下3的倍数,5的倍数,15的倍数减一减输出就好了。

【TCO14 Round 1C 950】RedPaint [tex]dp_{i,j,k}[/tex]表示走了[tex]i[/tex]步,染红区间长度为[tex]j[/tex],现在的位置距离最左边的红色方格[tex]k[/tex]个单位,暴力DP就好了。感觉TCO14年的1系列三场就是在搞笑啊。

【TCO14 Round 2A 250】SixteenBricks 开始YY了一个无脑状压..然后发现可以贪心。因为是最小化相邻两个单位格子高度较小值的和,所以考虑交错放,枚举是左上角放高的还是放低的,算出每一个格子对答案的贡献,贪心就好了。

【TCO14 Round 2A 500】NarrowPassage 我记得以前有人讲过这题?那个时候太naive连题解都看不懂..分两种情况考虑,第一种是中间有一段没有走出过这个小巷,另外一种是一开始所有人都走出小巷,然后一部分人穿过小巷,最后所有人再走回来,因为数据范围很小直接爆枚就行了。

【TCO14 Round 2A 1000】TreePuzzle 开始自己YY了一个和标算差不多的做法可惜越写越乱然后就弃疗了。然后去看了一下题解理了一下重新写了一遍就A了。考虑每一步移动,分两种情况考虑:1.目标节点子树有空位。2.现在的位置的某一个后代至少两个子树有空位且现在位置到那一个后代的路径上都是空位。然后就大暴力,找到合法的点就随便选一个(虽然我也不知道为什么随便选是对的,题解也没说)

【TCO14 Round 2B 350】SwitchingGame 记录下当前的状态,如果某一盏灯是开着关着都可行的话就用问号表示,接着贪心的考虑到达下一个状态,先判断是不是一定要进行开灯或者关灯操作,如果不一定就不做,然后再更新当前的状态,能用问号表示的位置就尽可能的用问号。

【TCO14 Round 2B 500】SumAndProductPuzzle [tex]S[/tex]要满足的条件是[tex]S-1[/tex]不是质数,且存在[tex]a+b=S[/tex]使得对于[tex]ab[/tex]的约数[tex]k[/tex],[tex]k+\frac{ab}{k}-1[/tex]不为质数当且仅当[tex]k=a[/tex]或[tex]k=b[/tex],然后据说当[tex]ab \geq B[/tex]的时候是没有意义的,所以就直接筛就好了。至于为什么没有意义我也不知道

【TCO14 Round 2B 900】AlwaysDefined 最后函数值一定变成是[tex]km+1[/tex],之前的过程是在它上面乘上若干个数,可以发现转移很少,爆搜乘上哪些数即可。

【TCO14 Round 2C 300】SubstringReversal 预处理后缀与前缀反转的LCP以及后缀与后缀的LCP,枚举反转哪一段然后[tex]O(1)[/tex]比大小就好了。

【TCO14 Round 2C 500】CliqueGraph 对于每一个团建两个虚电连有向边,然后每一个点出发分别跑最短路累积答案就好了。

【TCO14 Round 2C 900】InverseRMQ 如果[tex]n[/tex]很小可以直接二分图匹配,而这儿限制很小可以对值离散化,然后用最大流来做,判断是否满流就好了。

【TCO14 Round 3A 300】BrightLamps 鏼爷省选讲课的题,按照下标对[tex]K[/tex]的余数分成[tex]K[/tex]组,通过这个操作我们可以同时改变所有组亮灯数的奇偶性或者在亮灯数奇偶性不变的情况下修改同一组的灯的开关状态。然后排序贪心就好了。

【TCO14 Round 3A 500】RandomFlights 挺好玩的题,先考虑没有初始边的情况下,显然操作结束后起始点和目标点的路径唯一,[tex]dp_S[/tex]表示和起始点联通的点集为[tex]S[/tex]的概率,然后枚举一个不在集合内的点[tex]i[/tex],设点集中所有点到[tex]i[/tex]距离的平均值为[tex]num[/tex],那么这一次操作对答案的贡献就是[tex]\frac{dp_S \times num}{(n-|S|)(|S|+1)}[/tex](因为点集[tex]S \cup \{ j \}[/tex]在接下来的操作中都是等价的)。原来有边之后细节多了很多,但是大致的算法还是一样的。

【TCO14 Round 3A 1000】PlumbersCoins 膜了鏼爷的题解,依然不知道那个结论为什么是对的..把所有硬币按照坐标排序,猜的结论是拿硬币的顺序最多改变两次,即先一直向右,然后再向左,最后再一直向右。然后预处理最短路之后DP求解。

【TCO14 Round 3B 250】IntoTheMatrix 挺有趣的题,每一个朋友都有[tex]turns+1[/tex]种状态(即在哪一轮被传送走),策略就是用所有朋友的状态来给这[tex]n[/tex]袋糖果编号,如果没有一对糖果编号相同,我们就可以把这些糖果区分出来,答案显然就是[tex]n[/tex]在[tex]k+1[/tex]进制下的位数。

【TCO14 Round 3B 500】OnePointNineNine 鏼爷省选讲课的题,显然距离小于[tex]0.99D[/tex]的点都是等价的,把这些点都缩起来之后可以证明得到的图所有点的度数都不多于2,然后DP就好了。

【TCO14 Round 3B 1000】TreeDistance 鏼爷省选讲课的题,那个时候还刷了一波存在感2333把非树边边权设为未知数[tex]x[/tex],树边设为1,跑基尔霍夫矩阵,得到的是一个关于[tex]x[/tex]的[tex]n-1[/tex]次多项式,答案就是这个多项式次数小于等于[tex]K[/tex]的系数之和。在解这个多项式的时候可以给这个未知数代[tex]n[/tex]个具体值进去,最后插值得到多项式。

【2014 TCO Celebrity Match 250】AnEasyProblem 枚举一下转折点二分就好了。

【2014 TCO Celebrity Match 450】ConcatenateNumbers 把串给拼出来然后预处理前缀模模数的值,然后把方程列出来发现可以把左端点和右端点分离,直接用个map扫一遍就好了。

【2014 TCO Celebrity Match 1000】CityRebuild 开始被百度翻译坑了..还以为就是等腰三角形..淦。二分显然,然后转化成2-sat问题,把正方形剖成四个小的等腰三角形,显然要满足的是对角线的异或值为1,直接跑2-sat判断是否可行就好了。判断等腰三角形是否相交略麻烦..写的特别高潮。

【2014 TCO Semifinal1 250】ZooExchangeProgram 把不能取的删掉,最后最多剩下22段,显然每一段都是取或者不取,枚举取的集合判定就好了。

【2014 TCO Semifinal1 450】AutomorphicTree 只有可以表示成阶乘的乘积的数可以构造,然后乱构造..然后各种FST,然后各种打补丁..最后终于爆过去了。

【2014 TCO Semifinal1 1000】CarrotField 显然就是问以每一个整点为圆心,半径为[tex]R[/tex]的圆交矩形的面积和,然后考虑四分之一圆分类讨论一下,预处理前缀弓形的面积和什么的就过了。开始各种爆int真是不能多说..

【2014 TCO Semifinal2 300】PlankTiling 显然每一列最多放一个竖过来的,考虑放到第[tex]i[/tex]列的轮廓,肯定有连续的[tex]H[/tex]行填到第[tex]i[/tex]列,其它行的长度相同且都不大于[tex]i[/tex],令[tex]dp_{i,j}[/tex]表示放到第[tex]i[/tex]列,其它的都在第[tex]j[/tex]列,随便脑补一下转移就好了。

【2014 TCO Semifinal2 500】RoadsReform 显然可以把边双缩起来,然后只要考虑在不同边双中的约束就好了。之后我一直在逗逼考虑状压后树形DP...数据范围这么小直接爆枚判断就好了...

【2014 TCO Semifinal2 850】TwiceTwiceTree 鏼爷省选讲课的题,讲课时推式子的时候逗逼了一下...做这题的时候重新推了一遍,感觉还是不是特别难的(JRY的瞎BB时间)..式子是[tex]\frac{2^nx-x(1+x)^{2n}}{1-2x-x^2}+2^n[/tex],然后直接暴力算算就好了。

【2014 TCO Wildcard 275】AndPicture 感觉Wildcard的题都好难啊..这一场三道题每道题我都是要么不会做要么不会做+FST,感觉进了i wanna的坑之后智商掉的厉害...开始YY了一个通过每一行每一列的1的个数来判断的算法,然后直接FST了。正解应该是先算出行中每一个2的幂次的位置,因为每一位是独立的,所以给这些位任意赋值,这样就可以推出每一行每一列的值,直接判断一下就好了。我真TM傻逼..

【2014 TCO Wildcard 750】CountTables 750的计数题..开始一直在逗逼..不停的逗逼。折腾了三个多小时最后还是X大爷告诉我算法..然而知道了算法之后感觉是道傻逼题..我TM还有救吗。首先求出[tex]n[/tex]行[tex]i[/tex]列,每一行都不同的方案数,这个直接排列算一下就好了。然后考虑容斥,通过枚举等价类个数用第二类斯特林数来搞。我真TM傻逼...

【2014 TCO Wildcard 1100】EnergyGameOnGrid 开始我的做法是把每一个点拆成四个点表示转移过来的方向,然后跑SPFA,结果就是一百多个测试点,5sT了一个。然后卡了很久很久很久的常数无果。最后还是鏼爷告诉我反过来从终止点开始就可以直接BFS了...我真TM傻逼..

【2014 TCO Final 350】LoopyPath 显然1的区域的轮廓肯定是都要走到了,把这些边给描出来,设这些边连成了[tex]k[/tex]个环,我们要把这些环联通起来,所以要付出[tex]2(k-1)[/tex]的额外代价,最后因为要走到没有走到的节点,所以要付出剩余节点数的两倍的额外代价,最后累加起来就好了。[tex]k[/tex]可以通过算八连通联通块个数来得到。

【2014 TCO Final 550】MagicalRocketCar 令[tex]x_i \leq y_i[/tex],可以发现最后使用的顺序是加速度单调不降的,所以我们按照[tex]\frac{x_i}{y_i}[/tex]排序,则剩下的一个模式一定排在第一个模式的后面且顺序恰好相反。令[tex]dp_{i,j}[/tex]表示考虑了排序后后[tex]i[/tex]桶油,可以使用[tex]j[/tex]秒时最远可以走多远,直接DP就好了。

【2014 TCO Final 1100】FrozenStandings 根本不会容斥...根本不会计数题。想了很久最后还是X大爷教我的。把所有人可能的成绩都放在一起排序,如果在同一个人的两个成绩之间没有选任何一个人,那么就会产生重复的方案,所以可以容斥,直接DP就好了。

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 2093

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com