新 版 騙 分 導(dǎo) 論

THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD

蒟 蒻 的 寶 書

目錄

第1章 緒論

第2章 從無解出發(fā)

2.1 無解情況

2.2 樣例——白送的分?jǐn)?shù)

第3章 “艱苦樸素永不忘”

3.1 模擬

3.2 萬能鑰匙——DFS

第4章 騙分的關(guān)鍵——猜想

4.1 聽天由命

4.2 猜測答案

4.3 尋找規(guī)律

4.4 小數(shù)據(jù)殺手——打表

第5章 做貪心的人

5.1 貪心的算法

5.2 貪心地得分

第6章 C++的福利

6.1 快速排序

6.2 “如意金箍棒”

第7章 “寧為玉碎，不為瓦全”

第8章 實(shí)戰(zhàn)演練

第9章 結(jié)語

第1章 緒論

在Oier中，有一句話廣為流傳：

任何蒟蒻必須經(jīng)過大量的刷題練習(xí)才能成為大牛乃至于神牛。

這就是著名的lzn定理。然而，我們這些蒟蒻們，沒有經(jīng)過那么多歷練，卻要和大牛們同場競技，我們該怎么以弱勝強(qiáng)呢？答案就是：

騙分 那么，騙分是什么呢？騙分就是用簡單的程序（比標(biāo)準(zhǔn)算法簡單很多，保證蒟蒻能輕松搞定的程序），盡可能多得騙取分?jǐn)?shù)。

讓我們走進(jìn)這本《新版騙分導(dǎo)論》，來學(xué)習(xí)騙分的技巧，來挑戰(zhàn)神牛吧！

第2章 從無解出發(fā)

2.1 無解情況

在很多題目中都有這句話：“若無解，請輸出-1.”

看到這句話時(shí)，騙分的蒟蒻們就欣喜若狂，因?yàn)椤獢?shù)據(jù)中必定會(huì)有無解的

情況！那么，只要打出下面這個(gè)程序：

printf(“-1”);

就能得到10分，甚至20分，30分！

舉個(gè)例子：

NOIP2012第4題，文化之旅

題目描述 Description

有一位使者要游歷各國，他每到一個(gè)國家，都能學(xué)到一種文化，但他不愿意學(xué)習(xí)任何一種文化超過一次（即如果他學(xué)習(xí)了某種文化，則他就不能到達(dá)其他有這種文化的國家）。不同的國家可能有相同的文化。不同文化的國家對其他文化的看法不同，有些文化會(huì)排斥外來文化（即如果他學(xué)習(xí)了某種文化，則他不能到達(dá)排斥這種文化的其他國家）。

現(xiàn)給定各個(gè)國家間的地理關(guān)系，各個(gè)國家的文化，每種文化對其他文化的看法，以及這位使者游歷的起點(diǎn)和終點(diǎn)（在起點(diǎn)和終點(diǎn)也會(huì)學(xué)習(xí)當(dāng)?shù)氐奈幕?，國家間的道路距離，試求從起點(diǎn)到終點(diǎn)最少需走多少路。

輸入描述 Input Description

第一行為五個(gè)整數(shù)N，K，M，S，T，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，依次代表國家個(gè)數(shù)（國家編號(hào)為1到N），文化種數(shù)（文化編號(hào)為1到K），道路的條數(shù)，以及起點(diǎn)和終點(diǎn)的編號(hào)（保證S不等于T）；

第二行為N個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，其中第i個(gè)數(shù)Ci，表示國家i的文化為Ci。

接下來的K行，每行K個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，記第i行的第j個(gè)數(shù)為aij，aij= 1表示文化i排斥外來文化j（i等于j時(shí)表示排斥相同文化的外來人），aij= 0表示不排斥（注意i排斥j并不保證j一定也排斥i）。

接下來的M行，每行三個(gè)整數(shù)u，v，d，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示國家u與國家v有一條距離為d的可雙向通行的道路（保證u不等于v，兩個(gè)國家之間可能有多條道路）。

輸出描述 Output Description

輸出只有一行，一個(gè)整數(shù)，表示使者從起點(diǎn)國家到達(dá)終點(diǎn)國家最少需要走的距離數(shù)（如果無解則輸出-1）。

