全球云服务器

【划重点】我对TopCoder的一些看法

发布时间：2022-07-24 01:17:02 作者：wooyu 阅读量：9816

以下是我做TopCoder（简称TC）的一些总结，希望对你有所帮助。
 

 

1、题目形式

 

TopCoder和大多数OJ的题不太一样，大多数OJ都是使用用标准输入输出，而TopCoder只需实现一个关键的类（class）中的一个函数即可。函数传入的参数和返回值取代了标准输入输出。

 

TC的输入输出规模比较小，大多数题的数据范围都在 5050 以内，这是因为太大的数据点超出了Arena的容纳范围。事实上数据范围只有 5050 的题仍然颇有难度，这一点在之后会提到。

 

大多数的题目和日常做的OI题还是很类似的，但侧重点不一样。TC的组合计数以及组合优化类问题比较多，大多数题的主要难点在于思维上（当然也不乏代码题），很多题都是“暴力是指数级复杂度，难点在于想出一个多项式算法”，例如SRM 577的500，只要想到DP状态如何设计，很高的复杂度都能通过。当然也有一些 O(n3)O(n3) 卡 O(n4)O(n4) 之类的题，通常需要用特殊的方式进行输入（如输入字符串解密数字，输入随机数种子递推出随机数）。

 

2、解题遇到的困难

 

TC题比较难（当然是对我而言，对于C_SUNSHINE、matthew99、immortalCO等神犇来说应该是比较容易的？），我在做的时候遇到了不少的困难。

 

有一类问题，一开始看到的时候毫无思路，经过长时间多种方向的尝试最后才解决。

 

SRM 562的1000是一道有结论的树形DP问题，这题我研究了很久，终于推出了两种不同情况下的结论。其中一种情况是：2k>n2k>n 时，排列 p0,p1,...,pn−1p0,p1,...,pn−1 合法当且仅当：①pn−k,pn−k+1,...,pk−1pn−k,pn−k+1,...,pk−1 这 2k−n2k−n 个点构成一个连通块；②将该连通块删掉后，如果 pi,pjpi,pj 位于同一连通块，那么或者 i,j<n−ki,j<n−k，或者 i,j≥ki,j≥k；③对任意 i<n−ki<n−k，pi,pi+1,...,pn−k−1pi,pi+1,...,pn−k−1 构成连通块，以及对任意 i≥ki≥k，pk,pk+1,...,pi−1pk,pk+1,...,pi−1 构成连通块。想到这个结论以后我开始尝试用树形DP求出有多少个连通块大小恰为 2k−n2k−n，用树形背包的经典算法容易把满足③的排列个数也算进来，但是，对于每种选连通块的方案，贡献为满足②的把点分成 i<n−ki<n−k 和 i≥ki≥k 两类的方案数，这个我并不会统计。绕了不少弯路才发现其实是不从“对每个 [n−k,k)[n−k,k) 求有多少个 [0,n−k)[0,n−k) 和 [k,n)[k,n) 以及它们的排列方案数”考虑而是从“对每个 [0,n−k)[0,n−k)、[n−k,k)[n−k,k)、[k,n)[k,n) 求有多少个排列方案数”，也就是DP时把位于中间和位于两边的点数都计入状态。这样问题就得以解决了。事实证明这样的求和的问题转化思路是相当有趣的，以后可以出这类的题。

 

SRM 568的1000是我掉坑掉得比较久的一道题。由于每个半圆可以放上面或者下面，并且半圆不相交，我很快把问题转化成了：给一个圆和 nn 个点，给出一些连接两个点的弦，问能否把剩下的点也连起来使得每个点属于一条弦，且把相交的弦连一条边之后图是二分图。但是这样转化并没有什么卵用，依然只会解决空的点数不超过 1212 的情况。后来把转化的想法扔了，脑洞大开：能不能枚举已有的半圆的二分图染色情况（也就是放上面还是下面），然后判断是否存在可行解呢？推了不久我就推出了一个结论：当且仅当存在一种把点分为上下两类的方案，使得对每一测，每条圆弧里面的点都是偶数个。这就可以用经典的前缀xor建图了。把这种算法和暴力结合起来就能通过了。这个问题也让我体会到“是否存在一对(A,B)”既可以转化为“是否存在一个A，使得存在一个B”（枚举A，高效判定B）也可以转化为“是否存在一个B，使得存在一个A”（枚举B，高效判定A）。

 

