????????第二場賽后，出題人DDOSvoid一直在搜索“如何評價...”的話題，他去年每次打完吃完飯的時候就在看評價，今年一直刷不到，因此我作為自己人來評價一下。

????????4月底教練問我能不能組織三個隊伍一起出一套多校，我當(dāng)時覺得9個人出12題肯定不難，便組織了這一場比賽的命題。這是我們唯一一次負(fù)責(zé)大型比賽的命題，要為全國的選手提供一套有訓(xùn)練價值的題目，對我們來說是非常有難度的，因為我們一年前參加多校的時候也是罰坐，要讓我們出很難的題，那是根本憋不出來。不過在我看來，一次次地罰坐并不能起到良好的訓(xùn)練效果，反而浪費了不少時間和精力，當(dāng)年多次5小時里只有一個多小時有效輸出時間，那簡直就算坐牢。如果題目難度能夠剛好讓大部分人持續(xù)思考5小時，就能對不同水平的選手都有訓(xùn)練價值。

1001 Alice Game（出題人：starry）

????????我們當(dāng)初沒有人有實力出防AK題，鉆研博弈已久的starry主席說可以出得難一點，然后我們把防AK的任務(wù)交給了他。這題預(yù)定的難度是hard+防AK，但是在校內(nèi)測試賽被當(dāng)成第三簽給簽掉了（當(dāng)時的String Problem還不是簽到）。出題人開始懷疑人生，不過也不錯，就當(dāng)是找規(guī)律簽到題。這題題目描述可能不夠清楚，有很多人來提問，隨著問題越來越多，我們多位出題人也多次反復(fù)檢查了題意，都覺得不難理解，也不知道怎么修改，只能對因無法理解題意而耽誤時間的隊伍表示抱歉。

1002 Binary Number （出題人：Markyyz）

????????按教練要求，需要來一道非常簡單的題目，可以從校ACM新生賽里面挑一道簡單的，我選擇了自己出的easy題，這題是我去年上“中國建筑賞析”（T0級水課）課時想的，當(dāng)時想出個二進(jìn)制數(shù)操作恰好k次的簽到題，突然來了idea，想出了這道題，并花了一分鐘想清楚了所有情況，后來越想越覺得這題坑爹，出給新生賽豈不是要坑得新生懷疑人生，于是設(shè)置了良心樣例，當(dāng)時的校ACM新生賽的樣例是這樣的：

????????但是既然要出給暑假多校集訓(xùn)，簽到題也應(yīng)該有其訓(xùn)練價值。為了起到良好的訓(xùn)練效果，我把良心樣例換成了“涼心樣例”，最終收獲了937/5719的超高WA率，希望大家能養(yǎng)成簽到題考慮極端情況的好習(xí)慣。有個別選手在反復(fù)WA之后開始質(zhì)疑數(shù)據(jù)范圍是否正確，這里分享一個經(jīng)驗，如果AC率是0/137，確實值得質(zhì)疑，如果AC率是2/234，建議暫時放棄這題，如果AC率是200/1000，就很明顯可以看出是有坑的簽到題。

1003 Counter Strike（出題人：Markyyz）

????????當(dāng)時想出個圓方樹題，5月分想出的idea，出這道題加起來花了將近100小時間。本來題意是多次詢問，每次給定一個詢問點集，求有多少個點滿足刪掉它可以讓剩余詢問點兩兩不聯(lián)通，有五名驗題人驗過，但是校內(nèi)測試賽有學(xué)弟發(fā)現(xiàn)這題和【SDOI2018】戰(zhàn)略游戲（https://www.luogu.com.cn/problem/P4606）很像，我搜索后直接震驚，這也能原？（其實我還出了一道題，也原了，直接廢棄）不能說是過于相似，只能說是完全一樣，詢問描述、數(shù)據(jù)格式、數(shù)據(jù)范圍都是一樣的，只是它那題求的是存在兩點不連通，我是任意兩點不連通。于是在賽前一周開始緊急修題，好在靈機一動，略微修改后變成了現(xiàn)在的樣子，樣例的圖片再稍微P一下接著用，500行g(shù)enerator也順利重構(gòu)。。最后改generator和validator時，validator有一處漏考慮了，出了一個鍋，感謝某支隊伍assert發(fā)現(xiàn)錯誤后，私聊了教練而不是在clarification里指責(zé)。但是對題目影響較小，賽時發(fā)了個公告補充說明，沒有改數(shù)據(jù)/重測，現(xiàn)在題庫里的數(shù)據(jù)是正確的。我的做法確實不是最優(yōu)的，但是復(fù)雜度也可以接受，受實力限制，最后一周改題沒有時間細(xì)想了。

