2008-06-01 18:40| 
17 Comments | 本文内容遵从昨天的，一题滑动窗口，二题O(n^3)的DP。三题是二维线段树？ 大家说得对，三题用线段树套平衡树显然更简单、更科学。
四题显然应该是先二分k，关键是怎么检验？我的做法是枚举交点Pi，枚举圆Cj（Pi不在Cj上），然后找出Cj上的所有交点所能产生的弦的中点与Pi的连线的中点，对它们进行检验。如果是三个圆交成一个空心的“瘪三角形”区域的话，画画草图就能明白我这样做的理由，关键是圆多了的话不知有反例没。结果最后没调出来，搞了半天就把一二两题做了。后来一想也就算了，反正第四题这么做也没啥根据，估计是错的。
今天下午的，一题垃圾题，二题纯计算几何，三题二分加网络流？
四题是个科学题目，O(根号n)的算法：先预处理数组f[d][r][s]，表示后一半有d位数，模k余r，数字都在给定集合内，数字和为s的情况有多少种。然后枚举前面一半，直接查表累加就可以了。代码不是一般难写，要处理很多特殊情况。我已经N久没写过这么麻烦的代码了。最后还是写垃圾了，效率居然比暴力还慢，不知道是不是哪儿写错了。谢wywcgs提醒，算法错了。即使只处理一半的长度，k仍然巨大无比。 刚才在路上突然想到了（其实最初我也是这样想的，后来做着做着就忘了这个细节）：正如网友Zero所说，这道题目可以分情况套用两种不同的算法。k较小时用上面的算法没错，当k的长度超过y的一半时可以直接暴力枚举k的倍数，复杂度仍为O(根号n)。
几乎都是科学题目。算法大概都知道，就是写代码的能力太差太差了啊。
我把题目搞丢了，麻烦哪位给一个比赛题目的链接，谢了。
Update: 感谢网友dahe_1984提供两次比赛题目的链接：
http://hi.baidu.com/one%5Fperson/blog/item/ef8d0d4ce0d952fcd62afc35.html
http://hi.baidu.com/one%5Fperson/blog/item/4d211e23db8ddd4b93580737.html
SF~~
偶也很想参加的说~~问题语言……他是C++的
= =||||
题目在TJU的bbs上放出来了
@竹子的叶子
C 和 C++ 都可以的
昨天第三题块状连表搞？
我垃圾了……昨天第一题是用二分查找做的。
昨天第三题可以用线段树里套平衡树 (std::set)，当然二维线段树也可以，只不过写起来麻烦。
今天没参加。
第四题貌似k巨大
http://www.baiduer.com.cn/?p=2841
http://hi.baidu.com/one%5Fperson/blog/item/4d211e23db8ddd4b93580737.html
第2试第4题和不考虑，暴力和动规一起处理呢，当K大的时候暴力会比较快，K小的时候动规会比较快，这样搞下来应该会有个比较漂亮的复杂度吧
今天1，2比较传统，3是2分答案+最大费用流，4应该是带数论的DP
昨天第三题好像还是只能线段树套平衡树
有一个复杂度略高的方法就是块状链表，每一块内排序。然后每次要么重新排序，要么二份查找。都是sqrt(n)log(n)的复杂度。这个估计算比较好写的了
第一个链接这么快就不能用了？
第一天第三题，如果是在NOI中遇到的话，不能用std::set，一种比较好写的方法是先离散化再用二维线段树，应该会比线段树套平衡树代码量小些。
第一天第三题，线段树套平衡树恐怕要超时
第一场第4题，我的做法跟你相似：
枚举交点Pi，不同点在于，然后检验是否有其他的圆包含Pi。
当然事先检测矩形的四条边...
一题滑动窗口。。。。请问这个是什么意思，谢谢了。
第二天第四题：先预处理数组f[d][r][s]，表示后一半有d位数，模k余r，数字都在给定集合内，数字和为s的情况有多少种。
预处理方法：枚举后一半（for i = 1 to FFFFF），若i满足条件“数字都在给定集合内”，则f[d][i%k][s]++;