寫在讀前：

1. 本文主要面對廣大c語言初學者，文中除部分特例代碼采用c++書寫外，大部分代碼均采用c語言，大家可放心食用，
2. 題解內容包含：題目與考點分析、演算法思路講解、參考程式的代碼模塊設計、注意事項，在以上所有部分都講解完成后，在一道題的最后會給出參考代碼，同時部分題目兼有背景補充或拓展知識，希望可以幫助您全面深入的理解到每一個考點，
3. 在每道題的講解部分會給出各種方法非常詳細的講解，從思想到實作逐步分析，請結合代碼與文字一起食用，
4. 文中代碼均有較為詳細的注釋，如果在看不懂的情況下，不妨先結合注釋轉動下靈活的頭腦，同時也非常歡迎讀者在評論區留下異議或者其他見解，

A. 阿正的忐忑不安

題目分析：
給出五個正整數，讓你判斷前四個數與第五個數的大小關系，若是前四個數大于等于第五個數，則輸出一段文本，否則輸出另一段文本，
本題意在考察最基本的順序、分支與邏輯設計，難度屬于低級梯隊，

思路講解：
使用一個if結構即可，判斷條件位前四個數的和是否大于第五個數，

對于資料型別的選擇，本題考察重點并非資料范圍，雖然題目中表明了資料的大小，但對分支陳述句判斷等核心演算法并未造成影響，采用int型別的整數即可處理所有輸入與運算，

代碼模塊：
輸入與初始化——判斷——輸出

注意事項：
在輸出時有一個略坑的地方需要考慮，便是引號的輸出，采用printf函式中輸出引號需要用到轉義字符的輸出方法，類似但又不同于換行符，引號的輸出需要采用如下格式：

printf(" \" "):
//運行結果：
 " 

printf函式內寫下了一個空格，一個反斜杠，一個引號，一個空格，最后的運行輸出結果是一個空格，一個引號，一個空格，

參考代碼：

#include<stdio.h>

int sum=0,goal;
//sum來儲存阿正的總分; goal來儲存錄取分數線,即第五個輸入值

int main()
{
	 for(int i=0;i<4;i++){						//四科分數,定義臨時變數temp分四次來參與輸入與計算
	 	 int temp;
	 	 scanf("%d",&temp);						//輸入
	 	 sum+=temp;								//計算
	 }
//以下代碼與上等效
/*	 int a,b,c,d;				`				//也可以定義四個變數分別輸入計算
	 scanf("%d%d%d%d",&a,&b,&c,&d);
	 sum=a+b+c+d;								*/

	 scanf("%d",&goal);							//輸入分數線的值

	 //在if框體內只有一條陳述句時,可以省略大括號
	 if(sum>=goal) printf("Blessings for your college career!\n");				//大于等于的情況
	 else printf("Blessings for your \"fourth grade\" in high school!\n");		//小于的情況
	 return 0; 									//必須return 0;
}

拓展與背景補充（引自百度百科）：

半角字符：半角字符是指一字符占用一個標準的字符位置，通常的英文字母、數字鍵、符號鍵都是半角的，半角的顯示內碼都是一個位元組，

轉義字符：所有的ASCII碼都可以用“\”加數字（一般是8進制數字）來表示，而C中定義了一些字母前加"\"來表示常見的那些不能顯示的ASCII字符，如\0,\t,\n等，就稱為轉義字符，因為后面的字符，都不是它本來的ASCII字符意思了，

B. 阿正的學期準備

題目分析：
題目給了你幾種具有一定規律的優惠方案與阿正所持有的金幣數量，我們需要根據金幣數量組合出可以獲利最大的優惠方案，并輸出最后連本帶利的金幣數量，
我們細看題目中給出的五種優惠方案，可以發現獲贈金幣與充值金幣是成正比的，只有發現了這個規律，分析才能繼續進行，我們后續的演算法設計皆是建立在此基礎之上的，

本題更加靈活的考察了代碼設計能力與最簡單的貪心思想，選手可以從分支回圈等多個角度靈活地書寫代碼，難度屬于低級梯隊中最難的一道題，

而何謂”貪心“思想與具體解題方法，請參考下文：

思路講解：
在獲贈金幣與充值金幣是成正比的基礎上，肯定是充值的越多，獲利越多，因此我們在已有可以用來充值的金幣數固定的情況下，選擇充值金幣數量多的方案肯定是獲利最多的，只要服從”金幣數量夠，就選最大的“原則，便可以獲得最大的利潤，

上述敘述就是一個簡單的貪心案例，所謂”貪心“，就是當前情況選擇可以獲利最大的即可，不需要考慮對后續的影響，

在了解了我們設計代碼的核心思想后，我們只需要服從上述原則進行設計即可，在這里筆者提供兩種思路，讀者不必僅局限于此：