SRM 579的1000是一个策略问题，但是这题的特点是“对方以一定方式随机，我方可以根据之前的结果决定之后的策略”，这类问题的解决方法我之前没有思考过，因此想了很久。事实上这一类问题还是有解决方法的：我们需要构造一个决策树 TT，TT 是一个 nn 层的三叉Trie树，每个节点有三条出边，边 (u,v)(u,v) 上的字母 d(u,v)d(u,v) 为 R、P、S 中的一个，目标是对每个非叶节点 vv 分配 R、P、S 三个字母中的一个作为策略 d(v)d(v)，边 (u,v)(u,v)（vv 为子节点）的权值定义为我方出 d(v)d(v)，对方出 d(u,v)d(u,v) 时的得分，使得对方从根开始，每次出手时根据当前节点上的字母往下走，经过的路径权值期望最大。这样只需求出每条边被经过的概率就可以对每个节点选取最优决策。虽然节点数为 O(3n)O(3n) 级别，但通过数学推导可以发现一个节点 vv 被经过的概率只和根到 vv 的路径的边上 R、P、S 的个数有关，从而设计 O(n4)O(n4) 的DP去解决它。决策树的思想是我在WC2016时讲的IOI2015 scales的解法中学到的，知识不是死的而是活的，只有灵活运用才能解决更多的问题。

 

还有一些问题，难点在细节以及实现上，有些问题花费了我大量的时间才解决。

 

SRM 549的950是一道做法很暴力的枚举题，需要枚举所有 n(n≤6)n(n≤6) 个点的分层图，对每个分层图使用网络流和状压DP（或者直接枚举）来判断是否合法。思想很简单，但枚举分层图、网络流、状压DP每一步都有细节，因此如果全都写完再调试比较难调。遗憾的是我就是全都写完再调，调不出来。事实上分部调试程序的方法是比较高效的，因为可以针对每一部分找出问题，而不是主要花费时间在遇到问题以后查哪里错了。最后这题写了一下午，调过样例的时间比写的时间长。所幸调过样例以后AC了，不知道是样例足够强还是运气比较好。这题我写了3KB左右，对我来说算比较长的了。

 

SRM 574的1050是一道看起来很可怕的题。首先这个问题需要找性质，并且这个性质极！其！容！易！推！错！反正我一开始就想错了。immortalCO跟我说他第一次也把性质推错，写了错误算法WA了。正确的性质是，网格内和网格外的每个连通块是一条路径 u→vu→v，可以缩成一条边 (u,v)(u,v)，要求在网格外加一些边，使得不会有 a<b<c<da<b<c<d 的边 (a,c),(b,d)(a,c),(b,d) 出现，且每条路径深度是递增的（对于网格内的路径 (u,v)(u,v)，若 xu<xvxu<xv，则定向为 u→vu→v，反之亦然，若 xu=xvxu=xv 则不定向）。一条路径不相邻的点在网格中也不相邻，实际上是限制了部分格子不能连。问题转化后可以用一个 O(n3)O(n3) 的DP解决掉。但是前面部分把网格转化为连边的模型有有相当多的细节要讨论，一不小心就错了，并且这种题难以对拍（没有什么好写的暴力）。我调了很久的样例，终于调过以后交上去还是WA了。这题一共FST了两次，两次都是细节实现上的问题。这种细节多的题我暂时还没想到什么好的方法来应对。

 

3、学习的算法

 

做TC题的过程中遇到了一些知识盲点，学习了一些新的算法。

SRM 551的1000一开始看起来就是一个生成树计数问题，但是是带约束的，不能直接上prüfer编码解决。一种暴力做法是从点权非负的点集 SS 内枚举一个点权和不超过限制的子集 TT，然后强制 ∀v∈T,∃u∈T,(u,v)∈E∀v∈T,∃u∈T,(u,v)∈E 且 ∀v∈−T,u∈S,(u,v)∉E∀v∈S−T,u∈S,(u,v)∉E。注意到集合个数只和 SS 中的点数有关，用Meet-in-the-middle统计每种大小的集合个数即可，并且前面一个限制可以通过容斥原理去掉，这样问题就转化为统计一个图 G=(V,E)G=(V,E) 中有两个点集 S,TS,T，(u,v)∉E(u,v)∉E 当且仅当 v∈S−T,u∈Sv∈S−T,u∈S 或 u∈S−T,v∈Su∈S−T,v∈S。这是一个生成树计数问题，看似没有高效的解决方法。不过有一个很神的技巧“矩阵树定理”，可以很高效的解决这个问题。于是我学习了矩阵树定理在 O(n3)O(n3) 时间内通过求行列式进行生成树计数，之后便解决了这个问题。

 

