Codeforces Round 1035 (Div. 2) VP記錄

A. Add or XOR

考慮，只有當操作為 \(XOR\) 且 \(a\) 的末位為 \(1\) 時，\(a\) 才有可能減 \(1\) 。

所以，如果 \(a > b+1\) 時一定不可能達成。

那么，在 \(a<b\) 時，當 ADD 的開銷小于 XOR 的開銷的時候，直接加1加到 \(b\) 一定更優。

但是，當 ADD 的開銷大于 XOR 的開銷的時候，能用XOR一定優先用XOR操作更優。

可是，當 \(a\) 的末位為0時，XOR操作才可能加1，所以要注意特殊情況。

最后，注意 \(a\) ，\(b\) 的邊界和細節。

AC code

B. Line Segments

簡單結論題,考慮到在歐拉平面上,用 \(n\) 條線段連接兩個點. 由于線端可以拐彎或者調頭, 所以考慮連接終點與起點,然后選擇所有線段中最長的一組線段,然后在上面依次連邊,如果最長邊的長度達于其他邊的長度之和,那么不可能構成一個閉環圖形.否則可以構成.

AC code

C. Leftmost Below

考慮到 \(n\) 是奇數時,只要令 \(a_1=a_2=a_3=...=a_n=l\) 即可保證 \(a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n=l\) 成立.

考慮到對于任何\(a_1\) , \(a_1 \& a_1 \& a_1 \&\ldots\& a_1=a_1\)總是成立.

又對于\(\overbrace{a_1 \oplus a_1 \oplus a_1 \oplus \ldots \oplus a_1}^{偶數個a_1}=0\) 總是成立.

所以可以推出 \(a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n=0\) 的答案可行, 下面考慮構造最優的答案.

由于 \(a\) 有偶數個,所以對于 \(\oplus\) 操作可以分成 \(n-2\) 個和 \(2\) 個進行操作. 其中只需要保證前 \(n-2\) 個 和 后 \(2\) 個數值相同即可令 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n=0\)

考慮到 \(\&\) 的情況,完全可以讓 \(a_{n-2} \& a_{n-1}=0\) 就可以保證 \(a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n=0\)

所以,對于一 \(l\) 而言,它是最高位為1的情況下的最小值,想要找到最小的 \(a_{n-2} \& a_{n-1}=0\) 可以考慮將 \(a_{n-1}\) 進位.

如果 \(a_{n-2}=01010001011\)
那么 \(a_{n-1}=10000000000\)

即可滿足條件,設 \(x=a_{n-1}\)

所以我們在前 \(a_{n-2}\) 項取 \(l\) 可以保證字典序在前 \(n-2\) 項最小,又因為字典序在取最后兩項時取了最小的 \(x\) ,所以此方案滿足題意且字典序最小.

AC code