比赛最终board

上海是cfop第一站，出现了很多问题。希望下次不会再有这么多的遗憾。

过去的时候赶火车出了点问题，但是最后还是顺利坐上了火车。

比赛开始的时候还是和以前一样，yxb看前面，xh中间，我最后，yxb看完了第一题过后就发现这是一个简单的bfs的题目，但是没有着急的写，而是继续看其他的题目。然后过了一段时间过后看board，发现有些队伍过了A题，于是和xh确认了一下后开始写A，但是稍微有一些紧张，所以代码出了一点问题，后来重写后过掉。

这个时候已经有好多人过了其他题目，我发现I题不难，但是需要用计算几何处理，而且当时没有人过，所以还是先看别人过的最多的题目，B。

这期间没有人用电脑的时候我上去暴力写了一下F，然后TLE了。

xh在我们B没什么想法的时候抽空写了一下H（一个计算几何的预处理，然后就是求最大团），但是没有写完。

B题最开始以为可以用快速幂来做，后来想清楚了数据规模后放弃这个想法，然后yxb发现和暑期集训的时候的一个题目很像，上去写完代码后过掉。

这个时候过得最多的就是J了，但是我却没有什么想法，所以和xh说了一下I题的做法，让他去写I。我和yxb一起看J，后来顺利过掉I。

这是我们的J题还是没有什么很好的想法。于是xh继续写写H，到还有不到一个小时的时候，yxb想法了J的一个初步想法，但是感觉过得可能性没有H大，所以还是选择了做H，但是很可惜的是，一直到最后H也没有过。

感觉这次出现的问题：

1.最开始的时候我们有点太紧张了，居然到90分钟的时候才过A。

2.在过了A之后，我们应该立刻认识到这次题目比较难，然后三个人加强讨论，共同做同一个题目的。但是我们却依然自己做自己的。

3.最后一个小时还是没有把握好，一个小时的时间居然一个题目都没有做出来。

希望我们在下一场比赛中可以尽量避免这次出现的问题。

最后预祝这周去武汉赛区的队伍可以取得好成绩。

    首先为本人很挫的英语向各位看题看得郁闷的大牛深表歉意。
    由于本人能力有限，比赛的筹备一直到赛前30分钟才弄好，并且没有仔细检查题面和数据出现的问题，特别是E题，数据和题面均出现较大问题是本人准备工作没有做到位，还请各位大牛海涵。
    另外，十分遗憾的是，原本所出的一道求圆和多边形面积交的计算几何题不小心和武大等校的十校联赛第10场中的某题本质一样，并且已作为训练题给大家练习，所以不得已临时换题，在此特别向补上计算几何题目空缺的Isun大牛表示感谢。
    下面简单评述本次比赛，并给出简要解题报告：
    本次比赛大部分题目不难，主要解法均为基本算法，部分题目可能需要注意细节，部分题目题面出得有点猥琐。但总体来说，算法覆盖面比较广，没有侧重考哪一方面的算法。所有题目的解法覆盖 搜索、动态规划+线段树维护单调性优化、背包、高精度（或Java大整数的应用）、基本最小生成树、字符串的细节处理、AC自动机、 简单数制转换、计算几何。
    其中E、G属于水题，D题可能题目描述没说清楚，抱歉，C题有点小麻烦（Java可能好点），B、F、H属于较难题，A题属于较巧妙题。
    在3小时40分钟的时候被电子科技大学的队伍全切了，是命题中的失误。但F、H被迅速解决，A题撑到最后是意料之外的。总得来说他们还是很强的，这里小小的赞许下，基地的队伍也要加油啊。
    下面是解题报告，其中F题由Rocket323提供，H题由Isun提供：
    A题，整场比赛中很少有人开动的一题，也是AC队伍最少的题。最初一看题，状态数无论怎么算都是一个暴大的数。仔细想想，也只能猜测要达到目标走的步数不会很多，但并不能确定上限是多少。DFSID?经验证数据最多走7步即可出解，7^7大约80万，但题目给出了10000组数据，不出意外的话，应该会TLE。另一个想法是双向广搜，首先最多7步出解这个很难证明，然后双向广搜很难写，然后10000组数据话应该会很悬。其实换种思维方式，如果我们在移动某种颜色的时候不考虑其他颜色，那么这种颜色在魔环中的状态数只有C(20,4)，只有4845种状态，这样已经没有状态压缩的必要了，当然如果会写排列数生成，用用也无妨。只要从目标状态开始BFS，把4845种状态到目标状态需要的最少步数求出来，不需要多少时间。而题目所求无非是5种颜色，分别处理取5种颜色里面的最小值就是解了，如果之前预处理了，这里的效率应该只是常数级的。
    B题，过得人很多，有些意外。之前写的时候有想过要把某些可能退化到N^2的算法卡掉，后来不记得加强数据了。这题我的做法是，设w(i,j)是从i到j的Value的最大值，那么固定j，i从1枚举到j，w(i,j)一定是单调不上升的，再使用一个队列来处理Point的情况，用线段树来处理值，可以做到NlogN。
    C题，枚举的话可能要100^4，加上这题需要高精度，就会TLE。这题我的做法是背包，再写一个高精度。这题用Java的人会比较方便，其实时限如果开小点Java也可能会TLE，这里特意放过的。
    D题，可能题面没写清楚，如果看懂了就知道是一个不需要任何优化的N^2的最小生成树问题，需要注意的是在求两个灯塔之间的距离时，如果是用int来求double，很有可能中间值越界。
    E题，出问题最多的一个题目，其实是很水的题。当时看到很多人RE,WA，后来一查数据才发现，本来要加入11750个数的一行手误多加了10000个，本题没加特别的数据来刁难人，但还是有很多人在这上面郁闷了。
    F题，原本我是想出成AC自动机＋状态dp的题的，后来有神牛用了很诡异的方法彪悍的过掉了，看了一下他的代码，貌似是枚举m个不合法的串的组合形式，然后统计？
我的做法是f[i][j]表示目前状态为i，且走到了自动机的第j个节点用多少种方法，然后枚举下一个数字转移，貌似时间不是很好，窘。。。
    G题，就是一个简单的数制转换的题目，想清楚本质应该是很简单的水题。
    H题，我的方法是:以三角形2为基准,如果
1.三角形1有两个或以上顶点落在三角形2所在平面，则输出NO
2.三角形1恰有1个顶点落在2所在平面，那么(这个顶点在三角形2内)和(这个顶点的对边穿过三角形2)两者恰有一个为真时，输出YES
2.三角形1没有顶点落在2所在平面，那么当且仅当三角形1有且仅有1条边穿过三角形2时,输出YES。
这个题提示大家3D几何的模板也要精心准备。很多AC的代码都很短，应该有更简洁的方法。

===========================
筹备这次月赛，花了不少时间，但也学会了很多东西。
细节很重要，英语也很重要。
预计时间从8月3日一直拖延到8月21日，导致本次比赛不可能在呼喊生日邀请赛，不得不说是一种遗憾。十分狼狈的是直到比赛前半个小时还在测数据是否正确也是导致了某些不应该发生的悲剧发生的原因。
校内最强的kissworld同学精准的提交和高AC率实在让人敬佩。但这次比赛我们过得最多的队伍也只有4题，跟外校比起来确实也是一种差距，大家要加油了。

另外，本次比赛得到了很多大牛的协助，特别向Rocket323、Isun、yh等同学的协助表示感谢。同时也感谢各校牛队的捧场。