如何評價 SDOI2017 Round2？

01-08

有著豪華出題組陣容的這次比賽是什麼樣的呢？

2017.06.08 更新

今天是 SDOI2017 Round2 Day2（過去的第 21 天），

驗題總結見 tangjz 老師的這個回答如何評價 SDOI2017 Round2？

先總結一下結果，

最高分 150，不少於 100 分有 6 人，平均數 49.4，中位數 47.5，

每題最高分分別是 T1=25，T2=70，T3=75。

------------------------------------------------------------------------------------

2017.05.17 更新

今天是 SDOI2017 Round2 Day1，

首先恭喜 AC 了 T1 的兩位同學，這題是我出的，

看了一遍選手代碼，

有一小部分同學前 4 個測試點沒有加前綴和優化，TLE 了後面 3 個點，

只有少部分同學特判了第 11 和第 12 個測試點，

大部分正確實現 FFT 的同學都得到了不低於 60 的分數，由於時限開得很大，無論是多項式快速冪還是點值快速冪都能通過 60 分，其中點值快速冪由於只做了三次 DFT/IDFT（利用 @毛嘯同學在16年集訓隊論文中提到的黑科技可以只做兩次），有著相對優秀的常數，其中一份 AC 代碼是在這個做法的基礎上，將右側的尾巴循環加到了左側（因為概率非常小，對結果的影響忽略不計）又節約了一個常數，從而通過了此題，

另一份 AC 代碼幾乎就是標算，只是在積分的時候沒有使用自適應 simpson 積分，而是將積分區間切成很多小段，

最初的想法是，60 分這一檔既允許在暴力 dp 的時候忽略掉兩端概率很小的狀態（但是幾乎沒有選手寫這個做法）以及直接多項式快速冪（點值快速冪在驗題時並沒有想到，這是一個疏忽）這兩種方法通過，100 分則是期望利用正態分布對概率進行估計，同時在驗題時也提出將 60 分的兩種做法合在一起就能 AC 的思路，

最後總結一下今天的結果，

最高分 180，不少於 100 分有 12 人，平均數 61.9，中位數 60，

每題最高分分別是 T1=100，T2=50，T3=50，

即使發揮失常也請千萬不要氣餒，明天是更大的挑戰和機遇。

------------------------------------------------------------------------------------

2017.05.16 更新

今天是 SDOI2017 Round2 Day0，不出意外會有電子版題面以及大樣例，希望各位選手賽出水平。

------------------------------------------------------------------------------------

謝Claris和tangjz邀，希望不出鍋、不翻車，預祝各位選手取得滿意的成績。

Day1 與 Day2 整體情況見這個回答如何評價 SDOI2017 Round2？

Day2 T1 天才黑客

出題組發現缺一個圖論，於是準備強行造一個圖論題。

經過一段長時間的討論，出題組敲定由Q老師出一道建圖很巧妙的圖論題，做法與clrs97老師出給Bestcoder的一道題類似。

出題人寫標程寫了很久，驗題人驗題過程中多次懷疑人生，所幸他們沒有放棄這道圖論題並去出一道幾何題。

出題人不確定數據是否能夠避免奇怪的做法得分，但是本題的模型接近完全圖，使用SPFA(Shortest Path Faster Algorithm)計算最短路的代碼沒有得到良好的結果。

clrs97："小Q啊，T1太失敗了"

Day2 T2 遺忘的集合

一個很無聊的題，出題人寫了18個程序測試部分分，發現數據太水，於是增強了數據範圍，就變成現在這個無聊的版本了。

該題需要寫出精度較好的 FFT ，然而沒有選手在最後的 30% 數據浪費時間。

驗題人也表示這道題很水。

Day2 T3 文本校正

兩天內唯一一道加強自官方真題的題目，儘管這個官方只是歐洲某區域賽。

出題人轉化成雙迴文串判定的做法很巧妙，驗題人設計了一些哈希演算法去撞答案，數據在互相測試的過程中越變越強。

出題人看了一眼 CTSC 的論文答辯中關於迴文樹的內容，表示這道題目可能要讓大家見見世面了。

Day2 一些吐槽

不願意透露姓名的Q老師："大家都喜歡寫 spfa ，不能理解"

clrs97老師："T1特別好寫" Q老師："反正現場還是沒人過"

FFT, FFT, and FFT everywhere!