在得到可利用最大金幣數量后，我們可以自多至少地依次判斷金幣數量是否滿足優惠條件，即從充值金幣數量最大的開始判斷，如果符合優惠條件，那么便將此項優惠記錄，并減少已有的金幣數量，繼而判斷下一項優惠是否滿足，直至五項優惠全部判斷完，

上文敘述了采用純分支陳述句的判斷方法，我們按照從多到少的順序寫下五個分支陳述句便可，同時，我們也可以將這些引數存盤到陣列中，然后采用回圈依次判斷是否符合優惠條件：

首先建立兩個陣列分別來存盤充值所需金額與對應的獲利金額，此處要注意，我們回圈的方向要與上文分支中判斷的方向一致，即仍然從大到小進行判斷，所以我們在存盤資料時可以將資料倒置一下，即將第五種優惠的引數存盤到陣列下標位0的位置，將第一種優惠的引數存盤到陣列下標為4的位置，繼而，再進行回圈依次遍歷，

并且對于資料型別的選擇，與本次比賽大部分題目相同，本題中明確給出了所有資料均在整形范圍內，因此選擇整形便足夠了，

代碼模塊：
輸入與初始化——資料處理——輸出

注意事項：
分支陳述句的寫法不必多言，只需要在進入當前分支后記得減去花費掉的金幣數，加上獲得的金幣數即可，
但若是采用回圈的整體框架，則寫法更加靈活，可以在回圈陳述句里進行分支判斷，也可以進行其他更優的操作，

參考代碼：

分支書寫：

#include<stdio.h>

int n;											//n即為最初的金幣總數

int main()
{
	 scanf("%d",&n);
	 int now=n,result=n;
	 //now為執行程序中實時更新的金幣數量, result即為購物卡中實時更新的金幣數量,即"連本帶利"的金幣數
	 //此處將result初始化為n,后續計算中只用考慮獲利即可;
	 //如果初始化為0,則在分支中不僅要添加"本金的部分", 在遍歷完五個方案后,還要加上五個方案沒花完的"剩余的部分"
	 
	 if(now>=648) now-=648,result+=108;			//從多到少依次判斷, 如果符合條件更改兩個引數的值
	 if(now>=324) now-=324,result+= 54;
	 if(now>=108) now-=108,result+= 18;
	 if(now>= 36) now-= 36,result+=  6;
	 if(now>=  6) now-=  6,result+=  1;
	 
	 printf("%d\n",result);						//輸出結果
	 return 0;									//必須return 0;
}

回圈書寫：

#include<stdio.h>
 
int n,pointer=0;								//與上同理,n為初始金幣數,而pointer則記錄遍歷到哪種優惠情況
int cost[6]={648,324,108,36,6,0},extra[6]={108,54,18,6,1,0};
//cost存盤需要充值數量,extra存盤額外獲利的金幣數量;
//并且將最后一位留給0的位置,pointer指向最后一位,便說明金幣已經花完了,不能再進行充值了
 
int main()
{
     scanf("%d",&n);
     int now=n,result=0;						//now為程序中實時更新的所持有的金幣數量,result為實時更新的購物卡中金幣總數
     while(pointer<6){							//只有pointer小于5時才能進行充值
         while(cost[pointer]>now) pointer++;	//尋找當前金幣數可以選擇的最大優惠方案,包括陣列第六位的"0"方案,即代表不能再進行充值
         now-=cost[pointer];					//更新兩個引數的值,此處result需要"連本帶利"地進行更新
         result+=(extra[pointer]+cost[pointer++]);
     }
     result+=now;								//并且最后加上能享受的優惠都享受后, 剩余的金幣數
     printf("%d\n",result);						//最后輸出結果
     return 0; 									//必須return 0;
}

C. 阿正的快樂源泉

題目分析：

題目敘述很長，首先感謝大家有耐心讀完 = =，

具有一定演算法基礎的同學能夠輕而易舉的發現題目中所給的操作與進行的程序其實就是在模擬 “二分查找” ，（二分查找的介紹詳見思路講解部分）

我們需要在區間[0, Rightmax]中通過二分查找的方法查找值H，并輸出進行 “二分操作” 的次數，

并且，由于本題需要輸出"二分"的次數便只能通過模擬"二分"的程序來實作，出題人便很仁慈的將資料范圍仍然設定為全部在整形內，

本題的意圖在于讓大家手動模擬二分查找的程序，題目中已經給出了實作的方法，所以大家只需要按部就班的寫回圈即可，由于許多同學可能從未見過"二分查找"，且題面繁瑣難懂，，，，故，難度屬于中級梯隊，

思路講解：

查找與排序問題是最為基礎同時也是最為經典的演算法，如何從一段序列中查找到想要的值，或者如何將一段序列按照一定的方法排序，其中大有研究，在此處，我們介紹一種比 “遍歷區間每個元素來查找目標” 更快捷的方法——二分查找，

