A. Polo the Penguin and Segments
- 模拟。
B. Polo the Penguin and Matrix
- 每個數字模d餘數必須一樣。
- 枚舉結果，可計算操作次數，取最小。
C. Polo the Penguin and Strings
- ababab……cdef……
- 對于n、k分别為1時，需要特判。
D. Polo the Penguin and Houses
- 前k個暴力枚舉，後n-k個每個可取個數為n-k。
E. Polo the Penguin and XOR operation
- 顯然為了讓結果盡量大，是以異或和應該和加法和接近。
- 觀察樣例可知，結果為n(n+1)，是以可猜測對于任意的n可構造出異或和n(n+1)的序列，即異或不存在兩個1相消。
- xjb證明：對于n來說，假設二進制最高位為p，則\(2^{p + 1} - 1 \oplus n\) 顯然小于n；對于n-1來說(假設二進制最高位不變)，\(2^{p+1}-1 \oplus n - 1\)會大于\(2^{p+1} - 1 \oplus n\)。也就是\([2^{p + 1}-1 \oplus n, n]\)構成一個我們要的區間，而\([1,2^{p + 1}-1 \oplus n)\)則變成一個子問題。
D. Polo the Penguin and Trees
- 考慮每個點的貢獻，把一個點挖掉後會形成若幹棵子樹，對于每個子樹内的路徑與經過目前點的路徑必然不相交。
E. Polo the Penguin and Lucky Numbers
- 因為\(l,r\)沒有前導0，即最後的幸運數字長度均為\(|l|,|r|\)。
- 将問題看成求\([1,n]\)内\(a_1a_2+a_2a_3+…+a_{n-1}a_n\)的值。
- 長度為1時，幸運數字有4,7；
- 長度為2時，幸運數字有44,47,74,77;
- 記長度為\(l\)時，幸運數字有\(a_{1}^{l},a_{2}^{l},…,a_{n}^{l}\)，那麼長度為\(l+1\)時，新的幸運數字為\(\overline{a_{1}^{l}4},\overline{a_{1}^{l}7},\overline{a_{2}^{l}4},\overline{a_{2}^{l}7}…,\overline{a_{n}^{l}4},\overline{a_{n}^{l}7}\)。此時是不考慮有上界的情況，有上界的情況時，最大值是字首，且添加4、7時要根據下一位的值考慮，下一位是4時，最大值隻能加4得到新的幸運數字，下一位是7時則相當于沒有限制。
- 假設\(F_i=\sum_{i=1}^{K_i-1}{a_ia_{i+1}}\)，\(K_i\)表示幸運數字的個數。
- 當\(時s_{i+1}=4時\)\[F_{i+1}=\sum_{i=1}^{K_{i+1}-1}{A_iA_{i+1}}\\=\sum_{i=1}^{K_i-1}{\overline{a_i4}\cdot\overline{a_i7}}+\sum_{i=1}^{K_i-1}{\overline{a_i7}\cdot\overline{a_{i+1}4}}\\=\sum_{i=1}^{K_i-1}{(100a_i^2+110a_i+28)}+\sum_{i=1}^{K_i-1}{(100a_ia_{i+1}+40a_i+70a_{i+1}+28)}\\=100\sum_{i=1}^{K_i-1}{a_ia_{i+1}}+100\sum_{i=1}^{K_i-1}{a_i^2}+220\sum_{i=1}^{K_i-1}{a_i}+70(a_{K_i}-a_1)+56(K_i-1)\]
- 當\(s_{i+1}=7\)時，隻需要加上\(\overline{a_{K_i}7}\)這項即可。
- 為了得到\(F_i\)，需要維護和、平方和，兩個值推導與上面的類似。
轉載于:https://www.cnblogs.com/mcginn/p/6275589.html