寒假前班主任幫我們報了名，是得好好準備準備，作為一個CSer，coding能力一定不能太弱，我反思，好久沒寫C/C++代碼了，凈是些隨手寫的python腳本，剛開始上手題目bug一大堆，
由于也不是啥特別的演算法競賽，就把列入這個系列吧，整理發出來，也就是一個回顧，
00 賽事了解
00-1 oi賽制
每道題提交之后都沒有任何的反饋，每個題都有多個測驗點，根據通過的測驗點的數量，來給予分數，每道題不限提交次數，如果提交錯誤沒有任何懲罰，僅以最后一次提交為準，比賽程序中看不到實時排名，賽后按照總得分排名，
輸入輸出明確按規定來做，
00-2 基礎語法
要熟悉一門語言的語法，對于我來說就是C/C++，這一點需要再翻翻書，避免一些低級錯誤，
00-3 演算法與資料結構
這一點需要再復習一下自己的資料結構學習筆記，然后再看看網課，確保自己刷題能夠不卡頓，
00-4 刷題
- 洛谷的官方題單
- 藍橋杯真題
- 北京大學的poj
- acwing
- 力扣（只有介面函式，不是完全，所以這點不好）
遞回和暴力需要多練，保證自己有辦法做出來題目，另外再學學貪心、搜索（深搜極其重要、廣搜一般）、動態規劃，
我此前練了幾十道力扣，今天注冊（0310）了洛谷，做了入門題目，大致了解了一下如何把一個題目通過，
關于如何找題，這個知乎博主回答得比較好：
- 在左側欄里的題單廣場里找，建議先做官方題單，再做用戶分享題單
- 在左側欄里的題庫里找，要搜哪道題就直接搜就行，要搜哪種題就在高級搜索里添加演算法標簽就行，要搜哪種難度的題直接選擇，還有不要只看主題庫里的題，看看CodeForces，SPOJ，AtCoder，UVA的題都不錯
- 還可以看主頁的智能推薦（不過最近智能推薦掛了）
- 終極辦法（不要經常用），直接發帖求題
01 0310
01-1 P1014 [NOIP1999 普及組] Cantor 表
01-1-1 題目描述
現代數學的著名證明之一是 Georg Cantor 證明了有理數是可列舉的，他是用下面這一張表來證明這一命題的：
1/11/1,1/21/2 , 1/31/3, 1/41/4, 1/51/5, …
2/12/1, 2/22/2 , 2/32/3, 2/42/4, …
3/13/1 , 3/23/2, 3/33/3, …
4/14/1, 4/24/2, …
5/15/1, …
…
我們以 Z 字形給上表的每一項編號，第一項是 1/11/1，然后是 1/21/2，2/12/1，3/13/1，2/22/2，…
輸入格式
整數(1<= N <=10^7)，
輸出格式
表中的第 N 項，
01-1-2 輸入輸出樣例
輸入
7
輸出
1/4
01-1-3 解決代碼
#include <iostream>
using namespace std;
int main()
{
int n = 0, sum = 0, i = 1;
cin >> n;
while(sum < n)
{
++i;
//這里用for在回圈上不太好，一定要讓i先自增再求和，否則求出來的和少一項
sum = i*(i - 1)/2;
//首項公差均為1的等引數列求和，此處的和為第i行為止的Cantor表的總項數
}
//總項數與所找項的項數的差
int sub = sum - n;
if(i % 2 != 0)
//如果i奇數，從左開始數
cout << i - 1 - sub << "/" << 1 + sub;
else
//第i行為偶數行，從右邊數
cout << 1 + sub<< "/" << i - 1 - sub;
}
01-2 P1035 [NOIP2002 普及組] 級數求和
01-2-1 題目描述
已知：
\[S_n= 1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n} \]顯然對于任意一個整數 k，當 n 足夠大的時候，有Sn>k；現給出一個整數 k，要求計算出一個最小的 n，使得 Sn > k，
輸入格式
一個正整數 k，
輸出格式
一個正整數 n，
01-2-2 輸入輸出樣例
輸入
1
輸出
2
01-2-3 解決代碼
這個題沒什么好說的，唯一值得注意的是C語言除法里的型別轉換，由于sum是double，如果兩個整數用 ‘/’ 運算子，會得到一個整數，所以得用1./i，
#include<iostream>
using namespace std;
int main(){
int k;
cin >> k;
double sum = 0;
int count = 0,i = 1;
while(sum <= k){
sum += 1./i;
count = i;
i++;
}
cout << count << endl;
return 0;
}
//思路很簡單，但最重要的是要注意1./i的資料型別轉換
//改為1/i就會死回圈
01-3 P1046 [NOIP2005 普及組] 陶陶摘蘋果
01-3-1 題目描述
陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結出 10 個蘋果，
蘋果成熟的時候，陶陶就會跑去摘蘋果，
陶陶有個 30 厘米高的板凳，當她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試，
現在已知 10 個蘋果到地面的高度，以及陶陶把手伸直的時候能夠達到的最大高度，
請幫陶陶算一下她能夠摘到的蘋果的數目，假設她碰到蘋果，蘋果就會掉下來，
輸入格式
輸入包括兩行資料，
第一行包含 10 個 100 到 200 之間（包括 100 和 200 ）的整數（以厘米為單位）
分別表示 10 個蘋果到地面的高度，
兩個相鄰的整數之間用一個空格隔開，
第二行只包括一個 100 到 120 之間（包含 100 和 120 ）的整數（以厘米為單位），
表示陶陶把手伸直的時候能夠達到的最大高度，
輸出格式
輸出包括一行，這一行只包含一個整數，表示陶陶能夠摘到的蘋果的數目，
01-3-2 輸入輸出樣例
輸入
100 200 150 140 129 134 167 198 200 111
110
輸出
5
01-3-3 解決代碼
一遍過了，就是回圈 / 判斷結構，
#include<iostream>
using namespace std;
int main(){
int apple[10]={0};
for(int i = 0; i < 10; i++){
cin >> apple[i];
}
int height;
cin >> height;
int count = 0;
for(int i = 0; i < 10; i++){
if((height+30) >= apple[i]){
count++;
}
}
cout << count;
return 0;
}
//值得注意的是夠不著會踩板凳 +30
02 0311
02-1 P1047 [NOIP2005 普及組] 校門外的樹
02-1-1 題目描述
某校大門外長度為 L 的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是 1 米，
我們可以把馬路看成一個數軸，馬路的一端在數軸 0 的位置，另一端在 L 的位置；
數軸上的每個整數點，即 0,1,2,...,L，都種有一棵樹，
由于馬路上有一些區域要用來建地鐵，
這些區域用它們在數軸上的起始點和終止點表示，
已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分，
現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走，
你的任務是計算將這些樹都移走后，馬路上還有多少棵樹，
輸入格式
第一行有兩個整數，分別表示馬路的長度 L 和區域的數目 m，
接下來 m 行，每行兩個整數 u, v，表示一個區域的起始點和終止點的坐標，
輸出格式
輸出一行一個整數，表示將這些樹都移走后，馬路上剩余的樹木數量，
02-1-2 輸入輸出樣例
輸入
500 3
150 300
100 200
470 471
輸出
298
說明 / 提示 | 資料范圍：
-
對于 20% 的資料，保證區域之間沒有重合的部分，
-
對于 100% 的資料，保證：
\[1 \leq L \leq 10^4 \\ 1 \leq m \leq 100，\\ 0 \leq u \leq v \leq L \]
02-1-3 解決代碼
這基本就是查表思想，如果樹在拆的范圍內，就給標志一下，重復拆也是給相同的標志，最后遍歷輸出樹的陣列，如果沒有標志，則說明是剩余下來的，
不過值得注意的代碼后面我也列出來了：
- 弄清楚取值范圍，題目中是從0到L，左閉右閉；
- 提交代碼要注釋掉測驗的代碼；
#include<iostream>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
int A[n+1]={0};
// for(int i = 0; i < n; i++){
// A[n] = 1;
// }
int B[m][2];
for(int i = 0; i < m; i++){
for(int j = 0; j < 2; j++){
cin >> B[i][j];
}
}
// for(int i = 0; i < m; i++){
// for(int j = 0; j < 2; j++){
// cout << B[i][j]<<endl;
// }
// }
for(int i = 0; i < m; i++){
for(int cnt = B[i][0];cnt<=B[i][1];cnt++){
A[cnt] = 1;
}
}
// for(int i = 0; i < n; i++){
// cout << A[i]<<endl;
// }
int count = 0;
for(int i = 0; i <= n; i++){
//cout << A[i]<<endl;
if(A[i]==0){
count++;
}
}
cout << count;
return 0;
}
//這個題不難，遇到了幾個問題：
1.題目審題，陣列的范圍是什么，是0到l，左閉右閉
2.提交代碼，把一些測驗用的代碼沒有注釋掉就交了
02-2 P1059 [NOIP2006 普及組] 明明的亂數
02-2-1 題目描述
明明想在學校中請一些同學一起做一項問卷調查，
為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(N≤100)，
對于其中重復的數字，只保留一個，把其余相同的數去掉，
不同的數對應著不同的學生的學號，
然后再把這些數從小到大排序，按照排好的順序去找同學做調查，
請你協助明明完成“去重”與“排序”的作業，
輸入格式
輸入有兩行，第1行為1個正整數，表示所生成的亂數的個數N*
第2行有N*個用空格隔開的正整數，為所產生的亂數，
輸出格式
輸出也是兩行，第1行為1個正整數M，表示不相同的亂數的個數，
第2行為M*個用空格隔開的正整數，為從小到大排好序的不相同的亂數，
02-2-2 輸入輸出樣例
輸入
10
20 40 32 67 40 20 89 300 400 15
輸出
8
15 20 32 40 67 89 300 400
02-2-3 解決代碼
這道題在大體思路上很清晰，但在具體細節上還是有點意思的，所以雖然是一遍過，但是花費時間還是久了點，
具體細節就是：
- 排序可以直接排，
- 洗掉元素我有兩種考慮，一種是雙指標，即一個為主指標，另一個輔助指標以主指標為起點向后探測，如果與主指標值相同則繼續向后，直到不同，再讓主指標直接跳躍過去，這種需要建立一個新陣列來存主指標指到過的值，
- 另外一種就是哈希表了，畢竟也是學過資料結構刷過幾道力扣的人了，哈希表雖然空間復雜度高一些，但時間上很不錯，思路實作上更簡單，于是最終使用的是哈希表，
4.由于對于STL的不熟悉，在原陣列上動刀的事情目前干不出來，說來也是慚愧，STL當初在一個專案上好好學了，現在卻不能熟練的用出來，
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int N;
cin >> N;
int A[N];
for(int i = 0; i < N; i++){
cin >> A[i];
}
sort(A,A+N);
// for(int i = 0; i < N; i++){
// cout << A[i] << " ";
// }
// 排序完成，下面看看能不能刪掉重復的
int hash[1000]={0};
for(int i = 0; i < 1000;i++){
for(int j = 0; j < N; j++){
if(A[j]==i){
hash[i]=1;
}
}
}
//cout << endl;
int count = 0;
int result[100]={0};
int j = 0;
for(int i = 0; i < 1000; i++){
if(hash[i]==1){
//cout << i+1 << " ";
result[count++]=i;
}
}
cout << count << endl;
for(int i = 0; result[i]!=0&&i<100;i++){
cout << result[i]<< " ";
}
//哈希表實作
//雙指標
// for(int i = 0; i<N;i++){
// for(int j = i+1; j < N;j++){
// if(A[j]!=A[i]){
// break;
// }
// }
// }
return 0;
}
02-3 P1075 [NOIP2012 普及組] 質因數分解
02-3-1 題目描述
已知正整數n是兩個不同的質數的乘積，試求出兩者中較大的那個質數，
輸入格式
一個正整數n，
輸出格式
一個正整數p*，即較大的那個質數，
02-3-2 輸入輸出樣例
輸入
21
輸出
7
說明/提示
\[n\le 2\times 10^9 \]02-3-3 解決代碼
這道題考察一個基礎的數論知識：
唯一分解定理:一個數能且只能分解為一組質數的乘積，
并且還要明白，題目中的一個正整數，可以被分解為兩個質數對于測驗資料的限制，自己就不要打23或是45這種資料來測驗，因為根本就不在范圍內，
#include<iostream>
using namespace std;
int main(){
long int num, i;
cin >> num;
for( i = 2 ; i * i < num; i++){
if(num%i==0){
break;
}
}
cout << num/i <<endl;
}
//實作挺簡單的，可以從num開始--，也可以從2開始++求出小質數再求大質數，
02-4 P1085 [NOIP2004 普及組] 不高興的津津
02-4-1 題目描述
津津上初中了，
媽媽認為津津應該更加用功學習，所以津津除了上學之外，還要參加媽媽為她報名的各科復習班，
另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴，
但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興，
假設津津不會因為其它事不高興，并且她的不高興不會持續到第二天，
請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興，
輸入格式
輸入包括7行資料，分別表示周一到周日的日程安排，
每行包括兩個小于10的非負整數，用空格隔開，
分別表示津津在學校上課的時間和媽媽安排她上課的時間，
輸出格式
一個數字，如果不會不高興則輸出0，
如果會則輸出最不高興的是周幾
（用1, 2, 3, 4, 5, 6, 71,2,3,4,5,6,7分別表示周一，周二，周三，周四，周五，周六，周日），
如果有兩天或兩天以上不高興的程度相當，則輸出時間最靠前的一天，
02-4-2 輸入輸出樣例
輸入
5 3
6 2
7 2
5 3
5 4
0 4
0 6
輸出
3
02-4-3 解決代碼以及優化
思路很簡單，甚至我寫起來還會顯得笨手笨腳的（代碼有點啰嗦）一步一步的太笨重，
值得注意的是最后的tag判斷，如果把放到最外一層的for回圈內部，最后一組資料會出錯，當時結果出來還有點頭疼，后來意識到是放在回圈里可能會導致一些不能預料的結果，
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int data[7][2],sum[7];
for(int i = 0 ; i < 7; i++){
for(int j = 0; j < 2; j++){
cin >> data[i][j];
}
}
for(int i = 0; i < 7; i++){
sum[i] = data[i][0] + data[i][1];
}
int count = 0, tag = 0;
for(int i = 0; i < 7; i++){
if(sum[i]<=8){
tag++;
continue;
}
else{
int* temp = max_element(sum,sum+7);
for(int j = 0; j < 7; j++){
if(sum[j]==*temp){
cout << j+1 <<endl;
break;
}
}
break;
}
}
if(tag==7){
cout << 0 << endl;
}
return 0;
}
//奧對，最重點的是使用了一個直接求陣列中最大值的函式max_element,回傳值是一個指標
//還是被此前專案函式調包什么的慣壞了，資料結構老師要是知道了得罵死我，
由于覺得自己寫的實在是太笨重了，我決定看看題解，發現我被陣列牢牢地束縛住了，離開陣列就很難做事情，就比如下面洛谷題解中贊最多的這一個(個人手打，原作者爭持Zill）：
#include<iostream>
using namespace std;
int main(){
int num1，num2, sum;
int day = 0, max = 0;
for(int i = 1; i < 8; i++){
cin >> a >>b;
sum = num1 + num2;
if((s > max)&&(sum>8)){
max = sum;
day =i;
}
}
cout << day;
return 0;
}
還有一個作者，直接順序分支結構，確實，題目中明確只有七組數，七個if陳述句就可以解決，按照復雜度理論，將會是O(1)，hhhh，（實際上是用手寫所有if來代替回圈了，
03 0312 / 0315
事實上這期間只寫了這一道題（除了上一道題在0312也有一些作業，比如看題解），因為有其他的事情，練題計劃中斷了（比如寫Java作業、復變、概率論作業等等），0312的思路沒寫出來，0315晚上靈機一動，有了另一種解決方案，
03-1 P1089 [NOIP2004 提高組] 津津的儲蓄計劃
津津的零花錢一直都是自己管理，每個月的月初媽媽給津津300300元錢，津津會預算這個月的花銷，并且總能做到實際花銷和預算的相同，
為了讓津津學習如何儲蓄，媽媽提出，津津可以隨時把整百的錢存在她那里，到了年末她會加上20%還給津津，
因此津津制定了一個儲蓄計劃：每個月的月初，在得到媽媽給的零花錢后，
如果她預計到這個月的月末手中還會有多于100元或恰好100元，她就會把整百的錢存在媽媽那里，剩余的錢留在自己手中，
例如11月初津津手中還有83元，媽媽給了津津300元，津津預計1111月的花銷是180元，那么她就會在媽媽那里存200元，自己留下183元，到了11月月末，津津手中會剩下3元錢，
津津發現這個儲蓄計劃的主要風險是，存在媽媽那里的錢在年末之前不能取出，有可能在某個月的月初，津津手中的錢加上這個月媽媽給的錢，不夠這個月的原定預算，如果出現這種情況，津津將不得不在這個月省吃儉用，壓縮預算，
現在請你根據2004年1月到12月每個月津津的預算，判斷會不會出現這種情況，如果不會，計算到2004年年末，媽媽將津津平常存的錢加上20％還給津津之后，津津手中會有多少錢，
輸入格式
12行資料，每行包含一個小于350的非負整數，分別表示1月到12月津津的預算，
輸出格式
一個整數，如果儲蓄計劃實施程序中出現某個月錢不夠用的情況，輸出-X，
X表示出現這種情況的第一個月；
否則輸出到20042004年年末津津手中會有多少錢，
注意，洛谷不需要進行檔案輸入輸出，而是標準輸入輸出，
03-1-2 輸入輸出樣例
輸入1
290
230
280
200
300
170
340
50
90
80
200
60
輸出1
-7
輸入2
290
230
280
200
300
170
330
50
90
80
200
60
輸出2
1580
03-1-3 解決代碼
這道題在說法上比較繞，
第一步，輸入當月預算cost，+上月剩余last1到剩下的錢last2，300+0-290=10，
第二步，判斷是否>=100：
如果大于，則減去整百部分，
如果小于，繼續一二步，
第三步，如果12個月回圈完畢一直是小于，那就輸出last+save*1.2
如果>=100后，last取負值，則輸出當月的月份，
上述編程的邏輯問題就在一處，即，第三步中的，last取負值的判定，我采用的是last<0，則輸出此前記錄的月份的負值，問題就在于last最后不一定<0
//上面思路走不下去，借鑒題解再來一次
#include<iostream>
using namespace std;
int main(){
int money = 0, cost[12] = {0}, save = 0, flag = 1, failid = 0;
for(int i = 0; i < 12; i++){
cin >> cost[i];
}
for(int i = 1; i <= 12; i++){
money+=300;
//cin >> cost;
money-=cost[i-1];
if(money<0){
flag = 0;
//說明已經透支
failid = i;
break;
}
save+=money/100;//用100的個數代替100
money%=100;//存款后剩余的前
//與我最初的思路相差在于，我冗余了一個判斷是否超過100的陳述句
//事實上money不超過100的話，%100還是它自己，
}
if(flag==1){
money+=save*120;
cout << money;
}
else{
cout <<-failid;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/445323.html
標籤：其他
上一篇：外包的選擇
下一篇：API 介面的安全處理