2017-C11-team3

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(0830.png)]]
= 流水账 =
   前期，reku看了K很多人过，就和几何选手Johann讨论半天，感觉好难啊，怎么别人6分钟就过了啊。lzw学长在电脑上默默开起了A和I，分别WA了一次和两次，这个开局十分糟糕？

   然后reku和Johann费劲全力搞了一个dfs的做法，想了想证明了一下，感觉时间复杂度可能没啥问题，就让Johann学长去写，写了一会才过。reku和lzw在Johann学长写K的时候，发现C是个傻逼贪心，然后过了一会，K和C都过了，总算是签到成功。

  之后Johann学长推出了F，lzw敲了个快速幂也过了。然后三个人讨论H，lzw搞了个单调队列，但是有点复杂，复杂度好像也很悬，和reku讨论了好久。Johann学长早退之前甩了一个很吊的优化，然后reku和lzw加了优化之后，又debug了半天才过。赛后发现我们K和H的做法都很迷，打出GG。
= 总结 =

== reku ==
   这一场还行，问题不算很大。就是前期几个简单题确实做的有一点问题，完全可以更好。然后H题，好多错误我也没有看出来。如果快速的搞出前面的题的话，我觉得D应该是能做出来的。因为是7月集训的原题而且还是我们组的题目，这个题还是我验的。感觉有点遗憾。
== lzw4896s ==
   前期队友去讨论K，我发现A是签到题，写好之后跑过样例就交了，喜获WA，把Johann学长强行拉过来看我的代码，一下子就发现错了。过了A之后队友还在讨论K，我看了看I，发现也是简单题，写好之后过了样例又直接交了,WA了2发，其中还有一发是因为没有输出"Case #：”，非常不应该。 以后就算是签到题也应该至少让一个队友知道我的做法，看过我的代码，减少不必要的罚时。
== Johann ==

= 教训 =

= 题解 =
 * 对于每种数单独计算对答案的贡献。问题转化为给出一个01矩阵，求包含1的子矩阵个数，可以反过来求全0矩阵的个数，枚举右下角，用单调栈O（n * m）搞一搞就好了。 这样的复杂度是O(n^2^m^2^) Johann学长给出了一个优化：如果有连续的两行全是0，那么第二行的贡献可以由第一行的贡献O(1)得到(加上m*（m + 1）/ 2)。 加上这个优化就可以过了。  赛后想了想发现其实这个优化非常厉害，可以把复杂度优化到O(n*m^2^)。 证明：考虑出现次数大于等于n的数，那么最多只需要做(n * m / n) 次O(mn)的求全0矩阵的个数的算法，也就是只要O（m^2^n）的操作次数。  对于出现次数<=n的数, 假设出现次数为k,根据上面的优化,最坏情况下需要算2*k行,操作数是O(2*k*m)的, 对k求和就是O(2 * n * m^2^). 所以总的复杂度是O(n * m^2^).
 * E : 如果没有交换操作的话，那么我们可以O(N)的简单贪心，贪心出最多可以分割成多少段，并且答案一定唯一。然后如果存在一次交换操作的话，我们可以把贪心出的某一段分成两段或者三段。如果某一段的长度大于2，那么我们一定可以把他分成两段。然后判断分成三段的时候，之前预处理一下对于i到j最多能分成有序的几段，然后枚举两个分界点O(N^2^)判一判就好了。
 * D : 根据我们组七月集训出的那道题，这个华容道的变化就是根据把这些东西排成一列后的逆序数的奇偶性有关，容易发现，对于每一次取数，数字后面比他小的数的个数是一个公差的p-1的等差数列，那我们对于每一次取数搞个等差数列求和就好了。

流水账

前期，reku看了K很多人过，就和几何选手Johann讨论半天，感觉好难啊，怎么别人6分钟就过了啊。lzw学长在电脑上默默开起了A和I，分别WA了一次和两次，这个开局十分糟糕？

然后reku和Johann费劲全力搞了一个dfs的做法，想了想证明了一下，感觉时间复杂度可能没啥问题，就让Johann学长去写，写了一会才过。reku和lzw在Johann学长写K的时候，发现C是个傻逼贪心，然后过了一会，K和C都过了，总算是签到成功。

之后Johann学长推出了F，lzw敲了个快速幂也过了。然后三个人讨论H，lzw搞了个单调队列，但是有点复杂，复杂度好像也很悬，和reku讨论了好久。Johann学长早退之前甩了一个很吊的优化，然后reku和lzw加了优化之后，又debug了半天才过。赛后发现我们K和H的做法都很迷，打出GG。

总结

reku

这一场还行，问题不算很大。就是前期几个简单题确实做的有一点问题，完全可以更好。然后H题，好多错误我也没有看出来。如果快速的搞出前面的题的话，我觉得D应该是能做出来的。因为是7月集训的原题而且还是我们组的题目，这个题还是我验的。感觉有点遗憾。

lzw4896s

前期队友去讨论K，我发现A是签到题，写好之后跑过样例就交了，喜获WA，把Johann学长强行拉过来看我的代码，一下子就发现错了。过了A之后队友还在讨论K，我看了看I，发现也是简单题，写好之后过了样例又直接交了,WA了2发，其中还有一发是因为没有输出"Case #：”，非常不应该。 以后就算是签到题也应该至少让一个队友知道我的做法，看过我的代码，减少不必要的罚时。

Johann

教训

题解

  • 对于每种数单独计算对答案的贡献。问题转化为给出一个01矩阵，求包含1的子矩阵个数，可以反过来求全0矩阵的个数，枚举右下角，用单调栈O（n * m）搞一搞就好了。 这样的复杂度是O(n2m2) Johann学长给出了一个优化：如果有连续的两行全是0，那么第二行的贡献可以由第一行的贡献O(1)得到(加上m*（m + 1）/ 2)。 加上这个优化就可以过了。 赛后想了想发现其实这个优化非常厉害，可以把复杂度优化到O(n*m2)。 证明：考虑出现次数大于等于n的数，那么最多只需要做(n * m / n) 次O(mn)的求全0矩阵的个数的算法，也就是只要O（m2n）的操作次数。 对于出现次数<=n的数, 假设出现次数为k,根据上面的优化,最坏情况下需要算2*k行,操作数是O(2*k*m)的, 对k求和就是O(2 * n * m2). 所以总的复杂度是O(n * m2).
  • E : 如果没有交换操作的话，那么我们可以O(N)的简单贪心，贪心出最多可以分割成多少段，并且答案一定唯一。然后如果存在一次交换操作的话，我们可以把贪心出的某一段分成两段或者三段。如果某一段的长度大于2，那么我们一定可以把他分成两段。然后判断分成三段的时候，之前预处理一下对于i到j最多能分成有序的几段，然后枚举两个分界点O(N2)判一判就好了。
  • D : 根据我们组七月集训出的那道题，这个华容道的变化就是根据把这些东西排成一列后的逆序数的奇偶性有关，容易发现，对于每一次取数，数字后面比他小的数的个数是一个公差的p-1的等差数列，那我们对于每一次取数搞个等差数列求和就好了。
附加文件