猎奇！THUWC2017试机题

A

题目大意

  一个长度为 $n$ 的序列，选择一个长度为 $k$ 的子序列，使得字典序最小。
  $O(n \log n)$ 会被卡，要求线性。

  （这题其实挺正常挺经典的。。。）

解法

  本质是贪心，假设目前是第 $i$ 轮，上一轮选了第 $x$ 个，那么现在就是在 $[x+1,n-k+i]$ 里取最小值。
  求最小值的区间是滑窗向右的，可以用单调队列

A加强版

题目大意

  这是一道交互题。
  先给你一个整数 $k$ ($k \le 10^6$)，然后按顺序给你未知个整数 $a_1,\cdots,a_n$（$n \le 1.5 \times 10^7$，$n$ 不输入），要求你求出一个长度为 $k$ 的字典序最小的子序列。
  内存 32M，即空间限制是 $O(k)$ 的。

解法1

  其实跟上一题是差不多的。。。
  由于不知道什么时候读完所有的数，所以要开多一个队列存最后读进来的 $k$ 个数，然后每来一个数，就把队头拿去维护单调队列。

解法2

  直接考虑每 $k$ 个数做一次。
  假设我们目前的答案子序列为 A，然后又读了 $k$ 个数存在 B 里，那我可以用两个指针扫这两个数组来合并。
  时间是 $O(n/k \cdot k) = O(n)$。

B

题目大意

  读入一个字符串（长度 <= 20），请你读懂字符串的含义并用程序输出对应的数字。
  比如字符串是“This year”，你应该输出“2016”。
  该题有 20 组数据，每组数据的字符串都是相同的。
  该题可以多次提交，每次提交都能返回评测结果（AC、WA 等）。

猎奇题

解法1

  枚举答案显然是不行的。。。
  让机器变成 AI 读懂字符串好像也不行。。。
  只有我们自己想办法知道字符串是什么了。

  试通过评测结果来推断字符串是什么。
  比如我们猜字符串第一位是 a，那么如果 s[1] 果然是 'a'，就让它返回 RE，否则让他返回 TLE。我们知道肯定有办法设计算法使它强行 RE 或 TLE 或其他什么的。
  然后每一次提交可以判断 20 次，所以可以在有限步数内得到字符串。

解法2

  用提交状态判断还是慢了点。
  我们可以考虑用时间来判断。比如，如果它第一位为 a，就让它循环 100 次，b 就 1000 次……这样一次提交就知道整个字符串了。
  时间误差比较大，所以可以再改，用空间来判！

C

题目大意

  这是一道提答题，有 10 组数据。
  一组数据中，若读入是 x，正确答案是 ans，则 |ans-x|<=5。
  一个测试点你输出 y，可以获得的分值是 max( 0, 11-e^|y-ans| )，分值会下取整。
  现在让你 AC 这个题。

解法

  得 10 分：y=ans
  得 8 分：|y-ans|=1
  得 3 分：|y-ans|=2
  其余得 0 分。

  于是我们先猜 x，若不为 0 则再猜一次就出解；若为 0 就猜 x+5，再不行就 x-5，则一定出解了。
  最坏情况下，第 4 次提交即可 AC。