如何評價NOIP2016卡常數?

時間 2021-05-31 15:50:13

1樓:immortalCO

針對題目的回答在後面。我們先來分析一下實際的情況。

對於出題人來說,時間限制的決定其實是乙個比較糾結的事情,因為不同的實現方式可能會是巨大的。

這裡舉乙個例子,比如 TC605Hard 一題(BZOJ4621),同樣是 n=500 的資料範圍,同樣是 O(n^3) 的複雜度,實際的效率差距可能達到 50 倍之多。在這種情況下,時間限制就是乙個十分難以確定的因素:如果你是命題人,並且你的演算法擁有較高效率,就算你設定了高達 10~20 倍於標程執行時間的時間限制,也仍然可能造成複雜度正確的演算法嚴重超時。

(具體的優化方法我可能會在明年 WC 上的營員交流中提到)

這種巨大的常數差異的危害在於出題人難以預料。出題人不可能考慮到所有正確(或者錯誤)的演算法,只能根據自己的標程效率確定時間限制。而標程的效率過高、過低都會導致時間限制的不合理,如 NOIP2016 中,D2T2 的正確複雜度演算法(因為常數過大)超時,而 D2T3 的錯誤複雜度演算法卻(因為常數較小)無壓力通過了,而這些情況的的發生一般並不是出題人的本意。

因此,時間限制是有一定的隨機性的。

結論:由於上述不確定性,我們作為選手,唯一能做的就是在優化複雜度的前提下盡量優化實現的常數,比如避免使用 cin/cout 等進行輸出,及在陣列呼叫上記錄頭指標等。只要優化得當,分數一定會是不降的(正確複雜度的演算法能拿到滿分,錯誤複雜度演算法能多通過一些測試點)。

因此,我們要 RCSYHCWYZXG。

2樓:於紀平

貼std:

並沒有用任何特殊的卡常數技巧

3樓:

請把疑似兩字去掉。

選手需要考慮常數,但常數不能成為主要障礙。

你寫乙個常數為10之類的臭程式,而且還有正常優化的餘地,是選手的問題。而這次d2t2,幾乎所有被卡常的人都只超了一點點,現在還把鍋甩給選手。

如果出題人本身用了各種刁鑽精奇的手法優化常數,然後還以標程的2倍開時限,明擺著不讓人過。

出題人遭雷劈。

update-161130

上面把std貼出來了,如果只有內嵌彙編才叫特殊卡常技巧的話就當我什麼也沒說。

我再說一遍。你寫乙個常數為10之類的臭程式,而且還有正常優化的餘地,是選手的問題。而這次d2t2,幾乎所有被卡常的人都只超了一點點。

如何評價 NOIP2018 ?

不要以為你是出題人你就可以亂出重題,不要以為你不會出題就出重題。你沒有權利!CCF,就是出題人享有最高權力,你認為我罵你,你就噴我吧,你甚至可以讓我禁賽。但是,群眾的眼睛是雪亮的! 個人看到了以下的事件怒答 NOI 全國青少年資訊學奧林匹克競賽 NOI 全國青少年資訊學奧林匹克競賽 NOI 全國青少...

如何評價NOIP2021?

T1秒切 然後T2沒有大例解會有點害怕但還是不管了 T3打了乙個很隨便的貪心 隨便交換看看答案有沒有變小,但沒有退火 T4打暴力 然後分數是這樣 T3 32分是我沒想到的,原本覺得能過n 4就很不錯了這也是我第一次NOIp能過其他省的1 獎分數線可惜澳門最強的那幾個都翻車 不然澳門是很有可能多拿乙個...

如何評價 NOIP 2017 初賽

lsh 當年我的數學水平還在巔峰的時候初賽整天考些編碼格式啊,網路協議啊,物件導向啊,體系結構啊 exm?我tm在考noip?現在我終於掌握了這些東西,然後今天本想虐虐初賽,然後發現初賽改考數學題了?exm?滾粗 張瑯小強 利申 退役複賽的廣東高三狗。全程慵懶做題,提前30min交卷,送監考老師乙個...