【题解】CF1336D Yui and Mahjong Set

给一个稍微复杂点的做法()。

考虑用 \(\mathbf{triplet}\) 为辅确定单个元素,\(\mathbf{straight}\) 为主求解。首先将问题以 \(n\) 的奇偶性分成两种情况,然后可以注意到两个点:

  • 问某个 \(a_i\) 第两次后一定能确定它的值。
  • 当知道某个 \(a_i\) 是否为 \(0\) 时,只需要问一次就可以知道它的值。

那么首先考虑 \(n\) 是奇数的情况:

  • 首先问所有偶数,保证此时所有偶数上的值大于 \(0\) 。注意问 \(a_2\) 的时候需要保证 \(a_4\) 大于 \(0\),问 \(a_{n-1}\) 的时候需要保证 \(a_{n-3}\) 大于 \(0\) 。
  • 此时借用 \(a_2\) 的结果判断 \(a_3\) 是否够等于 \(0\),用 \(a_{n-1}\) 的结果判断 \(a_{n-2}\) 是否等于 \(0\),然后花两次询问确定 \(a_3,a_{n-2}\) 。
  • 接着将除去 \(a_{n-1}\) 之外的所有偶数都问一遍确定值,然后用 \(a_4,\cdots a_{n-5}\) 的结果求得 \(a_{5}\cdots a_{n-4}\),再用 \(a_{n-3}\) 的结果求出 \(a_{n-1}\) 。
  • 最后用原来 \(a_{3},a_{n-2}\) 的结果求出 \(a_{1},a_{n}\),总共恰好花费 \(n\) 次操作,注意 \(n=5,7\) 的情况。

然后考虑 \(n\) 是偶数的情况:

  • 首先询问所有的偶数,注意仍然要最后问 \(a_2,a_n\) 。
  • 再问一次 \(a_{n-2}\),得到 \(a_{n-2}\) 的值,然后通过 \(a_{n}\) 的结果求得 \(a_{n-1}\) 的值。(如果 \(a_{n-1}=0\) 就很难继续做,处理方式是再问一次 \(a_{n}\) 然后同时去掉后两项,注意不要删到只剩下两个,然后特殊处理 \(n=4\) 的情况)。
  • 问出 \(a_3\),然后再问一遍所有除 \(a_{n},a_{n-2}\) 以外的所有偶数,求出之间的所有奇数。
  • 最后求出 \(a_{1}\) 即可。

代码:Submission #145298385 - Codeforces

上一篇:计算机三级网络技术最全知识点总结【6】


下一篇:mysql修改my.ini配置文件后无法启动问题解决办法,及修改mysql默认编码为utf8mb4的方法