樣例輸入 Sample Input

輸入樣例1

2 2 1 1 2

1 2 0 1 1 0 1 2 10

輸入樣例2

2 2 1 1 2

1 2 0 1 0 0 1 2 10

樣例輸出Sample Output

輸出樣例1

-1

輸出樣例2

10

數(shù)據(jù)范圍及提示 Data Size & Hint

【輸入輸出樣例1說明】

由于到國家2必須要經(jīng)過國家1，而國家2的文明卻排斥國家1的文明，所以不可能到達(dá)國家2。

【輸入輸出樣例2說明】

路線為1 -> 2。

【數(shù)據(jù)范圍】

對于20%的數(shù)據(jù)，有2≤N≤8，K≤5；

對于30%的數(shù)據(jù)，有2≤N≤10，K≤5；

對于50%的數(shù)據(jù)，有2≤N≤20，K≤8；

對于70%的數(shù)據(jù)，有2≤N≤100，K≤10；

對于100%的數(shù)據(jù)，有2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u,v≤N，1≤d≤1000，S≠T，1 ≤S, T≤N。

這道題看起來很復(fù)雜，但其中有振奮人心的一句話“輸出-1”，我考試時(shí)就高興壞了（當(dāng)時(shí)我才初一，水平太爛），隨手打了個(gè)printf(“-1”);,得10分。

2.2 樣例——白送的分?jǐn)?shù)

每道題目的后面，都有一組“樣例輸入”和“樣例輸出”。它們的價(jià)值極大，不僅能初步幫你檢驗(yàn)程序的對錯(cuò)（特別坑的樣例除外），而且，如果你不會(huì)做這道題（這種情況蒟蒻們已經(jīng)司空見慣了），你就可以直接輸出樣例！

例如美國的USACO，它的題目有一個(gè)規(guī)則，就是第一組數(shù)據(jù)必須是樣例。那么，只要你輸出所有的樣例，你就能得到100分（滿分1000）！這是相當(dāng)可觀的分?jǐn)?shù)了。

現(xiàn)在，你已經(jīng)掌握了最基礎(chǔ)的騙分技巧。只要你會(huì)基本的輸入輸出語句，你就能實(shí)現(xiàn)這些騙分方法。那么，如果你有一定的基礎(chǔ)，請看下一章——我將教你怎樣用簡單方法騙取部分分?jǐn)?shù)。

第3章 “艱苦樸素永不忘”

本章的標(biāo)題來源于《學(xué)習(xí)雷鋒好榜樣》的一句歌詞，但我不是想教導(dǎo)你們學(xué)習(xí)雷鋒精神，而是學(xué)習(xí)騙分！

看到“樸素”兩個(gè)字了嗎？它們代表了一類算法，主要有模擬和DFS。下面我就來介紹它們在騙分中的應(yīng)用。

3.1 模擬

所謂模擬，就是用計(jì)算機(jī)程序來模擬實(shí)際的事件。例如NOIP2012的“尋寶”，就是寫一個(gè)程序來模擬小明上藏寶塔的動(dòng)作。

較繁的模擬就不叫騙分了，我這里也不討論這個(gè)問題。

模擬主要可以應(yīng)用在騙高級(jí)數(shù)據(jù)結(jié)構(gòu)題上的分，例如線段樹。下面舉一個(gè)例子來說明一下。

排?隊(duì)(USACO 2007 January Silver)

【問題描述】

每天，農(nóng)夫約翰的N（1≤N≤50000）頭奶?？偸前赐豁樞蚺藕藐?duì)，有一天，約翰決定讓一些牛玩一場飛盤游戲（Ultimate Frisbee），他決定在隊(duì)列里選擇一群位置連續(xù)的奶牛進(jìn)行比賽，為了避免比賽結(jié)果過于懸殊，要求挑出的奶牛身高不要相差太大。

約翰準(zhǔn)備了Q（1≤Q≤200000）組奶牛選擇，并告訴你所有奶牛的身高Hi（1≤ Hi ≤106）。他想知道每組里最高的奶牛和最矮的奶牛身高差是多少。