1004 Card Game（出題人：SPY）

????????這題是他幾個月前想的，當(dāng)時在去華為軟件精英挑戰(zhàn)賽復(fù)賽現(xiàn)場，做活動的時候，他就和我說了這道題，本來想出給Debug杯計算機學(xué)院院賽，但是后來沒出出來，正好用于多校。有一天晚上我和他討論這題，我想很久也想不通怎么做，但是他很快就會了，還給我講了半天，我直呼妙啊，然后給另一位出題人Pedestrian1驗題，他直接秒殺。這題本被加強成medium，但校內(nèi)測試賽發(fā)現(xiàn)加強后的做法假了，于是重新削弱回easy題，還給了一組大（臭）樣例，便于大家猜結(jié)論，想必有超過一半的AC是瞎猜的（不可能，我做不來的題不可能大家都秒得掉doge）。

1005 Or（出題人：DDOSvoid）

????????因為杜老師水平比較高，我們當(dāng)時請他出一道hard，他搬出了本想出給普及組比賽的題...（這題是個有難度的數(shù)據(jù)結(jié)構(gòu)題，其實我還沒想過咋做，就不多評價了，感覺不是什么很好做的題，而且需要求的異或求和式比較奇怪，我根本不想看），出題人和驗題人都覺得難度不高，實際上有人認(rèn)為不難，有人認(rèn)為很難。

1006 Fencing the cows（出題人：小手冰涼）

????????我認(rèn)為是非常好的一題，看似是計算幾何凸包難題，實則叉積判方向后Floyd求最小環(huán)，這是一個算法思路很靈活的題，考察選手綜合運用能力。雖然用到的是兩個非常簡單的知識，但是實際通過只有30多個隊伍（部分學(xué)校用單賬號重復(fù)提交的不算），只有最強的強者才能在這道題上靈活運用簡單算法。如果陷入凸包死胡同，則會無法自拔。但是由于出題人能力有限，而且這題數(shù)據(jù)比較難出，沒有考慮充分，有一些凸包+暴力DP的做法能過通過。

1007 foreverlasting and fried-chicken（出題人：Pedestrian1）

????????一個圖論計數(shù)簽到題，枚舉兩個點是容易想到的，然后求中間幾個點的個數(shù)時，也不難想到bitset優(yōu)化（如果已經(jīng)掌握bitset的話）。這題題意不太清楚，當(dāng)時覺得有點問題，但是測試賽的時候沒人問，后來忘記修了。賽時clarification里出現(xiàn)了大量提問，我們回復(fù)的比較慢，我一直想幫他修改，但是怕改錯，因為我沒做過這個題，想先聯(lián)系出題人，而出題人下午1：30才睡醒，和他確認(rèn)后也是我?guī)兔π薜念}面，其實集合的順序也沒講清楚，好在沒有人接著提問。給大家造成了誤解，非常抱歉。

1008 Hello World 3 Pro Max（出題人：SPY）

????????當(dāng)時計劃出一個線段樹優(yōu)化DP，然后決定要不線段樹維護(hù)矩陣乘法吧，同時我們都很喜歡helloworld，于是有了這個題。這題復(fù)雜度是11^3nlogn，矩陣復(fù)雜度較大，出題人為了卡暴力測試了好久的數(shù)據(jù)，結(jié)果在測試賽被一個隊14960ms（當(dāng)時時限還是15s）暴力通過了，然后SPY繼續(xù)造數(shù)據(jù)。比賽前一天我才開始讀題，然后一眼秒了，當(dāng)時SPY的std時間還是5000ms，比校內(nèi)測試賽大部分代碼都要慢，我一發(fā)AC就是1700ms，然后我們覺得std有大問題，優(yōu)化了一下午，最后std被優(yōu)化成了546ms，但是那一份過于離譜，最終使用了800多ms的std，時限也被壓縮到3s。要求大家在做矩陣乘法時不要取模滿n^3次，最內(nèi)層循環(huán)枚舉k的a[i][k]*b[k][j]不應(yīng)該每次取模，如果模數(shù)1e9級別，那么使用long long可以9次一取模，unsigned long long可以18次一取模，觀察到矩陣均為的上三角/下三角的性質(zhì)，也是能夠大大降低矩陣乘法復(fù)雜度的常系數(shù)，雖然理論上都是常數(shù)優(yōu)化，但是多個細(xì)節(jié)合并起來，可能就是10多倍的運行時間差，畢竟取模運算的開銷是比較大的。希望大家能夠關(guān)注到代碼的細(xì)節(jié)，養(yǎng)成減小常數(shù)的好習(xí)慣。萬一正式賽場上，很多人能恰好AC，而你莫名其妙TLE了，那時你將沒有任何理由去責(zé)怪出題人。

