2012-C06-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{2 team1   7   891 3/67    1/11    1/98    4/212   1/51    1/188   1/--    3/124   3/--    4/--    22/7}}}

{{{
上来发现B题是写过很多次的Stern-Brocot tree,而且深度有限,于是只要简单模拟就好了，发现过不了样例，再看了一遍题原来是隔一层交换左右的
然后敲了A题，返回WA，换prowindy学长敲E，发现A可能是计算时有个应该是longlong的算成int了，改了还是WA,然后又发现用long double先判比较没加eps 可能会跪
于是删了这部分，只用整数比较改了就过了。
之后MJ给我说了D和F的题意，然后想想想想出了D的一个错误的算法，白色的在同一块，只会是一行奇数一行偶数，所以想求个最大匹配,边只在黑色有时才连，然后敲了预处理和一个匈牙利的函数.
过了样例，交了WA，又手造了一些数据，发现输入顺序不同时，结果不一样，发现没有每个testcase初始化，改了还是WA..
于是觉得算法可能错了，应该是每个黑色的和一个竖的一个横的白匹配，等价一个黑的要同时和一个奇数一个偶数行匹配，分别要求满匹配才是yes,交了还是WA...
感觉这样肯定对了，于是让MJ看程序，MJ过了会发现我的匈牙利算法有个地方写错了，因为点比较多，我加了个优化，然后没有同步匹配的节点,改了就AC了，
不确定能写对的算法一定要敲模板，,虽然可能会超时，或者直接上Hiphop-Karp的最大匹配......
此后，prowindy学长奋战J，我和MJ讨论G和I,G题先觉得只有点近的后听见的信息是有用的，然后MJ去敲了，在他敲时发现题目里又有10^-7^的eps就觉得不这么简单，所有信息都是有用的，
要解差分约束的不等式判断,本着可能水过的心理没有打断G题，但返回果然是WA，时间不多了，然后讨论了下觉得要放弃G，换Prowindy学长写J，
最后封榜前发现I题有人过，之前由于图形复杂，跳过了，结果看了范围超大，但有一个点间距大于一定值的限制，而且查找的范围很小，就可以离散化排序查找大大降低复杂度，
代码除了一个线段判交其他的都可一用STL，而且坐标范围不大甚至不需要离散化，于是上去敲，敲的时候MJ在旁边监查代码边指导，此时时间紧迫没有敲模板，敲完后于样例出入很大，
换Prowindy调J，MJ再纸上改了一些比较明显的Bug，过了样例，返回WA，又改了一个跨可能爆出数组的bug，还是WA，最后乱改了查找数量，必然还是WA，于是结束了。。。。


错误线段相交没做快速分离测试只做了跨立实验于是就跪了，赛后只加了快速分离测试，就过了。

我算法各种不炸实,在D题花了太多时间，匈牙利算法都改错了，要是早点出D，I敲模板应该是来得及的，就不会写错线段判交了......
   --zYc
}}}

{{{

占楼待编，赛前准备自己用得熟悉的模板是必须的，
我想不到手敲有任何优势，更快？更正确？都没这说法。。。
平时锻炼能力可以手敲，比赛时可别玩大了，继续磨J，两位学长快想队名啊！！

这两天每天比赛时最后在写的题都没过，总结一下发生的错误，以后比赛前来wiki复习所有遇到过的错误：
1. 本场的I题用SPFA做需要循环更新的DP是对的，比赛时推的DP方程也是对的，
错误在于没考虑DEP[I]（火车发车时间）这个变量！一个读入变量在程序中没被用到也没发现，丢！！
还有个错误，偷懒把mark清零写到for循环上，结果清零的个数是N不是T，太新手了！
2. 第二天这场的J题是树形DP，艰难看懂的题意原来是对的（它想表达的就是我们猜到的那样……）
但是！DP的时候少考虑了一个转移，领悟到的是把DP多维的意义都定义清楚！
3. 一般图最大独立集？想这个都花了很多时间，ZYC学长还坑爹得想出了并茶几的方法。。。
MJ一语道破，当你发现模型是NPC问题，说明一定有附加条件！下次注意。
——prowindy
}}}

{{{
我觉得对于我个人而言，那些网络流之类的算法其实手敲比敲模板要快很多，特别用自己熟悉的写法的时候，如果要输出方案什么的更会写得很顺手。
本来几何那题想敲模板的，但是时间好像不是很够...-.-后来还是玩出事了。要是直接用模板大概就直接过了。只要不是非常熟悉的算法，还是准备好自己的模板比较好。
--edward_mj
}}}