注意：在最大的數(shù)據(jù)上，輸入輸出將占據(jù)大部分時(shí)間。

【輸入】

第一行，兩個(gè)用空格隔開的整數(shù)N和Q。

第2到第N+1行，每行一個(gè)整數(shù)，第i+1行表示第i頭奶牛的身高Hi

第N+2到第N+Q+1行，每行兩個(gè)用空格隔開的整數(shù)A和B，表示選擇從A到B的所有牛（1 ≤ A ≤ B ≤ N）

【輸出】

共Q行，每行一個(gè)整數(shù)，代表每個(gè)詢問的答案。

輸入樣例 輸出樣例

6 3 1 7 3 4 2 5 1 5 4 6 2 2 6

3 0

對于這個(gè)例子，大牛們可以寫個(gè)線段樹，而我們蒟蒻，就模擬吧。

附模擬程序：

for(int i=1;i<=q;i++){

scanf(“%d%d”,&a,&b);int min=INT_MAX,max=INT_MIN;for(int i=a;i<=b;i++){if(h[i]<min)min=h[i];if(h[i]>max)max=h[i];}printf(“%d\n”,max-min);}

程序簡潔明了，并且能高效騙分。本程序得50分。

3.2 萬能鑰匙——DFS

DFS是圖論中的重要算法，但我們看來，圖論神馬的都是浮云，關(guān)鍵就是如何騙分。下面引出本書的第2條定理：

DFS是萬能的。

這對于你的騙分是至關(guān)重要的。

比如說，一些動(dòng)態(tài)規(guī)劃題，可以DFS；數(shù)學(xué)題，可以DFS；剪枝的題，更能DFS。

下面以一道省選題為例，解釋一下DFS騙分。

例題：

NOIP2003，采藥

題目描述 Description

辰辰是個(gè)天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?/p>

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

輸入描述 Input Description

輸入第一行有兩個(gè)整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一個(gè)空格隔開，T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。

輸出描述 Output Description

輸出包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。

樣例輸入 Sample Input

70 3 71 100 69 1 1 2

樣例輸出 Sample Output

3

數(shù)據(jù)范圍及提示 Data Size & Hint

對于30%的數(shù)據(jù)，M<=10；

對于全部的數(shù)據(jù)，M<=100。

這題的方法很簡單。我們瞄準(zhǔn)20%的數(shù)據(jù)來做，可以用DFS枚舉方案，然后模擬計(jì)算出最優(yōu)解。附一個(gè)大致的代碼：

void?DFS(int d,int c){if(d==n){if(c>ans)ans=c; return;}

DFS(d+1,c+w[i]);

DFS(d+1,c);}

第4章 騙分的關(guān)鍵——猜想

4.1 聽天由命

如果你覺得你的人品很好，可以試試這一招——輸出隨機(jī)數(shù)。

先看一下代碼：

#include<stdlib.h>#include<time.h>//以上兩個(gè)頭文件必須加

srand(time(NULL));//輸出隨機(jī)數(shù)前執(zhí)行此語句printf(“%d”,rand()%X);//輸出一個(gè)0~X-1的隨機(jī)整數(shù)。

這種方法適用于輸出一個(gè)整數(shù)（或判斷是否）的題目中，答案的范圍越小越好。讓老天決定你的得分吧。

據(jù)說，在NOIP2013中，有人最后一題不會(huì)，憤然打了個(gè)隨機(jī)數(shù)，結(jié)果得了70分啊!!

4.2 猜測答案

有些時(shí)候，問題的答案可能很有特點(diǎn)：對于大多數(shù)情況，答案是一樣的。

這時(shí)，騙分就該出手了。

你需要做的，就是發(fā)掘出這個(gè)答案，然后直接輸出。

有時(shí)，你需要運(yùn)用第3章中學(xué)到的知識(shí)，先寫出樸素算法，然后造一些數(shù)據(jù)，可能就會(huì)發(fā)現(xiàn)規(guī)律。

例如，本班月賽中有一道題：

炸毀計(jì)劃

【問題描述】

