5
17
2015
0

论逗逼的自我修养之TCO2015

TCO2015的round1已经比完了..这个坑先开着以后跟着比赛进度慢慢填好了。

[upd 7.31]TCO 2C Clear!最近代码(智)能力(商)掉的厉害..被出题事故两连重击之后有点想灭退保了..不过还是来稍微填一下坑吧..

现在做了几题

24

【TCO15 Round 1A 250】Similars 枚举区间里的每一个数记下这个数的出现状态,之后枚举答案的两个数中的相同部分判断就好了。

【TCO15 Round 1A 500】Autogame 倍增预处理出[tex]K[/tex]轮后会在同一个位置的每一个集合,满足条件的局面只能从每一个集合中取出至多一个数,把集合大小加一乘起来就好了。

【TCO15 Round 1A 1000】Revmatching 霍尔定理,一个存在完备匹配的二分图任意大小为[tex]k[/tex]的集合至少与[tex]k[/tex]个节点相邻。就可以枚举哪一个子集没有满足这个条件,贪心的删边更新答案。

【TCO15 Round 1B 250】TheNicePair 枚举被哪一个数整除,然后枚举区间左端点,从小到大枚举右端点判断是否合法就好了。

【TCO15 Round 1B 500】TheTips 算出每一个点可以被那些点到达,这个点不会选当且仅当可以到达它的点都没有被选,把贡献加起来就是答案了。

【TCO15 Round 1B 1000】TheTreeAndMan 树上随便DP一下就是[tex]O(n^2)[/tex]的了。

【TCO15 Round 1C 250】DevuAndPlantingTrees 每一列最多放一个,可以发现同一列的两个是等价的,直接扫一遍贪过去就行了。

【TCO15 Round 1C 450】UnrelatedPaths 答案就是叶子个数。

【TCO15 Round 1C 1000】DevuAndBeautifulSubstrings [tex]dp_{i,j}[/tex]表示前[tex]i[/tex]个字符有[tex]j[/tex]个美丽子串的方案数,枚举下一段有多长就行了。

【TCO15 Round 2A 300】ModModMod 令[tex]A_i[/tex]为[tex]1[/tex]到[tex]R[/tex]中当前值为[tex]i[/tex]的个数,然后直接模拟就好了,时间复杂度是[tex]O(R)[/tex]的。

【TCO15 Round 2A 600】FoxMeeting 首先二分答案,然后枚举第一只狐狸的终止位置,剩下的狐狸存在一个贪心策略:能往根跑就往根跑。我们把所有这个贪心策略执行完之后的所有点和根的路径标记起来得到是个树的结构,如果当前状态是合法的,终止状态一定是这棵虚树状物体,于是跑一下匹配就好了。
 
【TCO15 Round 2A 950】TrianglePainting 听说有个定理..T^T姿势水平太低了什么都不知道。把两个凸包按照题目中的方式合并得到的多边形和把两个凸包的向量排序后首尾相接得到的大多边形是相同的。所以可以把所有三角形的边先排序好,那么一条向量[tex](x,y)[/tex]的贡献的两倍就是[tex]x\times toty-y\times totx[/tex],其中[tex]totx[/tex]和[tex]toty[/tex]是在这条边之前取的向量的和,然后就可以直接算了。
 
【TCO15 Round 2B 250】Bitwisdom 直接DP出有[tex]i[/tex]段开头是0或者1的概率,然后累加一下答案就好了。
 
【TCO15 Round 2B 500】Balance 联通块之间的包含关系是不会变的,把树建出来就变成了同构的判断,直接哈希就好了。
 
【TCO15 Round 2B 1000】MinimumCuts 令[tex]dp_{i,j}[/tex]为最多使用[tex]j[/tex]的代价使得Bob无法到达祖先为[tex]i[/tex]的叶子节点的最小代价。然后一通乱转移...写的时候也是挺晕的..WA了之后几乎又对着毛爷的代码改了一遍才过..
 
【TCO15 Round 2C 250】YetAnotherCardGame 先排序,然后要选出一个最长的可能取到的序列。子序列要满足的条件就是它可以由两人在[tex]n[/tex]轮之内轮流取完,似乎只要贪心就好了..写的时候脑抽了码了一发DP..
 
【TCO15 Round 2C 500】LongSeat 如果已经知道了坐到凳子上的人的相对顺序以及站着的人的集合,判断这个状态能不能达到可以直接使用差分约束系统..于是就可以用一个set存下当前所有合法的状态,然后枚举下一个来的人的状态判断可以不可行即可..时间复杂度似乎是[tex]n![/tex]乘上[tex]n[/tex]的若干次..跑出来还是不虚的..
 
【TCO15 Round 2C 1000】PopcountRobot 开始一直当POI的某道分形题做..直接爆搜剪枝大力出奇迹..然而并过不了样例..打表可以发现如果走[tex]x[/tex]步得到的点是[tex](a,b)[/tex],那么走[tex]2x[/tex]步得到的点是[tex](a-b,a+b)[/tex]。证明也很方便,假设走[tex]x[/tex]后每一种余数的出现次数分别是[tex]k1,k2,k3,k4[/tex],那么走[tex]2x[/tex]步相当于把[tex]x[/tex]内的所有数都加上一位0或1,所以每一种余数出现次数分别是[tex]k1+k4,k2+k1,k3+k2,k4+k3[/tex],把坐标用这四个变量表示出来就可以发现这个关系了..于是就可以直接枚举到达那个位置模4的余数然后递归下去判断,终止状态就是坐标为0且模4余0..感觉考场上以我的智商根本想不到啊..
 
【TCO15 Round 2D 250】BalancedSubstrings 枚举左端点然后可以发现支点随着右端点的右移单调不降,所以直接扫一遍就好了。
 
【TCO15 Round 2D 500】BallsInBoxes 如果[tex]n > 2k[/tex],那么可以直接把[tex]n[/tex]的最前面每[tex]k[/tex]个询问一次,直到[tex]n \leq 2k[/tex],这时询问次数的最大值一定出现在剩下的那部分中。当[tex]n=k[/tex]的时候显然不需要询问,所以我们可以每一次把[tex]n[/tex]比[tex]k[/tex]多的部分等分,即询问中点,这样前半部分的询问次数一定不多于后半部分,直接递归求解就好了。
 
【TCO15 Round 2D 1000】AToughGame 只需要DP前最后那段单调不降的部分的贡献就行了,于是就可以从前往后DP在每一个位置有停留的概率,开始我正着DP怎么都不对,倒过来就对了..感觉非常玄幻我再感受一下..
 
Category: 论逗逼的自我修养系列 | Tags: | Read Count: 1476

登录 *


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