在講解前，我們首先要明白三個概念，區間的左值、中值、右值，左值即為區間可以取到的最小值，右值即為區間可以取到的最大值，中值即為左右值的平均數，在數軸上表示即為最左邊的點， 中間的點，最右邊的點，因此稱為左、中、右值，

實作二分查找的基礎是查找范圍必須是有序的，本題中范圍即遞增排列的從0到Rightmax的整數，

其次，二分操作就是將查找目標值與當前查找區間的中值進行比較，如果當前區間的中值大于目標值，則目標查找值一定在查找區間的左半區間，因此便將查找區間縮小到左半區間，對應題目中"藍色藥丸"的操作，就是將當前區間的右值更改為當前區間的中值，
若當前區間的中值小于查找目標值，則目標值一定在右半區間，那么便指向"紅色藥丸"的操作，將查找區間縮小到右半區間，將當前左值更新為中值，

重復上述程序，直至使中值mid等于目標值，便是找到了目標值，

為了讓大家認識二分查找，出題人不僅在題面中詳細敘述了二分查找的程序，也簡略了一些步驟，本題中判斷是否找到目標值的指標即為中值是否等于目標值，而在不同的問題中，這個指標也不盡相同，大家往往要撰寫與二分查找結合使用的的check函式來判斷當前區間是否可以找到目標值，

介紹完"二分查找"，我們結合本題，來具體說明如何撰寫一份最簡單的二分查找的代碼：

首先初始化區間的左右值，即為題目中給出的Leftmin與Rightmax，左值一直為0，右值需要題目輸入，同時，我們還需要一個變數來記錄"二分"的次數，

int times=0,right=maxd,left=0;
//times為記錄查找次數的變數，maxd為輸入的區間最大的右值,將其賦給right, left則一直為0

之后我們便要模擬 “不斷折半” 這個程序，而既然這是個回圈執行的程序，那么便一定需要知道邊界，二分題目中邊界的往往是根據如何進行"折半操作"設定的，而在本題中，我們不斷改變左右邊界的值，最后使得左右邊界相加的中值是目標值的時候就可以退出二分的程序了，結合我們的區間覆寫了從0到Rightmax內的所有制，我們可以想到，這是個在有限步數內的必然結果，所以此處的邊界設定只要不在查找到目標之前提前結束，便可以隨意設定，

while(left<right){
	//...
}
//同時也可以寫為while(1)
//while判斷括號內的值不為0便可以一直進入,如果while內部沒有其他出口的話,這便是一個死回圈
//因此采用while(1)的寫法, while內部一定要寫break的情況

接下來就是 “二分” 的具體操作了，不管是上文還是題面中的敘述都已經非常詳細了，此處直接給出具體操作的代碼：

		 int mid=(left+right)/2;
	 	 
	 	 if(mid<standard) left=mid,times++;			//紅色藥丸的操作, 將區間縮小到右半區間, 更新左值
	 	 else if(mid>standard) right=mid,times++;	//藍色藥丸的操作, 將區間縮小到左半區間, 更新右值
	 	 else if(mid==standard) break;				//如果找到目標值，那么便直接退出回圈
	 	 //else if(mid==standard) return times;		//如果采用函式的寫法，也可以直接退出二分函式

至此，將上述代碼組合起來，便是一個最基本的，完整的二分查找了，也是本題的標準程式，

模塊設計：
輸入與初始化——查找——輸出

注意事項：

再次強調，本題目中出現的二分查找是最最最簡單的二分查找，實際中二分查找的應用更加廣泛也更加靈活，本題只是介紹基本的實作程序，萬萬不可拘泥于本題給出的模板，

參考代碼：

#include<stdio.h>

int standard,maxd;									//standard即為查找目標值,maxd為最大的上界

int binary_search();								//本程式采用函式的方式書寫二分查找,非函式方式在上文中已給出

int main()
{
	 while(scanf("%d%d",&maxd,&standard)!=EOF){		//多實體輸入
	 	 int counter=binary_search();				//由于左值一直為0,而右值又是全域變數,所以不用傳遞引數,直接呼叫即可
		 printf("%d\n",counter);					//輸出
	 }
	 return 0;										//必須return 0;
}

int binary_search(){								//在0到maxd中查找值standard, 并回傳折半次數
	 int times=0,right=maxd,left=0;					//定義與初始化左右值和查找次數
	 
	 while(right>left){								//回圈條件,不必拘泥于本程式
	 	 int mid=(left+right)/2;					//定義與初始化中值
	 	 if(mid==standard) return times;			//如果找到則直接回傳times的值, 作用相當于check函式
	 	 
	 	 if(mid<standard) left=mid,times++;			//縮小到右半區間
	 	 else if(mid>standard) right=mid,times++;	//縮小到左半區間
	 }
}

