Topcoder乱做

考虑到我的智商常年处于没救状态，再不刷刷tc就药丸了...

如果可以的话争取每天刷一场？感觉并不能坚持几天...

1.12 update:TCO好难T_T还是做做SRM吧...

1.20 update:终于滚完期末了...今天冷静一下，明天开始接着干SRM。

2.2 update:终于从绵阳回来了...考虑到还有一大堆寒假作业没写更新速度min。

2.5 update:50题啦！撒花庆祝！

2.27 update:Arena登不上去怎么办啊T_T

3.1 update:今天登了七八次终于上去了...

3.29 update:div2普及组题不会捉怎么办啊T_T

4.3 update:细节题各种不想写怎么办啊T_T

4.7 update:SRM爆零了爽。

完成数：76

 

[TCO2013round1A easy] 枚举最小值直接算。

[TCO2013round1A medium] 容易发现最优方案一定经过至少一个边界，枚举后判定即可，记得加小优化，细节挺多的。一开始又wa又t，在tc上调试真是爽飞了...

[TCO2013round1A hard] 似乎在梦中bzoj见过的样子...TJOI循环格...费用流随便跑...

[TCO2013round1B easy] sort一下就行了。

[TCO2013round1B medium] 想了一会突然发现范围只有15...真是感人...爆搜行，贪心列。

[TCO2013round1B hard] 这题还比较有趣。由于可以任意反转偶数长度的前缀，我们把每两个字符看成一个无序集合，再把所有这些集合看成一个大的集合，直接比较就行了。

[TCO2013round1C easy] 枚举中间点。

[TCO2013round1C medium] 二分+贪心。

[TCO2013round1C hard] 不算难但挺麻烦的题目...由于期望线性性只需要算每个格子被多少个格子覆盖。注意到可以把棋盘划分成5*5的矩形，每一块是等价的，暴力就行了。

[TCO2013semifinal1 easy] (这场好难...一题都不会捉...)看了题解发现结论其实挺显然的。只有当[tex]R\le C[/tex]或[tex]R=C+d,d|C[/tex]时符合条件。

[TCO2013semifinal1 medium] 把式子化简一下，[tex]n\le 9[/tex]直接[tex]O(n!)[/tex]枚举每个点拓扑序比它小的最后一个节点是哪个，然后直接算就行了。似乎有更好的状压dp做法不过感觉会很麻烦。

[TCO2013semifinal1 hard] 这题真心挺神的，虽然结论也不难猜...容易发现每一个白色节点是独立的(似乎并不容易证...)，大胆猜想每个白色节点的SG值是[tex]2^{d-1}[/tex]，其中[tex]d[/tex]是子树中的最大深度。证明挺有趣的。

[TCO2013semifinal2 easy] 容斥显然，然后要求满足若干个条件的方案数，可以对[tex]b_i[/tex]再来一次容斥。

[TCO2013semifinal2 medium] 容易发现最优方案一定是跑到某个位置停下来加能量最后再跑到终点。因此时间只要转移[tex]O(nm)[/tex]次就行了。

[TCO2013semifinal2 hard] 最后还是忍不住看了题解，然后发现挺简单的...把没卯用的点去掉，答案乘2。然后就是对一个DAG球点割集的数量。平面图转对偶图后dp。写起来意外的麻烦呢>_<...

[SRM550 easy] 模拟一遍球得边界，再模拟一遍check答案。

[SRM550 medium] 似乎在黑书上看过的分形...懒得找规律直接抄结论了...

[SRM550 hard]　一开始以为操作是双向的怎么也不会做。后来发现是单向的就可以很容易把代价限制转变为步数限制，然后就是一个经典的矩乘了。

[SRM551 easy] 不错的普及组好题。

[SRM551 medium]　不错的提高组好题。不过由于我太sb，一开始还是fst了T_T

[SRM551 hard] (今天突然听yyl说这题他们去HN集训时听到的...)这个题还比较有趣。可以容斥+基尔霍夫矩阵算[tex]k[/tex]个特殊点的生成树数量。然而我非常sb看到范围40并没有想到meet-in-the-middle，于是只好膜题解了T_T

[SRM552 easy] (这题比500难啊...)一开始又看错题了...注意到确定顶端的球就可以推出整个三角形了，然后二分搞一下。

[SRM552 medium] 真·sb题。放在TC上勉强算个码农题。

[SRM552 hard] 爆搜可以过...爆搜可以过...爆搜可以过...复杂度玄学，不过最大点800ms可以跑出来...

[SRM553 easy] sb题，把未知数带进去模拟即可。

[SRM553 medium] 一看就知道是讨论题，可惜还是没想出来T_T...分四个角每种颜色的数量进行dp，脑补一下图就知道怎么转移了。

[SRM553 hard]　真·神题。vfk博客上有详细题解，强烈怀疑UR2那道sxbk的B题就是来源于这儿。大致就是差分约束系统，负环等价于长度为[tex]n+1[/tex]的一个自环小于0。把不等式的斜率带进去用bellmanford搞。

[SRM554 easy] 分brick高度是否相等两种情况分别列一个式子。

[SRM554 medium] 挺有趣的贪心。最优解一定是所有数的和减去最小数，所以排列方案一定是一段单调减再一段单调增，贪心取前面一段就好了。

[SRM554 hard] 无聊的码农矩乘。

[SRM555 easy] 非常sb的dp。

[SRM555 medium] 显然只跟哪些行列翻转了奇数次有关，枚举，组合数乘一乘。不用管操作序列顺序实在是好评。

