寫在前面
剛到長沙，補完作業，自然選擇號八題第六，算是正常發揮，畢竟邀請賽沒什么強隊來打，不過賽前確實想過拿個獎杯回去… 再接再厲吧，
周六先去長沙理工打了藍橋杯國賽，感覺比之前要簡單，甚至比第一場省賽還簡單？然后就做城際鐵路去了湘潭，熱身賽看了眼題沒啥意思就沒寫（為什么是中文題面？），期間發現了前面的前面的湖大隊伍，看起來挺厲害的，晚上第一次吃自助火鍋，那里的老板是真的能聊，拿著啤酒不停和我們碰杯，還讓我給他挑了一個耳機，實在是有點過于熱情，
復盤
不得不說在機房比賽就少了點味道，地方比體育館擁擠，桌子上也沒多少空，而且原定九點半開始的比賽到點都沒發紙質題目和密碼，一直推遲到了九點四十，
開場 wjy 和我快速過掉 A、K 兩題，接著 zcq 就上機拿到了 E 的一血，同時我也想出了 I，一個比較裸的線段樹優化 dp，而且發現 J 直接啟發式合并就能做，因為 I 稍微沒那么好寫，于是 wjy 就先寫 J，但寫到一半好像出現了些問題，我就上 I，這個時候 I 是沒人過的，我也很想再拿一個一血，但最后 RE 了一發以后還是沒有實作，這也是這場比賽里我比較遺憾的一個點吧，我過了 I 以后 wjy 又接著過了 J，這時候自然選擇號在榜上來到了前五的位置，
然后我們進入了一段時間的低迷期，跟榜發現 BCF 都有人過了，但過得很少，我看了一會 F，沒有想到比拆絕對值然后二維樹狀陣列更好的做法，直到我看了 G，沒想一會兒就會做了，于是滿心驚喜地摸上鍵盤想拿一個一血，卻突然發現已經過了七十多個隊了？md 為啥三個人都沒看見這個開場四十分鐘就被過掉的簡單題啊，，，
我快速寫完 G，然后從兩小時十三分就開始躺了，和 zcq 討論了下 C，他寫掉了；讓 wjy 想想看起來可做并且他比較擅長的 B，他寫了寫沒調處來，然后我一直在想 F 的優秀做法，想來想去毫無思路，我一直以為 F 有什么驚為天人的 NM 或者至多帶一個 log 的優秀做法，畢竟 J 啟發式合并一個 log 只開了十萬，F 一百萬不大可能是兩個 log 吧，但是已經過去了七八支隊伍了，我又覺得不會太難的，正好 zcq 也在看 F，就寫了二維樹狀陣列試試，果然沒 T，又找了好久的錯終于在比賽結束前十多分鐘過掉了這個題，期間勇石博士一直在查 B 題的錯，一直沒什么結果，最后八題走人，
最后果然是被湖大以罰時優勢踩了，
簡要題解
L
題目大意：給定一個序列 N 和一個數，每次可以把這個數和序列中的某個數交換，求最少的步數使得序列不降，
這個題沒人過，我在場上有些思路，但沒想到底，場上想到可以列舉最后手上剩下的數，然后這個序列最后的樣子也就知道了（記為 N’），標記出 N 和 N‘ 不同的位置（設有 k 個），這些位置是必定要交換的，
然后假設我們知道了最后每個位置的數要去哪個位置，相當于有若干個環（記為 n），那么最少交換次數大概就是 k + n 減個一之類的，因為每次拆環需要多付出 1 的代價，
問題是我們不知道最后每個位置的數要去哪里，因為可能有相同的數（如果給出的是排列這個題就做完了），當時的我就在這里斷了思路，
做法是對于相同的數我們看做一個點，然后還是那么連邊（可能有重邊），然后答案是 k - 聯通塊數量 - 1，然后我們需要支持刪邊/加邊，維護聯通塊數量，離線以后時間分治并查集即可，
emmmm 感覺如果沒陷在 F 里的話這個題應該是能做出來的吧？
總結
這次比賽主要有兩個教訓，一是基本不要同時開多于一個題，除了調了一段時間還沒出來的情況，最好是一個題過了以后再開別的，這就要求上機前想清楚做法有沒有假，細節怎么實作，如果頻繁換人心態很容易炸裂，也很浪費時間，
第二個教訓是要善于根據過題的隊伍數判斷題目難度，就像這個 F，過了七八個隊的題肯定不會太難（根據邀請賽的水準來說），三個人同時判斷錯難度的概率也不會太大，我就是太糾結了，一直不敢寫，其實抄個二維樹狀陣列真的用不了多久，
這幾次比賽（除了 ecFinal）大多是前半場貢獻較大，后半場淪為口胡選手，我能做出來的題基本上能在很短的時間想出來，要不然就是怎么想也不會，很少出現思考很長時間以后做出一道題的情況，這說明思維的深度還是不夠，解出來的題還是多半靠著高中練出來的本能反應，當然后期比賽題目本來也都不大好做，
總之還算是正常發揮，
這周考試和雜七雜八的事挺多的，就先不碰鍵盤了，等下周再說，往 re 方向靠靠，
青島二中高考加油！
艸，藍橋杯掛麻了，這是掛了多少題掛到國三了啊，，，
又被 oi 賽制搞怕了啊，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286227.html
標籤：其他
上一篇：C++入門程式
下一篇：Linux網路編程（協議決議）