D. 阿正的平面行進

題目分析：
給定兩個平面坐標，輸出兩個點位的對應橫縱坐標差的絕對值之和，
本題意在考察最基本的代碼撰寫能力，函式呼叫能力，難度屬于低級梯隊，

思路講解：
依舊是所有資料都在整形范圍內，只需要計算出兩個點位x坐標差的絕對值，y坐標差的絕對值，并相加后輸出即可，

模塊設計：
輸入與初始化——計算——輸出

注意事項：
記得對差取絕對值并且帶上其所屬的<math.h>頭檔案即可，
同時如果使用了全域變數，則要避免使用某些意義沖突的變數名稱，比如y1（小寫），本地編譯器可以通過，但oj會報編譯錯誤，

參考代碼：

#include<math.h>										//取絕對值函式在math.h的頭檔案內,一定要加上,不然會編譯錯誤
#include<stdio.h>

int X1,Y1,X2,Y2;										//來存盤兩點坐標
int result;												//存盤距離, 即結果

int main()
{
	 while(scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2)!=EOF){		//多實體輸入
	 	 result=abs(X1-X2)+abs(Y1-Y2);					//取差 取絕對值 取和,按運算優先級依次進行
		 printf("%d\n",result);							//輸出
	 }
	 return 0;											//必須return 0;
}

拓展背景：

出租車幾何或曼哈頓距離（Manhattan Distance）是由十九世紀的赫爾曼·閔可夫斯基所創詞匯，是種使用在幾何度量空間的幾何學用語，用以標明兩個點在標準坐標系上的絕對軸距總和，（引自百度百科）

據說曼哈頓距離命名是由于曼哈頓市區高樓林立，兩點間沒有直線距離，必須沿一個平面的x軸或者y軸走才能到達，
同時在西洋棋的規則中，車（城堡）是以曼哈頓距離來計算棋盤格上的距離，

E. 阿正的英語閱讀

題目分析：
給你一段指定要求的英語文本，你需要找到其中出現次數最多的單詞并輸出，
這道題最初問世的時候并不長這樣子，考慮到大家課程進度或許還沒有進行到字串這一章，最終出題人在好 (壞) 心眼的阿樹的建議下，將文本的單詞范圍限制到規定的十個單詞內，

本題意在考察大家對字串的處理能力，包括輸入輸出、存盤以及各種字串函式的呼叫，當然由于單詞只有10個，大家也可以列舉10個單詞出現的次數進行比較即可，但當沒有10個限制時，便必須采用字串處理的方法了，

同時，這道題除了使用char陣列與處理char型別函式解決外，還有更加方便但也更為陌生的方法，便是呼叫c++語言中非常強大的stl函式來解決問題，兩種方法在下文中均有提及，

細節在此不表，請參考思路講解部分，由于部分同學并不熟悉字串，并且暴力列舉較為繁瑣，此題難度屬于中級梯隊，

由于出題者本意并不是想讓大家列舉10個單詞比較次數，，，所以這種方法就不介紹了，大家可以直接來學習下面介紹的字串處理的方法，實在對列舉10個單詞的方法有不明白的地方也可以直接私聊我或者在群里討論，

基礎方法：

思路講解：

第一步先考慮英語文本輸入的方式，其本質便是多實體的以空格分隔的字串輸入，如果會用scanf輸入字串，便可以直接scanf()!=EOF即可，但如果不會使用字串的輸入方式，也可以單個單個字符的輸入，先完整的輸入多個子母湊成一個單詞，遇到空格便表明這個單詞結束了，之后也可以直接遇到檔案末結束即可，
兩種輸入方法如下：

字串輸入：

char temp[100];
while(scanf("%s",temp)!=EOF){
	 //...
}

字符輸入：

int index=0;
char temp[100],single;
while(scanf("%c",&single)!=EOF){
	 if(single!=" ") temp[index++]=single;
	 //如果不是空格,表示這個單詞還沒有輸入完,那么將字母single填充到temp當前的位置上,并且使下標+1
	 else{
	 	 //...
	 	 index=0;
	 }
	 //如果是空格,便對當前以及輸入完成的單詞進行后續操作,并在操作完成后將下標置0
}

首先我們需要考慮如何存盤出現的子母，我們第一個想到的肯定是char型別的陣列，但是一維的char型別陣列在空間上是一串連續的序列，我們需要想辦法將每個單詞分隔開來，
在單詞與單詞之間添加特殊的標記作為分隔符？不失為一種解決方法，
但當我們繼續考慮下去，如何通過char陣列來訪問每個單詞呢？如何對每個單詞進行計數呢？這些情況通過一維陣列添加識別符號的方法來實作均有著較大的困難，
那么我們便繼續思考下去，采用二維的char型別陣列呢？
使用二維陣列，我們首先要考慮的是空間夠不夠用，這道題中單詞最多會出現十種，且每個單詞長度最多不超過10，所以二維陣列我們可以10*10的空間足夠我們使用了，（小白也可以暫時不考慮空間的問題）
之后我們來考慮二維陣列的意義，我們用一個維度來存盤不同的單詞，然后用下一維度存盤每個單詞不同的子母，根據題目中的樣例，詳細的存盤單元如下圖：