皇軍侵占了通往招遠(yuǎn)的黃金要道。為了保護(hù)渤海通道的安全，使得黃金能夠順利地運(yùn)送到敵后戰(zhàn)略總指揮地延安，從而購買戰(zhàn)需武器，所以我們要通過你的程序確定這條戰(zhàn)略走廊是否安全。

已知我們有N座小島，只有使得每一個(gè)小島都能與其他任意一個(gè)小島聯(lián)通才能保證走廊的安全。每個(gè)小島之間只能通過若干雙向聯(lián)通的橋保持聯(lián)系，已知有M座橋(Ai,Bi)表示第i座橋連接了Ai與Bi這兩座城市。

現(xiàn)在，敵人的只能炸毀其中一座橋，請問在僅僅炸毀這一座橋的情況下，能否保證所有島嶼安全，都能聯(lián)通起來。

現(xiàn)在給出Q個(gè)詢問Ci，其中Ci表示橋梁編號(hào)，橋梁的編號(hào)按照輸入順序編號(hào)。每個(gè)詢問表示在僅僅炸毀第Ci座橋的情況下能否保證所有島嶼安全。如果可以，在輸出文件當(dāng)中，對應(yīng)輸入順序輸出yes，否則輸出no（輸出為半角英文單詞，區(qū)分大小寫，默認(rèn)為小寫，不含任何小寫符號(hào)，每行輸出一個(gè)空格，忽略文末空格）。

【輸入格式】

第一行 三個(gè)整數(shù)N，M，Q，分別表示島嶼的個(gè)數(shù)，橋梁的個(gè)數(shù)和詢問的個(gè)數(shù)。

第二行到第M+1行 每行兩個(gè)整數(shù)。第i+1行有兩個(gè)整數(shù)Ai Bi表示這個(gè)橋梁的屬性。

第M+2行 有Q個(gè)整數(shù)Ci表示查詢。

【輸出格式】

Q行，表示查詢結(jié)果。

【樣例】

http://destroy.in

destroy.out

2 1 1

1 2

1

no

【樣例范圍】

對于80%的數(shù)據(jù)，N≤100。

對于100%的數(shù)據(jù)，N≤1000，N,Q≤M≤2000 。

你發(fā)現(xiàn)問題了嗎？那么多座橋，炸一座就破壞島嶼的聯(lián)系，可能性微乎其微（除非特別設(shè)計(jì)數(shù)據(jù)）。

那么，我們的騙分策略就出來了：對于所有詢問，輸出yes.果然，此算法效果不錯(cuò)，得80分。

現(xiàn)在知道猜測答案的厲害了吧？

4.3 尋找規(guī)律

首先聲明：本節(jié)講的規(guī)律不是正當(dāng)?shù)乃惴ㄒ?guī)律，而是數(shù)據(jù)的特點(diǎn)。

某些題目會(huì)給你很多樣例，你就可以觀察他們的特點(diǎn)了。

有時(shí)，數(shù)據(jù)中的某一個(gè)（或幾個(gè)）數(shù)，能通過簡單的關(guān)系直接算出答案。

只要你找到了規(guī)律，在很多情況下你都能得到可觀的分?jǐn)?shù)。

這樣的題目大多出現(xiàn)在NOI或更高等級(jí)的比賽中，本人蒟蒻一個(gè)，就不舉例了。

傳說某人去省選時(shí)專門琢磨數(shù)據(jù)的規(guī)律，結(jié)果有一題得了30分。

4.4 小數(shù)據(jù)殺手——打表

我認(rèn)識(shí)一個(gè)人，他在某老師家上C語言家教，老師每講一題，他都喊一句：“打表行嗎？”

他真的是打表的忠實(shí)粉絲。表雖然不能亂打，但還是很有用的。

先看一個(gè)例子：

NOIP2003 棧

題目描述 Description

棧是計(jì)算機(jī)中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡單的說，棧就是限制在一端進(jìn)行插入刪除操作的線性表。

棧有兩種最重要的操作，即pop（從棧頂彈出一個(gè)元素）和push（將一個(gè)元素進(jìn)棧）。

棧的重要性不言自明，任何一門數(shù)據(jù)結(jié)構(gòu)的課程都會(huì)介紹棧。

