2017-C08-team3

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(8-26.PNG)]]
= 流水账 =
      今天还是有一些失误，并不是特别满意。

      lzw和reku顺利签完了签到，然后所有队伍都没有短时间搞出第3题，所以暂时登顶了一段时间。

      Johann学长写J的时候有很多错误，和lzw debug了一下，终于过了。

      reku的H有些复杂，不过写的时间不太长，看上去没什么问题之后交了一下，喜获WA。然而和lzw看了整整一个小时，才看出是把一个long long搞成int了...

     在reku和lzw debug的时候，Johann学长一直在一个人搞E，想了一个dp方法，却有许多问题。最后半个小时想了一下矩阵，终于想到了一个合理的做法，然而时间不够，打出GG。
= 总结 =

== reku ==
   感觉J题还算正常范围内的犯错，今天主要是失误是H题，花的时间太长了，第一次提交的代码其实除了那个long long之外其实没什么问题，然而看了整整一个小时才发现这个错误。如果H题能做的快一点，我觉得5个题应该没什么问题，我们队伍的能力完全可以达到。

   E题思考的方向之前也产生了很大的偏差，思考时间过长。
== lzw4896s ==
    今天除了做了一个签到题，一直在帮队友看代码的错误。J题和Johann学长一起发现了好几个细节错误，甚至极角排序都写错了。 帮reku学长看H题的代码，看不出错误，然后我写了个对拍，造数据的时候因为偷懒造的
    全是int范围内的数据，结果没有发现我们代码有个地方没开long long的错误，要吸取教训。 这两天很多时间都在帮队友debug，觉得我们之间可能需要协调一下代码风格，复杂的程序变量名一定要写清楚，不能随便取
    aa,bb,pp这样的变量名，否则会给队友造成不必要的麻烦。
== Johann ==
    今天写J题之前没有想到一些细节，导致写的时候非常无奈。后来把极角排序写错了。这个锅Andrew背！我一直是用水平序的QAQ！之后lzw教了我正确的姿势，于是就过了。好菜菜呀。

    想E题想了很久。感觉这个题肯定是个DP。这个感觉非常错误。导致浪费了很多时间。最后矩阵乘法的idea要orz reku，但当时因为觉得复杂度不对被ignore了。。
= 教训 =
    一个极角排序的方法：先给每个向量的终点确定象限。确定后先比较象限，若相同再用叉积判断。
= 题解 =
  * A: 问题转化为每个人都是在一个有m个点的环上走，每次步长都是n,每走到一个点钱+1或-1,问什么时候钱变为0. 先倍增预处理sum[i][j]表示从环上第i个点开始走2^j^步的代价和, Min[i][j]表示如果一开始是0块钱，从环上第i个点开始走2^j^ 步，过程中钱最少的时候是多少。 对于每个人, 他在环上走的周期是m / gcd(n, m). 根据sum和Min数组可以求出他走一个周期的代价，从而求出他会走多少个周期，最后一个不完整的周期再利用这两个数组求出。
  * B: 先将AB序列离散化,显然如果B序列颜色数<=k可以直接输出。否则A序列中颜色数<=k, B序列中颜色数>k. 考虑A染色只出现一次的颜色, 对于每个这样的颜色c(c <= k), 看看B中哪些点被染成颜色c(B中颜色数>k保证会有点被染成颜色c), 将A中这些点也都染成颜色c。 这样一次操作后会使得A中某些颜色出现次数变少，如果变成1，那么需要再次对这种颜色做同样的操作，利用队列实现即可。 这样保证不会冲突，因为对于A中每种颜色只会被“扩展”一次，每次被重新染色的点在B中的颜色相同。
  * E: 首先枚举左端点i。固定左端点S[i] == T[1]，对答案的贡献就是sum{ g[i + 1][j] * f[i + k][j + 1]}. f[i][j]表示 S[i...n]中有多少个T[j...m]的序列,从后往前DP一下就出来了。   g[i][j]表示 S[i+1, i + k - 1]与中含有多少个等于T[2...j]的子序列。   关键就在于如何求出g[i][j]. 实际上就是 要对S每个长度为k - 1的子串 与T串做类似f数组的DP。  可以考虑用矩阵来做DP, 对于每个字母对应了一个转移矩阵，现在就是要求每一段k - 1个矩阵的乘积。 观察到转移矩阵很特殊，全是对角线为1的上三角矩阵，都是可逆的。因此 [1...k - 1] -> [2...k]这一段 只要左乘S[1]对应的转移矩阵的逆矩阵，右乘S[k]对应的转移矩阵即可。 总的复杂度是O(N*M^3^),可以在两个矩阵相乘的时候利用上三角矩阵的性质优化一下常数。

