信息學競賽中有哪些令人高呼「還有這種操作」的技巧？

12-30

看到樓上有說隨機化的，就想到了自己的經歷。

APIO2011的第三題要求根據輸入數據輸出yes/no，一個測試數據中可能包含20組輸入。直到考試結束之前半小時都對這題毫無思路，於是當時寫下了不抱任何希望的騙分程序，大概的邏輯如下：

srand(我的生日) print(rand()%2)

跑了一下，樣例居然過了！當時冥冥之中就有一種預感這個程序能騙到分，就把這個作為最終版本交了。

然後最終評測成績出來，這段代碼拿了15分，也就是過了整整3個測試數據！

最後憑藉這個15分拿了國內rank1......

大概是這次比賽RP用完了，後來當年的NOI和WC都滾粗了......

原題的鏈接Problem 2305. -- [Apio2011]猜單詞

初中的時候xjoi上有這麼一個題rp game，大致的意思是輸出兩個數然後spj也會隨機兩個數看看是否一樣。

然後當時所有人沒事情干都在爆這個題，評測機也經常宕機，然後xy就把這個題給ban了。當時大部分人都爆過去了，我爆了幾百發都沒過。

過了幾年騙到了許可權號，有一天突然想起來去查了一下這個題。突然發現在評測機重啟之後第一發提交過這個題的概率特別高，查了一下資料庫發現這些代碼輸出都是一樣的。

（懷疑是spj用了什麼重啟之後就清零的東西srand

然後我強行把這個題開放然後重啟評測機然後快如閃電的a了這個題然後再隱藏

一套操作行雲流水

結果那個時候隔壁在模擬賽重啟那段時間提交的代碼莫名爆0。xy以為是評測機寫掛了讓管理評測機的人查了好久的bug