寧寧同學(xué)在復(fù)習(xí)棧的基本概念時(shí)，想到了一個(gè)書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙

寧寧考慮的是這樣一個(gè)問題：一個(gè)操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n。

現(xiàn)在可以進(jìn)行兩種操作，

1.將一個(gè)數(shù)，從操作數(shù)序列的頭端移到棧的頭端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作）

2.將一個(gè)數(shù)，從棧的頭端移到輸出序列的尾端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）

使用這兩種操作，由一個(gè)操作數(shù)序列就可以得到一系列的輸出序列，下圖所示為由1 2 3生成序列2 3 1的過程。（原始狀態(tài)如上圖所示） 。

你的程序?qū)o定的n，計(jì)算并輸出由操作數(shù)序列1，2，…，n經(jīng)過操作可能得到的輸出序列的總數(shù)。

輸入描述 Input Description

輸入文件只含一個(gè)整數(shù)n（1≤n≤18）

輸出描述 Output Description

輸出文件只有一行，即可能輸出序列的總數(shù)目

樣例輸入 Sample Input

3

樣例輸出 Sample Output

5

這題看似復(fù)雜，但數(shù)據(jù)范圍太小，N<=18。所以，騙分程序就好寫了：

int a[18]={1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};

scanf(“%d”,&n):

printf(“%d”,ans[n-1]);

測試結(jié)果不言而喻，AC了。

學(xué)完這一章，你已基本掌握了騙分技巧。

下面的內(nèi)容涉及一點(diǎn)算法知識(shí)，難度有所增加。蒟蒻中的蒟蒻可以止步于此了。

第5章 做貪心的人

5.1 貪心的算法

給你一堆紙幣，讓你挑一張，相信你一定會(huì)挑面值最大的。其實(shí)，這就是貪心算法。

貪心算法是個(gè)復(fù)雜的問題，但你不用管那么多。我們只關(guān)心騙分。給你一個(gè)問題，讓你從一些東西中選出一些，你就可以使用貪心的方法，盡量挑好的。

舉個(gè)例子：這是我們的市隊(duì)選拔的一道題。

有趣的問題

【問題描述】

2013 年的NOIP 結(jié)束后， Smart 發(fā)現(xiàn)自己又被題目碾壓了，心里非常地不爽，于是

暗下決心瘋狂地刷數(shù)學(xué)題目，做到天昏地暗、廢寢忘食，準(zhǔn)備在今年的中考中大展身手。

有一天，他在做題時(shí)發(fā)現(xiàn)了一個(gè)有趣的問題：

給定n 個(gè)二元組(ai, bi) i)，記函數(shù)：

y=100*sigma(ai)/sigma(bi);

將函數(shù)y 的值四舍五入取整。

現(xiàn)將n 個(gè)二元組去掉其中的k 個(gè)計(jì)算一個(gè)新的y 值（也四舍五入取整），均能滿足：y <= z ，求出最小的z值。Smart 想讓你幫他一起找出最小的z值。

【輸入格式】

輸入包含多組測試數(shù)據(jù)。每組測試數(shù)據(jù)第一行兩個(gè)整數(shù)：n和k；第二行為n 個(gè)數(shù)：

a1 a2 …… an；第三行為；n 個(gè)數(shù)： b1 b2 …… bn。

輸入數(shù)據(jù)當(dāng)n、k 均為0 時(shí)結(jié)束。

【輸出格式】

對于每組測試數(shù)據(jù)輸出一行，即找出的最小的冘值。

注意：為避免精度四舍五入出現(xiàn)誤差，測試點(diǎn)保證每個(gè)函數(shù)值與最終結(jié)果的差值至

少為0.001 。

【樣例】

http://math.in

3 1 5 0 1 5 1 6 4 2 1 2 7 9

5 6 7 9

0 0

math. out

83 100

【數(shù)據(jù)范圍】

對于40% 的數(shù)據(jù)： n≤20；

對于70% 的數(shù)據(jù)： n≤1000；

對于100% 的數(shù)據(jù)： n≤10000，ai,bi 都在int 范圍內(nèi)。

這題讓人望而生畏，但我們有貪心的手段。

