首碼和 首碼和，顧名思義，就是所有首碼之和，給一個最基本的例子： 如圖，a為原始數組，s為完成預處理後的數組，很容易看出來s[ i ]=s[ i - 1 ]+a[ i ]，而也就是s[ i ]=a[1]+a[2]+……+a[ i ]，需要註意的是記s[0]=0。 那麼，如果我想要知道一個區間的區間和 ...
快考pat乙級了，花了十塊錢做了一下去年冬天的pat乙級，不難，現在在花ac之後的時間來寫文章，默默許願幾天後的也不難，但是我們也要做好準備啊~
更新
map使用insert插入如果鍵已存在，插入時不是覆蓋而是忽略:C++ map容器插入具有相同鍵的鍵值對的覆蓋問題
B-1 謠言檢測儀
分數 15 作者 陳越 單位 浙江大學
喜歡用大圖看題目的點這裡哦，為你們準備啦
謠言有很多種，本題請你設計一種檢測儀，專門針對一類吹牛話術進行驗證。有人喜歡吹牛，說自己做一場報告有 N 次掌聲。現給定這個人的報告錄音文字版，其中如果有掌聲，記錄中會出現 (zhangsheng) 字樣。請你統計一下報告過程中到底出現了多少次掌聲，並且與其說出的掌聲次數做個比較，來判斷這是不是謠言。
輸入格式：
輸入在第一行給出一個不超過 100 的正整數 N，即某人號稱自己收穫的掌聲次數。
隨後給出由英文字母、數字、標點符號（包括 ,、.、;、:、!）、空格、回車、以及 (zhangsheng) 組成的報告文本，為不超過 10^5個字元的非空字元串，其中語音記錄的文本以 #結尾。
輸出格式：
首先輸出語音記錄中真實的掌聲次數。如果真實次數不小於 N，則隨後空 1 格輸出 True；否則輸出 False。
輸入樣例 1：
3
Hello (zhangsheng). Glad to meet everyone(zhangsheng).
See you (zhangsheng) next time.#
輸出樣例 1：
3 True
輸入樣例 2：
3
Hello (zhangsheng). Glad to meet everyone(zhang
sheng). Let me hear your zhangsheng!\#
輸出樣例 2：
1 False
思路：
一看這道題，要讀入含回車的字元串好麻煩，沒法使用string直接讀入。那隻能轉c語言裡面的getchar()，只需要判斷以'#'結尾就行。
其實你硬要使用string讀也可以，只是我這樣更簡單，完全可以在每次讀入後做一次檢查，然後結束輸入就行
代碼
#include<bits/stdc++.h>
using namespace std;
char a[100010];
int main(){
int n,i=0;cin>>n;
do{
a[i++]=getchar();
}while(a[i-1]!='#');
string b(a,a+i);
//string c="(zhangsheng)";
int cnt=0;//count(b.begin(),b.end(),'(');沒有使用count直接數字元串的功能
while(b.find("(zhangsheng)")!=string::npos){
b.erase(b.find("(zhangsheng)"),12);
cnt++;//使用計數
}
cout<<cnt<<" ";
if(cnt>=n)cout<<"True";
else cout<<"False";
return 0;
}
B-2 一道數學題
分數 20 作者 陳越 單位 浙江大學
設整數 m 和 n 在給定閉區間 [a,b] 內，且滿足等式 
請你求出 m2+n2的最大值。
喜歡用大圖看題目的點這裡哦，為你們準備啦
輸入格式：
輸入給出兩個正整數 a 和 b（1<a<b≤3×10^4），為閉區間的兩個端點。
輸出格式：
在一行中按照以下格式輸出：
max( m^2 + n^2 ) = s
其中 s 是題面要求的m2+n2的最大值，m 和 n 分別對應能取到最大值的 m 和 n 的值。
輸入樣例：
10 100
輸出樣例：
max( 55^2 + 89^2 ) = 10946
思路：
這題直接無腦暴力破解就行，一點腦子都不用
代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;cin>>a>>b;int maxm=0,maxn=0,maxzhi=0;
for(int m=a;m<b;m++){
for(int n=a;n<=b;n++){
if((n*n-m*n-m*m)*(n*n-m*n-m*m)==1){
if(m*m+n*n>maxzhi){
maxm=m;maxn=n;
maxzhi=m*m+n*n;
}
}
}
}
cout<<"max( "<<maxm<<"^2 + "<<maxn<<"^2 ) = "<<maxzhi;
return 0;
}
B-3 代號大本鐘
分數 20 作者 陳越 單位 浙江大學
喜歡用大圖看題目的點這裡哦，為你們準備啦
在“一年一度喜劇大賽”上有一部作品《代號大本鐘》，講的是二戰期間德國情報站里有一位英國間諜，代號“大本鐘”。當最後情報站只剩下兩個人的時候，站長堅信真正的間諜不是間諜，然後用了一下排除法，那就只有他自己是大本鐘了……
現在假設情報站進行了 N 人次排查，最後請你用排除法來查一下，誰是那個“大本鐘”？
輸入格式：
輸入第一行給出一個正整數 N（≤10^4）。隨後 N 行，按照排查的時間先後順序，每行給出一人次排查的結果，格式為：
代號 排查結果
其中 代號 是一個 4 位數字，為被排查的人的編號；排查結果 為 1 表示這人有間諜嫌疑，為 0 表示排除了這人的嫌疑。註意：同一個人可能被排查多次，但無論此前有多少次被列為嫌疑人，本次排查結果為 0 就排除了前面的所有懷疑。
輸出格式：
根據排除法，在一行中列出所有被排查的人中有可能是“大本鐘”的人的編號。編號按遞增序給出，相鄰編號間以 1 個空格分隔，行首尾不得有多餘空格。
如果只有一個人有嫌疑，則在第二行輸出 Da Ben Zhong is found!；如果有多個嫌疑，則輸出 There are n suspects.，其中 n 是嫌疑人的個數。題目保證至少有一個人是“大本鐘”。
輸入樣例 1：
10
1234 1
2234 0
3234 1
1234 1
3234 1
2234 0
2234 1
3234 0
1234 0
1234 0
輸出樣例 1：
2234
Da Ben Zhong is found!
輸入樣例 2：
10
1234 1
2234 0
3234 1
1234 1
3234 1
2234 0
2234 1
3234 0
1234 0
1234 1
輸出樣例 2：
1234 2234
There are 2 suspects.
思路：
也不難，按題目要求模擬就行，因為後面哪個只有0，1輸入用bool就夠了，也沒有卡時間
代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int>booy;
map<int,bool>xyren;
int n,cnt=0;cin>>n;
for(int i=0;i<n;i++){
int bianhao;scanf("%d",&bianhao);
bool b;cin>>b;
xyren[bianhao]=b;//這個也多用不了多少時間
//xyren.insert(make_pair(bianhao,b));本來想用insert省時間，但是用insert會導致出錯，所以還是用重載的[]吧
}
for(auto it=xyren.begin();it!=xyren.end();it++){
if(it->second==1){
cnt++;
booy.emplace_back(it->first);
}
}
int k=booy.size();
for(int i=0;i<k;i++){
printf("%04d",booy[i]);
if(i<k-1)printf(" ");
}
if(cnt==1){
printf("\nDa Ben Zhong is found!");
return 0;
}
printf("\nThere are %d suspects.",cnt);
return 0;
}
B-4 真分數的約分
分數 20 作者 陳越 單位 浙江大學
喜歡用大圖看題目的點這裡哦，為你們準備啦
真分數是指分子小於分母的分數。對分數進行約分，是指將分子分母共同的因數消去。但還有一種另類的簡單約分：直接將分子分母共有的一對數字消去。這種方法大多數情況下都得不到正確的結果，但有時候卻也碰巧能對！例如 26/65 = 2/5 就是直接消去 6 的結果。
現給定一個真分數，你的任務是判斷它是否能用簡單約分方法得到正確結果。註意：如果有多種簡單約分的可能，一定按從左到右的順序約掉數字。
輸入格式：
輸入在一行中給出一個真分數的分子 a 和分母 b，其間以空格分隔。題目保證 0<a<b≤10^5。
輸出格式：
在一行中先後輸出這個真分數在簡單約分前後的樣子。如果兩個分數相等，則在兩者間加一個 = 號；否則加一個 != 號。格式為 a/b = c/d 或 a/b != c/d。
輸入樣例 1：
39 195
輸出樣例 1：
39/195 = 3/15
輸入樣例 2：
1234 23452
輸出樣例 2：
1234/23452 != 1/52
輸入樣例 3：
1234 5678
輸出樣例 3：
1234/5678 = 1234/5678
思路：
做多了的人都知道，到這題就會變著法子的卡測試點了，不過這次不是卡的時間，卡的有兩個點詳情看我代碼
代碼：
#include<bits/stdc++.h>
using namespace std;
int main(){
int m,n;cin>>m>>n;
string a=to_string(m),b=to_string(n);
for(int i=0;i<a.size();i++){
if(b.find(a[i])!=string::npos){
b.erase(b.find(a[i]),1);
a.erase(i,1);
i--;
}
}
if(a.size()==0)a="0";//坑人；首先是全部刪除運行錯誤，我把它保留
//最後一位，又答案錯誤。看了很久才看出來是要把它補為0
if(stod(b)>0&&(double)m/(double)n==stod(a)/stod(b))cout<<m<<"/"<<n<<" = "<<stoi(a)<<"/"<<stoi(b)<<endl;
else cout<<m<<"/"<<n<<" != "<<stoi(a)<<"/"<<stoi(b)<<endl;
//輸出整數儘量不要使用字元串輸出，不然去前導零很麻煩
return 0;
}
B-5 取行李
分數 25 作者 陳越 單位 浙江大學
喜歡用大圖看題目的點這裡哦，為你們準備啦
一般機場里，航班到達後，旅客們會去到達區的行李傳送帶那裡取自己的行李。現假設有一座特別的機場，每條傳送帶只有一個取行李的視窗。旅客們必須排好隊，逐一到視窗取自己的行李。但是當某人到視窗前，發現行李不是自己的，那人就只好走到隊尾去等下一次機會。此時那件行李會一直等在視窗，直到它的主人把它取走。假設每一次認領需要 1 分鐘，本題就要求你計算傳送帶清空需要的時間、以及旅客們的平均等待時間。
例如，假設行李 i 屬於旅客 i。行李的到達順序是 1、2、3，旅客的到達順序是 2、1、3。則 1 號行李要等 2 分鐘才能被主人 1 號旅客取走。這時行李隊列中有 2、3，旅客隊列中是 3、2。於是 2 號行李還要等 2 分鐘才能被 2 號旅客取走，最後 3 號在第 5 分鐘取走行李。旅客們的平均等待時間是 (2+4+5)/3≈3.7。
輸入格式：
輸入首先在第一行給出一個正整數 N（≤10^3）。下一行給出 N 個數字，是 [1,N] 區間內整數的一個重排列，表示旅客隊列。這裡我們假設行李隊列是按 1、2、……、N 有序的，並且行李 i 屬於旅客 i。一行中數字間以空格分隔。
輸出格式：
在一行中輸出傳送帶清空需要的時間、以及旅客們的平均等待時間（輸出小數點後 1 位）。數字間以 1 個空格分隔，行首尾不得有多餘空格。
輸入樣例：
5
3 5 1 2 4
輸出樣例：
9 6.0
思路：
一看到這題，這不就是為隊列準備的題嗎？幸好我早有準備，哈哈哈，就不知道考試的時候運氣有沒有這麼好了，一開始我還以為，行李會每隔一個人取（也就是一分鐘）就會出來一個，但是它卻一直留在那裡，哈哈，和現實生活中機場不太一樣。還是給我調出來了。
代碼
#include<bits/stdc++.h>
using namespace std;
int b[1001]={0};
int main(){
int n;cin>>n;queue<int>a;
for(int i=0;i<n;i++){
int lke;cin>>lke;
a.push(lke);
}
int cnt=0,xli=1;
while(!a.empty()){
cnt++;
int num=a.front();
a.pop();//讀入完就把它pop
if(xli!=num){
a.push(num);//不是它就讓他到隊尾
}
else{
//cout<<num<<" "<<cnt<<endl;//調試用的
b[num]=cnt;
xli++;
}
}
double num=0;
for(int i=1;i<=n;i++){
num+=b[i];
}
cout<<cnt<<" ";printf("%.1lf",num/n);
return 0;
}
都讀到這裡了，給個推薦唄。如果您有疑問或者有更好的解法歡迎評論~
