前言/背景編程競賽報名地址:https://edu.csdn.net/contest/detail/16
題目與解題代碼目前已經(jīng)連續(xù)參加10次的編程競賽了,這種比賽挺有意義,希望一直舉辦下去!
1. 圓小藝本次題目與往常一樣有四個,這邊貼出我當(dāng)時的解題代碼。
輸入描述:
第一行輸入整數(shù)n.(1<=n<=1000)表示圓的數(shù)量。
第二行輸入n個圓的半徑。(1<=r<=1000)
輸出描述:
輸出染色面積,保留小數(shù)點后3位。
輸入樣例:
3
1 2 3
輸出樣例:
18.849
這題乍一看以為是染色問題,但仔細一想比染色問題簡單多了。只需要記錄下奇數(shù)層圓環(huán)的面積和偶數(shù)層圓環(huán)的面積,然后判斷最外層屬于偶數(shù)層還是奇數(shù)層即可。
#include#include#include#include#include
#includedouble solution(int n, std::vector& vec){sort(vec.begin(),vec.end());
double result;
double PI =3.14159265354;
// TODO:
double ji_area = 0.0;
double ou_area = 0.0;
for(int i=0;iif(i%2==0){if(i==0){ou_area+=PI*vec[i]*vec[i];
}else{ou_area+=PI*(vec[i]*vec[i]-vec[i-1]*vec[i-1]);
}
}if
(i%2!=0){ji_area+=PI*(vec[i]*vec[i]-vec[i-1]*vec[i-1]);
}
}if
(n%2==0){result=ji_area;
}else{result=ou_area;
}return result;
} int main() {int n;
std::vectorvec;
std::cin>>n;
std::string line_0, token_0;
getline(std::cin >>std::ws,line_0);
std::stringstream tokens_0(line_0);
while(std::getline(tokens_0, token_0, ' ')){vec.push_back(std::stoi(token_0));
}
double result = solution(n,vec);
std::cout<
2. K皇把妹還需要注意的是精度問題,題目要求精度是3位小數(shù),所以 π \pi π需要盡可能地取得精確點。
輸入描述:
第一行輸入整數(shù)n,m,k.(1<=n,m,k<=100)
第二行輸入n個整數(shù)的權(quán)值。(1<=a<=1000)
輸出描述:
輸出最小距離
輸入樣例:
7 3 50
62 0 0 0 99 33 22
輸出樣例:
3
這題也很簡單,從節(jié)點 m m m分別向左、向右找滿足條件的值即可。
#include#include#include#includeint solution(int n, int m, int k, std::vector& vec){int result=0;
// TODO:
int start = m-1;
int index1 = -10000;
int index2=-10000;
for(int i=start+1;iif(k>=vec[i]&&vec[i]>0){index1=i;
break;
}
}
for(int i=start-1;i>=0;i--){if(k>=vec[i]&&vec[i]>0){index2=i;
break;
}
}
result = abs(start-index1)>abs(start-index2)?abs(start-index2):abs(start-index1);
return result;
}
int main() {int n;
int m;
int k;
std::vectorvec;
std::cin>>n;
std::cin>>m;
std::cin>>k;
std::string line_0, token_0;
getline(std::cin >>std::ws,line_0);
std::stringstream tokens_0(line_0);
while(std::getline(tokens_0, token_0, ' ')) {vec.push_back(std::stoi(token_0));
}
int result = solution(n, m, k,vec);
std::cout<
3. 篩選寶物輸入描述:
第一行輸入寶物的數(shù)量n(1
這是一道經(jīng)典的背包問題。背包問題的講解非常推薦看代碼隨想錄。
#include#include#include#includeint solution(int n, int M, std::vector>& vec){int result;
// TODO:
std::vector>dp(n,std::vector(M+1,0));
for(int j=vec[0][0];j<=M;++j){dp[0][j]=vec[0][1];
}
for(int i=1;ifor(int j=0;j<=M;j++){if(jdp[i][j]=dp[i-1][j]>dp[i-1][j-vec[i][0]]+vec[i][1]?dp[i-1][j]:dp[i-1][j-vec[i][0]]+vec[i][1];
}
}
}
result = dp[n-1][M];
return result;
}
int main() {int n;
int M;
std::cin >>n;
std::cin >>M;
std::vector>vec(n, std::vector(2));
for (int i = 0; i< n; i++) {std::cin >>vec[i][0] >>vec[i][1];
}
int result = solution(n, M, vec);
std::cout<< result<< std::endl;
return 0;
}
4. 圓桌輸入描述:
第一行輸入一個整數(shù)N,(1<=N<=10000),代表客人的數(shù)量
接下來N行,每行兩個整數(shù)li與ri,(1<=i<=N,1<=li<=ri<=1000000000)
代表第i位客人希望左邊有l(wèi)i個空座位,右邊有ri個空座位。
輸出描述:
輸出一個整數(shù),代表主人需要準備的最少座位數(shù)量。
輸入樣例:
3
1 1
1 1
1 1
輸出樣例:
6
這一題對我來說難度挺高,我也不知道怎么做。。所以當(dāng)時用非常投機取巧的方式過了 40 % 40\% 40%。
#include#include#include#includeint solution(int n, std::vector>& vec){int result=0;
// TODO:
result+=n;
for(int i=0;iif(vec[i][0]>vec[i][1]){result+=vec[i][0];
}else{result+=vec[i][1];
}
}
return result;
} int main() {int n;
std::cin >>n;
std::vector>vec(n, std::vector(2));
for (int i = 0; i< n; i++) {std::cin >>vec[i][0] >>vec[i][1];
}
int result = solution(n, vec);
std::cout<< result<< std::endl;
return 0;
}
后面看別人題解時說是一道原題,原題出處戳此,屬于貪心題型。
正確解法如下:
#include#include#include#include#include
int solution(int n, std::vector>& vec){int result=0;
// TODO:
std::vectorleft(n),right(n);
for(int i=0;ileft[i]=vec[i][0];
right[i]=vec[i][1];
}
sort(left.begin(),left.end());
sort(right.begin(),right.end());
result = n;
for(int i=0;iresult+=std::max(left[i],right[i]);
}
return result;
} int main() {int n;
std::cin >>n;
std::vector>vec(n, std::vector(2));
for (int i = 0; i< n; i++) {std::cin >>vec[i][0] >>vec[i][1];
}
int result = solution(n, vec);
std::cout<< result<< std::endl;
return 0;
}
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源,準確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