每個(gè)二元組的a值是乘到答案中的，所以a越大越好，那么只要選擇出最小的k個(gè)去掉即可。

代碼就不寫了，因?yàn)檫@個(gè)涉及到下一章的內(nèi)容：排序。

此代碼得20分。

5.2 貪心地得分

我們已經(jīng)學(xué)了很多騙分方法，但他們中的大多效率并不高，一般能騙10~20分。

這不能滿足我們的貪心。

然而，我們可以合成騙分的程序。

舉個(gè)最簡單的例子，有些含有無解情況的題目，它們同樣有樣例。我們可以寫這個(gè)程序

if(是樣例)printf(樣例);

else printf(“-1”);

這樣也許能變10分為20分，甚至更多。

當(dāng)然，合并騙分方法時(shí)要注意，不要重復(fù)騙同一種情況，或漏考慮一些情況。

大量能騙分的問題都能用此法，大家可以試試用新方法騙2.1中的例子“文化之旅”。

第6章 C++的福利

（請P黨們跳過本章，這不是你們的福利）

在C++中，有一個(gè)好東西，名喚STL，被萬千Oier們所崇拜，所喜愛。下面讓我們走進(jìn)STL。

6.1 快速排序

快速排序是一個(gè)經(jīng)典算法，也是C++黨的經(jīng)典福利。他們有這樣的代碼：

#include<algorithm>//這是必須的

sort(A,A+n);//對一個(gè)下標(biāo)從0開始存儲(chǔ)，長度為n的數(shù)組升序排序

就這么簡單，完成了P黨一大堆代碼干的事情。

6.2 “如意金箍棒”

C++里有一種東西，叫vector容器。它好比如意金箍棒，可以隨著元素的數(shù)量而改變大小。它其實(shí)就是數(shù)組，卻比數(shù)組強(qiáng)得多。

下面看看它的幾種操作：

vector<int> V;//定義

V.push_back(x);//末尾增加一個(gè)元素x

V.pop_back();//末尾刪除一個(gè)元素

V.size();//返回容器中的元素個(gè)數(shù)

它同樣可以使用下標(biāo)訪問。（從0開始）

第7章 “寧為玉碎，不為瓦全”

至此，我已介紹完了我所知的騙分方法。如果上面的方法都不奏效，我也無能為力。但是，我還有最后一招——

有句古話說：“寧為玉碎，不為瓦全”。我們蒟蒻也應(yīng)有這樣的精神。騙不到分，就報(bào)復(fù)一下，卡評(píng)測以泄憤吧！

卡評(píng)測主要有兩種方法：一是死循環(huán)，故意超時(shí)；二是進(jìn)入終端，卡住編譯器。

先介紹下第一種。代碼很簡單，請看：

while(1);

就是這短短一句話，就能卡住評(píng)測機(jī)長達(dá)10s，20s，甚至更多！

對于測試點(diǎn)多、時(shí)限長的題目，這是個(gè)不錯(cuò)的方法。

第二種方法也很簡單，但危害性較大，建議不要在重要比賽中使用，否則可能讓你追悔莫及。它就是：

#include<con> （windows系統(tǒng)中使用）

#include</dev/console> （Linux系統(tǒng)中使用）

它非常強(qiáng)大，可以卡住評(píng)測系統(tǒng)，使其永遠(yuǎn)停止不了編譯你的程序。

唯一的解除方法是，工作人員強(qiáng)行關(guān)機(jī)，重啟，重測。

當(dāng)然，我不保證他們不會(huì)氣憤地把你的成績變成0分。

請慎用此方法。

第8章 實(shí)戰(zhàn)演練

下面我們來做一些習(xí)題，練習(xí)騙分技巧。

我們來一起分析一下NOIP2013普及組的試題吧。

記數(shù)問題（NOIP普及組2013第一題）

(count.cpp/c/pas)

描述 試計(jì)算在區(qū)間 1 到 n 的所有整數(shù)中,數(shù)字 x(0 ≤ x ≤ 9)共出現(xiàn)了多少次?例如,在 1 到 11 中,即在 1、2、3、4、5、6、7、8、9、10、11 中,數(shù)字 1 出現(xiàn)了 4 次。

