2017-C15-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(0904.png)]]
= 流水账 =
   今天Johann学长继续军训，lzw和reku继续两个人打。

   开局lzw的D看错题意了，以为是签到题，上去就开始写，写一写发现不对，然后reku上去写了两道真签到题。之后lzw发现了C的做法，写完之后测一下感觉会超时。然后两个人一起卡常，试图调整米勒罗宾的次数，发现好像不太行。后来lzw发现似乎不用米勒罗宾，卡了一个多小时才过。

  两个人一起看了看D，感觉没啥思路啊。后来reku看了下L，发现是大力n2log2的dp，xjb写一下就过了。lzw学长发现D就是个线段树，也过了。

  然后两个人讨论了一下G，感觉好像很简单，也过了。最后半个小时开始点外卖，后来觉得不应该这样堕落，就看了看B，lzw说了一个差不多的解法，然而没有时间了，打出GG。
= 总结 =

== reku ==
  今天还行吧，如果C能空出来一点时间，或者我去写G，让lzw去开B的话，说不定还能多过一题呢？
== lzw4896s ==
  C题卡主的时候心态有点崩，感觉今天要2题GG了，把C过掉之后才渐渐调整过来。B题最后已经想到解法了，没有时间写，有点可惜。主要的失误还是C绕了远路，以后卡题的时候应该适时换一个思路，不要一直顺着原来的思路死磕。
== Johann ==
  热热热，热热热。大概已经黑的你们都认不出了。

= 教训 =

= 题解 =
   * B: f[i][j]表示S[1...i]中含有多少个T[1...j],  g[i][j]表示S[i...n]中含有多少个T[j...m]。  can[i][j]表示 S[i-j+1...i]是否与T[1...j]匹配, f[i][j] = can[1...i][j]. g数组的求法同理。 跨过中间的答案是sum{f[L][i] * g[R][i + 1]}.  两边的答案是 f[1...L][m] * (n - R + 1) + g[R...n][1] * L. 
   * E: 从2回到2，最少增加的路径长度w可以很轻松的计算出来。然后我们需要知道从2出发到每个点的路径长度为w的不同取余值的（也就是w的剩余系）的最短路，知道所有剩余系的最短路之后，答案就随便枚举一下计算就好了。
   * L: O（N^2^）做法。 f[i][j][0...1] 表示考虑A的前i个数, 强制用B[j]，01表示上升还是下降的方案数。  f[i][j][0] = f[i - 1][j][0] + (A[i] == B[j]) * sum{f[i - 1][k][1]}(1<= k < j && B[k] < A[i]).固定i, sum{f[i - 1][k][1]}(1<= k < j && B[k] < A[i])这一部分可以 j从小到大 一边求 一边维护。

流水账

今天Johann学长继续军训，lzw和reku继续两个人打。

开局lzw的D看错题意了，以为是签到题，上去就开始写，写一写发现不对，然后reku上去写了两道真签到题。之后lzw发现了C的做法，写完之后测一下感觉会超时。然后两个人一起卡常，试图调整米勒罗宾的次数，发现好像不太行。后来lzw发现似乎不用米勒罗宾，卡了一个多小时才过。

两个人一起看了看D，感觉没啥思路啊。后来reku看了下L，发现是大力n2log2的dp，xjb写一下就过了。lzw学长发现D就是个线段树，也过了。

然后两个人讨论了一下G，感觉好像很简单，也过了。最后半个小时开始点外卖，后来觉得不应该这样堕落，就看了看B，lzw说了一个差不多的解法，然而没有时间了，打出GG。

总结

reku

今天还行吧，如果C能空出来一点时间，或者我去写G，让lzw去开B的话，说不定还能多过一题呢？

lzw4896s

C题卡主的时候心态有点崩，感觉今天要2题GG了，把C过掉之后才渐渐调整过来。B题最后已经想到解法了，没有时间写，有点可惜。主要的失误还是C绕了远路，以后卡题的时候应该适时换一个思路，不要一直顺着原来的思路死磕。

Johann

热热热，热热热。大概已经黑的你们都认不出了。

教训

题解

  • B: f[i][j]表示S[1...i]中含有多少个T[1...j], g[i][j]表示S[i...n]中含有多少个T[j...m]。 can[i][j]表示 S[i-j+1...i]是否与T[1...j]匹配, f[i][j] = can[1...i][j]. g数组的求法同理。 跨过中间的答案是sum{f[L][i] * g[R][i + 1]}. 两边的答案是 f[1...L][m] * (n - R + 1) + g[R...n][1] * L.
  • E: 从2回到2，最少增加的路径长度w可以很轻松的计算出来。然后我们需要知道从2出发到每个点的路径长度为w的不同取余值的（也就是w的剩余系）的最短路，知道所有剩余系的最短路之后，答案就随便枚举一下计算就好了。
  • L: O（N2）做法。 f[i][j][0...1] 表示考虑A的前i个数, 强制用B[j]，01表示上升还是下降的方案数。 f[i][j][0] = f[i - 1][j][0] + (A[i] == B[j]) * sum{f[i - 1][k][1]}(1<= k < j && B[k] < A[i]).固定i, sum{f[i - 1][k][1]}(1<= k < j && B[k] < A[i])这一部分可以 j从小到大 一边求 一边维护。
附加文件