定義二維陣列text[][]來存盤英語文本，那么在全部輸入完成后，text[0]就可以代表 “Azheng” 這個單詞，text[0][0]代表的就是 “A” 這個子母，其他位置同理，

這樣我們便可以明確用text中一個維度的下標來表示單詞的位置，在定義一個counter[] 計數陣列，相應位置代表text[][]相應下標位置單詞出現的次數就能滿足我們這道題的所有操作要求了，即counter[0]代表的是text[0]中 “Azheng” 出現的次數，

這樣輸入與存盤的問題就解決了，下一個問題便是我們如何進行計數？

計數首先要判斷這個單詞有沒有出現過，是否和以前出現過的單詞相等，因為我們采用的是二維陣列來存盤單詞，每個單詞的子母都可以通過下標來訪問，所以我們在讀入一個單詞后，可以直接遍歷已有的text陣列，這個單詞是否以及被我們存盤在text陣列里面了，如果找到了，那么對應位置的counter便+1，如果沒有，那么就在text內下一個空位存盤當前單詞即可，同時使counter對應的位置等于1，

計數的問題也解決了，最后我們遍歷一遍counter陣列，找到counter內的最大值，并輸出對應下標處的text內的單詞即可，

如果最大值有多個怎么辦？此刻我們根據題意，尋找出現最早的單詞，便是最早被我們存到text陣列內的單詞即可，

至此，這道題使用char型別解決的方法已經全部完成，其中涉及到的細節處理請參考注意事項以及下文中的代碼，

模塊設計：
輸入與初始化——計數——輸出

注意事項：
在進行演算法設計時要考慮時間復雜度與空間復雜度，拿此題為例，空間復雜度在上文已經說明，此處講一下這道題的空間復雜度：在解題時，由于輸入資料的不確定性，我們一般考慮最大時間復雜度，即所有資料都是范圍內最大的情況下的時間復雜度，
之后估算時間復雜度，參考代碼中執行頻數最高的陳述句，其往往是for回圈或者函式的遞回，此題中在依次輸入不同單詞時我們需要采用第一個for回圈，在輸入后判斷判斷單詞是否與之前重復時，我們需要遍歷以前的所有單詞，此處采用第二個for回圈，而在判斷兩個單詞是否想等時，我們有需要遍歷每個字母，此處為第三個for回圈，
這三重回圈便是這個程式中執行頻數最高的陳述句，隨后結合資料范圍進行判斷，第一重回圈最后會有10個不同的單詞，第二重回圈也是最多出現10個單詞，第三重回圈每個單詞最多10個字符，因此最大的復雜度便是10 * 10 * 10，遠遠小于題目限制，我們便可以放心進行了，

繼而再說一下處理的細節：

1. 在判斷兩個單詞是否相等時，如果我們選擇while回圈，那么便可以不考慮單詞長度，遇到text[i1][i2]=="\000"時結束，即字符陣列的末尾符；如果我們選擇使用for回圈，那么我們也可以直接用strlen函式來計算字串長度，
2. 如果當前單詞沒有出現過，我們可以直接使用字串復制strcpy函式將其復制到text陣列中，

參考代碼：

#include<stdio.h>
#include<string.h>

int counter[105],num=0;									//num存當前已經出現的單詞個數,counter用來計數
char word[105][20];										//word來實時更新已經讀到的單詞串列
char temp[20];											//temp來存目前讀到的單詞