瞎bb一個小trick，也不是非常驚奇(如果有問題dalao輕噴

比如我們dp的時候經常有f_i,delta這樣的狀態，delta往往有正有負，懶得偏移到正了怎麼辦

直接把第二維開兩倍大小之後，直接寫，這樣只要不用f0,-x就可以了

其實很多讓人眼前一亮的科技現在都爛大街了吧。。。

分塊打表

「求[a,b]之間有多少個數滿足balabalabala，b&<=10^9」

單次Check很快然而枚舉會T

計算前綴和，打表，打不下，怎麼辦？

10^9=10^3 * 10^6，把前綴和序列分塊，一塊10^3，打10^6，還是打得下的

然後查詢的時候找到最近的一個塊端點，從塊端點的下一個位置開始到查詢的值為止枚舉，複雜度O(Check*10^3)

還有一道坑題

Please contact lydsy2012@163.com!

我只能說是A+B Problem的題解……

你可以自行百度，也可以食用以下鏈接（僅供參考）：

題解 P1001 - 百科 - 洛谷

洛谷的A+B Problem題解，食用後，你會發現一個全新的世界。

祝生活愉快。

不是oi碰到的，是ACM/ICPC碰到的。

Problems :: Show Problem

zoj 3952 Fibonacci Sequence Chicken Edition

一讀表就知道，是用一個基於棧的指令集實現一個程序，這裡是求fib的1~30中的任意一項。

基於棧的指令集？有什麼實用的機器碼是基於棧的嗎？

有！Java的！

來，先寫一個Java代碼：

public class Main { public static void main(String[] args) { for(int i=1;i&<10;i++) System.out.println(fib(i)); } public static int fib(int x){ int f2=0,f1=1,tmp; for(int i=1;i&<=x;i++){ tmp=f1+f2; f2=f1; f1=tmp; } return f2; } }

然後我們都知道，Java代碼要javac先編譯一下，編譯成java位元組碼。

但是Javac基本不做優化！還得手工優化一下下：

public static int fib(int x){ int f2=0,f1=1,f,i=0; do{ f=f1+f2; f2=f1; f1=f; i++; }while(i!=x); return f2; }

（不用for循環，不要while循環，要do-while形的。跳回去的代價小。）

然後看java位元組碼，用javap -c命令：

F: oipacmcontestshduacm2017team20170409-17thzju20170409-Eabcsrc&>"C:Program FilesJavajdk1.8.0_131injavap.exe" -c Main.class Compiled from "Main.java" public class Main { public Main(); Code: 0: aload_0 1: invokespecial #1 // Method java/lang/Object."&":()V 4: return


  public static void main(java.lang.String[]);

    Code:

       0: iconst_1

       1: istore_1

       2: iload_1

       3: bipush        10

       5: if_icmpge     24

       8: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;

      11: iload_1

      12: invokestatic  #3                  // Method fib:(I)I

      15: invokevirtual #4                  // Method java/io/PrintStream.println:(I)V

      18: iinc          1, 1

      21: goto          2

      24: return

public static int fib(int); Code: 0: iconst_0 1: istore_1 2: iconst_1 3: istore_2 4: iconst_0 5: istore 4 7: iload_2 8: iload_1 9: iadd 10: istore_3 11: iload_2 12: istore_1 13: iload_3 14: istore_2 15: iinc 4, 1 18: iload 4 20: iload_0 21: if_icmpne 7 24: iload_1 25: ireturn }

然後參考著這個java機器碼，來寫一份這個題的機器碼「彙編」程序：

（有簡單注釋，其中棧底是n，第2、3、4個依次為f2、f1、i）

（這種機器碼不能帶參數，悲傷……只能手工push參數進去）

load (1) push 0 (2 f2) push 1 (3 f1) push 0 (4 i) push 0 push 2 push 5 copy push 0 push 3 push 6 copy add push 3 push 2 copy push 5 push 3 copy push 0 push 5 push 6 copy compare add push 0 push 4 push 5 copy push 0 push 1 push 6 copy sub push 5 jump push 0 push 2 push 5 copy

然後檢查：小於1w個c一定滿足，循環體30行，最多執行30遍，滿足最多執行1000行指令的要求。

然後再寫一個「編譯器」，把這個「彙編」代碼變成全c的形式，最後把編譯出來的代碼提交。

第一發的時候搞錯一個地方（sub那行想錯了，寫成compare了），改了一下，過了！

Java真是一個對競賽有用的編程語言啊（逃

然後當場「嘲諷」了Claris他們隊一波：我是寫了Java代碼，然後藉助Java機器碼做的哦！然後把他們整個隊最後一題給送進死胡同了（他們隊把題目讀錯了2333，不能執行超過1000行指令，理解成整個代碼不超過1000行了。他們也直接寫「彙編」代碼了，但是最終成品的優化不夠，因為題讀錯了，也沒覺得這是個問題……）。

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

P.S. 賽後對答案，發現跑偏了……

正解：直接往棧里堆算好的fib(1)~fib(30)，然後讀入n，用copy指令複製到棧尾，退出……

樹分塊。

考慮每個節點，讓它有 $frac{1}{sqrt n}$ 的概率成為「重點」。那麼就有下面兩條性質：

樹上期望有 $sqrt n$ 個重點。
一個點往上跳 $sqrt n$ 步，期望有一個重點。（推廣：長度為 $sqrt n$ 的路徑上期望有一個重點）

那麼便有：一個點跳到根節點，最多期望走過 $sqrt n$ 個重點。

這個方法的意義是，使得序列上的分塊也可以推廣到樹上。

一個例子，BZOJ1103。

給定一棵樹，初始時所有的邊權都是1。要求處理下面的操作：

把某條邊的邊權改為0（每條邊只會被改一次）
求根到某個點的路徑的邊權和。

定義top[x]為距x最近的祖先重點。我們記錄blo[x]，表示x號重點到top[x]這一段區間的權值和。
另外，預處理出att[x][i]。如果att[x][i]==1，則表示修改i會影響到blo[x]的答案。這一步複雜度 $O(n sqrt n)$ 。

修改操作：考慮所有的重點，如果修改的點對重點x造成影響，則修改blo[x]。期望 $O(sqrt n)$ 。
詢問操作：先暴力往上跳，跳到重點後不停地往top跳。期望 $O(sqrt n)$ 。

這樣，整個題就 $O(nsqrt n)$ 解決了。

這個分塊方法也可以處理路徑權值和之類的各種問題。一般來說序列上可分塊做的，樹上也可以了。

感謝提醒，「重點」應該叫做「關鍵點」。

另外，有用define搞事情的朋友，我喜歡用這個define來調段錯誤：

#define DEBUG printf("Passing [%s] in LINE %d ",__FUNCTION__,__LINE__)

Problem 1494. -- [NOI2007]生成樹計數

這個……實在沒看懂狀壓連通性怎麼做，於是就打了個表，用 Mathematica 的 FindLinearRecurrence 搞了個每個 k 值的線性遞推式，寫了個快速冪。

然後就過了

UOJ 上有個 NOIP2015 的「鬥地主」的加強版

不想出順子了的話，手牌的情況可以表示 S_k = m 表示「有 m 種牌有 k 張」，如 S_2 = 有多少個對兒（不算三張的），然後 dp 一下。

不想想那麼多情況。於是，well，那就把所有情況寫成 if 吧，反正 -O2 會幫我的

CPS 宏是個好東西（見以下宏的 k 參數）

（這段代碼用 C++ 高亮出來是灰的，還不如不高亮）

#define MUT(ix, n, k) do { if (a[ix] + n &>= 0) { a[ix] += n; k; a[ix] -= n; } } while (0)


#define UPDATE ans = min(ans, 1 + dp[a[1]][a[2]][a[3]][a[4]][a[5]])

#define FIND_N(minu, k) do { if (minu == 1) { for (int i = 1; i &<= 5; i ++) if (i == 1 || i == 5) MUT(i, -1, k); else MUT(i, -1, MUT(i-1, +1, k)); } else { for (int i = minu; i &<= 4; i++) if (i == minu) MUT(i, -1, k); else MUT(i, -1, MUT(i - minu, +1, k)); } } while (0)

練習：這段代碼展開後總共有多少個 UPDATE？來數一下吧

這裡的「還有這種操作」是這個神犇們都用了的寫法，但是我太弱了想不出來這個，所以只能寫宏

如何優雅地生成隨機數？

xmk 大神給出了非常優雅的方法，只有一行：

srand ((unsigned long long) new char);

然後你的 rand 就基本沒法搞掉了。沒有 clock 也做到了生成每次運行不一樣的隨機數。

畢竟，「天時」比「地利」，還是，容易那麼一點，只要……

然後隨便找道樹鏈剖分什麼的

你的數組是這樣的么？

int depth[MAXN], top[MAXN], num[MAXN], size[MAXN], ...;

試試這個：

typedef int iarr[MAXN]; iarr depth, top, num, size, ...;

（先佔個坑，有空再更）

記得那是一個下午，老師剛講完啟發式搜索，甩給我們一道最高分90的15數碼讓我們練練手。

就在大家都在摸魚的時候，LP同學從椅子上一躍而起：「噫，我A了！」，他大叫道。

我們趕緊刷新評測記錄，果真如此，LP同學的第一次提交就AC了這道題。我急忙點開詳情，希望看看LP同學使用了什麼奇巧才能夠破解這道連IOI金都沒有AC的題目。

恩，很普通的搜索，很普通的隨機化……最後翻到了main函數的第一行，赫然寫著：

srand(time(0));

腦中迴響著「這是LP同學的一小步，OIer們的一大步」。

後來我們將其稱為歷史性的一刻。

LP他不上知乎吧（逃

非信息競賽選手，只是在刷過一些 OJ，記得大二上 DSA CST 的時候，作業在鄧俊輝老師自己搭的一個 OJ (TOJ) 上做 PA，然後有一道題卡住了，找不到錯誤的輸入樣例，但是提交就是錯誤。不過 TOJ 是會給出內存信息的，並且是按 4KB 一個塊申請的。

於是先估算出每次申請內存塊的大小 BLOCK_SIZE，然後每次只執行一條 new char[BLOCK_SIZE * n]，n 是想要的數據，連續提交了好多次，成功拿到一條錯誤的數據。然後 debug，AC。

我看很多OJ都會給錯誤的數據內存信息，只要大致估算出每次申請的內存塊大小，就能通過各種奇技淫巧推出錯誤的輸入樣例，僅供參考。

最後這道題整整提交了 134 次（感覺老師看這個提交記錄可能是看智障的眼神（

區間加區間kth的nsqrt( n )logn演算法。。。

用了一些分塊小技巧

當時覺得神了

Problem 4867. -- [Ynoi2017]舌尖上的由乃

（我自己想的做法和每次加的值的值域有關，也是個奇怪東西，然後被ccz大爺艹標程了）

然後還有某不知名維護序列專用數據結構，挺玄學的，可惜現在不能掛上來

大概是這樣的一個數據結構

還有YNOI2018的兩道題，可惜現在不能掛上來

（YNOI不是雲南OI）

現在你見到的很平凡的解題方法在剛被發明時都是這種技巧。

參考評論區更新一個版本

#define $ if(DEBUG)

#define DEBUG 1 // or 0

比較喜歡這個版本，不僅寫起來用起來都省事，而且多條語句的時候用的也是花括弧，和語言規範更加契合。

經評論區 @xmcp 提醒，使用此版本需注意外部 if 語句的 else 配對問題，避免下方可能存在的 else 與 if(DEBUG) 配對。

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

退役 C++ 選手答一發，僅作拋磚引玉

C 系的宏可以有很多應用，比如簡化一些常用函數的調用或者是 for 語句，但是我一般只用 debug 宏。

#define DEBUG

#ifdef DEBUG

#define debug(a) a

#else

#define debug(a)

#endif

（原諒爪機打不出格式）

上邊語句讓 debug(...) 裡面的語句依據是否定義 DEBUG 宏決定執行與否，尤其適合我等面向輸出調試的蒟蒻來快速開關 debug 中的輸出（逃

其實我覺得大多數人都是在說"這類題還可以這樣做？"而不是"競賽中還有這種操作？"我舉一個例子吧。

如果你想知道一道題的某個數據大概是多少，可以去二分。方法是提交一個程序。讀入這個數據後若大於某個值，就死循環；反之，則輸出一個格式正確的答案。通過返回蛙還是 TLE 來判斷。

《一道防AK好題》

隨機法求最大團

每次隨機一個排列，按照排列的順序貪心選擇最多的點加入答案

一般50個點基本跑個千把次就出解了，美滋滋

50~100個點用這個方法也能騙到可觀的分

隨機法求HAOI 2006 均分數據問題

每次隨機一個排列，然後在排列上隨機幾段連續的區間作為答案

跑個百萬把次就行……

論時限5秒的題用6sAC是一種怎樣的體驗

隨機調整替罪羊樹alpha參數

TC上某題，寫的平衡樹總被卡常，只好用這方法提交多次，終於得過……

以前，剛聽說ac自動機的時候。

「woc，還有這種東西」

（逃）

正經答題：所有做題人的非預期亂搞都是符合這道題描述的。只就是我為什麼反對acm賽制，反對一群人要求亂搞減分的原因。

高級暴力本身就是一種智慧，只用一小部分的資源去完成絕大多數情況。

好像是去年還是前年吧，湖南NOI選拔賽的時候發生的事情

我當時已經退坑搞單片機了，朋友還在為了打OI而奮鬥

某天下午他在群里咆哮說這考試是什麼玩意，我順口就回了一句什麼題目把你整成這樣啊

然後

第一題擴散性乖離

第二題 osu ctb

我還以為我打開了假的題目

基於變換合併的動態 DP 演算法

通過重新定義加法和乘法，結合矩陣的結合律，讓一些 DP 可以支持單點修改並在修改後快速求出 DP 值。計數類和最優化 DP 都可以這麼做。

對於序列上的動態 DP，只需要用線段樹維護區間矩陣積就可以支持單點修改和查詢某個區間的 DP 值。

對於有根樹的動態 DP，首先輕重鏈剖分成多條重鏈，按照重鏈的順序求值，每條重鏈上就是一個序列 DP，套用序列上的演算法即可。可以詢問子樹 DP 值。還可以結合 LCT 獲得更好的複雜度，還支持 Link/Cut 和換根。

參考：http://immortalco.blog.uoj.ac/blog/2625

對sam的狀態按maxl基數排序可以得到拓撲序，常數比bfs小得多