手機(jī)站首頁散文詩歌雜文隨筆日記小小說

散文網(wǎng) » 科技 »學(xué)習(xí) » 第45屆ICPC亞洲區(qū)域賽昆明賽區(qū) 個人題解與心得

第45屆ICPC亞洲區(qū)域賽昆明賽區(qū) 個人題解與心得

2021-04-04 22:33 作者:俊杰_Charles 0人讀過 | 我要投稿

比賽地址：https://ac.nowcoder.com/acm/contest/12548

官方題解：https://www.zhihu.com/question/435057733

難度：ICPC區(qū)域賽

賽后合影左起：rockdu, Macaron_lin, cjj490168650

本文中的題目順序參照?？途W(wǎng)上的題目順序。由于B站專欄的代碼塊功能有 bug，如果代碼塊不能正常顯示，請通過代碼鏈接查看代碼。

H. Hard Calculation

題意：輸出 $2020%2Bx$ 。

題解：簽到題，很幸運我們隊一開始就找到了這道題。

代碼鏈接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376389

I. Mr. Main and Windmills

題意：在一個二維平面上，你從點? $s$ 沿線段走到點 $t$ 。在? $st$ 的一側(cè)有? $n$ 個點，對于其中兩個點? $u%2Cv$ 以及 $st%20$ 上一點 $p$ ，當(dāng)你經(jīng)過? $p$ 之前觀察? $u%2Cv$ 時? $u$ 在? $v$ 的左側(cè)，而經(jīng)過? $p$ 之后觀察? $u%2Cv$ 時? $u$ 在? $v$ 的右側(cè)，則稱? $u%2Cv$ 在? $p$ 處發(fā)生了一次“交換”。現(xiàn)有? $m$ 次詢問，每次詢問某個點與其他點第? $k$ 次發(fā)生“交換”的位置。保證任意三點不共線。

題解：對于每個點來說，它和某點發(fā)生“交換”的地方位于這兩點所在直線與線段? $st$ 的交點處。因此發(fā)生第? $k$ 次“交換”的位置，則是這個點與其他所有點形成的直線與線段? $st$ 的交點離? $s$ 第? $k$ 近的點。詢問前預(yù)處理出交點位置并排序，時間復(fù)雜度 $O(n%5E2%5Clog%20n%2Bm)$ 。

這題很多人說是數(shù)據(jù)“卡精度”了，其實不然，就賽后出題人的說明來看這題的數(shù)據(jù)其實挺水的。如果被“卡精度”，很可能是在代碼中引入了不必要的精度問題。具體可見這篇帖子：https://www.zhihu.com/question/435057733/answer/1816005081。我作為隊里的幾何選手，賽前做過一些涉及求交點的幾何題，如 WF2017 的 Airport Construction，踩了一些坑，所以賽場上也有意識的避免了類似問題。所以說多做題還是很有必要的。

代碼鏈接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376405

J. Parallel Sort

題意：給出一個? $1$ 到? $n$ 的排列，每輪你可以選擇若干對互不相同的數(shù)進(jìn)行交換，要求將數(shù)列排好序，且操作輪數(shù)最少，輸出方案。

題解：后六題里最需要思維的題目了。首先可以想到的是，不同的置換環(huán)可以分開考慮。比如考慮如下的置換環(huán)（第? $i$ 個數(shù)為? $p_i$ 的話， $i$ 向 $p_i$ 連邊）。

可以發(fā)現(xiàn)對于一次交換操作，交換的是兩個點的出邊。比如交換第 3 和第 6 個數(shù)，置換環(huán)發(fā)生如下變化。

最開始的時候有一個樸素的想法，就是每次交換置換環(huán)中相鄰兩點，如在第一張圖中交換 (1,2) (3,4) (5,6)，得到如下置換環(huán)。

可以發(fā)現(xiàn)，每次操作會有一半的點歸位，剩下一半的點形成一個新的置換環(huán)。如此下去，每次置換環(huán)的大小減半，操作輪數(shù)為 $O(%5Clog%20n)$ 。

感覺非常的有道理啊，然后寫好代碼交上去，喜提 WA。在檢查代碼確認(rèn)無代碼錯誤后，我分析認(rèn)為這種策略很可能不是最優(yōu)的，因此開始尋找更好的策略。一通分析后，我意識到可能有操作輪數(shù)至多為 2 的策略，關(guān)鍵在于將原置換環(huán)構(gòu)造形成若干個二元環(huán)。隨后我找到了正確的方法，就是從兩邊往中間交換，如在第一張圖中交換 (1,7) (2,6) (3,5)。