1009 String Problem（出題人：void_f）

????????本來出題人說是一道字符串medium題，本意是不用PAM，是一個有一定思維難度的字符串題，但是測試賽時沒幾個人想得到如何不用PAM做，又有很多人用PAM最小回文分割的板子輕松通過，我們覺得這題難度不太合理，當(dāng)時又覺得中檔題難度整體比預(yù)估得要高，于是削弱成了超級大簽到（我看到改完的題目直接笑死，真有這么簡單）。

1010 Klee likes making friends（出題人：suimu）

????????這是一個思路比較明顯的DP題，只要狀態(tài)設(shè)置正確應(yīng)該不會有太大的問題，但是需要進(jìn)行一個空間復(fù)雜度的優(yōu)化，并且DP轉(zhuǎn)移也有一些細(xì)節(jié)需要注意，比較容易WA/TLE。（我的評價是，這題就是一個毒瘤題，時間限制實在是太緊了，卡常非常嚴(yán)重。其實這題被卡常了可能是HDOJ的原因而不是選手代碼的原因。我多次要問他需不需要放寬時限到1500/2000，但他心意已決，必須是這個時間，而且已經(jīng)超過std2倍了，也不是不合理。）

1011 SPY finding NPY（出題人：Markyyz）

????????這題是后來加的easy-medium題，靈感來源于一天晚上b站上刷到的“秘書問題”。其實我小時候就聽說過“最大麥穗問題”，后來也看過畢導(dǎo)的這個視頻（單身狗速進(jìn)！如何科學(xué)有效地脫單？）。本意是想送個簡單的，原以為很多人都聽說過，應(yīng)該一搜就有答案，就算沒聽說過，應(yīng)該稍微計數(shù)一下就能得出答案。結(jié)果賽時好像知道這個的人不是很多，實際上這個計數(shù)也沒有那么簡單。本打算2e5組詢問，n不超過3e7，但是意識到精度有問題，用python高精度浮點數(shù)測試后發(fā)現(xiàn)n=290000多時炸精度，干脆n小一點吧，反正難度沒有本質(zhì)區(qū)別。

1012 Coins（出題人：void_f）

????????當(dāng)時出題人說有一個簽到一個medium（舊版本的String Problem），我問他簽到準(zhǔn)備好了嗎，他說準(zhǔn)備好了，一個網(wǎng)絡(luò)流簽到。我直接震驚：網(wǎng)絡(luò)流《簽到》？網(wǎng)絡(luò)流和簽到這兩個詞也許很難放一起吧？放一起的話應(yīng)該是很簡單的網(wǎng)絡(luò)流。當(dāng)時忙著整別的題，我就沒細(xì)看，直到校內(nèi)測試賽，我們發(fā)現(xiàn)這個“網(wǎng)絡(luò)流簽到”根本沒人做，我點開一看，發(fā)現(xiàn)自己根本不會，于是問出題人要題解，看了題解恍然大悟，是一個不錯的最大流題，但難度也被重新評估。

1013 Turrent（出題人：6B8B4567）

????????這是一個比較有難度的計算幾何題，乍一看沒有什么思路，仔細(xì)一想可以枚舉出兩兩直線交點，但是然后呢？似乎要使用一些科技，不過暴力也可能通過。據(jù)說這題std精度炸了？這個我也不太清楚，畢竟我也不會做，有2個驗題隊伍AC了。題目本身確實是不錯的hard題。

????????最后的AC數(shù)量和預(yù)估的不太一樣，1008和1011實際難度比預(yù)估高很多，其他還是符合預(yù)期的，區(qū)分度還可以，大家有不同的題可以做，有幾個AK。問了幾個網(wǎng)友，都說是能做滿5小時不罰坐。有一點遺憾就是我想出的數(shù)論和SAM都沒出出來，只能說實力有限出題實在是太難了，我再也不想出題了?？偟膩碚f我們對本場比賽還是比較滿意的，期待接下來幾場的出題人和做題人優(yōu)秀表現(xiàn)。