int main()
{
	 memset(counter,0,sizeof(counter));
	 memset(word,0,sizeof(word));						//初始化函式
	 //可以將第一個引數內第三個引數空間大小的值全部初始化為第二個引數
	 //等價于for(int i=0;i<n;i++) counter[i]=0;       	//n為counte陣列的長度
	 while(scanf("%s",temp)!=EOF){						//采用字串讀入的方法
	 	 int address=-1;								//adress存當前單詞即將放到word中的哪個位置
	 	 for(int i=0;i<num;i++){						//num為以前讀入的不同的單詞個數,遍歷它們依次判斷
	 	 	 int flag=1,pointer=0;
	 	 	 //必須所有位置上的字母都相等才是舊單詞,否則出現一個不相等的,便使flag=0,標記為新單詞
	 	 	 while(pointer==0||(temp[pointer-1]!='\000'||word[i][pointer-1]!='\000')){
	 	 	 	 if(temp[pointer]!=word[i][pointer]){	//不相等,標記為新單詞
	 	 	 	 	 flag=0;
	 	 	 	 	 break;
				 }else pointer++;						//相等,繼續判斷下一個字母
			 }
			 if(flag==1){								//如果是舊單詞
			 	  address=i;							//獲取address的值
			 	  counter[address]++;					//更新counter內對應位置的值
			 }
		 }
		 if(address==-1){								//如果address值沒有更新過,即是新單詞
		 	 strcpy(word[num],temp);					//將temp賦到word下一個位置上
		 	 counter[num++]=1;							//對應counter位置等于1
		 }
	 }
	 
	 int maxd=0,flag=-1;								//maxd來存出現最多的次數,flag來存最多者的下標
	 for(int i=0;i<num;i++){							//遍歷出現的單詞,尋找出現次數最多者
	 	 if(counter[i]>maxd){							//如果遇到更多的
	 	 	 flag=i;
	 	 	 maxd=counter[i];							//更新maxd與flag
		 }
	 }
	 
	 printf("%s\n",word[flag]);							//最后輸出word中下標為flag處的單詞
	 return 0;											//必須return 0;
}

拓展方法：

上文中提到，可以使用C++中強大的stl函式庫來快速解決這道題，stl庫中含有大量快捷的函式與容器，但此處僅給出使用stl解題的參考代碼，有興趣者可以自行查找資料進行學習，

#include<bits/stdc++.h>
using namespace std;

map<string,int> counter;								//map容器,內涵兩個引數值,可以根據第一個引數來獲取第二個引數的值
vector<string> indexd;									//vector容器,為動態陣列,即長度不固定的陣列

string temp,answer;										//string,字串,相當于char陣列但功能要比char陣列強大許多
int maxd=0;

int main()
{
	 while(cin>>temp){									//c++的多實體讀入方法
	 	 counter[temp]++;								//可以直接通過temp來訪問counter內的值
	 	 if(counter[temp]==1) indexd.push_back(temp);	//vector內置函式的使用
	 }
	 for(int i=0;i<indexd.size();i++)					//通過下標遍歷vector,尋找出現次數最多的單詞
	 	 if(counter[indexd[i]]>maxd) answer=indexd[i],maxd=counter[indexd[i]];
	 cout<<answer<<endl;								//輸出
	 return 0;											//必須return 0;
}

F. 阿正的子母序列

題目分析：
題面雖然繁瑣，但用一句話概括其實非常簡明，即為求一個序列中所有不相同的連續非遞減子序列個數以及長度和，

本題資料量較大，使用列舉所有連續非遞減子序列的方法在時間上并不合理，需要大家估算出時間復雜度，考慮更為快捷的方法，

本題綜合性較高，且涉及相對較多的演算法思想，難度屬于高級梯隊，

思路講解：

下文將從低性能演算法的基礎上逐步優化，推出最終符合時間限度的方法，若您已經有了部分思路或者想直接跳過方繁瑣的文字，不妨參考這篇博客：關于前綴和與差分的講解，

初看此題，大家首先想到的大多數都是找出所有連續非遞減子序列，統計個數以及長度，這樣對于長度為10000的序列來說，需要從每個位置上開始判斷其為首元素的序列是否遞增，遞增到哪個位置，這樣最低復雜度也是O(n平方)級別的，對于1e4（即1*10的4次方）的資料來說會有超時的風險，

“大部分高性能的演算法都是從低性能演算法的基礎上優化而來的”，換位排序一題中 “你” 這樣安慰阿正道，此題中同樣如此，

我們首先考慮列舉全部連續非遞減子序列的方法最浪費時間的地方在哪里？

我們再來回顧一下列舉全部連續非遞減子序列的程序，首先遍歷序列的每個元素，列舉出以當前元素為首元素的所有序列，這是第一重回圈，其次在確定了首元素之后，需要遍歷其后的所有元素，尋找連續非遞減序列最長可以延申到哪個位置，多向后延申一個位置，那么符合要求的序列個數便+1，而其前面所有以當前元素為首元素的序列的長度都要+1，這是第二重回圈，

在第二重回圈計數的程序中，我們其實可以將零碎的多部計數合并成概括性高的一步計數，拿樣例為例子，我們計算從a[0]到a[3]這段序列中符合要求的個數時，首先以a[0]為首元素，列舉出{1}，{1 2}，{1 2 4}，{1 2 4 5}，其次以a[1]為首元素，列舉出{2}，{2 4}，{2 4 5}…等等，直至以a[3]為首元素，列舉到{5}，

上述描述本質作業即為：統計長度為4的連續非遞減序列所包含的所有連續非遞減子序列的個數，加上其本身也算1個，

我們不妨手算一下，從a[0]到a[3]所有符合題意的序列個數為：4 (以a[0]為首元素的個數) + 3 (以a[1]為首元素的個數) + 2 (以a[2]為首元素的個數) + 1 (以a[3]為首元素的個數) ，

