\[\large \text{Round 2 : AtCoder Beginner Contest 313 (VP)} \]
一言:
当我拔出第二把剑时,就是为了我所爱之人
——刀剑神域
这场比赛真的是大败而归,只 A 了 \(A,B,C,E\)。。。
虽然但是,\(F,G\) 确实不可做,但是 \(D\) 题还是有点可惜了。
\(\text{D: Odd or Even}\)
感觉考场上最有价值的就是这道题了。
首先对于 \(k=1\),我们直接特判,每次询问 \(1 \le i \le n\) 即可。
注意,以下定义均基于前 \(k+1\) 个数。
我们定义 \(a_i\) 表示第 \(i\) 个位置上最终的答案,\(b_i\) 表示除开第 \(i\) 个位置的异或和,即 \(b_i = a_1 \oplus a_2 \oplus a_3.... \oplus a_{i-1} \oplus a_{i+1} ... \oplus a_{k+1}\)。
接着我们可以考虑一种特殊情况,即 \(n=k+1\)。
显然,我们可以每次查询 \(b_i\),因为 \(k\) 是奇数,所以 \(A=a_1 \oplus a_2 \oplus a_3.... \oplus a_{k+1}=b_1 \oplus b_2 \oplus ..... \oplus b_{k+1}\)。接着根据异或的性质,有 \(a_i=A \oplus b_i\),也就求出了前 \(k+1\) 个数。
那么对于一般情况,我们就需要求出剩余的数,可以每次在查询时从输出 \([3,k+2]\) 开始,每次往后面挪一位,然后就可以根据以前的答案,异或后得到答案。
\(\text{What I learned:}\)
-
当题目与奇偶性相关时,一定要想到异或哦。
-
求一个序列时,可以先求出前 \(k\) 个,然后再慢慢递推下去。