信息学集训队作业zhangning

1、第三阶段：相互学习与任务申请：学校：市复旦大学附属中学一、关于每道题目，写出你的收获和看过大家说的话后，自己另外想说的话。序号你的收获（在叙述时 记提到给你收获的人）实在没收获的可空着，这项主要是给 自己学习看的。想说的话（可以是别人说的话表示同意，产生疑问或者参加）0001大家的都差不多，但是没具体实现方法，希望大家一下如何设计 A*算法0002这道题目，多数想法和我一致，但是有些同学关于分治法的运用对我有些启示。但是我仍然没有理解一些同学的想法，例如：0003这道题目我也只想到了O(N2)的算法，但是 Hash法还是给了我一定的启示。大家能否合力研究一下所谓的特殊的数据结构0004这道题目

2、我原先设想的算法有一点问题，看了各位同学的分析之后，取长补短，对修改算法很有帮 助。对于情况的改进还没头绪0005这道题目让我明白如何活用算法，运用差分约束系统来求解。这道题目可以说得益于 lxd 的提示0006Zhouyuan、wzk、helin 对这道题目的证明方法是调整法，对我有一定的启示。0007有些同学的做法和我不同，但仍可行，本质是二分，对我有一定的启发。条条大路通罗马0008大家的 多数是搜索的优化，对于是否存在多项式的算法，有启示的想法不多。0009这道题目大家都有一些独特的贪心策略，综合运用应该会有比较好的效果。这道题目始终没有能够得到一个正确算法的证明或是一个准确的时间复杂

3、度估计。0010lxd 的方法与寻找割点的方法本质相同，因为非割点必然在一个圈中，只是两种思路的思考方向不同。0011lrj 的思路给启发最大，lrj 想到了一些与众不同的实现方法。lrj 果然强0012很多同学利用半平面的交的算法来处理这个问题，使得问题很好的解决，对我很有启发。我怎么没想到呢？0013这道题目的描述太复杂，也难怪会看错。0014有直接的数学方法吗？0015Jinkai、raoxiangrong 这道题目使用Polya 原理解决，使我明白要活用这些定理、概念。与其说是用Polya，不如说是用了 Burnside 引理。0016当时觉得题目数据小，搜索没问题，就没有怎么太不过还

4、没有想清楚怎样分治。IOI2003 中国国家集训队难题活动多的考虑，确实匹配的做法就比较优秀。0017冬令营分析了一下，大家都会做了，看来冬令营的很有必要。0018Xzl、lxd、lym 的贪心法很好，的方法也很有新意。不过贪心法能明其正确性？另外有线性的算法吗？0019很有收获，每个人都有不同的证明方法，但最终都是靠解模方程解决的。0020其实很简单。0021改造生成树算法真是很有学问。lrj 真佩服你，怎么知道这么多知识，可惜你的数没有中文的，我 english 太差，只能期待你的著作了，希望在选拔赛前见到，恶补一下。0022Lxd 同学的算法很好。由于是人为掐时，就很难估计时间复杂度了。

5、0023相比用几何方法，用染色就比较容易实现了。确实很繁。0024确实不用再了。0025E 文太差，好书看不懂。0026NP 问题好难啊！0027此题数据规模不明，不过也找不到什么多项式算法。这题依然一头雾水。00280029首先这道题目由于有立方体总数的限制，很难找到组合公式，并且这道题目有两个难点，一个是内存限制，一个是算第k 个塔的方案要重推，正如 zhouyuan 所说的理论上会超时。0030动态规划的公式好像无法再简化，很抱歉，我上次的结论似乎是错的，好像有反例。0031把费用变为流量，对于没做过的同学，还是很有启发的。0032的题目。00330034就看怎么搜了。0035大家都会。

6、0036由考虑Ann 转而考虑Billy，补集转化。但是是否Billy 没有必胜策略就一定有Ann 有必胜策略呢？需要证明一下吧。0037同学的做法很 ，很有创造性，如果从贪心算法出发考虑这个问题会遇到 ，而 同学构造出了一种解法，很有启发性。我只会证明上界，却无法证明上界取得到，同学的做法很。0038侯的方法值得仔细研究。0039同学的思路挺好。应该继续。0040这道题目是我去年集训队作业时做的，当时想出了一个可行的方法，觉得题目挺有趣，但并没有深究其 问题。因此有关 Fibonnac 数列的引入，对问题的研究有了一个深入的认识。不知道是谁先想到 Fibonnac 数列，是lrj 吗？004

7、1大家都会。0042jinkai 求较优解进行优化的方法不错。怎么估计复杂度？0043Luoji 的中的方法比较好。可惜我之前没看过。0044的估界方法很好。0045对这个感：高构造过不重复搜索正方形的方法。反演？！lrj 我是越来越佩服你了，随口说说就有我听都没听过的概念。0046原来n=16，那么问题就容易。0047强烈期待中0048Xrj、lxd、lym 的方法非常好，分析的很清楚，并且可以直接排除方案大于 29 的可能情况。0049Lyd、lxd 不解方程而bfs 的方法简洁、有效，非常好。怎么lym 和lxd 的想法老是一样的，过吧。0050非连通的情况太了。0051m=0 的情况可