那么當我們在母序列中找到一串最長的連續非遞減子序列時，例如樣例中的{1 2 4 5}與{3}（因為這些序列作為非遞減子序列無法再延長）時，只需要計算出這些 “最長” 的子序列包含了多少符合要求的 “子子序列” ，再加上其本身的個數，即可，

而經過我們上文中的手算，我們可以發現這些 “子子序列” 的個數是符合一定規律的，我們倒推一遍，從"最長子序列"末尾元素開始計數：
末尾元素可以構成的"子子序列"無疑只有一個；
倒數第二個元素可以構成的子序列為 {倒二元素本身}，{倒二元素，倒一元素}，兩個‘；
同理，其他位置包含的 “子子序列"個數也與其長度相等；
那么對于長度為n的"最長子序列”，其包含的 “子子序列” 個數便為 1+2+…+n；

對于上式，我們將其稱為"n的前綴和"，如果你看完了上述長篇大論，還是不能理解的話，可以參考一下這篇講解：
關于前綴和與差分的講解，

至此，我們便將 “零碎的多步” 化為了 “高度概括性的一步”，即只找到出母序列中所有 “最長子序列” ，后求出所有"子子序列" 加上其本身的個數即可，“子子序列” 的方法，我們稱之為 “前綴和” ，

在解決完個數問題后，我們再來考慮長度如何計算，

在求個數時，我們每發現一個序列，那么便將結果+1；在求長度時，我們每發現一個序列，那么便將結果+這個序列的長度即可，

比如對一個長度為4的連續非遞減序列，求其符合要求的子序列個數與長度和：
對應個數公式為： 4 + 3 + 2 + 1 ；
那么其長度和公式便為：（1+2+3+4）+（1+2+3）+（1+2）+（1）；

看到這里有沒有茅塞頓開的感覺？ 又是一個前綴和操作！

模塊設計：
預處理、輸入與初始化——遍歷計算——輸出

注意事項：
關于前綴和的詳細介紹與使用方法請參考這篇博客：關于前綴和與差分的講解，
計算前綴和可以在輸出與初始化之前進行，我們稱之為 “預處理” ，即預先進行一些處理，
在進行長度累加計算時，由于資料范圍過大，需要使用長整型型別的變數，

更多的細節將會在代碼中以注釋的形式給出，

參考代碼：

#include<stdio.h>

int n,a[100005],counter[100005];					//a存序列
long long value[100005];							//counter為個數前綴和, value為長度前綴和, 即個數的二重前綴和

int main()
{
	 for(int i=1;i<100001;i++){
	 	 counter[i]=i+counter[i-1];
	 	 value[i]=counter[i]+value[i-1];
	 }												//計算前綴和陣列
	 
	 int result=0,temp=1;							//temp實時更新當前"最長子序列"的長度
	 long long value_sum=0;							//result為最終的個數,value_sum為最終的權值和
	 scanf("%d",&n);
	 for(int i=0;i<n;i++) scanf("%d",&a[i]);		//輸入a陣列
	 
	 for(int i=0;i<n;i++){
	 	 if(a[i+1]>=a[i]&&i!=n-1) temp++;			//如果子序列仍然非遞減,那么長度+1
	 	 else{										//非遞減結束, 開始計算
	 	 	 result+=counter[temp];					//更新個數
	 	 	 value_sum+=value[temp];				//更新長度和
	 	 	 temp=1;								//temp置為1
		 }
	 }
	 
	 printf("%d\n%lld\n",result,value_sum);			//輸出結果,由于value_sum為長整型變數,所以需要用%lld
	 return 0;										//必須return 0;
}

G. 阿正的排球測驗

題目分析：
給出一個正整數，讓你將其轉換為32位的二進制數，空位以0補齊，并在一系列操作后求出給定范圍內1的個數與1的總數的比值，

本題意在給大家普及二進制與位運算的相關知識，考察基本的模擬能力，難度屬于中級梯隊，

思路分析：

純模擬題，將讀入的正整數轉化為32位的01陣列，

之后根據讀入進行相應的操作，最后再統計輸出即可，

位運算的相關知識可以參考這篇博客，包括左移右移、與、或、異或，
位運算基本操作，

代碼模塊：
初始化與輸入——處理與計算——輸出

注意事項：

1. 可以轉化為32位的正整數最大范圍高達1e10，所以需要開長整型變數進行儲存，
2. printf函式默認保留四舍五入的輸出方式，所以不需要對結果進行再處理，
3. 資料細節較多，需要考慮各種邊界情況，比如阿正處于0的位置，但是接球半徑為31，則可以覆寫全場，
4. 輸出記得加百分號，

參考代碼：

#include<stdio.h>

long long num;											//長整型來儲存給定的十進制數
int t,n=0,pos,temp,r,order,counter=0;
//n來存盤最后1的總個數,counter來存盤范圍內1的個數
int s[32];