流水账

今天还是有一些失误，并不是特别满意。

lzw和reku顺利签完了签到，然后所有队伍都没有短时间搞出第3题，所以暂时登顶了一段时间。

Johann学长写J的时候有很多错误，和lzw debug了一下，终于过了。

reku的H有些复杂，不过写的时间不太长，看上去没什么问题之后交了一下，喜获WA。然而和lzw看了整整一个小时，才看出是把一个long long搞成int了...

在reku和lzw debug的时候，Johann学长一直在一个人搞E，想了一个dp方法，却有许多问题。最后半个小时想了一下矩阵，终于想到了一个合理的做法，然而时间不够，打出GG。

总结

reku

感觉J题还算正常范围内的犯错，今天主要是失误是H题，花的时间太长了，第一次提交的代码其实除了那个long long之外其实没什么问题，然而看了整整一个小时才发现这个错误。如果H题能做的快一点，我觉得5个题应该没什么问题，我们队伍的能力完全可以达到。

E题思考的方向之前也产生了很大的偏差，思考时间过长。

lzw4896s

今天除了做了一个签到题，一直在帮队友看代码的错误。J题和Johann学长一起发现了好几个细节错误，甚至极角排序都写错了。 帮reku学长看H题的代码，看不出错误，然后我写了个对拍，造数据的时候因为偷懒造的

全是int范围内的数据，结果没有发现我们代码有个地方没开long long的错误，要吸取教训。 这两天很多时间都在帮队友debug，觉得我们之间可能需要协调一下代码风格，复杂的程序变量名一定要写清楚，不能随便取

aa,bb,pp这样的变量名，否则会给队友造成不必要的麻烦。

Johann

今天写J题之前没有想到一些细节，导致写的时候非常无奈。后来把极角排序写错了。这个锅Andrew背！我一直是用水平序的QAQ！之后lzw教了我正确的姿势，于是就过了。好菜菜呀。

想E题想了很久。感觉这个题肯定是个DP。这个感觉非常错误。导致浪费了很多时间。最后矩阵乘法的idea要orz reku，但当时因为觉得复杂度不对被ignore了。。

教训

一个极角排序的方法：先给每个向量的终点确定象限。确定后先比较象限，若相同再用叉积判断。

题解

• A: 问题转化为每个人都是在一个有m个点的环上走，每次步长都是n,每走到一个点钱+1或-1,问什么时候钱变为0. 先倍增预处理sum[i][j]表示从环上第i个点开始走2^j步的代价和, Min[i][j]表示如果一开始是0块钱，从环上第i个点开始走2^j 步，过程中钱最少的时候是多少。 对于每个人, 他在环上走的周期是m / gcd(n, m). 根据sum和Min数组可以求出他走一个周期的代价，从而求出他会走多少个周期，最后一个不完整的周期再利用这两个数组求出。
• B: 先将AB序列离散化,显然如果B序列颜色数<=k可以直接输出。否则A序列中颜色数<=k, B序列中颜色数>k. 考虑A染色只出现一次的颜色, 对于每个这样的颜色c(c <= k), 看看B中哪些点被染成颜色c(B中颜色数>k保证会有点被染成颜色c), 将A中这些点也都染成颜色c。 这样一次操作后会使得A中某些颜色出现次数变少，如果变成1，那么需要再次对这种颜色做同样的操作，利用队列实现即可。 这样保证不会冲突，因为对于A中每种颜色只会被“扩展”一次，每次被重新染色的点在B中的颜色相同。
• E: 首先枚举左端点i。固定左端点S[i] == T[1]，对答案的贡献就是sum{ g[i + 1][j] * f[i + k][j + 1]}. f[i][j]表示 S[i...n]中有多少个T[j...m]的序列,从后往前DP一下就出来了。 g[i][j]表示 S[i+1, i + k - 1]与中含有多少个等于T[2...j]的子序列。 关键就在于如何求出g[i][j]. 实际上就是 要对S每个长度为k - 1的子串 与T串做类似f数组的DP。 可以考虑用矩阵来做DP, 对于每个字母对应了一个转移矩阵，现在就是要求每一段k - 1个矩阵的乘积。 观察到转移矩阵很特殊，全是对角线为1的上三角矩阵，都是可逆的。因此 [1...k - 1] -> [2...k]这一段 只要左乘S[1]对应的转移矩阵的逆矩阵，右乘S[k]对应的转移矩阵即可。 总的复杂度是O(N*M³),可以在两个矩阵相乘的时候利用上三角矩阵的性质优化一下常数。

附加文件

• 8-26.PNG by ruiker