2016 ACM/ICPC Asia Regional Dalian Online 总结

这场比赛打到了名额,但题目基本是抱大腿做出来的,我还是要提高 STL 的姿势水平啊,先写个大致做法吧。
这场比赛槽点还是太多了啊!我只想知道出题人是谁!知乎上的回答

 

1002 Different GCD Subarray Query

FOJ 2244 原题, 从区间里的 GCD 个数不会超过 log n 入手,转换为 RMQ 问题。直接将 FOJ 那题中代码中的离散化去掉即可。

 

1005 Seats

1990 CMO 原题。按照答案写出的做法,虽然是错的,但还是A了,说明标程也是错的啊!赛后就被清华爷 Hack 了。
做法大概是算出一排最多能做几个学校,记为 a, 接着算出一排 a 个学校至少要几个人,记为 m, 最后算出总共的学校个数 n, 将这 n 个全部安排下来算出答案。

 

1007 Friends and Enemies

结论题,最坏的情况是个二分图。

 

1009 Sparse Graph

首先如果这个图很小的话,那就用正常的方法去做。当这个图很大的时候,就会有很多不跟任何点相连的点,那么在补图中,这种点能与任何点直接相连,从这个地方入手就很简单了。

 

1010 Weak Pair

边 DFS 边维护一个 treap 和一个 multiset, 将路径上所有的点压进去,现在 multiset 中二分出最近的满足条件的数,再在 treap 中找出这个数字的 rank ,这样就能求出当前点作为子节点时对答案的贡献,累加即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注