T3 是一道好題，只不過給原題數據範圍末尾加了3個0

---------------以下為Day1及之前的回答---------------

Day1 T1 龍與地下城

有一天Q老師問我是不是有一個"試驗次數越多試驗結果越接近期望值"的定理，後來他用中心極限定理作為理論分析的基礎出了這麼一道題。

在出題過程中，Q老師發現這道題目可以使用快速傅里葉變換(Fast Fourier Transform)求解，於是他設置了一個倍增+FFT能通過的部分分，實際情況是一些寫暴力FFT做法的同學遇到了精度不夠的問題，而一位寫剪枝優化過的FFT做法的同學得到了滿分，據出題人透露，另一位得到滿分的選手利用分段求和巧妙地通過了此題。我不知道上帝會不會擲骰子，但是Q老師是會的。

在驗題過程中，doc老師利用C++數學庫中的誤差函數 erf() 在代碼很短的情況下通過了所有的測試點，Q老師決定將題目修改為多組數據捆綁測試，這才使得doc老師需要用十行左右的代碼才能通過。

Day1 T2 蘋果樹

經過doc老師的加強（數據範圍加0），這道樹形依賴背包還多了一個需要考慮的問題——cache miss，這時clrs97老師建議按照節點訪問順序（例如dfs序）分配內存，於是這道題目最終的數據範圍要求選手需要用一維數組模擬二維數組或其他的方法來實現演算法，不過從實際情況來看，這對選手的成績影響不大。

順帶一提，doc老師在考後突然發現前30%的數據只需要排序就沒樹形依賴背包什麼事情了，並為此舉感到惋惜。

Day1 T3 切樹遊戲

一位不願意透露姓名的驗題人寫了一個暴力通過了需要樹的輕重鏈剖分但是不需要快速沃爾什哈達瑪變換(Fast Walsh-Hadamard Transform)的部分，於是這道題對樹的輕重鏈剖分進行了相關數據加強，從現場情況來看，選手們沒有拿到不應得的分數。

clrs97老師在考前發現國際信息學奧林匹克競賽中國隊選拔賽(China Team Selection Competition)的論文答辯環節出現了與該題演算法相關的內容，感覺不妙，然而現場還是沒有人通過此題。

據說出題人沒有考慮分塊做法能否暴力通過鏈的數據。出題人："大家數據結構都很厲害啊/可憐"

Day1 一些吐槽

根據T2與T3的出題人自述，兩道題分別加強自兩場線上比賽的題目，為什麼會選擇線上比賽的題目進行加強，而不是選擇IOI/WF/PA/POI等來源的真題進行加強,加強,再加強呢？請允許我做一個滑稽的表情。

快速XXX變換在OI界的應用程度之廣，是否到了在一天比賽中出兩個的地步？歡迎討論。

我們對標程爆棧感到震驚，為什麼對30000個點的鏈進行深度優先搜索也會造成棧溢出呢？希望能得到解答。

---------------以下為Day0及之前的回答---------------

SDOI 2017 Round 2 Bless All~

比賽結束後我想和大家分享一點驗題的經歷。

聽說考了鏈分治+FWT優化樹上動態DP。。。？

// 題外話：本來互測題想出鏈分治+樹分解+FMT優化集合併卷積的。。。後來覺得太套路了就改成了另一種不那麼套路的題。。。

Cena+動態內存=一定幾率爆炸

如果看SD的水平，大概是暴力就能進隊吧

板子都背不熟的蒟蒻竟然連fft都寫錯

考場現場推一遍fft...

然而第一題的fft快速冪精度會炸呀

雖然我大樣例過了呀

然後day1就15+30+20滾粗了

感覺自己學了假的oi，暴力都寫不出來，連大眾分都到不了了。

講題聽得我一臉懵逼，講之前會多少講之後還是會多少。不得不說這種題sd境內竟然也有人AC？

雖然不知道具體成績但肯定掛出前11了。行吧。明天翻盤概率渺茫，只能明年再來了

正態分布公式X的次方下面那一項是啥來著？我只記得前邊是1/sigma根下2pi 上面是x-mu 下面哪一項是啥來著

然後就狗帶了

順便摸一摸hyd大爺QAQ

感覺還是T1可做啊說實話t3比t2難

暴力分還是很良心的，比去年好很多

不過day2 spfa一分不得。。。