按照這種策略，任意大小的置換環(huán)都可以經(jīng)過一輪操作形成若干大小至多為 2 的環(huán)，然后再進(jìn)行一輪操作便可將所有數(shù)歸位，操作輪數(shù)至多為 2。

代碼鏈接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376420

K. Riichi!!

題意：給定一麻將牌型，如果能直接和牌輸出“自摸”，否則輸出打哪張牌能聽牌以及聽哪些牌。注意本題中每種牌的張數(shù)沒有上限。

題解：寫一個判和牌的函數(shù)。如果給出的牌型能直接和牌則輸出“自摸”，否則枚舉打出的牌，再枚舉進(jìn)張的牌，判斷能否和牌。

本場比賽唯一把我坑到的一題。本來作為麻將玩家自信滿滿地去開這道題，結(jié)果寫了個爆搜 T 飛了。后嘗試了一系列剪枝，未果。最后在隊友的幫助下，將判斷和牌的策略從爆搜改為了貪心，過了此題。賽后詢問了出題人，出題人表示確實故意卡了爆搜的時間。個人不是很喜歡這題，既然有這么復(fù)雜的背景我覺得就沒必要太卡時間了。

代碼鏈接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376463

L. Simone and graph coloring

題意：給定一個數(shù)列 $a_1%2Ca_2%2C%5Cdots%2Ca_n$ ，每對逆序?qū)? $(a_i%2Ca_j)$ 在圖中對應(yīng)一條 $(i%2Cj)%20$ 的無向邊。然后在圖中染色，要求相鄰兩點不能染成同一顏色，求最少顏色數(shù)并輸出方案。

題解：最長下降子序列，隊友寫的。

M. Stone Games

這題是隊友寫的，我沒有讀題，應(yīng)該是個可持久化線段樹的題，據(jù)說還是 19 年徐州原題。雖然隊友貌似沒有原題的印象，不過還是成功分析并通過了此題。

其實我們隊更好發(fā)揮的話還有可能過 G 題和 C 題，然而由于被 K 題卡的時間太長，隊友寫 G 的時間不太夠了，最終 6 題收尾。還好保住了金牌，否則我就要背鍋了555。

比賽整體體驗還行，個人覺得題目整體難度偏低，題目質(zhì)量中等，J 題讓我眼前一亮，但 K 把我卡得挺不爽。主辦方提供的鮮花餅挺好吃，但承辦比賽水平不足，給參賽者傳達(dá)的信息經(jīng)常前后不一致，希望主辦方能夠所有反思。

這是我拿到的第二塊ICPC金牌，我覺得這塊金牌的意義比第一塊更大。如果說第一塊金牌是抱隊友大腿拿到的話，那這一塊金牌可以說是我們實實在在努力的結(jié)果。

這里感謝我的兩個隊友：Macaron_lin 和 rockdu（下稱小馬和小杜）。小馬是我的大學(xué)同學(xué)，也是被我拉進(jìn)算法競賽坑的人。小馬沒有任何中學(xué)OI基礎(chǔ)，但依舊憑借自己的努力通過了校隊選拔。小馬的競賽之路并不順暢，在其他隊伍紛紛獲得ICPC或CCPC金牌后，小馬最好成績?nèi)允倾~牌。而昆明這場比賽，算是小馬的“背水一戰(zhàn)”了。這塊金牌，圓了小馬的夢，也完成了我倆共同的目標(biāo)。而小杜是我的中學(xué)同學(xué)，是一名OI爺，在赤兔馬缺少一名成員時及時補(bǔ)位，他扎實的基礎(chǔ)可以說是拿到這塊金牌的有力保障。同時還要感謝前赤兔馬成員zh，暑期集訓(xùn)時優(yōu)異的表現(xiàn)讓赤兔馬拿到了打EC-Final的機(jī)會。

這個賽季結(jié)束后，赤兔馬這支隊伍可能就解散了。我之后的算法競賽路途會是怎樣，我不清楚，但至少現(xiàn)在，我已經(jīng)完成了一個階段性的目標(biāo)。之后的路途，我會繼續(xù)努力的。

大兔子的算法競賽交流群：1043272289

標(biāo)簽：