给一个稍微复杂点的做法()。
考虑用 \(\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