2 team1 7 891 3/67 1/11 1/98 4/212 1/51 1/188 1/-- 3/124 3/-- 4/-- 22/7

上来发现B题是写过很多次的Stern-Brocot tree,而且深度有限,于是只要简单模拟就好了，发现过不了样例，再看了一遍题原来是隔一层交换左右的
然后敲了A题，返回WA，换prowindy学长敲E，发现A可能是计算时有个应该是longlong的算成int了，改了还是WA,然后又发现用long double先判比较没加eps 可能会跪
于是删了这部分，只用整数比较改了就过了。
之后MJ给我说了D和F的题意，然后想想想想出了D的一个错误的算法，白色的在同一块，只会是一行奇数一行偶数，所以想求个最大匹配,边只在黑色有时才连，然后敲了预处理和一个匈牙利的函数.
过了样例，交了WA，又手造了一些数据，发现输入顺序不同时，结果不一样，发现没有每个testcase初始化，改了还是WA..
于是觉得算法可能错了，应该是每个黑色的和一个竖的一个横的白匹配，等价一个黑的要同时和一个奇数一个偶数行匹配，分别要求满匹配才是yes,交了还是WA...
感觉这样肯定对了，于是让MJ看程序，MJ过了会发现我的匈牙利算法有个地方写错了，因为点比较多，我加了个优化，然后没有同步匹配的节点,改了就AC了，
不确定能写对的算法一定要敲模板，,虽然可能会超时，或者直接上Hiphop-Karp的最大匹配......
此后，prowindy学长奋战J，我和MJ讨论G和I,G题先觉得只有点近的后听见的信息是有用的，然后MJ去敲了，在他敲时发现题目里又有10^-7^的eps就觉得不这么简单，所有信息都是有用的，
要解差分约束的不等式判断,本着可能水过的心理没有打断G题，但返回果然是WA，时间不多了，然后讨论了下觉得要放弃G，换Prowindy学长写J，
最后封榜前发现I题有人过，之前由于图形复杂，跳过了，结果看了范围超大，但有一个点间距大于一定值的限制，而且查找的范围很小，就可以离散化排序查找大大降低复杂度，
代码除了一个线段判交其他的都可一用STL，而且坐标范围不大甚至不需要离散化，于是上去敲，敲的时候MJ在旁边监查代码边指导，此时时间紧迫没有敲模板，敲完后于样例出入很大，
换Prowindy调J，MJ再纸上改了一些比较明显的Bug，过了样例，返回WA，又改了一个跨可能爆出数组的bug，还是WA，最后乱改了查找数量，必然还是WA，于是结束了。。。。
错误线段相交没做快速分离测试只做了跨立实验于是就跪了，赛后只加了快速分离测试，就过了。
我算法各种不炸实,在D题花了太多时间，匈牙利算法都改错了，要是早点出D，I敲模板应该是来得及的，就不会写错线段判交了......
   --zYc

占楼待编，赛前准备自己用得熟悉的模板是必须的，
我想不到手敲有任何优势，更快？更正确？都没这说法。。。
平时锻炼能力可以手敲，比赛时可别玩大了，继续磨J，两位学长快想队名啊！！
这两天每天比赛时最后在写的题都没过，总结一下发生的错误，以后比赛前来wiki复习所有遇到过的错误：
1. 本场的I题用SPFA做需要循环更新的DP是对的，比赛时推的DP方程也是对的，
错误在于没考虑DEP[I]（火车发车时间）这个变量！一个读入变量在程序中没被用到也没发现，丢！！
还有个错误，偷懒把mark清零写到for循环上，结果清零的个数是N不是T，太新手了！
2. 第二天这场的J题是树形DP，艰难看懂的题意原来是对的（它想表达的就是我们猜到的那样……）
但是！DP的时候少考虑了一个转移，领悟到的是把DP多维的意义都定义清楚！
3. 一般图最大独立集？想这个都花了很多时间，ZYC学长还坑爹得想出了并茶几的方法。。。
MJ一语道破，当你发现模型是NPC问题，说明一定有附加条件！下次注意。
——prowindy

我觉得对于我个人而言，那些网络流之类的算法其实手敲比敲模板要快很多，特别用自己熟悉的写法的时候，如果要输出方案什么的更会写得很顺手。
本来几何那题想敲模板的，但是时间好像不是很够...-.-后来还是玩出事了。要是直接用模板大概就直接过了。只要不是非常熟悉的算法，还是准备好自己的模板比较好。
--edward_mj
附加文件