2017-C31-team3

从 Trac 迁移的文章

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

原文章内容如下：

= 流水账 =
  之前的几场都是徘徊在爆炸的边缘，今天是真的爆炸了。前五道题都还算顺利，思路和写的都挺顺的。然而到了Ｄ，其实早就一眼看出bitset做法，就是不敢写，三个人想了好久，实在想不出，莽了一发，竟然过了...后来发现别的队都是这么过的...fuck...然后Ｅ用n^2^算法都没卡过去，其他队都用奇奇怪怪的方法卡过了，感觉很生气。
= 总结 =

== reku ==
  为什么最近总是爆炸呢？其实Ｅ的这个做法，想到二分那个暴力其实就挺显然的啊....感觉很难过
== lzw4896s ==
  E没做出来有些难受，其他队乱搞虽然用了奇怪的姿势，但复杂度也是合理的，还是我们太菜了QAQ。
== Johann ==

= 教训 =

= 题解 =
  * E：先用二分求LIS的方法处理出g[i][j]表示前i个数，长度为j的LIS末尾最小是多少。 删掉一个数后，LIS最多只会-1，假设以i结尾的LIS长度原来是k，那么 只需要检查g[k - 1],g[k - 2]就好，不需要再二分了。
  也可以用支配树搞搞

流水账

之前的几场都是徘徊在爆炸的边缘，今天是真的爆炸了。前五道题都还算顺利，思路和写的都挺顺的。然而到了Ｄ，其实早就一眼看出bitset做法，就是不敢写，三个人想了好久，实在想不出，莽了一发，竟然过了...后来发现别的队都是这么过的...fuck...然后Ｅ用n2算法都没卡过去，其他队都用奇奇怪怪的方法卡过了，感觉很生气。

总结

reku

为什么最近总是爆炸呢？其实Ｅ的这个做法，想到二分那个暴力其实就挺显然的啊....感觉很难过

lzw4896s

E没做出来有些难受，其他队乱搞虽然用了奇怪的姿势，但复杂度也是合理的，还是我们太菜了QAQ。

Johann

教训

题解

  • E：先用二分求LIS的方法处理出g[i][j]表示前i个数，长度为j的LIS末尾最小是多少。 删掉一个数后，LIS最多只会-1，假设以i结尾的LIS长度原来是k，那么 只需要检查g[k - 1],g[k - 2]就好，不需要再二分了。

也可以用支配树搞搞

附加文件