[SRM555 hard] 挺麻烦的容斥...预处理每个开始位置能够正确覆盖哪些位置，容斥一个序列可以由哪些开始位置得到，讨论一下就可以了。

[SRM679 easy] sb树形dp。

[SRM679 medium] 枚举凸包上的一个点，预处理每个三角形内有多少个红点和蓝点，dp。

[SRM679 hard] dlh跟我讲是sb题可惜我还是想不出来T_T事实上由于只需要算卷积的和所以预处理每个背包每个位置与它卷积所产生的贡献和就行了。时间复杂度[tex]O(n^3)[/tex]。

[SRM556 easy] 直接球最大异或和。似乎是可以证的？

[SRM556 medium] 把操作倒过来变成数位dp。

[SRM556 hard] CQOI原题(似乎说反了)。正反做两次网络流。然而我并不会证为何old bridge正反各建容量为2的边是对的。

[SRM557 easy] sb细节题。

[SRM557 medium] (我就吐槽下题目背景怎么突然变成了马猴烧酒...)球最长反链。感觉大家都会捉river。

[SRM557 hard] 由于我不熟悉线性代数那一套理论，只好球个线性基找规律...

[SRM558 easy] 枚举[tex]L[/tex]，直接dp就好了。

[SRM558 medium] 一开始看错数据范围了以为是直接大暴力。枚举A,P,Q三个点，剩下三个点可以二分算出范围，加起来就好了。

[SRM558 hard]　超神的最小割。我语死早还是看官方题解吧。

[SRM559 easy] 分类讨论题。

[SRM559 medium] 枚举根dp，记忆化可以做到[tex]O(n)[/tex]。

[SRM559 hard] (大坑待填)奇怪的几何实在是搞不动了...

[SRM560 easy] 一层一层叠上去贪心就行。

[SRM560 medium] 一开始看错题了，一直在想"这题能做？"看了题解发现是sb题。二分答案直接暴力把每个点展开就行了。

[SRM560 hard] 先可以转换成图论模型。然后发现如果两个点之间没边，总可以调整法使一个点到达上界或下界。因此枚举一个团，外面的点暴力枚举取上界还是下界，里面的点可以用求导直接取最优值，最后判一下合不合法就行了。很有趣的题。

[TCO2009semifinal hard] 注意到运算有结合律。分成两部分，暴力算后一部分的匹配位置扔进map，枚举前一部分的位置就行了。

[TCO2009championship hard] 线性筛球欧拉函数搞出可以杀死每种数量的monster的角度数量，map记录哪些位置被删除了直接搞一下，然后从大到小取就行了。

[TCO2015final hard] 我突然发现我好像并不会证明...球老司机指导...(看了毛爷爷的证明感觉并不难的样子T_T)字典序最小可以从后往前取，每次优先找编号小的。

[SRM561 easy] sb大暴力。

[SRM561 medium] (为啥一道裸题是550？)建出树来裸sg函数。

[SRM561 hard] (好不容易找到一场三题都会(hen)捉(shui))显然最小代价就是边数*2-直径。期望线性性随便搞。

[TCO2015semifinal easy] 从大到小贪心就行了。

[TCO2015semifinal medium] 一个强连通分量并上一条从这个分量出去再回来的路径还是强连通分量。大暴力状压即可。

[TCO2015semifinal hard] 这题的题解看得我一脸懵逼...做法非常玄学的样子...

[SRM683 easy] 有趣的结论题。shanquan2说他猜的结论是错的，然而我实测并没有问题...不过听说他最后写的费用流...

[SRM683 medium] 很有趣的结论题。分别考虑每一种质因数就好了。

[SRM685 easy] 看不懂题照样可以做。

[SRM685 medium] 跟shanquan2的题挺像的。结论就是把图划分成若干个联通块，联通块之间的边数要保证能构成两棵树。

[SRM685 hard] (这场不打太可惜了)UR原题。

[TCO2016round1A hard] bx2k教我们贪贪贪。

[SRM621 easy] sb题。

[SRM621 medium] 显然可以做到[tex]O(n^2)[/tex]。

[SRM621 hard] 求出后缀数组。对于每个左端点，二分答案，然后二分出右端点，判断一下就行了。

[TCO2014round3B easy] 答案就是[tex]turn+1[/tex]进制下的位数。

[TCO2014round3B medium] (大坑待填)建出反图，可以发现一定是若干个团组成的链或环。分别拿出来dp。还是挺码农的吧...

[TCO2014round3B hard] 树边权值为1，非树边权值为[tex]x[/tex]。把多项式带进matrix-tree，答案就是行列式前[tex]k[/tex]次项的系数之和。可以带[tex]n[/tex]个值进去求出行列式，拉格朗日插值求出多项式。

[TCO2014round2C easy] 贪心+大暴力。

[TCO2014round2C medium] 每个团加两个点，然后bfs。

[TCO2014round2C hard] (大坑待填)比较难写的sb题...显然离散化以后跑网络流就行了...

[TCO2014round3A easy] 模[tex]k[/tex]分组贪心。

[TCO2014round3A medium] 状压dp每个点集到每个点最短路的期望。枚举一条边即可。注意转移时要除掉这个点集出现的概率。

[SRM687 easy] shanquan2猜(zheng)的结论。从大到小贪心，只要减掉之后不是1就可以减，最后特判。正确性显然。我手贱特判打出了重复的数。

[SRM687 medium] 四个人开黑在515讨论了半天逗逼做法。最后突然发现直接构造一棵树好像是对的[捂脸熊]。最后一秒钟来不及batch test就直接交了。交完一看果然re了。

 

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter