11.1多校聯訓

Sol

卡常臭題。但是關我一個考場寫\(O(n^3)\)暴力什麼事呢？

好像可以優化到\(\sum_{i=1}^n f(n)\)，\(f(n)\)表示\(n\)二進制下<code>1</code>的個數。但是這是基于随機資料優化。如果全部是\(2^{64}-1\)那效率甚至不如我的。

按位統計。從左往右：

如果第\(i\)個數二進制第\(j\)位是<code>1</code>，那麼這一位貢獻就是\(\frac{(i-1)*(i-2)}{2}*(1&lt;&lt;j)\)，表示前面随便選兩個數都可以；同時\(t_j++\)，表示目前有多少數第\(j\)位是<code>1</code>。

如果第\(i\)個數二進制第\(j\)位是<code>0</code>，那麼這一位貢獻就是\(f_j*(i-1-f_j)*(1&lt;&lt;j)\)，表示前面選擇一個第\(j\)位是<code>1</code>，一個是<code>0</code>的，這樣異或起來就是<code>1</code>。

綜上所述：開一個桶統計每一位目前<code>1</code>個數，時間複雜度\(O(64*n)\)，且常數非常小（當然大于\(1\)）。隻帶O2隻能1.09秒，火車頭加上輕松過。

Code

都不會。不過T3的80分可以提一下。

對于80分，假設一共有\(k\)個島嶼\(x\)塊陸地，先\(O(n^2)\)DFS一遍算出每個點屬于的島嶼。然後\(O(x^2)\)計算一對島嶼之間的直飛距離。由于直飛距離顯然\(\leq n+m\)，是以設\(dp[i][j]\)表示已經過長度為\(i\)，現在在\(j\)最多坐了幾次飛機。那麼枚舉每條邊即可，時間複雜度\(O(k^2n)\)，雖然在最壞條件下\(subtask\ 3\;n\leq 90\)是過不了的，但是實際上資料比較水且本題1.5s開O2，是以能喜提80分。

和julian異曲同工的臭題。

最大的統計天數也不超過long long資料範圍，是以先把輸入轉換成總計天數。然後把這個天數分段處理，我的做法分的比較細，先8月，然後-3114年，然後-3113-3101年，然後-3101-2801年，然後-2801~-1年，然後公元年以後。

每次都更新一下目前時間，注意細節即可。票池的解法是先把400年的大循環暴力預處理出來，這裡時間複雜度\(O(10^5)\)，很低。然後直接不斷取模再尋找對應日期就可以了，注意跨年的特殊處理即可。很可惜，最後突然改題幹以後票池炸了，或許慢慢來分類更穩吧。

Code（臭死了）