搞oi/acm的大神為什麼要#define N 1000+10？

01-01

請問
#define N 1000+10
int a[N];
或
#define N 1000

int a[N+5];
相較於
#define N 1000
int a[N];
有什麼優勢呢？

我覺得這不像編程的高手, 倒像是搞OI的.

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

對於搞OI的嘛, 每個人或多或少都碰到過數組overflow的問題, 有時候不明所以能調試得欲仙欲死.

想當年某段代碼中我開了兩個數組a和b, 然後Debug了一個下午為什麼改a, b也會跟著變.

這是寫ACM或者OI競賽程序的習慣。並不是像很多樓提到的擔心出題人不按規則來，一般出題人手抖也是多一個零，加10根本救不回來。

主要的考慮有以下幾個（默認為c++）：

0) N個元素的題目經常會從1到N編號，此時要麼輸入都-1要麼數組定義+1，顯然前者會提高調試難度，後者更簡單有效。

1) DP題目中初始狀態的存在。例如長度為N的數列a[1..N]求前綴和，則有s[0]=0，s[i]=s[i-1]+a[i]，1&<=i&<=N，從而s必須定義為int[N+1]

2) 網路流題目中源和匯的存在。例如N個點的圖求網路流，添加源和匯則有N+2個點。

3) 計算幾何題目中邊界框的存在。例如求N條直線的半平面交，需要添加(-inf,-inf)到(inf,inf)的矩形框作為強制外邊界（以保證解區域有限大，從而不用處理特殊情況），這樣就會有N+4條邊。

綜上，有一定競賽經驗的選手都會在數據規模N的題目定義N+x（x往往&>=5)的數組，目的是為了使得演算法可以將人工添加的特殊元素和輸入的元素統一處理，降低編程複雜度以提高解題速度，久而久之就養成習慣了。

話說，為什麼都用define啊……

在ACMer基本都是C++黨的情況下，const int MAXN=1000;不是更安全且更值得推薦嗎？

ACM/OI圈中數組都有開大一點的習慣，

加多少，怎麼加的習慣各不相同，這種做法的來源已不可考，但是在一代代前人寫博客/直接言傳身教的影響下，這個習慣已被ACM/OI圈所接受、默認。

這個習慣如此有生存力，個人感覺可能有以下原因：

1、如果寫到一半發現下標從0開始不合適，想改成下標從1開始的時候，養成這種習慣，數組多那麼一點，那隻需要改游標附近的代碼即可，不需要回頭再改改數組範圍——回頭改是最容易被遺忘的。

2、如果是char數組，總有人會忘了最後有個來作為結束符的，而這個就要一個數組位置，一般題目里告訴了你字元串長度，但是，忘了多加1就可能要覆蓋到別地導致莫名其妙的Wrong Answer/Runtime Error/Time Limit Exceeded了，更別提半路想起來下標從1開始更方便的時候，數組大小要長度+2不是+1了，那就乾脆+5、+10。

上面都是還算正常的，下面的就（也不是沒有）……

1、拿多出來的那些數組全0位置當邊界，省事，也不用判斷邊界寫一大堆了

2、受到過奇怪的題目的坑害，知道真相後，對出題人給的數據範圍喪失了信任

3、以前莫名其妙數組開剛剛好，交上去居然WA/RE了，聽別人意見，+10，居然就過了，就過了，就過了~我乾脆也每個數組都+10、+10、+10

4、+5、+10很順口啊，看起來很「整」啊

===========================

話說define定義常量里直接做加法很危險的啊！

比如，我想開個線段樹，維護1~100000

如果define的是 #define N 100000+10

結果線段樹數組開成了int maxnum[N*4];

直接起飛了！！！而且還很難看出來！

我反正是沒事絕對不玩define的，const int 就挺好的。

在隊友的調教下我已經養成了能用1000絕不用1001的習慣。

後者有個壞處，如果代碼寫搓了，哪裡有個不期望的數組越界，但是越的不明顯，這種情況下會比較難debug，因為越界之後可能還是在這個數組的範圍內，對別的變數沒有破壞性修改。而前者的話，越界之後要麼程序掛掉，要麼修改了其它變數的值，這時候就能比較容易的發現程序的異常（比如結果不對啦之類的）。

