2017-C24-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(0923.png,1000px)]]
= 流水账 =
 初期lzw签到A，Joahnn签到I，reku乱搞D，然后他们都过了，reku的D乱搞不过去。

 然后很快开了G，reku瞬间猜了一个错的结论，然后lzw和Johann推了很久很久公式，之后就一直在WA，三个人卡G卡成狗，Johann看这两个人不太靠谱，就去单开了E。

 最后四十分钟，才开始写G的对拍，发现妈的傻逼reku猜的结论就是错的，期间Johann和lzw问了数次reku这个结论稳不稳啊，reku都说稳的不行。然后最后十分钟，reku又猜了一个结论，总算过掉了G。

 这场打的真是垃圾...
= 总结 =

== reku ==
 其实那个结论的反例很显然，感觉没想出来是自己智障。

 然后感觉要好好思考卡题之后的策略，感觉我们队只要卡题就必崩，而且网络赛出现了很多次卡题的情况。以后卡题并且三个人都看不出什么错误的情况下，一定要及时写对拍，尤其是算法连猜带蒙的那种题目。卡题超过四十分钟，就一定要对拍了。
== lzw4896s ==
  作为敝队的(假)数学选手，G题没想出来有些垃圾。其实看到这题就感觉是和gcd有关的，后来和reku一起推出的错误结论和gcd没有任何关系，被错误的结论带歪了，我也有挺大的锅。 最后算答案的时候我的做法非常繁琐，好几个分类讨论，所以我们几个后来一直在检查后面的部分。 另外这个题我嫌弃写暴力对拍麻烦，总有一种再看两眼代码就能找出错误的错觉，到了比赛最后一个小时才写对拍。 不过感觉运气也有些糟糕，我们队在纸上花了好多个小数据，打开excel画了三个20 * 30左右的大数据，错误的结论都能得出正确的答案。 
== Johann ==
  这场我的锅也挺大的。比赛中电脑很长时间处于闲置的状态，自己也不是很耐心，有点急。想到要开别的题的时候，已经只有一个半小时多一点了。

  教训写的很好，这场真鸡儿丢人。(~~reku决定来一波骚操作~~)

= 教训 =
  * 卡题时如果觉得复杂度有些不稳的题TLE 1小时，换算法或换题。 如果是WA且找不到错，早点写对拍。

  * 不要三个人同时花很长时间去搞一道题，除非是后期没有别的题可以做。 一定至少要有一个人再想新的题。
= 题解 =
  * G：先把每个格子中间的点拿出来,转化为点阵上的镜面反射。 先考虑 x = n - 1, y = m - 1 gcd(x, y) = 1的情况, 把(0,0)-(x,y)这个矩阵x方向复制y份，y方向复制x份，得到一个(0,0)-(xy, xy)的点阵，然后做一条直线连接(0,0)-(xy, xy)， 这条直线被格点分成xy段，对应到原图，恰好原图的每一个格子里都有一段。  gcd（x, y）！= 1的情况就是等比例放大的过程。 这就可以解释为什么最终的反射路径会像样例的图一样由很多个边长为gcd(n -1,m-1)的45°正方形构成了。
  * C：考虑包含修改点的矩形，枚举上下边，然后枚举修改点在哪一列，计算从这一列开始向左向右最多延伸多少。 对于不包含修改点的矩形，除了整个n*m矩形，其他子矩形都是可能成为答案的，所以计算最大和次大子矩阵和, 如果最大和是 所有格子的sum 而次大值不是， 那么答案应该取次大值。

流水账

初期lzw签到A，Joahnn签到I，reku乱搞D，然后他们都过了，reku的D乱搞不过去。

然后很快开了G，reku瞬间猜了一个错的结论，然后lzw和Johann推了很久很久公式，之后就一直在WA，三个人卡G卡成狗，Johann看这两个人不太靠谱，就去单开了E。

最后四十分钟，才开始写G的对拍，发现妈的傻逼reku猜的结论就是错的，期间Johann和lzw问了数次reku这个结论稳不稳啊，reku都说稳的不行。然后最后十分钟，reku又猜了一个结论，总算过掉了G。

这场打的真是垃圾...

总结

reku

其实那个结论的反例很显然，感觉没想出来是自己智障。

然后感觉要好好思考卡题之后的策略，感觉我们队只要卡题就必崩，而且网络赛出现了很多次卡题的情况。以后卡题并且三个人都看不出什么错误的情况下，一定要及时写对拍，尤其是算法连猜带蒙的那种题目。卡题超过四十分钟，就一定要对拍了。

lzw4896s

作为敝队的(假)数学选手，G题没想出来有些垃圾。其实看到这题就感觉是和gcd有关的，后来和reku一起推出的错误结论和gcd没有任何关系，被错误的结论带歪了，我也有挺大的锅。 最后算答案的时候我的做法非常繁琐，好几个分类讨论，所以我们几个后来一直在检查后面的部分。 另外这个题我嫌弃写暴力对拍麻烦，总有一种再看两眼代码就能找出错误的错觉，到了比赛最后一个小时才写对拍。 不过感觉运气也有些糟糕，我们队在纸上花了好多个小数据，打开excel画了三个20 * 30左右的大数据，错误的结论都能得出正确的答案。

Johann

这场我的锅也挺大的。比赛中电脑很长时间处于闲置的状态，自己也不是很耐心，有点急。想到要开别的题的时候，已经只有一个半小时多一点了。

教训写的很好，这场真鸡儿丢人。(reku决定来一波骚操作)

教训

• 卡题时如果觉得复杂度有些不稳的题TLE 1小时，换算法或换题。 如果是WA且找不到错，早点写对拍。
• 不要三个人同时花很长时间去搞一道题，除非是后期没有别的题可以做。 一定至少要有一个人再想新的题。

题解

• G：先把每个格子中间的点拿出来,转化为点阵上的镜面反射。 先考虑 x = n - 1, y = m - 1 gcd(x, y) = 1的情况, 把(0,0)-(x,y)这个矩阵x方向复制y份，y方向复制x份，得到一个(0,0)-(xy, xy)的点阵，然后做一条直线连接(0,0)-(xy, xy)， 这条直线被格点分成xy段，对应到原图，恰好原图的每一个格子里都有一段。 gcd（x, y）！= 1的情况就是等比例放大的过程。 这就可以解释为什么最终的反射路径会像样例的图一样由很多个边长为gcd(n -1,m-1)的45°正方形构成了。
• C：考虑包含修改点的矩形，枚举上下边，然后枚举修改点在哪一列，计算从这一列开始向左向右最多延伸多少。 对于不包含修改点的矩形，除了整个n*m矩形，其他子矩形都是可能成为答案的，所以计算最大和次大子矩阵和, 如果最大和是 所有格子的sum 而次大值不是， 那么答案应该取次大值。

附加文件

• 0923.png by ruiker