算法競賽入門【碼蹄集新手村600題】(MT1151-1200）
(文章目錄)
前言
為什麼突然想學算法了？
> 用較為“官方”的語言講，是因為算法對計算機科學的所有分支都非常重要。 在絕大多數的計算機科學分支領域中，要想完成任何實質性的工作，了解算法的基礎知識并掌握與算法密切相關的資料結構知識是必不可少的。
> 但從實際而言，是因為當下快到了考研和找工作的年紀(ಥ_ಥ)，無論走哪一條路，都不免需要一些相對豐富的算法知識，是故，便産生了一個暑假速成算法的計劃，可能對于像我這種算法競賽小白而言，幾乎很難，但我仍然還是想嘗試一下，畢竟，夢想還是要有的，萬一實作了呢？～(￣▽￣～)~
為什麼選擇碼蹄集*作為刷題軟體？
碼蹄集，是在全國高等學校計算機教學與産業實踐資源建設專家委員會(TIPCC) 指導下建設的，其依托全國各大名校計算機系和清華大學出版社等機關的強大資源，旨在為計算機學習愛好者提供全面和權威的計算機習題。
算法競賽入門【碼蹄集新手村600題】(MT1151-1200）算法競賽入門【碼蹄集新手村600題】(MT1151-1200）前言目錄
目錄
1. MT1151 韓信生氣
（1）題目描述
韓信點兵(大于10人)，三個三個一排多2個，五個五個一排又多2個，七個七個一排還多2個。韓信生氣了，怎麼總多你倆，出去!問原本隊伍裡面最少應該有多少人。
格式
輸入格式: 無
.
輸出格式: 輸出整型
樣例1
輸入格式: 無
.
輸出格式: 107
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x=11;
while(x++){
if(x%3==2&&x%5==2&&x%7==2){
cout<<x;
break;
}
}
return 0;
}
2. MT1152 韓信又生氣了
（1）題目描述
韓信點兵(大于10人)，三個三個一排少1個人，五個五個一排又少1個人，七個七個一排還少1個人。韓信生氣了，從别的隊伍裡調來一個人!這樣不管是三個一排五個一排還是七個一排都完美了。問原本最少應該有多少人。
格式
輸入格式: 無
.
輸出格式:輸出整型
樣例1
輸入格式: 無
.
輸出格式: 104
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x=11;
while(x++){
if(x%3==2&&x%5==4&&x%7==6){
cout<<x;
break;
}
}
return 0;
}
3. MT1153 真因子
（1）題目描述
輸入正整數N，計算其所有真因子之和。自然數的真因子是嚴格小于該數的除數。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 10
.
輸出格式: 8
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,ans=0;
cin >> n;
for(int i=1;i<=n/2+1;i++){
if(n%i==0) ans+=i;
}
cout<<ans<<endl;
return 0;
}
4. MT1154 缺數
（1）題目描述
若一個自然數的所有真因數之和比這個數小，此數就叫做缺數。輸入正整數N，找出該數字是否為缺數輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 21
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,ans=0;
cin >> n;
for(int i=1;i<=n/2+1;i++){
if(n%i==0) ans+=i;
}
if(ans<n) cout<<"YES";
else cout<<"NO";
return 0;
}
5. MT1155 機關矩陣
（1）題目描述
輸入3X3的整型矩陣A，判斷是否為機關矩陣，輸出YES或者NO。
格式
輸入格式: 輸入矩陣，空格分隔
.
輸出格式:輸出YES或者NO
樣例1
輸入格式: 1 0 0 0 1 0 0 0 1
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[4][4],cnt=0;
bool flag=false;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cin >> a[i][j];
if(a[i][j]) cnt++;
}
}
if(a[1][1]&&a[2][2]&&a[3][3]&&cnt==3) flag=true;
if(a[1][3]&&a[2][2]&&a[3][1]&&cnt==3) flag=true;
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
6. MT1156 稀疏矩陣
（1）題目描述
輸入3X3的整型矩陣A，判斷是否為稀疏矩陣，輸出YES或者NO。若矩陣中數值為0的元素數目多于非0元素的數目就叫做稀疏矩陣。
格式
輸入格式: 輸入矩陣，空格分隔
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 4 0 0 0 5 0 0 0 6
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[4][4],cnt=0,num=0;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cin >> a[i][j];
if(a[i][j]==0) cnt++;
else num++;
}
}
if(cnt>num) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
7. MT1157 矩陣相等
（1）題目描述
輸入4X4的整型矩陣A和B，判斷是否為相等，輸出YES或者NO。
格式
輸入格式: 輸入矩陣，空格分隔。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
4 0 0 0 5 0 0 0 6 1 2 3 4 5 6 7
4 0 0 0 5 0 0 0 6 1 2 3 4 5 6 7
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[5][5],b[5][5];
bool flag=false;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin >> a[i][j];
}
}
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin >> b[i][j];
if(a[i][j]!=b[i][j]){
cout<<"NO"<<endl;
return 0;
}
}
}
cout<<"YES"<<endl;
return 0;
}
8. MT1158 分解
（1）題目描述
輸入正整數N和M，判斷N是否可以分解成M個不同的正整數的和，輸出YES或者NO。
格式
輸入格式: 輸入正整數N和M，空格分隔
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 5 2
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,m,sum=0;
cin >>n>>m;
for(int i=1;i<m;i++){
sum+=i;
}
if(n>=sum) cout<< "YES";
else cout<<"NO";
return 0;
}
9. MT1159 指定集合
（1）題目描述
某數組含有N個元素，輸出那些數字來自集合{4,5,6}的元素，按原序。沒有就輸出-1。
格式
輸入格式: 第一行輸入數組長度N，第二行輸入數組元素，整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式:
4
1 2 3 4
.
輸出格式: 4
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,m;
bool flag=false;
cin >> n;
for(int i=1;i<=n;i++){
cin >> m;
if(m==4 || m==5 || m==6){
flag=true;
cout << m<<" ";
}
}
if(!flag) cout << -1 <<endl;
return 0;
}
10. MT1160 尾數為零
（1）題目描述
輸入正整數N，請在1!，2! ， 3! ...N!中查找尾數為零的數，統計這樣的數字的個數并輸出。
格式
輸入格式: 輸入正整數N
.
輸出格式:輸出整型
樣例1
輸入格式: 5
.
輸出格式: 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,num=1,ans=0;
cin >>n;
for(int i=1;i<=n;i++){
num*=i;
if(num%10==0) ans++;
}
cout<<ans;
return 0;
}
11. MT1161 N的零
（1）題目描述
輸入正整數N，将N的所有零轉換為5。沒有0就原樣輸出。不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 5002
.
輸出格式: 5552
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
string s;
int len;
cin >> s;
len = s.size();
for(int i=0;i<len;i++){
if(s[i]=='0') s[i]='5';
}
cout << s <<endl;
return 0;
}
12. MT1162 數組最大公約數
（1）題目描述
給定一個由N個正整數組成的數組，求所有數組元素的最大公約數。
格式
輸入格式: 第一行輸入數組長度N，第二行輸入數組元素，整型，空格分隔。
.
輸出格式: 輸出整型
樣例1
輸入格式:
3
2 4 6
.
輸出格式: 2
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int getGCD(int a,int b){
if(a%b==0) return b;
else return getGCD(b, a%b);
}
int main( )
{
int nums[100],n,ans=0;
cin >> n;
for(int i=0;i<n;i++) cin >> nums[i];
sort(nums,nums+n);
ans = getGCD(nums[n-1],nums[n-2]);
for(int i=n-3;i>=2;i--) ans = getGCD(ans, nums[i]);
cout<<ans;
return 0;
}
13. MT1163 孿生質數
（1）題目描述
在質數中，若兩個質數之差為2,我們稱之為孿生質數,例如(3、5)(5、7)，輸入2個正整數，判斷他是不是孿生質數，輸出YES或者NO。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出YES或NO
樣例1
輸入格式: 2 6
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
bool zhi(int n){
if(n==1) return false;
for(int i=2;i<=n/2;i++){
if(n%i==0){
return false;
}
}
return true;
}
int main( )
{
int a,b;
cin >> a >>b;
if(zhi(a)&&zhi(b)&&b-a==2||a-b==2) cout<<"YES";
else cout<<"NO";
return 0;
}
小結(一)
經典範例：
MT1153(真因子)、MT1155、MT1156、MT1157、MT1159
MT1160、MT1161、MT1162、MT1163(判斷質數)
14. MT1164 最大數字
（1）題目描述
輸入正整數N，找到小于或等于它的最大數字，并且其數字從高位到低位是非遞減的順序。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 200
.
輸出格式: 199
備注：
若N為個位數，則所求為它本身
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
bool cmp(int x,int y){
if(x>y) return false;
return true;
}
int main( )
{
string s;
int n,len;
double res;
cin >> n;
for(int i=n;i>=0;i--){
s = to_string(i);
len = s.size();
bool flag = true;
for(int j=0;j<len-1;j++){
flag = cmp(s[j]-'0',s[j+1]-'0');
if(!flag) break;
}
if(flag){
res=i;
break;
}
}
if(n<10) res=n;
cout << res <<endl;
return 0;
}
15. MT1165 卡羅爾數
（1）題目描述
卡羅爾數是其值滿足4n-2 (n+1) -1的整數(n為正整數)。輸入正整數N判斷它是不是卡羅爾數，輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 1
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
bool flag=false;
cin >> n;
for(int i=0;(2*i-3)<=n;i++){
if(n==2*i-3) flag=true;
}
if(flag) cout<<"YES";
else cout<<"NO";
return 0;
}
16. MT1166 自守數
（1）題目描述
輸入正整數N (N<10)，判斷該數是否為自守數輸出YES或者NO。當且僅當一個數的平方以與該數相同的數字結尾時，該數稱為自守數。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 5
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
cin >> n;
if(n*n%10==n) cout<<"YES";
else cout<<"NO";
return 0;
}
17. MT1167 自守數II
（1）題目描述
輸入正整數N，檢查該數是否為自守數輸出YES或者NO。當且僅當一個數的平方以與該數相同的數字結尾時，該數稱為自守數。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 76
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,l,m=1;
cin >> n;
l=n;
while(l>0){
m*=10;
l=l/10;
}
int k=n*n-n;
if(k%m==0) cout<<"YES";
else cout<<"NO";
return 0;
}
18. MT1168 階乘數
（1）題目描述
輸入正整數N，找出它是否是一個等于其他數的階乘值的數，輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 5
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,sum=1;
bool flag=false;
cin >> n;
for(int i=1;i<=n;i++){
sum*=i;
if(n==sum) flag=true;
}
if(flag) cout<<"YES";
else cout<<"NO";
return 0;
}
19. MT1169 平衡數
（1）題目描述
輸入一個正整數，它有N位數，N是大于1的奇數，判斷它是不是平衡數。如果左側的所有數字和等于右側的所有數字之和，則稱為平衡數。不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 1234006
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
string s;
int len,sum=0;
cin >> s;
len=s.size();
for(int i=0;i<len;i++){
if(i<len/2) sum+=s[i];
if(i>len/2) sum-=s[i];
}
if(sum==0) cout<<"YES";
else cout<<"NO";
return 0;
}
20. MT1170 四葉玫瑰數
（1）題目描述
輸入正整數N，判斷它是不是一個四葉玫瑰數，輸出YES或者NO。四位玫瑰數是4位數的自幂數，它的每個位上的數字的4次幂之和等于它本身。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 1634
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,len,ans;
bool flag;
string s;
cin >> n;
s = to_string(n);
len = s.size();
for(int i=0;i<len;i++){
ans+=pow(s[i]-'0',4);
}
if(ans == n) flag=true;
if(len != 4) flag = false;
if(flag) cout <<"YES"<<endl;
else cout <<"NO"<<endl;
return 0;
}
21. MT1171 幻數
（1）題目描述
一個數字，把他的各位數累加會得到一個新的數字，再把這個新數字的每一位加起來，重複這個過程，直到隻剩下一位數字，如果最後剩下的數字是1，就稱原數為一個幻數。輸入正整數N，檢查它是否是一個幻數，輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:1234
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
string s;
int ans,len,n;
bool flag;
int circleAdd(int n){
s = to_string(n);
len = s.size();
ans = 0;
for(int i = 0;i<len;i++){
ans+=s[i]-'0';
}
return ans;
}
int main( )
{
cin >> n;
int tmp = n;
while(1){
tmp = circleAdd(tmp);
if(tmp == 1){
flag = true;
break;
}else if(tmp<10) break;
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
小結(二)
經典例題
MT1164、MT1166、MT1167、MT1169、MT1170
MT1171(幻數)
22. MT1172 完美數字
（1）題目描述
輸入正整數N，檢查它是否完美輸出YES或者NO。把一個數字的每一位拆分開，計算他們的階乘再累加，如果和等于原數字，則該數字是完美的。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 145
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
string s;
int ans,len,n;
bool flag;
int factorial(int n){
int tmp=1;
for(int i=n;i>=1;i--){
tmp*=i;
}
return tmp;
}
int main( )
{
cin >> n;
s = to_string(n);
len = s.size();
for(int i=0;i<len;i++) ans+=factorial(s[i]-'0');
if(ans==n) flag=true;
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
23. MT1173 魔數
（1）題目描述
一個數字，把他乘以二，會得到一個新的數字，如果這個新數字依然由原數中那些數字組成，就稱原數為一個魔數。輸入正整數N，檢查它是否是一個魔數，輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 142857
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double pi=3.1415926;
double res;
int ans,n,m,t,len,cnt=0,minn=10000,maxx=0;
string s;
char ch;
bool flag = true;
int dp[1000] = {0},bucket1[1000]={0},bucket2[1000]={0};
int main( )
{
cin>>n;
s=to_string(n);
len=s.size();
for(int i=0;i<len;i++) bucket1[s[i]-'0']++;
ll tmp;
tmp = n*2;
s = to_string(tmp);
len = s.size();
for(int i=0;i<len;i++) bucket2[s[i]-'0']++;
for(int i=0;i<=9;i++){
if(bucket1[i]!=bucket2[i]){
flag = false;
break;
}
}
if(flag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
24. MT1174 A的B次方
（1）題目描述
輸入正整數N，判斷它是否可以表示為A的B次方，其中B>1，A>0，都是整數。輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 6
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,tmp;
bool flag=false;
cin >> n;
if(n==1){
cout<<"YES";
return 0;
}
for(int i=2;i*i<=n;i++){
for(int j=2;pow(i,j)<=n;j++){
if(pow(i,j)==n) flag=true;
}
}
if(flag) cout<<"YES";
else cout<<"NO";
return 0;
}
25. MT1175 網球比賽
（1）題目描述
兩個網球隊進行比賽，各出三人。甲隊為a,b,c三人，乙隊為x,y,z三人。已抽簽決定比賽名單。有人向隊員打聽比賽的名單。a說他不和x比，c說他不和x,z比，請程式設計式找出三對賽手的名單。
格式
輸入格式: 無
.
輸出格式: 分3行輸出，見樣例
樣例1
輸入格式: 無
.
輸出格式:
a with z
b with x
c with y
解析：
算一下即可，或者直接面向測試用例程式設計，沒必要一個一個循環進行周遊
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
cout<<"a with z"<<endl;
cout<<"b with x"<<endl;
cout<<"c with y"<<endl;
return 0;
}
26. MT1176 兩個點的距離
（1）題目描述
給定笛卡爾平面上兩個點的坐标，求它們之間的距離向上舍入為最接近的整數。
格式
輸入格式: 輸入整型，空格分隔
.
輸出格式: 輸出整型
樣例1
輸入格式: 0 0 2 -2
.
輸出格式: 3
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x1,y1,x2,y2,ans;
cin >> x1 >> y1;
cin >> x2 >> y2;
ans = ceil(sqrt(pow(x1-x2,2) + pow(y1-y2,2)));
cout << ans <<endl;
return 0;
}
27. MT1177 三角形
（1）題目描述
輸入三角形的三個頂點坐标，和點N的坐标。判斷N是否位于三角形内，輸出YES或者NO。
格式
輸入格式: 第一行輸入三角形的三個頂點坐标(x1,y1) , (x2，y2）和(x3，y3)，第二行輸入點N的坐标，整型，空格分隔。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
0 0 20 0 10 30
10 15
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int Area(int x1,int y1,int x2,int y2,int x3,int y3){
double result = abs((x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3)/2.0);
return result;
}
int main( )
{
int x1,y1,x2,y2,x3,y3,x4,y4;
double s123,s124,s134,s234;
cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
s123 = Area(x1, y1, x2, y2, x3, y3);
s124 = Area(x1, y1, x2, y2, x4, y4);
s134 = Area(x1, y1, x3, y3, x4, y4);
s234 = Area(x4, y4, x2, y2, x3, y3);
if(s123==s124+s134+s234){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
return 0;
}
28. MT1178 點與線段的關系
（1）題目描述
輸入線段的2個端點的坐标值x和y，再輸入第3個點的坐标，判斷點在不線上段上，輸出YES或者NO。
格式
輸入格式: 按照先起點(x,y）再終點(x,y）的次序。第二行輸入第3個點的坐标。坐标整型。第一行兩點之間空格，如樣例所示。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
(-20,20) (-20,-10)
(0,0)
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int p1x,p1y,p2x,p2y;
int qx,qy;
scanf("(%d,%d) (%d,%d)\n",&p1x,&p1y,&p2x,&p2y);
scanf("(%d,%d)",&qx,&qy);
if((qx-p1x)*(p2y-p1y)==(p2x-p1x)*(qy-p1y)&&min(p1x,p2x)<=qx&&qx<=max(p1x,p2x)&&min(p1y,p2y)<=qy&&qy<=max(p1y,p2y))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
29. MT1179 線段與線段的關系
（1）題目描述
輸入2個線段的端點的坐标值x和y，判斷兩條線是否為平行線。輸出YES或者NO。另:不考慮共線情況。
格式
輸入格式: 輸入整型，空格分隔。按照先起點（x,y)，空格，再終點(x,y)的次序。每行一個線段的資訊。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
(-20,20) (-20,-10)
(0,0) (5,0)
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a,b,c,d,aa,bb,cc,dd;
scanf("(%d,%d) (%d,%d)\n",&a,&b,&c,&d);
scanf("(%d,%d) (%d,%d)",&aa,&bb,&cc,&dd);
if((d-b)*(cc-aa)==(dd-bb)*(c-a)) cout<<"YES";
else cout<<"NO";
return 0;
}
30. MT1180 兩條線段
（1）題目描述
輸入2個線段的端點的坐标值x和y (x,y不重合)，判斷兩條線段是否交叉，輸出YES或者NO。
格式
輸入格式: 輸入整型，空格分隔。按照先起點(x,y)，空格，再終點(x,y)）的次序。每行一個線段的資訊。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
(-20,20) (-20,-10)
(0,0) (5,0)
.
輸出格式: NO
（2）參考代碼
#include<stdio.h>
#include<stdlib.h>
int judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2);
int main()
{
int Ax1,Ay1,Ax2,Ay2;
int Bx1,By1,Bx2,By2;
scanf("(%d,%d) (%d,%d)",&Ax1,&Ay1,&Ax2,&Ay2);
scanf("(%d,%d) (%d,%d)",&Bx1,&By1,&Bx2,&By2);
if(judge(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2))
printf("YES\n");
else
printf("NO");
return 0;
}
int max(int x, int y){
if(x>y) y=x;
return y;
}
int min(int x, int y){
if(x<y) y=x;
return y;
}
int judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2)
{
if(
( max(Ax1,Ax2)>=min(Bx1,Bx2)&&min(Ax1,Ax2)<=max(Bx1,Bx2) )&& //判斷x軸投影
( max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2) ) //判斷y軸投影
)
{
if(
( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) * //判斷B是否跨過A
( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) * //判斷A是否跨過B
( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
)
{
return 1;
}
else
return 0;
}
else
return 0;
}
31. MT1181 圓包含
（1）題目描述
輸入2個圓的圓心的坐标值(x，y)和半徑，判斷斷一個圓是否完全包含另一個圓，輸出YES或者NO。另:内切不算做完全包含。
格式
輸入格式: 輸入整型，空格分隔。每行輸入一組資訊。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
-20 20 50
50 50 1
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x1,x2,y1,y2,r1,r2,r3;
float l;
scanf("%d%d%d%d%d%d", &x1,&y1,&r1,&x2,&y2,&r2);
l = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
if(r1>r2){
if(r2+l<r1) cout<<"YES";
else cout<<"NO";
}else{
if(r1+l<r2) cout<<"YES";
else cout<<"NO";
}
return 0;
}
32. MT1182 圓相交
（1）題目描述
輸入2個圓的圓心的坐标值(x，y)和半徑，判斷2個圓是否相交，輸出YES或者NO。
格式
輸入格式: 輸入整型，空格分隔。每行輸入一組資訊。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
-20 20 50
50 50 1
.
輸出格式: NO
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
double x1,x2,y1,y2,r1,r2;
cin >> x1 >> y1 >> r1;
cin >> x2 >> y2 >> r2;
double r=r1+r2;
double dis=sqrt(pow(x1-x2,(double)2)+pow(y1-y2,(double)2));
if(r<=dis || abs(r1-r2)>=dis) cout<<"NO";
else cout<<"YES";
return 0;
}
33. MT1183 矩形包含
（1）題目描述
輸入2個矩形的左上角和右下角兩個點的坐标值(x，y)，判斷2個矩形是否互相包含(一個在另一個内部，邊框不重疊)，輸出YES或者NO。矩形的邊應與x，y軸相平行。
格式
輸入格式: 輸入整型，空格分隔。每行輸入一組資訊。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
-20 20 20 -10
-10 10 10 -5
.
輸出格式: YES
（2）參考代碼
#include<stdio.h>
int main()
{
int x1, y1,x2,y2,a1,b1,a2,b2;
scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&a1,&b1,&a2,&b2);
if(x1<a1&&y1>b1&&x2>a2&&y2<b2) printf("YES");
else if(x1>a1&&y1<b1&&x2<a2&&y2>b2) printf("YES");
else printf("NO");
return 0;
}
34. MT1184 矩形相交
（1）題目描述
輸入2個矩形的左上角和右下角兩個點的坐标值(x，y)，判斷2個矩形是否相交，輸出YES或者NO。矩形的邊應與x， y軸相平行。假定輸入坐标能順利構成矩形，不考慮無效矩形的情況。
格式
輸入格式: 輸入整型，空格分隔。每行輸入一組資訊。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式:
-20 20 20 -10
-10 10 10 -5
.
輸出格式: NO
（2）參考代碼
#include <bits/stdc++.h>
using namespace std;
int a[100];
int b[100];
int main()
{
for(int i= 0; i <4; i++) cin >> a[i];
for(int i= 0; i < 4;i++) cin >> b[i];
int x1 = max(a[0],b[0]);
int x2 = min(a[2],b[2]);
int y1 = max(a[3],b[3]);int y2 = min(a[1],b[1]);
int lenx = x2- x1;
int leny = y2 -y1;
int flag = 0;
if(min(lenx,leny)==0&&max(lenx,leny)>0) flag = 1;
if(lenx > 0 && leny > 0){
flag = 1;
if(b[0] > a[0] && b[1] < a[1] && b[2] < a[2] && b[3] > a[3]) flag=0;
}
if(flag == 1 ) puts("YES");
else puts("NO");
}
35. MT1185 while循環
（1）題目描述
請編寫一個簡單程式，從小到大輸出所有小于8的正整數和O（從0開始輸出)。
格式
輸入格式: 無
.
輸出格式:輸出整型，空格分隔
樣例1
輸入格式: 無
.
輸出格式: 0 1 2 3 4 5 6 7
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
for(int i=0;i<8;i++){
cout<<i<<" ";
}
return 0;
}
36. MT1186 do-while循環
（1）題目描述
請編寫一個簡單程式，從大到小輸出所有小于n的正整數，直到0為止(不含0)。n從鍵盤輸入
格式
輸入格式: 輸入整型數n
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式: 10
.
輸出格式: 10 9 8 7 6 5 4 3 2 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
cin >> n;
for(int i=n;i>0;i--){
cout<<i<<" ";
}
return 0;
}
37. MT1187 累加和
（1）題目描述
從1累加到10，輸出累加和。
格式
輸入格式: 無
.
輸出格式: 輸出整型
樣例1
輸入格式: 無
.
輸出格式: 55
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int sum=0;
for(int i=1;i<=10;i++){
sum+=i;
}
cout<<sum;
return 0;
}
38. MT1188 平均值
（1）題目描述
請編寫一個簡單程式，随機輸入n個數字，輸出他們的平均值
格式
輸入格式: 輸入分兩行，第一行輸入n，第二行輸入n個float型資料，空格分隔
.
輸出格式: 輸出float型，空格分隔，保留2位小數
樣例1
輸入格式:
5
1 3 6 2 5.2
.
輸出格式: 3.44
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
float a[n+1],sum=0,avg;
cin >> n;
for(int i=0;i<=n;i++){
cin >> a[i];
sum+=a[i];
}
avg=sum/n;
printf("%.2f",avg);
return 0;
}
39. MT1189 正負數的和
（1）題目描述
編寫程式先輸入n，再輸入n個實數并分别統計正數的和、負數的和，然後輸出統計結果。
格式
輸入格式: 輸入分兩行，第一行輸入整數n，第二行輸入n個實數，空格分隔。
.
輸出格式: 輸出正數的和，和負數的和，實型，中間一個空格
樣例1
輸入格式:
4
1 -3 0.5 -2
.
輸出格式: 1.500000 -5.000000
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
double a[50],zn=0,fn=0;
cin >> n;
for(int i=0;i<n;i++){
scanf("%lf",&a[i]);
if(a[i]<0) fn+=a[i];
else zn+=a[i];
}
printf("%lf %lf",zn,fn);
return 0;
}
40. MT1190 分數乘法
（1）題目描述
輸入5組分數，對他們進行乘法運算，輸出結果。不考慮分母為0等特殊情況。
格式
輸入格式: 輸入整型，每組一行，如樣例所示。
.
輸出格式: 輸出計算結果實型，如樣例所示。
樣例1
輸入格式:
1/2 1/4
2/3 1/7
3/5 2/7
3/13 2/5
1/9 11/15
.
輸出格式:
0.125000
0.095238
0.171429
0.092308
0.081481
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
double x1,y1,x2,y2;
for(int i=0;i<5;i++){
scanf("%lf/%lf %lf/%lf",&x1,&y1,&x2,&y2);
printf("%lf\n",(x1*x2)/(y1*y2));
}
return 0;
}
小結(三)
典型範例：
MT1173、MT1174(ceil()取整函數)、MT1177、MT1178、MT1179
MT1180、MT1181、MT1182、MT1183、MT1184
41. MT1191 減半
（1）題目描述
輸入兩個值N和M，輸出N做M次減半後的值。比如100，減半後依次為50，25,12...，減半3次後是12。輸入不考慮0，負數或者其他特殊情況。
格式
輸入格式: 輸入為整型，空格分隔
.
輸出格式: 輸出為整型
樣例1
輸入格式: 100 3
.
輸出格式: 12
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,m;
cin >>n>>m;
for(int i=0;i<m;i++) n/=2;
cout<<n;
return 0;
}
42. MT1192 翻倍
（1）題目描述
輸入兩個值N和M。輸出N做M次翻倍後的值。比如12，翻倍後依次為24，48,96...。輸入不考慮0，負數或者其他特殊情況。
格式
輸入格式: 輸入為整型，空格分隔
.
輸出格式: 輸出為整型
樣例1
輸入格式: 12 3
.
輸出格式: 96
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,m;
cin >>n>>m;
for(int i=0;i<m;i++) n*=2;
cout<<n;
return 0;
}
43. MT1193 偶數的平方和
（1）題目描述
輸入正整數N，求前N個偶數的平方和。不考慮溢出。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 3
.
輸出格式: 56
備注：
本題第一個偶數從2起算
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,sum=0,num;
cin >> n;
for(int i=0;num<=n;num++){
sum+=i*i;
i=i+2;
}
cout<<sum;
return 0;
}
44. MT1194 奇數的平方和
（1）題目描述
輸入正整數N，求前N個奇數的平方和。不考慮溢出。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 3
.
輸出格式: 35
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,sum=1,num;
cin >> n;
for(int i=3;num<n-1;num++){
sum+=i*i;
i=i+2;
}
cout<<sum;
return 0;
}
45. MT1195 公式求和
（1）題目描述
輸入正整數N和M，按照下列公式求和。
格式
輸入格式: 輸入整型，空格分隔
.
輸出格式: 輸出實型
樣例1
輸入格式: 2 4
.
輸出格式: 0.42361
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,m;
double sum=0;
cin >> n >> m;
for(int i=n;i<=m;i++){
sum+=1.0/(i*i);
}
printf("%.5lf",sum);
return 0;
}
46. MT1196 階乘
（1）題目描述
請編寫一個簡單程式，輸入正整數n，輸出n的階乘。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式:5
.
輸出格式:5!=120
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,res=1;
cin >> n;
for(int i=1;i<=n;i++){
res*=i;
}
printf("%d!=%d",n,res);
return 0;
}
47. MT1197 階乘和
（1）題目描述
求1!+2!+3!+...+n!
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 153
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,sum=0;
cin >> n;
for(int j=1;j<=n;j++){
int res=1;
for(int i=1;i<=j;i++){
res*=i;
}
sum+=res;
}
printf("%d",sum);
return 0;
}
48. MT1198 階乘差
（1）題目描述
求1!-2!-3!-...-n!
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: -151
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,sum=1;
cin >> n;
for(int j=2;j<=n;j++){
int res=1;
for(int i=2;i<=j;i++){
res*=i;
}
sum-=res;
}
printf("%d",sum);
return 0;
}
49. MT1199 公式計算
（1）題目描述
輸入正整數n和r，計算公式(n!)/ (n-r)!。
格式
輸入格式:輸入整型，空格分隔。
.
輸出格式: 輸出實型，保留2位小數。
樣例1
輸入格式:2 1
.
輸出格式:2.00
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,r;
double res=1;
cin >> n >> r;
for(int i=n-r+1;i<=n;i++) res*=i;
printf("%.2lf",res);
return 0;
}
50. MT1200 常數e
（1）題目描述
常數e的值可以表示為無窮級數: e=1+1/1!+1/2!+1/3! +... 1/n!編寫一個程式，計算e的值，其中n是使用者輸入的整數。輸入不考慮0，負數或者其他特殊情況。
格式
輸入格式:輸入整型，空格分隔。
.
輸出格式: 輸出實型，保留2位小數。
樣例1
輸入格式: 7
.
輸出格式: 2.72
#include<bits/stdc++.h>
using namespace std;
int fact(int n){
return n>1?n*fact(n-1):1;
}
int main( )
{
int n,r;
double res=1;
cin >> n >> r;
for(int i=1;i<=n;i++) res+=1.0/fact(i);
printf("%.2lf",res);
return 0;
}