交大 2019 年度賽

NCTU_Pusheen的第一場ICPC賽制比賽。

（角色：我、隊友H、隊友U）好像有點太早到了，9:30開始，我們8:05就全到了。然後就開始討論選課的事，還有推廣了「貼圖大戰」。似乎三個人還是有點緊張，隊友U算是最淡定的一個，於是就讓他坐電腦前了。只有九隊而已，真的很怕墊底。（明明前一天的新生賽才拿第一，但就是莫名沒自信QQ）

M很水，於是隊友H就用接近首殺的速度把M殺了。然後我發現K很水，然後就讓隊友U把他殺了，然後過程中順便想出了K的構造題Ｉ，原本差點就傳了，但剛好發現範圍到10^32，於是改用python寫掉，於是K和Ｉ都拿到首殺，這時大致過了半小時。

然後，我發現F似乎是簡單的DP建表，於是就丟給隊友U寫。因為G明顯是我不擅長的幾何題，於是丟給隊友H，隊友H就想出了一個假解，因為我懶得驗證正確性，也不覺得有其他簡單的作法，於是就丟上去讓他WA了。

E是一題矩陣題，賽中我覺得高斯消去能解，但隊友U阻止了我，提醒我高斯做出來不一定是整數。賽後這題似乎是能用高斯加一些處理弄過。

因為ABC的題序一樣，然後都沒靈感，於是就先擺著。J看得出來是DP，但以為沒這麼簡單，就擺一邊了，事後證明是個錯誤決定。

此時沒有人解出其他題目，於是就決定去開D和L。

D一開始以為是Dijkstra，後來WA了之後，證出等號成立時轉移會出事，於是我就想出了一個二分搜解，但因為複雜度卡卡的，於是繼續在Dijkstra上繞圈圈。然後在最後三十分鐘，隊友U想出了一個具體的二分搜＋BFS作法，但因為搜的東西不對，無法剪枝，於是常數太大，吃了TLE。

L大概是解出來最爽的一題，花了超過一小時。隊友H先推出大致的規律，然後我用了類似前綴和的東西，把空間和時間壓到lgN，然後交給隊友H和U寫。但賽後證實我們賽中想過本機跑分塊的作法也能喇過。

A後來有兩隊解出來，於是也稍微想了一下，猜是要建圖，但真的想不出來。

嗯，看到最後會發現我好像沒碰過鍵盤呢！！

題目是將L到R(0~1e9)的二進位字串接起來，然後求這個字串的1和0共有幾段。例如1~5，表示成11011100101，答案為7。