SRM 584的900根据题目意思可以转化为这样一个问题：给定图 G=(V,E)G=(V,E) 和 r∈Vr∈V，要从 EE 中选出权值和最小的边集 E′E′ 使得图 G′=(V,E′)G′=(V,E′) 中 rr 能到达所有点。如果是无向图就是最小生成树，有向图呢？应该就是算法竞赛入门经典训练指南里面的“最小有向生成树”，即“最小树形图”。可惜当时我只是了解了它的概念，并不会求出一个图的最小树形图。为了完成这题，我学习了如何用朱刘算法求解最小树形图，当然由于第一次写的时候不熟练而FST了两次。

 

4、写错过的题

 

由于我的代码能力不足，有超过10%的题没有一次通过系统测试，即第一次提交时Failed System Test（FST）了。事实上我的TC用户名为WAonSystemTest就是因为我老是过了样例交上去WA

 

SRM 548的450，看错题目，以为不可以填0，于是就错了，主要是没有看清楚题意导致的。

 

SRM 548的1000，我把组合数预处理到 N2×KN2×K，然而在程序用到了 C2iCi2，于是 K<2K<2 的时候挂了。可见虽然从题目上看大多数时候 K≥2K≥2，但还是要注意一些边界情况。

 

SRM 549的600，写的是三进制状压，由于想偷懒而开了 STL 的 map，但是我并不知道 map 的每个元素有 24B24B 的空间（不知道是不是，反正很大），这样开两个 313313 大小的 map 内存就超过 64MB64MB 了。最后改成数组才过。不少 STL 容器的内存都会比数组大，使用的时候要小心。

 

SRM 550的300，调了很久的样例，发现是题目理解有误，最后终于调过了，然而提交以后发现一个 <= 打成了 <，FST了。对于简单题也不要一调过样例就交，要多检查几遍代码看有没犯低级错误。

 

SRM 550的850，问题转化完以后相当于有不超过 1111 个 {0,1,2}{0,1,2} 中的数，允许经过不超过 mm 次操作，每次可以选取一个 xx 把它变成 (x+1)mod3(x+1)mod3，求把所有数变成 00 的方案数（方案不同当且仅当操作次数不同或某次操作的结果不同）。状态中只要记录 0,1,20,1,2 的个数即可。然而我又犯了个错误，DP的时候写成了从所有的 00 开始变成某个给定状态的方案数，这样是有问题的，因为只满足最终状态每种数的个数不一定正确，比如 (0,0,0,0)(0,0,0,0) 一步变成 (0,0,0,1)(0,0,0,1) 只有 11 种方案，而 44 个 00 一步变成 33 个 00 和 11 个 11 有 44 种方案。从当前状态递推到所有数都是 00 是正确的，因为全 00 的状态是唯一的。出现这么大的错误只能说明我对这类DP的认识还不够深入。

 

SRM 551的250，写了Two-Pointers然后右指针移动了左指针忘记移动了，挂掉。基本算法一定要写熟练，比如说，如果邻接表写挂了，那么树的题就可能无论怎么对拍都拍不出错。

 

SRM 553的1000，我写的做法大概是这样：首先找环长的最小值，用差分约束系统建图跑SPFA判定，每条边是 MM 的一个一次函数，二分一个环长 MM，如果找出一个负权环，那么当负权环上 MM 的系数小于 00 时，说明需要 MM 太大，需要减小 MM，否则需要增大 MM。直接二分在有解的时候不会出问题，在无解的时候可能系数为正和负的环同时存在，那么返回 MM 太小或者 MM 太大是不确定的，就会导致二分出的结果不正确。我实现的时候WA在了很后面的一个大点，调了挺久。判掉这种情况才能过。

 

SRM 556的1000，这题我没想出来，看了题解才做的。然后写的时候忘了限制 a1,a2,b1,b2a1,a2,b1,b2 的容量为 2an2an 或者 2bn2bn，第一次交的时候FST了，调的时候发现答案的infinity溢出了，第二次再FST以后才意识到这个问题。

 

SRM 563的1000，判断 a,ba,b 属于不同状态的时候，只判了能否使 aa 仍在棋盘而 bb 移出棋盘，没判能否使 bb 仍在棋盘而 aa 移出棋盘。这个问题用几组小数据都能查出问题，但我过了样例直接交了，导致FST。

 

SRM 565的500，预处理质数应处理到 109+106−−−−−−−−√109+106 而我只处理到 109−−−√109，手出极限数据无法发现这个问题（因为无法验证答案正确性），需要写的时候注意边界。

 

SRM 567的500，一开始问题想简单了，以为就是求个集合的交，过了样例交上去挂了。在immortalCO的提醒下我才意识到我考虑不周到，没注意到若干轮之后原本非最优的会变成最优，最后的解决方法是多加几层循环。

 