8、能大家的想法都或多或少会受已有的证明想法的影响，恐怕会大同小异。0052大家除了搜索似乎都没 更好的方法，也没 比较有效的优化措施。0053Lxd 的贪心法分析的很仔细。我之前对于贪心法的一些细节还不十分清楚，看过分析有就比较明白了。0054的分析蛮到位的，不过这种题目应该多加入一些人工智能的 ，例如遗传算法。0055Lcl 的证明真好，我原先一直不懂。这题大家也有一点混水摸鱼，都写数论两字，就像一些其他题目，都写搜索或者贪心，不过这往往也出于无奈啊，谁让 的题目这么多呢？00560057反例肯定有，当时王建德老师在这里讲这道题目的时候， 当场举出了一个反例，不过现在忘了，想想可能还想得出来。

9、0058所谓的数学方法呢？0059分成三角形、菱形、梯形的想法不错呵呵，江苏的同学开展的真好。0060006100620063Jk 和rxr 的算法很好。不过题目中n=20 也有一些误导往枚举方面想。00640065006600670068006900700071的解法很00720073观察规律有时真的有效二、队员互评最喜欢的三位队员：觉得做得不错的五位队员（不得与前三位重复）：队员总体理由讲得特别好的题目（及认为其讲得好的理由）分析的比较清楚。0005 的差分约束系统讲的比较清楚，0006 的证明很有普遍意义，0010 的证明挺好，0020 的hash 方法讲得挺清楚的，0062 讲的不错，

10、0071 讲的很好。有些题目有很独特的想法。0010 的方法不错，0018 的贪心法分析比较详细，0019的想法很好，0048、0049 的方法很好。对一些问题讲的比较深0006 的证明很有普遍意义，0029 讲的比较有针对性，队员总体理由讲得特别好的题目（及认为其讲得好的理由）林希德非常认真，很多题目都进行了深入的思考，有一些与众不同的想法。0010 的方法比较独特，0017 证明很详细，0019 分析得很详细，0022 做法与众不同，0048、0049 的方法很好， 0053 讲的很清楚，0073 讲的很好，0088 讲的很好。很多题目都有很好的思路，对我很有启发。0012 的半平面交讲得

11、很详细，0015 运用了polya 原理，0019 的做法不错，0037 的证明很详细，0042 的求较优解的方法不错，0046 的几个优化方法不错。我觉得有些题目，自己还讲的不错。0007 写的挺详细，0010 证明写的挺直观详细，0017 的证明也挺详细，0040 的解决方法是的，0060 讲的不错。0074007500760077、同学的算法讲得很好007800790080008100820083和同学的方法很好00840085008600870088林西德的发现很重要00890090这样的贪心方法我之前没有想到009100920093原来dp 指的是硬来，我ft 了0094理解就很，好

12、玩吗？不认为0095林西德和的方法很好00960097将贪心的具体做法讲的比较清晰0098听这题时我坐最后一排，当时就没听懂。00990100这题依然心里没底对于某些题目，特别想感谢以下的同学（可空缺，也可多写）：三、心得体会（至少 1000 字，可多写）IOI2003 中国国家集训队难题活动心得体会经过三个阶段的 ，整个 活动已经达到了 。而本次 活动到目前为止应该说开展得十分顺利，各种不同的 想法不断涌现，在 交流的过程中不断迸发出智慧的火花。并且可以说 每个人都受益非浅。对每个集训队成员来说，用一个人的力量来解决这一百道难题，简直天还难。对于这一 点，在刚进入第二阶段时就充分的体会到了。

13、那时题目的搜集已经完成，而却还未充分的 展开，往往是一个对这计算机屏幕冥然是望洋兴叹。那时候，我个人的感觉是：痛苦。而对此的？尤其是 SRbGa 的题目更是难的可怕。SRbGa 你是不是存心整人啊！经过一阵的痛苦后，发现自己的力量真是太渺小了，被 无奈，开始四处找人。虽然很多题目依然是一头雾水，但仍有一部分题目经过互相切磋之后渐渐有了眉目，大家的想法取长补短果然远胜于一个人埋头单干。到了冬令营，再经过大家大范围的交流，又攻克了一部分难题，回到家后总算能够在phaseIIform 上填上一些有想法的东西了。但是仍然有很多的空白，而 SRbGa令是不许留白，这真要了的小命，出于无奈才出现了那么多的

14、废话。在第三阶段发下的材料后 面，大家可以清楚的看到这一点，往往是四、五个“搜索”、“贪心”、“数论”。在仔细阅读第三部分的材料后，发现很多题目原来可以有如此优秀的算法，往往看到之后欣喜不已，对于自己不会做的题目更是一道也不能放过。在这里大家都会有共识：林希德同学的钻研精神实在值得每个人学习。她对于很多题目都有一些与众不同的见解，更有一些是开创性的想法。这对于而言，无疑是的。而SRbGa 短短的几句评语也让见识他的厉害，提到的算法听都没听到过。对于我个人而言，收获颇丰，当然具体的也就不一一提及。而此时回忆起刚开始的痛苦，别有一番滋味。对活动早就不再心存偏见，而且我认为这种作业形式值得发扬，应该推广下 去，这样的互补提高非常重要。到集训队这种水平，光靠做 uva 等题库收效不大，而这样的对于来说都是头一次，头一次遇到如此多又那么棘手的难题，但是共同努力的成绩是卓著 的、有目共睹的。活动可以说是一次集体的研究性学习，可以说是自己给自己上了一堂精彩纷呈的课。当然到最后也忘不了感谢之前被在心中埋怨的组织者：SrbGa。虽然 很成功，但是我也想提两个建议：一是题目量太大，有时候为了赶时间只能对多数题目泛泛而谈，而这样也就失去 的意义。二是组织者虽然