【輸入】

輸入文件名為?http://count.in。

輸入共 1 行，包含 2 個(gè)整數(shù) n、x，之間用一個(gè)空格隔開

【輸出】

輸出文件名為 count.out。

輸出共 1 行，包含一個(gè)整數(shù)，表示 x 出現(xiàn)的次數(shù)。

【輸入輸出樣例】

http://count.in?count.out

11 1 4 限制 每個(gè)測試點(diǎn)1s。

【數(shù)據(jù)說明】

對于 100%的數(shù)據(jù)，1≤ n ≤ 1,000,000，0 ≤ x ≤ 9。

表達(dá)式求值（noip2013普及組第二題）

(expr.cpp/c/pas)

描述 給定一個(gè)只包含加法和乘法的算術(shù)表達(dá)式,請你編程計(jì)算表達(dá)式的值。

【輸入】

輸入文件為?http://expr.in。

輸入僅有一行，為需要你計(jì)算的表達(dá)式，表達(dá)式中只包含數(shù)字、加法運(yùn)算符“+”和乘 ，且沒有括號(hào)，所有參與運(yùn)算的數(shù)字均為 0 到 231-1 之間的整數(shù)。輸入數(shù)據(jù)保 法運(yùn)算符“*”

證這一行只有 0~ 9、+、*這 12 種字符。

【輸出】

輸出文件名為 expr.out。

輸出只有一行，包含一個(gè)整數(shù)，表示這個(gè)表達(dá)式的值。注意：當(dāng)答案長度多于 4 位時(shí)，

請只輸出最后 4 位，前導(dǎo) 0 不輸出。

【輸入輸出樣例 1】

http://expr.in?expr.out

1+1*3+4 8

【輸入輸出樣例 2】

http://expr.in?expr.out

1+1234567890*1 7891

【輸入輸出樣例 3】

http://expr.in?expr.out

1+1000000003*1 4

【輸入輸出樣例說明】

樣例 1 計(jì)算的結(jié)果為 8，直接輸出 8。

樣例 2 計(jì)算的結(jié)果為 1234567891，輸出后 4 位，即 7891。

樣例 3 計(jì)算的結(jié)果為 1000000004，輸出后 4 位，即 4。

【數(shù)據(jù)范圍】

對于 30%的數(shù)據(jù)，0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤100；

對于 80%的數(shù)據(jù)，0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤1000；

對于 100%的數(shù)據(jù)，0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤100000。

以及。。。

小朋友的數(shù)字（noip2013普及組第三題）(number.cpp/c/pas)

描述 有 n 個(gè)小朋友排成一列。每個(gè)小朋友手上都有一個(gè)數(shù)字,這個(gè)數(shù)字可正可負(fù)。規(guī)定每個(gè)小朋友的特征值等于排在他前面(包括他本人)的小朋友中連續(xù)若干個(gè)(最少有一個(gè))小朋友手上的數(shù)字之和的最大值。 作為這些小朋友的老師,你需要給每個(gè)小朋友一個(gè)分?jǐn)?shù),分?jǐn)?shù)是這樣規(guī)定的:第一個(gè)小朋友的分?jǐn)?shù)是他的特征值,其它小朋友的分?jǐn)?shù)為排在他前面的所有小朋友中(不包括他本人),小朋友分?jǐn)?shù)加上其特征值的最大值。

請計(jì)算所有小朋友分?jǐn)?shù)的最大值,輸出時(shí)保持最大值的符號(hào),將其絕對值對 p 取模后輸出。

【輸入】

輸入文件為?http://number.in。

第一行包含兩個(gè)正整數(shù) n、p，之間用一個(gè)空格隔開。

第二行包含 n 個(gè)數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示每個(gè)小朋友手上的數(shù)字。

【輸出】

輸出文件名為 number.out。

輸出只有一行，包含一個(gè)整數(shù)，表示最大分?jǐn)?shù)對 p 取模的結(jié)果。

【輸入輸出樣例 1】

http://number.in?number.out

5 997 21

1 2 3 4 5

【輸入輸出樣例說明】

小朋友的特征值分別為 1、3、6、10、15，分?jǐn)?shù)分別為 1、2、5、11、21，最大值 21