SRM 574的1050是之前提到的细节题，我在这题上犯了不少错误，既因为分类讨论一种特殊情况判错FST一次，又因为一种情况把变量名打错FST一次。暂时不知道有什么比较好的解决方法。

SRM 578的250，写了个 O(R⋅C⋅(R+C))O(R⋅C⋅(R+C)) 的BFS做法，R,C≤50R,C≤50，然后犯了和SRM 565 500一样的错误，第一次数组只开了 50×50×5050×50×50，第二次数组只开了 50×50×10050×50×100，两次都挂了。实际上应该开 50×50×10150×50×101。

 

SRM 578的1000，树形DP有一步转移要用KM算法，我把KM算法过程写成了一个模块，然后这一部分数组忘记每次清空了……于是调了很久才调出来。

 

SRM 584的900，第一次写最小树形图，细节没有考虑清楚，找环的时候 vis[j] 表示编号最小的能到 j 的点编号，但一开始初始化时写 vis[0]=1 导致和1出发的点混淆于是WA了。

 

SRM 586的250，犯了一个相当低级的错误，把 yy 集合从 nn 个点扩充成 2n−12n−1 个点的时候忘记令 n=n*2-1 了，这个也是随便出几组数据就能发现的问题，然而我只测了一些特殊构造的数据，对于随机数据反而没有测，导致这种容易出问题的错误没有查出来。

 

5、未解决的题

 

有的题我花费了大量时间仍然没有想出做法，最后不得不借助题解来完成。当然有的题在看了题解之后完成了，也有少量的题最后依旧没有完成。

 

SRM 582的1000，我没有想出来。一开始看到题目觉得条件比较复杂，不是很好下手，于是打了个表找规律，发现形如 n=abcn=abc，其中整数 a,b,ca,b,c 满足 b>a≥1,c>1b>a≥1,c>1 的 nn 似乎都满足 2≤c≤32≤c≤3，于是发现 NN 以内满足 c=2c=2 和 c=3c=3 的 nn 的个数都不难在 O(N−−√3logN)O(N3log⁡N) 和 O(N−−√4logN)O(N4log⁡N) 的时间内求出，但是这样会算重复，因为有的 nn 满足存在整数 b1>a1≥1b1>a1≥1，b2>a2≥1b2>a2≥1 使得 n=a1b21=a2b32n=a1b12=a2b23。之后一直想找出这类数有何共同点，比如能表示成 ab6ab6 等等，但想了几个结论全是错的。同时又想能否不从推出简单结论入手，也不利用性质，强行求出满足两个约束的 nn 的个数，但式子一步也化简不下去。最后束手无策。

 

最后只好去看题解，发现题解是结合了两种方法：首先使用了一个性质，如果存在整数 b>a≥1b>a≥1 使得 n=ab3n=ab3，并且 bb 是所有满足条件的 a,ba,b 中最大的，那么 nn 不能被表示为 a′b′2a′b′2（整数 b′>a′≥1b′>a′≥1）的条件是：设 k2k2 为 abab 中最大的平方因子，则 abk2≥kbabk2≥kb。这样在求和的时候可以枚举一个 kk，然后就能转化成和 gcdgcd 有关的式子，用莫比乌斯反演解决。这个思想十分妙。

 

***本网站图片，文字之类版权申明，因为网站可以由注册用户自行上传图片或文字，本网站无法鉴别所上传图片或文字的知识版权，如果侵犯，请及时通知我们，本网站将在第一时间及时删除。

我要评论

网友评论

---

---

---

---

---

---

常见ftp命令 FTP命令使用详解双硬盘组建Raid0磁盘阵列图文教程用友软件客户端连接不上服务器的解决办法？WebService实例开发、运维不可不看的Linux调测工具DNS服务的启动和停止如何使用Charles抓取Websocket的消息如何用ODBC访问SQL数据库Windows Server 2003中如何启动ASP.NET扩展服务IIS中站点主属性配置如何搭建平台【超赞】专为小白整理的adobe xd入门教程小旋风asp服务器怎么使用设置DHCP数据库路径将基于域名的虚拟主机转换为基于IP的虚拟主机Linux视频教程：用户管理命令useradd快云存储技术服务器集群技术的分类重庆电信服务器托管注意事项什么是双线托管，比较便宜的双线托管有哪些Linux-PAM的工作流程IBM欲出售低端服务器业务是为何意基于域名的虚拟主机配置的两种方法大神教你5招加速Python分布式与集群是一回事儿么？【划重点】我对TopCoder的一些看法英特尔三季度全球微处理器市场份额达83.7%英特尔称服务器业务目前已基本恢复服务器技术之Pcrl语言文件的读写IDC：中国HPC发展迅猛曙光HPC销售额进全球前十强