资讯详情

• 比较简单的一场，一个半小时场切T1,T2

• T3

  • 通过观察可以发现 \(a_1, a_n, \max(a_i), \min(a_i)\) 是一定不会删掉的
  • 通过观察又可以发现第一个 \(\max(a_i) / \min(a_i)\) 一直到最后一个 \(\max(a_i) / \min(a_i)\) 之间不是 \(\max(a_i) / \min(a_i)\) 的数一定会被删
  • 通过画图可以发现不是 \(a_1\) 或者 \(a_n\) 或者 $ \max(a_i), \min(a_i)$ 的数是一定会被删了
  • 没有想出来的很大部分原因是因为惧怕题目/根本没有画图去发现性质或者说去分析
  • 所以我们可以发现最后留下来的一定是若干从 \(1\) 到第一个 \(\max / \min\) 之前的与 \(a_1\) 相同的 \(a_i\) 以及若干从 \(n\) 到最后一个 \(\max / \min\) 之后的与 \(a_n\) 相同的 \(a_i\)
  • 我们可以分别 \(dp\)
  • 以 \(a_1\) 为例
  • 定义 \(dp_{i,j}\) 表示到 \(i\) 为止有 \(j\) 个数是否可行 \(0/1\)
  • 考虑用 \(bitset\) 维护到 \(i\) 为自己可以有的 \(j\) 即可