算法競賽入門【碼蹄集新手村600題】（MT1301-1350）
(文章目錄)
前言
為什麼突然想學算法了？
> 用較為“官方”的語言講，是因為算法對計算機科學的所有分支都非常重要。 在絕大多數的計算機科學分支領域中，要想完成任何實質性的工作，了解算法的基礎知識并掌握與算法密切相關的資料結構知識是必不可少的。
> 但從實際而言，是因為當下快到了考研和找工作的年紀(ಥ_ಥ)，無論走哪一條路，都不免需要一些相對豐富的算法知識，是故，便産生了一個暑假速成算法的計劃，可能對于像我這種算法競賽小白而言，幾乎很難，但我仍然還是想嘗試一下，畢竟，夢想還是要有的，萬一實作了呢？～(￣▽￣～)~
為什麼選擇碼蹄集作為刷題軟體？
碼蹄集，是在全國高等學校計算機教學與産業實踐資源建設專家委員會(TIPCC) 指導下建設的，其依托全國各大名校計算機系和清華大學出版社等機關的強大資源，旨在為計算機學習愛好者提供全面和權威的計算機習題。
算法競賽入門【碼蹄集新手村600題】（MT1301-1350）算法競賽入門【碼蹄集新手村600題】（MT1301-1350）前言目錄
目錄
1. MT1301 1的補碼
（1）題目描述
給定一個整數N，編寫一個程式來查找該整數的1的補碼，輸出對應的十進制整數。比如5的二進制數是101，寫成4位是0101，它對應的1的補碼是1010，1010是十進制形式的10。不考慮不合理的輸入等特殊情況。
1的補碼的定義:
1對二進制數的補碼是另一個通過切換二進制數中的所有位而得到的二進制數，即:
(我們這裡預設每4位二進制下的位數，進行一次翻轉)0位轉換為1和1位轉化為0.
eg:
1010 - 0101
1001 -0110
0001 0001 -1110 1110
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 255
.
輸出格式: 0
備注：
N可能較大，需要定義為長整型
（2）參考代碼
import java.util.Scanner;
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextInt( );
long zn = Long.numberOfLeadingZeros(n) % 4;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < zn; i++) {
sb.append("0");
}
String n_s = sb.append(Long.toBinaryString(n)).toString( );
long sum = 0;
for (int i = 0; i < n_s.length( ); i++) {
if (n_s.charAt(i) == "0".charAt(0)) {
sum += Math. pow(2, n_s.length() - 1 - i);
}
}
System.out.println( sum);
sc.close();
}
}
2. MT1302 二進制轉格雷碼
（1）題目描述
二進制碼轉換格雷碼的方法:從右邊第一位起，依次将每一位與左邊一位異或(XOR)，作為對應格雷碼在該位的值，最左邊一位不變;比如二進制0010對應的格雷碼是0011。
輸入一個4位的二進制整數，輸出對應的格雷碼。
不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入二進制整數
.
輸出格式: 輸出二進制整數
樣例1
輸入格式: 0110
.
輸出格式: 0101
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
string n;
cin>>n;
string s=n;
for(int i=1;i<s.size();i++) cout<<((s[i]-'0')^(s[i-1]-'0'));
return 0;
}
3. MT1303 格雷碼轉二進制
（1）題目描述
格雷碼轉換二進制碼的方法:從左邊第二位起，将每位與左邊一位解碼後二進制碼的值異或，作為該位解碼後的值（最左邊一位不變)。比如格雷碼0011對應的二進制是0010。
輸入一個4位的格雷碼整數，輸出對應的二進制。
不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入二進制整數
.
輸出格式: 輸出二進制整數
樣例1
輸入格式: 1000
.
輸出格式: 1111
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
string s;
cin>>s;
cout<<s[0];
for(int i=1;i<s.length();i++){
int x=s[i-1]-'0';
int y=s[i]-'0';
int z=x^y;
s[i]=z+'0';
cout<<z;
}
cout<<endl;
return 0;
}
4. MT1304 十進制與格雷碼
（1）題目描述
給您一個十進制數n (O~7)。您需要找到數字n的格雷碼并将其轉換為十進制數。假定格雷碼為3位，則O~7的格雷碼序列是:000，001，011，010，110,111，101，100，可以看出4的格雷碼是110，而110對應的十進制數是6，是以G(4) =6。
不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 7
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,book[8]={0,1,3,2,6,7,5,4};
cin>>n;
cout<<book[n]<<endl;
return 0;
}
5. MT1305 三位數
（1）題目描述
一個自然數的七進制表達式是一個三位數，而這個自然數的九進制表示也是一個三位數，且這兩個三位數的數位正好相反，編寫程式求這個自然數。
格式
輸入格式: 無
.
輸出格式:輸出為整型
樣例1
輸入格式: 無
.
輸出格式: 248
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
for(int i=100;i<667;i++){
int b=i/100;
int s=i/10%10;
int g=i%10;
if(b*7*7+s*7+g==g*9*9+s*9+b&&s<7&&g<7)
cout<<b*7*7+s*7+g;
}
return 0;
}
6. MT1306 牛頓疊代法
（1）題目描述
由牛頓疊代法求方程2xxx+4xx-7x-6=0在x=1.5附近的根。
格式
輸入格式:無
.
輸出格式:輸出為實型
樣例1
輸入格式:無
.
輸出格式: 1.539441
備注：
精度控制在1e-6
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double newton_method(int a,int b,int c,int d){
double x1,x0,fx,f;
x1=1.5;
while(fabs(x1-x0)>=1e-6){
x0=x1;
fx=a*x0*x0*x0+b*x0*x0+c*x0+d;
f=3*a*x0*x0+2*b*x0+c;
x1=x0-fx/f;
}
return(x1);
}
int main( )
{
int a,b,c,d;
a=2,b=4,c=-7,d=-6;
double root;
root=newton_method(a,b,c,d);
printf("%lf",root);
return 0;
}
7. MT1307 對分法
（1）題目描述
用對分法求方程xx一6x-1=0在區間[-10,0]上的實根。
格式
輸入格式:無
.
輸出格式:輸出為實型
樣例1
輸入格式:無
.
輸出格式: -0.162278
備注：
精度控制在1e-6
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
float f(float x){
return x*x-6*x-1;
}
int main( )
{
float a,b,eps=1e-6,c;
a=-10;
b=0;
while((b-a)>0.0000001){
c=(a+b)/2;
if(f(c)==0) break;
else if(a*f(c)>0) b=c;
else a=c;
}
printf("%lf",c);
return 0;
}
8. MT1308 4個自然數
（1）題目描述
求4個自然數p,q,r,s(p≤q≤r≤s)，使得等式1/p+1/q+1/r+1/s=1成立。
格式
輸入格式: 無
.
輸出格式: 輸出為整型，空格分隔，每組一行
樣例1
輸入格式: 無
.
輸出格式:
2 3 7 42
2 3 8 24
2 3 9 18
2 3 10 15
2 3 12 12
2 4 5 20
2 4 6 12
2 4 8 8
2 5 5 10
2 6 6 6
3 3 4 12
3 3 6 6
3 4 4 6
4 4 4 4
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int p,q,r,s;
float t;
for(p=2;p<=4;p++){
for(q=p;q<=6;q++){
for(r=q;r<=12;r++){
for(s=r;s<=47;s++){
t=1.0/p+1.0/q+1.0/r+1.0/s;
if(t-1>-0.000001 && t-1<0.000001){
printf("%d %d %d %d\n",p,q,r,s);
}
}
}
}
}
return 0;
}
9. MT1309 最大和
（1）題目描述
數組中有N個元素，找出累加和最大的連續子序列，輸出這個和。
格式
輸入格式: 第—行輸入數組長度N，第二行輸入數組元素，整型，空格分隔。
.
輸出格式: 輸出整型
樣例1
輸入格式:
5
2 5 -1 2 -1
.
輸出格式: 8
備注：
連續子序列的元素個數可以是1個，也可以是N個。
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,nums[1000];
cin>>n;
for(int i=0;i<n;i++) cin>>nums[i];
int sum=nums[0];
for(int i=0;i<n;i++){
int tmp=0;
for(int j=i;j<n;j++){
tmp+=nums[j];
if(tmp>sum) sum=tmp;
}
}
cout<<sum;
return 0;
}
10. MT1310 最大乘積
（1）題目描述
數組中有N個元素，找出乘積最大的連續子序列，輸出他們的乘積。
格式
輸入格式: 第一行輸入數組長度N，第二行輸入數組元素，整型，空格分隔。
.
輸出格式:輸出整型
樣例1
輸入格式:
5
2 5 -1 2 -1
.
輸出格式: 20
備注：
數值較大，需要定義為長整型。N小于100。連續子序列的元素個數可以是1個，也可以是N個。
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
long long int nums[1000];
cin>>n;
for(int i=0;i<n;i++) cin>>nums[i];
long long int sum=nums[0];
for(int i=0;i<n;i++){
long long int tmp=1;
for(int j=i;j<n;j++){
tmp*=nums[j];
if(tmp>sum) sum=tmp;
}
}
cout<<sum;
return 0;
}
11. MT1311 組數
（1）題目描述
用0:9可以組成多少無重複的3位數。
格式
輸入格式: 無
.
輸出格式: 輸出為整型
樣例1
輸入格式: 無
.
輸出格式: 648
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int sum=0;
for(int i=0;i<=9;i++){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++){
if(k!=0 && i!=j && j!=k && i!=k) sum++;
}
}
}
cout<<sum;
return 0;
}
12. MT1312 給定的商
（1）題目描述
輸入一個給定的商（商<80)，商為正整數。求出對應的被除數(5位數)和除數(4位數)。要求被除數和除數每個位置上(個位，十位...）的數字隻能出現一次。
注:隻使用1到9的9個數字
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型，空格分隔。每組一行。如果沒有比對的結果，則不輸出。
樣例1
輸入格式: 62
.
輸出格式:
79546 1283
94736 1528
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int judge(ll a,ll b){
bool g[10] = {0};
ll f = a*100000+b;
for(int i=1;i<=10;i++){
if(g[f%10]==0) g[f%10]=1;
else return 0;
f = f/10;
}
return 1;
}
int main( )
{
int n;
cin>>n;
for(int i=1000;i<=9999;i++){
if(i*n>99999 || i*n<10000) continue;
if(judge(i,i*n)==1) cout<<i*n<<" "<<i<<endl;
}
return 0;
}
13. MT1313 1比2比3
（1）題目描述
程式設計求解3個特殊的整數A，B，C，他們的關系是1:2:3的關系，要求A，B，C，都是3位數，而且每個位置上(個位，十位和百位)的數字隻能出現一次。
注:隻使用1到9的9個數字
格式
輸入格式: 無
.
輸出格式: 輸出整型，如樣例所示
樣例1
輸入格式: 無
.
輸出格式:
.
192:384:576=1:2:3
219:438:657=1:2:3
273:546:819=1:2:3
327:654:981=1:2:3
（2）參考代碼
import java.util.Scanner;
import java.util.*;
class Main {
static boolean check(int a,int b, int c){
int[] num = new int[10];
String num_str = ""+a+b+c;
if(num_str.length()!=9){
return false;
}
int num_add = Integer.parseInt(num_str);
while(num_add>0){
int tmp = num_add % 10;
if(tmp == 0 || num[tmp] != 0){
return false;
}else{
num[tmp]=1;
}
num_add /=10;
}
return true;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// code here
for(int i=100;i<1000;i++){
for(int j=100;j<1000;j++){
for(int k=100;k<1000;k++){
if(i*2==j && i*3==k && check(i,j,k)){
System.out.format("%d:%d:%d=1:2:3\n",i,j,k);
}
}
}
}
input.close();
}
}
小結(一)
經典範例：
進制數：MT1301-1304
14. MT1314 精确的小數
（1）題目描述
以A/B的形式輸入一個分數，轉換成小數輸出，保留N位小數。
格式
輸入格式: 輸入整型A，B，N，空格分隔。
.
輸出格式: 輸出實型，保留N位小數。
樣例1
輸入格式: 1 6 3
.
輸出格式: 0.167
備注：
因為預設資料類型保留的小數位數有限，此題需要用代碼模拟除法和四舍五入過程。1<N<=100。
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a,b,n,dp[1005];
cin>>a>>b>>n;
dp[0] = a/b;
a=a%b;
for(int i=1;i<=n+1;i++){
a*=10;
dp[i]=a/b;
a=a%b;
}
if(dp[n+1]>=5){
dp[n]++;
for(int i=n-1;i>=1;i--){
if(dp[i+1]==10){
dp[i]++;
dp[i+1]=0;
}
}
if(dp[1]==10) dp[0]++,dp[1]=0;
}
cout<<dp[0]<<".";
for(int i=1;i<=n;i++) cout<<dp[i];
cout<<endl;
return 0;
}
15. MT1315 百戰天蟲
（1）題目描述
精靈女王派出精靈大軍對戰n隻天蟲，精靈一共有m個。傷害值為x的精靈，可以殺死防禦力小于等于x的天蟲并消耗x點體力。精靈女王如何安排才能保證大軍體力值消耗最小。假定精靈和天蟲都隻能各自出戰一次。
格式
輸入格式: 第一行輸入n和m，第二行輸入n隻天蟲防禦力，第三行輸入m個精靈傷害值，全部為正整數。
.
輸出格式: 輸出整型最小體力值消耗，若無法擊敗則輸出"null”。
樣例1
輸入格式:
2 3
5 4
7 8 4
.
輸出格式: 11
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000];
int main( )
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=m;j++) cin>>b[j];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int ans=0;
for(int i=1,j=1;i<=n;i++){
while(j<=m&&b[j]<a[i])j++;
if(j>m){
cout<<"null";
return 0;
}
ans+=b[j];
j++;
}
cout<<ans;
return 0;
}
16. MT1316 6個球
（1）題目描述
盒子裡共有12個球，其中3個紅球、3個白球、6個黑球。從中任取6個球，問至少有一個球是紅球的取法有多少種?輸出每一種具體的取法。
格式
輸入格式: 無
.
輸出格式: 輸入所有的取法，第一列是編号，後面依次是紅球，白球，黑球的數量，如樣例所示
樣例1
輸入格式: 無
.
輸出格式:
1: 1 0 5
2: 1 1 4
3: 1 2 3
4: 1 3 2
5: 2 0 4
6: 2 1 3
7: 2 2 2
8: 2 3 1
9: 3 0 3
10: 3 1 2
11: 3 2 1
12: 3 3 0
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a=3,b=3,c=6,num=1;
for(int i=1;i<=3;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=6;k++){
if(i+j+k==6 && i>=1){
cout<<num<<": "<<i<<" "<<j<<" "<<k<<endl;
num++;
}
}
}
}
return 0;
}
17. MT1317 雙色球
（1）題目描述
用遞歸法求解。有一些裝有黑球和白球的盒子，數量均足夠多。要求把n (小于30)個盒子放成一行，但至少有3個黑球放在一起，有多少種方法?
格式
輸入格式: 輸入整型n
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 8
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int count(int n){
if(n<3) return 0;
else if(n==3) return 1;
else if(n==4) return 3;
else return 2*count(n-1)+pow(2,n-4)-count(n-4);
}
int main( )
{
int n;
cin>>n;
cout<<count(n);
return 0;
}
18. MT1318 完美平方
（1）題目描述
輸入正整數N，檢查它是否為完美平方。完美平方數是指1個平方數可以分成兩部分後，每個部分仍然是平方數。如49=77，分成4和9，4和9都是平方數。再如1681=4141，1681分成16和81，也都是平方數。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 49
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
bool is_pifang(int n){
if((int)sqrt(n)*(int)sqrt(n)==n) return true;
else return false;
}
int main( )
{
int n;
cin>>n;
bool flag1=true;
string s=to_string(n);
int len=s.length();
if(is_pifang(n)){
for(int i=1;i<len;i++){
int tmp=0;
for(int j=i;j<len;j++){
tmp=tmp*10+s[j]-'0';
}
if(is_pifang(tmp)==0) continue;
tmp=0;
for(int j=i;j<len;j++) tmp=tmp*10+s[j]-'0';
if(is_pifang(tmp)==0) continue;
cout<<"YES";
return 0;
}
}
else cout<<"NO";
return 0;
}
19. MT1319 分數拆分
（1）題目描述
輸入正整數A，找出所有正整數B>=C，使得1/A = 1/B+1/C。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型A，B，C，空格分隔，每組一行。
樣例1
輸入格式: 4
.
輸出格式:
4 20 5
4 12 6
4 8 8
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a;
cin>>a;
for(int c=1;c<1000;c++){
for(int b=c;b<1000;b++){
if(b*c==a*c+a*b) cout<<a<<" "<<b<<" "<<c<<endl;
}
}
return 0;
}
20. MT1320 和為偶數
（1）題目描述
給定一個大小為N的數組arr[]，計算數組元素的和。再将數組中一個最小的數(應大于O)加上去，使數組的和變為偶數。求這個數是多少并輸出。比如arr[]={1，2，3，4,5，6,7，8,9}，則應該加1。
格式
輸入格式: 第一行輸入數組長度N，第二行輸入數組元素，正整數，空格分隔。
.
輸出格式: 輸出整型
樣例1
輸入格式:
8
1 2 3 4 5 6 7 8
.
輸出格式: 2
備注：
N小于100
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,a[10005],sum=0,res;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
sum+=a[i];
}
sort(a+1,a+n+1);
int ou=10000,ji=10000;
for(int i=1;i<=n;i++){
if((a[i]%2==1)&&a[i]<ji) ji=a[i];
if((a[i]%2==0)&&a[i]<ou) ou=a[i];
if(ou!=10000&&ji!=10000) break;
}
if(sum%2==0) res=ou;
else res=ji;
cout<<res<<endl;
return 0;
}
21. MT1321 乘積數組
（1）題目描述
數組A大小為N，構造一個同樣大小的乘積數組B，使B[i]等于A[i]以外的所有其他元素的乘積，輸出B數組。
格式
輸入格式: 第一行輸入數組長度N，第二行輸入數組元素，整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式:
5
1 3 5 6 20
.
輸出格式: 1800 600 360 300 90
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,a[105];
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
int div=1;
for(int j=0;j<n;++j)
if(j!=i) div*=a[j];
cout<<div<<" ";
}
return 0;
}
小結(二)
經典例題
- 百戰天蟲：MT1315
- 雙色球：MT1317
- 完美平方：MT1318
- 分數拆分：MT1319
- sort函數的用法：能夠對普通的快速排序進行優化，結合了插入排序和堆排序。根據不同的數量級别以及不同情況，能自動選用合适的排序方法。推薦連結1、推薦連結2
22. MT1322 N個骰子
（1）題目描述
給定N個骰子，每個骰子有M個面，編号從1到M，找出獲得總和SUM的方法的數量。SUM是所有骰子抛出時面上值的總和。
格式
輸入格式: 輸入整型N,M和SUM，空格分隔。
.
輸出格式: 輸出整型
樣例1
輸入格式: 3 6 12
.
輸出格式: 25
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int f[100][10000];
int main( )
{
int n,m,x;
cin>>n>>m>>x;
for(int j=1;j<=m&&j<=x;j++) f[1][j]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=x;j++){
for(int k=1;k<j&&k<=m;k++) f[i][j]+=f[i-1][j-k];
}
}
cout<<f[n][x];
return 0;
}
23. MT1323 元音
（1）題目描述
從1号球開始，每個球通向另外兩個球。1通向2和3。2通向4和5。3通向6和7等等，相連通的兩個球之間距離視為1。
如下圖所示：
給定x和y兩球的号，找出它們之間最短路徑的長度。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出Y或N
樣例1
輸入格式: 2 6
.
輸出格式: 3
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x,y,a=0,b=0;
cin>>x>>y;
while(x!=y){
if(x>y){
x/=2;
a++;
}else{
y/=2;
b++;
}
}
cout<<a+b;
return 0;
}
24. MT1324 兩數之和
（1）題目描述
輸入長度為n的數列a，和一個目标值x，輸出a中是否存在兩個位置不同的數之和為x。
格式
輸入格式:
第一行兩個整數n(n<100)，x，空格分隔
第二行n個整數的數列a，空格分隔
.
輸出格式: 0代表不存在，1代表存在
樣例1
輸入格式:
3 3
1 2 3
.
輸出格式: 1
備注：
n>1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x,n;
cin>>n>>x;
int a[105];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i]+a[j]==x&&i!=j){
cout<<1;
return 0;
}
}
}
cout<<0;
return 0;
}
25. MT1325 四數之和
（1）題目描述
輸入長度為n的數列a，和一個目标值x，輸出a中是否存在四個位置不同的數之和為x。
格式
輸入格式:
第一行兩個整數n(n<200)，x，空格分隔
第二行n個整數的數列a，空格分隔
.
輸出格式: 0代表不存在，1代表存在
樣例1
輸入格式:
5 10
1 2 3 4 5
.
輸出格式: 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x,n;
cin>>n>>x;
int a[105];
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(a[i]+a[j]>x){
cout<<"0"<<endl;
return 0;
}else{
int high = n-1,low=j+1;
int y=x-(a[i]+a[j]);
while(high>low){
if(a[high]+a[low]<y) low++;
else if(a[high]+a[low]>y) high--;
else{
cout<<"1";
return 0;
}
}
}
cout<<0;
return 0;
}
26. MT1326 波蘭國旗問題
（1）題目描述
給定一個長度為n的字元串，其中隻包含0和1，請在O(n)時間複雜度内将其從小到大排序後輸出。
格式
輸入格式:
輸出一個整數n(n<100)
第二行包含一個長度為n的字元串
.
輸出格式: 輸出排序後的字元串
樣例1
輸入格式:
7
0101010
.
輸出格式: 0000111
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
string s;
int bucket[105];
int main( )
{
int n;
cin>>n;
cin>>s;
for(int i=0;i<n;i++){
bucket[s[i]-'0']++;
}
for(int i=0;i<=1;i++){
for(int j=1;j<=bucket[i];j++){
cout<<i;
}
}
cout<<endl;
return 0;
}
27. MT1327 荷蘭國旗問題
（1）題目描述
給定一個長度為n的字元串，其中隻包含0，1和2，請在O(n)時間複雜度内将其從小到大排序後輸出。
格式
輸入格式:
輸出一個整數n(n<100)
第二行包含一個長度為n的字元串
.
輸出格式: 輸出排序後的字元串
樣例1
輸入格式:
7
0120120
.
輸出格式: 0001122
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
string s;
int bucket[105];
int main( )
{
int n;
cin>>n;
cin>>s;
for(int i=0;i<n;i++){
bucket[s[i]-'0']++;
}
for(int i=0;i<=2;i++){
for(int j=1;j<=bucket[i];j++){
cout<<i;
}
}
cout<<endl;
return 0;
}
28. MT1328 用函數求和
（1）題目描述
定義一個函數int add(int x,int y)，在主函數中輸入兩個整數a，b，調用add函數求a,b的和，再在主函數中輸出和。
格式
輸入格式: 輸入兩個整數a,b，逗号分隔
.
輸出格式: 輸出和，整型
樣例1
輸入格式: 2,4
.
輸出格式: 6
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int add(int x,int y){
return x+y;
}
int main( )
{
int a,b,s;
scanf("%d,%d",&a,&b);
s=add(a,b);
cout<<s;
return 0;
}
29. MT1329 用函數計算公式
（1）題目描述
編寫函數fun,求1+4＋7＋10 +..…..n的和。主函數中輸入正整數n，輸出累加和。比如輸入7，則求1＋4+7的和，如果輸入5，則求1＋4的和。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 5
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int fun(int n){
int sum=0;
for(int i=1;i<=n;i=i+3){
sum+=i;
}
return sum;
}
int main( )
{
int n;
cin>>n;
cout<<fun(n);
return 0;
}
30. MT1330 區間數字的總和
（1）題目描述
求[a,b]，[c,d]，[e,f]，三個區間整數的總和,abcdef的值由鍵盤輸入。
格式
輸入格式: 輸入整數abcdef，空格分隔
.
輸出格式: 輸出整型
樣例1
輸入格式: 1 2 3 4 5 6
.
輸出格式: 21
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int fun(int a,int b){
int sum=0;
for(int i=a;i<=b;i++){
sum+=i;
}
return sum;
}
int main( )
{
int a,b,c,d,e,f;
cin>>a>>b>>c>>d>>e>>f;
int sum=0;
sum=fun(a,b)+fun(c,d)+fun(e,f);
cout<<sum;
return 0;
}
31. MT1331 用函數求Π的近似值
（1）題目描述
編寫函數Fun，用公式Π/4=1-1/3+1/5-1/7+....求Π的近似值，直到某一項的絕對值小于10的-6次方，并傳回近似值。在main函數調用Fun函數，并輸出。
格式
輸入格式: 無
.
輸出格式: 輸出實型，保留2位小數
樣例1
輸入格式: 無
.
輸出格式: 3.14
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double fun(){
double pi=0,tmp=1;
int c=1,i=1;
while(tmp>1e-6){
tmp=1.0/i;
pi+=c*tmp;
c*=-1;
i+=2;
}
return pi*4;
}
int main( )
{
printf("%.2f",fun());
return 0;
}
32. MT1332 用函數求最大值
（1）題目描述
定義一個函數，在主函數中輸入4個整數，調用函數求最大值，再在主函數中輸出。
格式
輸入格式: 輸入整型，空格分隔
.
輸出格式: 輸出整型
樣例1
輸入格式: 5 6 9 1
.
輸出格式: 9
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a,b,c,d,tmp1,tmp2,tmp3;
cin>>a>>b>>c>>d;
tmp1=max(a,b);
tmp2=max(c,d);
tmp3=max(tmp1,tmp2);
cout<<tmp3;
return 0;
}
33. MT1333 用函數求最小值
（1）題目描述
定義一個函數，在主函數中輸入4個整數，調用函數求最小值，再在主函數中輸出。
格式
輸入格式: 輸入整型，空格分隔
.
輸出格式: 輸出整型
樣例1
輸入格式: 5 6 9 1
.
輸出格式: 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a,b,c,d,tmp1,tmp2,tmp3;
cin>>a>>b>>c>>d;
tmp1=min(a,b);
tmp2=min(c,d);
tmp3=min(tmp1,tmp2);
cout<<tmp3;
return 0;
}
34. MT1334 最小整數
（1）題目描述
編寫函數getceil(x)，傳回大于等于x的最小整數，例如getceil(2.8)為3，getceil(-2.8)為-2。
格式
輸入格式: 輸入為實型
.
輸出格式: 輸出為整型
樣例1
輸入格式: 2.8
.
輸出格式: 3
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int getceil(double x){
if(x>0) return int(x+1);
else return (int)x;
}
int main( )
{
double x;
cin>>x;
cout<<getceil(x);
return 0;
}
35. MT1335 最大整數
（1）題目描述
編寫函數getfloorl(x)，傳回大于等于x的最大整數，例如getceil(2.8)為2，getceil(-2.8)為-3。
格式
輸入格式: 輸入為實型
.
輸出格式: 輸出為整型
樣例1
輸入格式: 2.8
.
輸出格式: 2
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int getceil(double x){
int tmp=(int)x;
if(x>=0||(x-tmp)==0) return (int)x;
else return (int)x-1;
}
int main( )
{
double x;
cin>>x;
cout<<getceil(x);
return 0;
}
36. MT1336 用函數求階乘
（1）題目描述
定義一個函數int fact(int x)，在主函數中輸入正整數a，調用fact函數求a的階乘，再在主函數中輸出階乘
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 120
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int fact(int x){
int sum=1;
for(int i=1;i<=x;i++) sum*=i;
return sum;
}
int main( )
{
int n;
cin>>n;
cout<<fact(n);
return 0;
}
37. MT1337 n次方
（1）題目描述
編寫函數fun，求任一整數m的n次方(n為非負數)。
格式
輸入格式: 輸入整型，空格分隔
.
輸出格式: 輸出整型
樣例1
輸入格式: 4 3
.
輸出格式: 64
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int m,n;
cin>>m>>n;
cout<<(int)pow(m,n);
return 0;
}
38. MT1338 開n次方
（1）題目描述
編寫函數計算x開n次方的正實根S(x,n)，在主函數中輸入資料調用函數輸出結果。不考慮不合理輸入等特殊情況。本題使用二分法。
格式
輸入格式: 輸入x為實型，n為整數，空格分隔。前面是x，後面是n。
.
輸出格式: 輸出為實型
樣例1
輸入格式: 7 2
.
輸出格式: 2.645751
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double S(double x,int n){
return pow(x,1.0/n);
}
int main( )
{
double x;
int n;
cin>>x>>n;
cout<<fixed<<setprecision(6)<<S(x,n)<<endl;
return 0;
}
39. MT1339 平均數
（1）題目描述
編寫函數計算：
格式
輸入格式: 輸入為實型，第一行輸入n，第二行輸入n個數，空格分隔
.
輸出格式: 輸出為實型
樣例1
輸入格式:
3
1 2 3
.
輸出格式: 2.000000
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
double n,a[1000],sum=0,s=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
double avg=sum/n;
for(int i=1;i<=n;i++){
s+=(a[i]-avg)*(a[i]-avg);
}
printf("%lf",s);
return 0;
}
40. MT1340 平均值函數
（1）題目描述
有一個一維數組，含N個整型元素，編寫一個函數double avg(int arr[],intbegin,int end)，求解從起始位置下标begin到結束位置下标end的所有元素的平均值。不考慮不合理的輸入等特殊情況。
格式
輸入格式: 第一行輸入數組長度N，起始位置下标begin，結束位置下标end，第二行輸入數組元素，整型，空格分隔。
.
輸出格式: 輸出實型
樣例1
輸入格式:
10 1 8
1 2 3 4 5 6 7 8 9 10
.
輸出格式: 5.500000
備注：
N不大于100
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double avg(int arr[],int begin,int end){
double sum=0;
for(int i=begin;i<=end;i++){
sum+=arr[i];
}
double avg=sum/(end-begin+1);
return avg;
}
int main( )
{
int a[1000],begin,end,n;
cin>>n>>begin>>end;
for(int i=0; i<n;i++) cin>>a[i];
printf("%lf",avg(a, begin, end));
return 0;
}
小結(三)
典型範例：
- N個骰子：MT1322
- 最短路徑：MT1323-1325
- 桶排序：MT1326
- 二分法：MT1338
41. MT1341 反比例函數
（1）題目描述
已知f(x)=1/x，編寫函數用梯形法計算f(x)在區間[a,b]的積分(O<a<b)。(比如可以将區間等分為1000份)
格式
輸入格式: 輸入為整型，空格分隔。
.
輸出格式: 輸出為實型(保留2位小數)
樣例1
輸入格式: 2 3
.
輸出格式: 0.41
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double f(double x){
return 1/x;
}
int main( )
{
int a,b;
cin>>a>>b;
double area=0;
for(int i=0;i<1000;i++) area+=(f(a+i*(b-a)*0.001)+f(a+(i+1)*(b-a)*0.001))*(b-a)*0.001/2;
printf("%.2lf",area);
return 0;
}
42. MT1342 函數積分
（1）題目描述
已知f(x)=1/(1+x)，編寫函數用梯形法計算f(x)在區間[a,b]的積分。(確定x >-1,輸入不考慮不合法情況)
格式
輸入格式: 輸入為整型，空格分隔
.
輸出格式: 輸出為實型
樣例1
輸入格式: 0 10
.
輸出格式: 2.397895
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double f(double x){
return 1/(1+x);
}
int main( )
{
int a,b;
cin>>a>>b;
double area=0;
for(int i=0;i<(b-a)*1000;i++) area+=(f(a+i*0.001)+f(a+(i+1)*0.001))*0.001/2;
printf("%lf",area);
return 0;
}
43. MT1343 積分
（1）題目描述
已知f(x)=1/(1+x*x)，編寫函數用梯形法計算f(x)在區間[a,b]的積分。
格式
輸入格式: 輸入為整型，空格分隔
.
輸出格式: 輸出為實型
樣例1
輸入格式: -10 10
.
輸出格式: 2.942255
備注：
精度為0.001
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double f(double x){
return 1/(1+x*x);
}
int main( )
{
int a,b;
cin>>a>>b;
double area=0;
for(int i=0;i<(b-a)*1000;i++) area+=(f(a+i*0.001)+f(a+(i+1)*0.001))*0.001/2;
printf("%lf",area);
return 0;
}
44. MT1344 組合
（1）題目描述
編寫函數，計算從n個元素中取m個元素的組合數C(m,n)。
格式
輸入格式: 輸入為正整數，空格分隔
.
輸出格式: 輸出為整型
樣例1
輸入格式: 6 3
.
輸出格式: 20
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int factor(int n){
if(n<=1) return 1;
else return n*factor(n-1);
}
int c(int m,int n){
return factor(m) / (factor(m-n)*factor(n));
}
int main( )
{
int m,n;
cin>>m>>n;
cout<<c(m,n);
return 0;
}
45. MT1345 分段函數
（1）題目描述
編寫函數求Y的值，當輸入X大于等于0時，Y的值是X開2次方，當X小于0時，Y=X+33。在主函數中輸入×，調用函數輸出Y。
格式
輸入格式: 輸入為實型
.
輸出格式: 輸出為實型
樣例1
輸入格式:0
.
輸出格式: 0.000000
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
double fun(double x){
double y=0;
if(x>=0) y=sqrt(x);
else y=x+33;
return y;
}
int main( )
{
double x;
cin>>x;
printf("%lf",fun(x));
return 0;
}
46. MT1346 加密
（1）題目描述
某個公司采用公用電話傳遞資料，資料是四位的整數，在傳遞過程中是加密的。加密函數如下:每位數字都加上5，然後用除以10的餘數代替該數字，再将第一位和第四位交換，第二位和第三位交換。
本題要求用自定義函數。不考慮負數或者其他非法輸入等特殊情況。
格式
輸入格式: 輸入為整形
.
輸出格式: 輸出為整型
樣例1
輸入格式: 1234
.
輸出格式: 9876
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int func(int n){
string s=to_string(n);
int len = s.length();
for(int i=0;i<len;i++){
int tmp = s[i]-'0';
tmp=(tmp+5)%10;
s[i]=tmp+'0';
}
int sum=(s[0]-'0')+(s[3]-'0')*1000+(s[1]-'0')*10+(s[2]-'0')*100;
return sum;
}
int main( )
{
int n;
cin>>n;
cout<<func(n);
return 0;
}
47. MT1347 數組計算
（1）題目描述
有兩個數組A和B，他們都有N(<100)個非0整數元素，編寫4個函數，分别實作他們的“加減乘除”運算，即根據輸入的運算符把對應元素做加減乘除運算，結果放在C數組的對應位置，輸出C數組。
格式
輸入格式: 第一行輸入數組長度N，後兩行分别輸入A，B數組的元素，整型，空格分隔。最後一行輸入運算符。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式:
5
1 2 3 4 5
5 4 3 2 1
.
輸出格式: 6 6 6 6 6
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
void jia(int a[],int b[],int n){
for(int i=0;i<n;i++){
int tmp=a[i]+b[i];
cout<<tmp<<" ";
}
}
void jian(int a[],int b[],int n){
for(int i=0;i<n;i++){
int tmp=a[i]-b[i];
cout<<tmp<<" ";
}
}
void chen(int a[],int b[],int n){
for(int i=0;i<n;i++){
int tmp=a[i]*b[i];
cout<<tmp<<" ";
}
}
void chu(int a[],int b[],int n){
for(int i=0;i<n;i++){
int tmp=a[i]/b[i];
cout<<tmp<<" ";
}
}
int main( )
{
int n,a[105],b[105];
char ch;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
cin>>ch;
switch(ch){
case '+':
jia(a,b,n);
break;
case '-':
jian(a,b,n);
break;
case '*':
chen(a,b,n);
break;
case '/':
chu(a,b,n);
}
return 0;
}
48. MT1348 方程系數
（1）題目描述
輸入正整數a和b，編寫一個函數，求滿足方程ax-by=0中的x和y的最小值并輸出，其中x>0、y>0、a>0和b>0。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 25 35
.
輸出格式: 7 5
備注：
此題，x y為最小正整數解
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
void func(int a,int b){
int i=1;
while((a*i)%b!=0) i++;
cout<<i<<" "<<a*i/b;
}
int main( )
{
int a,b;
cin>>a>>b;
func(a,b);
return 0;
}
49. MT1349 歐幾裡得算法
（1）題目描述
編寫函數int gcd(int a, int b)，使用歐幾裡德算法，給定a和b計算最大公約數輸出。不考慮溢出等特殊情況。
格式
輸入格式:輸入正整數a和b，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 30 20
.
輸出格式：10
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a%b==0) return b;
else return gcd(b, a%b);
}
int main( )
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}
50. MT1350 分數計算
（1）題目描述
編寫函數，實作分數加減運算并輸出結果，注意結果要化為最簡分數。不考慮不合理的輸入等特殊情況，比如分母不能為0。
格式
輸入格式: 輸入形式A/B+C/D或者A/B-C/D，其中ABCD為整型。
.
輸出格式: 輸出形式X/Y，或-X/Y，其中XY為正整數。如果結果為0，則直接輸出0。
樣例1
輸入格式: 1/8+1/4
.
輸出格式: 3/8
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a%b==0) return b;
else return gcd(b, a%b);
}
int main( )
{
int a,b,c,d,den,ans;
char ch;
bool flag=false;
scanf("%d/%d%c%d/%d",&a,&b,&ch,&c,&d);
den = b*d;
a*=d;
c*=b;
if(ch=='+'){
a+=c;
ans = gcd(a,den);
a/=ans,den/=ans;
printf("%d/%d",a,den);
}else{
a-=c;
if(a==0){
cout<<0<<endl;
return 0;
}
if(a<0){
flag=true;
a=-a;
}
ans=gcd(abs(a),den);
a/=ans,den/=ans;
if(flag) printf("-%d/%d",a,den);
else printf("%d/%d",a,den);
}
return 0;
}
小結(四)
- 函數積分：MT1342
- 組合數：MT1344
- 分數計算：MT1350