int maxd(int x,int y){									//兩值比較取大
	 if(x>=y) return x;
	 else return y;
}

int mind(int x,int y){									//兩值比較取小
	 if(x<=y) return x;
	 else return y;
}

int main()
{
	 scanf("%lld",&num);								//輸入長整型
	 for(int i=0;i<32;i++) s[i]=((num>>(32-i-1))&1);	//將十進制數轉化為32位的陣列
	 
	 scanf("%d%d%d",&pos,&r,&t);						//輸入阿正的位置,阿正的接球半徑以及操作次數
	 while(t--){
	 	 scanf("%d%d",&order,&temp);					//order存盤操作型別,temp存盤操作物件
	 	 if(order==1) s[temp]&=0;						//按位與
	 	 if(order==2) s[temp]|=0;						//按位或
	 	 if(order==3) s[temp]^=1;						//按位異或
	 }
	 
	 for(int i=0;i<32;i++) if(s[i]==1) n++;				//統計總數
	 for(int i=maxd(pos-r,0);i<=mind(pos+r,31);i++) if(s[i]==1) counter++;
	 //處理邊界情況統計范圍內的數量
	 
	 printf("%.2lf%%",(counter*100.0)/(n*1.0));			//輸出結果
	 return 0;
}

H. 阿正的換位排序

題目分析：
給定你若干個序列，每個序列有一個長度n，對每個序列，若能只交換相鄰兩個元素的值在 [n(n-1)]/2 -1* 內完成排序，則輸出Yes，否則輸出No，

本題綜合性較高，著重考察思維活躍性，對基礎演算法的理解程度，難度屬于高級梯隊，
詳細程序見思路講解，

思路講解：

首先，使用冒泡排序和選擇排序直接計數會超時，

當你看到1e5的資料時，就應該估算到，冒泡排序和選擇排序的時間復雜度都是平方級別的，此題行不通，

當然如果你不了解冒泡排序和選擇排序，那么根據題目中"提示"的部分，也可以繼續進行下去，

如果你熟悉冒泡排序，那就更好了，我們接下來通過講解冒泡排序來揭示這道題正確的解法，

冒泡排序是個很形象的名字，通過選擇序列中的最值，然后將其置于一端，使這個最值 “冒泡” 跑出序列外，重復這個程序便可以完成排序，
每次查找最值的程序都需要遍歷一遍序列，所以復雜度是n平方級別的，

冒泡排序的 “將最值置于一端” 這個操作，便可以通過題目中的 “換位” 來實作，不斷交換相鄰兩個元素，使得最大值 “交換” 到序列最端，下一次冒泡便將這個最大值排除在外，假設現在對于一個長度為n的序列，最值處于序列中第i個位置，而序列最右端已經找到了k個最值，那么這個交換次數便為：n-k-i；

在此題中給出了交換次數的臨界值，即 [n(n-1)]/2 -1* ，那么我們就要考慮，什么情況下交換次數可以達到臨界值？

首先考慮交換次數最多的情況，我們使得冒泡排序的程序中，每次 “冒泡” 的交換次數都達到最多，即最大值處于序列最左端的位置，那么每次交換的次數都為 n-k ,（k為已經完成"冒泡"的次數，0<=k<n），

那么這個總次數便為 1+2+3+…+n-1 = [n(n-1)]/2*，

至此，結果已經明了，只要每次交換使得下一個最值一直出現在最左端，且必須交換到最右端，即**這個序列必須是嚴格遞增的，**只要符合這種情況，那么他的最小交換次數始終比題目要求大1，
而這也是唯一一種，會超出題目要求次數的情況，

那么此題便轉換為判斷序列是否嚴格遞增了，詳細代碼見下文，

模塊設計：
讀入與初始化——判斷——輸出

注意事項：
序列必須是嚴格遞增的情況下才會輸出no，如果序列中有相等的元素，其可以通過相等的元素減小交換次數，便不足以超過臨界值，

參考代碼：

#include<stdio.h>

int a[100005],n,flag=0;								//a來存盤原始序列,n代表序列長度,flag判斷序列是否嚴格遞增

int main()
{
	 while(scanf("%d",&n)!=EOF){					//多實體輸入
	 	 flag=0;									//每次都要初始化
		 for(int i=0;i<n;i++) scanf("%d",&a[i]);	//輸入序列
		 for(int i=0;i<n-1;i++){					//比較大小,判斷n-1次
		 	 if(a[i]<=a[i+1]){						//只要小于等于便不是嚴格遞增
		 	 	 flag=1;
		 	 	 break;
			 }
		 }
		 if(flag==0) printf("No\n");				//不符合條件
		 else if(flag==1) printf("Yes\n");			//符合條件
	 }
	 return 0;										//必須return 0;
}