對於那些數據規模和題目描述不一致的題目，我只想對出題人說：吔屎啦你！

萬一訪問越界還（可能）能搶救一下

我一般會湊整開成1024

然後N*2就雞寄了？

笑，編程高手怎麼會糾結於數組越界這種新手問題。

int a[1000][1000];

int b[1000][1005];

如果按第二維優先遍歷這兩個數組，它們消耗的時間是不一樣的。

通常後者消耗的時間更少。

這主要是由cpu cache機製造成的。

cpu cache的block大小通常是2的冪，而1005是一個奇數，它們是互素的。

所以cache衝突的概率極低，理論上只會在cache全部用完後才會發生替換。

而1000是個偶數，衝突的概率更高，1010稍微好點，1024就是一定衝突了。

在一維數組上這種衝突有時也會發生，但情況比較少（不一定）。

很多人只學到了高手寫代碼的姿勢，卻不理解高手的深謀遠慮啊。

這個+10 體現出了人與人之間的基本信任已經消失殆盡了

其實……我就是頂格黨的，能寫N就不寫N+1。

少一些數組溢出但是莫名其妙混到AC的可能性，也少一點面對錯誤數據莫名其妙AC的可能性，但是也避免數組溢出但是報告成WA然後打死調不出來的可能性。顯然如果對自己代碼和出題人比較有信心的話，會更傾向於不加上界。

但是不管是哪個黨，這裡的trade off的邏輯是不變的，寫+10和不寫都是考慮了tradeoff以後形成的習慣。

這怎麼可能有優勢啊。因為 oj 的編碼的目的就是用最快速度形成代碼並 AC。當以這個為目標時，任何編碼規範都要為此讓位。所以 oj 的一些技巧只能是在 oj 這個背景里存在。對數組加一點點裕度，就索引願意從 0 從 1都可以了。對數組邊界越界的考慮可以放寬，因為編程里對數組邊界部分經常要單獨仔細考慮，需要花一定時間，很繁瑣。但沒有人會鼓勵你這麼寫代碼或者把這當做什麼可以上檯面的技巧。工作里寫代碼，只有以嚴謹，穩定，可靠，可維護，可擴展性為目標，而不是你的提交速度。

當然是提升辨識度啊，當年學校只有幾個人搞OI的時候，+5 +7 +9 +10 +12 分別被幾個人佔了，這樣一來看到代碼就知道是誰的坑了 Orz

高手用的是#define N (1000+10)

除了以上的理由，我通常＋7，因為大一的時候，翻知乎有類似的問題，說的是，數組大小如果是個素數，內存分配速度會快？具體怎麼說的我忘了（弱說的有問題的話麻煩評論告訴我修正一下(? ′?` ?)么么噠（而通常1e9+7之類的會是個素數，所以我通常+7，或者+9，以上！

並沒有什麼*用，反正編譯器都會給你計算出來這個常數是多少

另外一種情況是為了是邏輯/意圖更清晰，比如:

#define M 1024*1024

所以不排除1000 + 10，這裡的10是為了表示某種意圖

define有毒，用的時候最好把1000+10加括弧，或者改用const。一次沒加括弧，用了N*N。RE了一次。死活不知道哪越界。。

我不贊同高手會使用 #define N 1000+10

一般是這樣吧：constexpr int MAX_N = 1000 + 10;

至少也要加個括弧 #define N (1000 + 10).

N一般表示problem size，這樣的話可以避免因為數組開小了而導致的有些時候難以發現的BUG。至於加幾，只是個人習慣而已，你想的太多了。

+10怎麼夠？

前幾天訓練時一個費用流調了4個小時沒調出來差點沒被隊友打死

最後發現實際數據範圍是題面的兩倍

當初作為OI小白的時候偶爾會迷之爆界然後WA，所以無腦式的多開大一點空間，有備無患。

……

後來發現改不掉了，索性不改了，多開一點點有時候還能用來寫個標誌位。

其實我感覺並沒有什麼特殊含義，你要是能算精確並保證不會爆界，不多開也是可以的。

以上。