對 997 的模是 21。

【輸入輸出樣例 2】

http://number.in?number.out

5 7 -1 -1 -1 -1 -1 -1

【輸入輸出樣例說明】

小朋友的特征值分別為-1、-1、-1、-1、-1，分?jǐn)?shù)分別為-1、-2、-2、-2、-2，最大值 -1 對 7 的模為-1，輸出-1。

【數(shù)據(jù)范圍】

對于 50%的數(shù)據(jù)，1 ≤ n ≤ 1,000，1 ≤ p ≤ 1,000所有數(shù)字的絕對值不超過 1000；

99 對于 100%的數(shù)據(jù)，1 ≤ n ≤ 1,000,000， 1≤ p ≤ 10， 其他數(shù)字的絕對值均不超過 10。

還有。。。

車站分級(jí)（NOIP普及組2013第四題）(level.cpp/c/pas)

描述 一條單向的鐵路線上,依次有編號(hào)為 1, 2, ..., n 的 n 個(gè)火車站。每個(gè)火車站都有一個(gè)級(jí)別,最低為 1 級(jí)?，F(xiàn)有若干趟車次在這條線路上行駛,每一趟都滿足如下要求:如果這趟車次停靠了火車站 x,則始發(fā)站、終點(diǎn)站之間所有級(jí)別大于等于火車站 x 的都必須停靠。

(注意:起始站和終點(diǎn)站自然也算作事先已知需要停靠的站點(diǎn))

例如,下表是 5 趟車次的運(yùn)行情況。其中,前 4 趟車次均滿足要求,而第 5 趟車次由于?？苛?3 號(hào)火車站(2 級(jí))卻未停靠途經(jīng)的 6 號(hào)火車站(亦為 2 級(jí))而不滿足要求。

現(xiàn)有 m 趟車次的運(yùn)行情況（全部滿足要求） ，試推算這 n 個(gè)火車站至少分為幾個(gè)不同的 級(jí)別。

【輸入】

輸入文件為?http://level.in。

第一行包含 2 個(gè)正整數(shù) n, m，用一個(gè)空格隔開。

第 i + 1 行（1 ≤ i ≤ m）中，首先是一個(gè)正整數(shù) si（2 ≤ si ≤ n），表示第 i 趟車次有 si 個(gè)停

靠站；接下來有 si 個(gè)正整數(shù)，表示所有?？空镜木幪?hào)，從小到大排列。每兩個(gè)數(shù)之間用一個(gè) 空格隔開。輸入保證所有的車次都滿足要求。

【輸出】

輸出文件為 level.out。

輸出只有一行，包含一個(gè)正整數(shù)，即 n 個(gè)火車站最少劃分的級(jí)別數(shù)。

【輸入輸出樣例】

【數(shù)據(jù)范圍】

對于 20%的數(shù)據(jù)，1 ≤ n, m ≤ 10； 對于 50%的數(shù)據(jù)，1 ≤ n, m ≤ 100； 對于 100%的數(shù)據(jù)，1 ≤ n, m ≤ 1000。

第1題，太弱了，不用騙，得100分。

第2題，數(shù)據(jù)很大，但是可以直接輸入一個(gè)數(shù)，輸出它mod 10000的值。得10分。

第3題，是一道非常基礎(chǔ)的DP，但對于不知DP為何物的蒟蒻來說，就使用暴力算法（即DFS）。得20分。

第4題，我們可以尋找一下數(shù)據(jù)的規(guī)律，你會(huì)發(fā)現(xiàn)，在所有樣例中，M值即為答案。所以直接輸出M，得10分。

這樣下來，一共得140分，比一等分?jǐn)?shù)線還高20分（弱省）！你的信心一定會(huì)得到鼓舞的。這就是騙分的神奇。

第9章 結(jié)語

騙分是蒟蒻的有力武器，可以在比賽中騙得大量分?jǐn)?shù)。相信大家在這本書中收獲了很多，希望本書能幫助你多得一些分。

但是，最后我還是要說一句：

不騙分，是騙分的最高境界。

“胡須如草芥瘋長，悲歡不過夢一場