###### tags: `多元選修`
# 基礎程式設計
## 一、CH1 變數與運算子
1. ### d483 hello, world
```c=
#include <iostream>
using namespace std;
int main()
{
cout << "hello, world";
return 0;
}
```
2. ### ★ a001 哈囉
```c=
#include <iostream>
using namespace std;
int main()
{
string s;
while(cin >> s)
{
cout << "hello, " << s << endl;
}
return 0;
}
```
**while重複運算**
5. ### ★ d827 買鉛筆
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
cout << n/12*50+n%12*5 << endl;
}
return 0;
}
```
6. ### ★ d060 還要等多久啊？
```c=
#include <iostream>
using namespace std;
int main()
{
int m;
while(cin >> m)
{
cout <<(m<=25 ? 25-m : 85-m )<<endl;
}
return 0;
}
```
8. ### ★ d051 糟糕，我發燒了！
```c=
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int f;
while(cin >> f)
{
cout << fixed << setprecision (3) <<(f-32)/1.8<<endl;
}
return 0;
```
### ★9. b004 繩子上吃草的牛
- const
- acos(0)、sqrt()，需 #include <cmath>
- 長邊：L/2，短邊：sqrt( (L/2\*L/2)-(D/2\*D/2))，橢圓面積：pi\*長邊\*短邊
- 小數點控制printf，需 #include <cstdio>
- [printf-引數說明](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)
```c=
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
double D,L,s,l;
const double PI=2*acos(0);
while (cin >> D >> L )
{
l=L/2;
s=sqrt((L/2)*(L/2)-(D/2)*(D/2));
printf("%.3lf\n",PI*l*s);
}
return 0;
}
```
### ★10. d039 11044 - Searching for Nessy
- 邊界可不計代表除不盡可捨棄
- 輸入的第一行有一個整數t，代表測試筆數
```c=
#include <iostream>
using namespace std;
int main()
{
int t,m,n;
cin >>t;
while(t--)
{
cin >> m >>n;
cout << (n/3)*(m/3) <<endl;
}
return 0;
}
```
## **CH1HW**
### 1.d226 10071 - Back to High School Physics
**HW**
1. - v-t 圖算面積
```c=
#include <iostream>
using namespace std;
int main()
{
int t,v;
while (cin >> t >> v)
{
cout << 2*t*v <<endl;
}
return 0;
}
```
### 2.d053 Big Chocolate
- 3x4巧克力需要11刀
- m-1+m*(n-1) (why?)
```c=
#include <iostream>
using namespace std;
int main()
{
int M,N;
while (cin >> M >> N)
{
cout << M*N-1 <<endl;
}
return 0;
}
```
### **3.** b681 1. 山洞探險
- 3元運算子
- 向北公式為2L-1，向南為？
- long long int
```c=
#include <iostream>
using namespace std;
int main()
{
long long L,D;
while (cin >> L )
{
(L>0 ? D=L*2-1 : D=(-L)*2 );
cout << D <<endl;
}
return 0;
}
```
L < 0 ，D = ( - L ) * 2
L > 0 ，D = L * 2 - 1
### 4. d127 牧場面積
- 接近正方型面積會最大
- long long int
```c=
#include <iostream>
using namespace std;
int main()
{
long long L,S;
while (cin >> L )
{
S=(L/4)*(L/2-L/4);
cout << S <<endl;
}
return 0;
}
```
### 5. d461 班際籃球賽
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while (cin >> n )
{
cout << n-1 <<endl;
}
return 0;
}
```
### 6.d277 矩陣對角線
- 3元運算子、%
- 對角線奇數可共用對角線交叉的花盆，偶數不共用
```c=
#include <iostream>
using namespace std;
int main()
{
int N;
while (cin >> N)
{
cout << N-(N%2==1) <<endl;
}
return 0;
}
```
### 7.**while重複運算**
```c=
#include <iostream>
using namespace std;
int main()
{
int A,H;
while (cin >> A >> H)
{
cout << (double)2*(A+H) <<endl;
}
return 0;
}
```
8. ### d096HW 00913 - Joana and the Odd Numbers
- long long int
- 有N個奇數為第(N+1)/2列
- 找出此列最後3個數字與第(N+1)/2列的關係
```c=
#include <iostream>
using namespace std;
int main()
{
long long int N;
while(cin >> N)
{
cout << 6*(((N+1)/2)*((N+1)/2))-9 << endl;
}
return 0;
}
```
9. ### c776 106北二1.六邊形屋瓦
- 扣掉重覆的白色屋瓦。公式？
```c=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m,n,x ;
while (cin >> n>> m)
{
x= n*m*3+n*2+m*1;
cout << x <<endl;
}
return 0;
}
```
10. ### d549 矩形中的几何
- PA^2^ + PC^2^ = PB^2^ + PD^2^ (畢氏定理，why?)
- sqrt()，需 #include <cmath>
- printf小數點，需 #include <cstdio>
- PA、PB、PC變數形態用long long int或double
```c=
#include<iostream>
using namespace std;
int main()
{
int T,a,b,sum,f=0;
while(cin>>T)
{
for(int i=0;i<T;i++)
{f++;sum=0;
cin>>a>>b;
for(int n=a;n<=b ;n++)
{
if(n%2!=0)
sum+=n;
}
cout<<"Case "<<f<<':'<<' '<<sum<<endl;
}
}
}
```
## 二、CH2 條件判斷
3. ### ★ d065三人行必有我師
- &&
```c=
#include <iostream>
using namespace std;
int main()
{
int a,b,c;
while(cin >> a >> b >> c)
{
if( a>b && a>c)
{
cout << a << endl;
}
else
{
if(b>c)
{
cout << b << endl;
}
else
{
cout << c << endl;
}
}
}
return 0;
}
```
4. ### ★ a053 Sagit's 計分程式
- 多項選擇
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
if(n>=0 && n<=10)
{
cout << 6*n << endl;
}
else if(n<20)
{
cout << 60+(n-10)*2 << endl;
}
else if(n<40)
{
cout << 80+(n-20) << endl;
}
else
{
cout << 100 << endl;
}
}
return 0;
}
```
6. ### ★ d984 棄保效應
```c=
#include <iostream>
using namespace std;
int main()
{
unsigned int a,b,c;
while(cin >> a >> b >> c)
{
if(a>b+c || b>a && a>c && a+c>b || c>a && a>b && a+b>c )
{
cout << "A" << endl;
}
else if(b>a+c || a>b && b>c && b+c>a || c>b && b>a && a+b>c)
{
cout << "B" << endl;
}
else
{
cout << "C" << endl;
}
}
return 0;
}
```
7. ### ★ a004 文文的求婚
- 閏年為可被4整除且不被100整除，或可被400整除
```c=
#include <iostream>
using namespace std;
int main()
{
int y;
while(cin >> y)
{
if(y%4==0 && y%100!=0 || y%400==0 )
{
cout << "¶|¦~" << endl;
}
else
{
cout << "¥¦~" << endl;
}
}
return 0;
}
```
## CH2HW
1. ### d064 ㄑㄧˊ 數？
- 比較運算子
- ==(等於)
- !=(不等於)
```c=
#include <iostream>
using namespace std;
int main()
{
int i,a;
while (cin >> a)
{
i=a%2;
if(i==1)
{
cout << "Odd" <<endl;
}
else
{
cout << "Even" <<endl;
}
}
return 0;
}
```
2. ## d066 上學去吧！
- 巢狀if
- 亦可將時化為分
```c=
#include <iostream>
using namespace std;
int main()
{
int hh,mm;
while (cin >> hh >> mm)
{
0<=hh<=24;
0<=mm<=60;
if(hh==7 && mm==30 || hh>7 && hh<17 )
{
cout << "At School" <<endl;
}
else
{
cout << "Off School" <<endl;
}
}
return 0;
}
```
3. ### d460 山六九之旅
- 多項選擇
```c=
#include <iostream>
using namespace std;
int main()
{
int a;
while(cin >> a)
{
if(a<6)
{
cout << "0" << endl;
}
else if(6<=a&&a<=11)
{
cout << "590" << endl;
}
else if(12<=a&&a<=17)
{
cout << "790" << endl;
}
else if(18<=a&&a<=59)
{
cout << "890" << endl;
}
else if(a>=60)
{
cout << "399" << endl;
}
}
return 0;
}
```
4. ### a273 小朋友下樓梯
- 小心n或k等於0的情形
```c=
#include <iostream>
using namespace std;
main()
{
int n,k;
while(cin>>n>>k)
{
if(k>0&&n!=k)
{
if(n%k==0)
{
cout<<"Ok!"<<endl;
}
else if(n%k!=0)
{
cout<<"Impossib1e!"<<endl;
}
}
else if(n==k)
{
cout<<"Ok!"<<endl;
}
else if(n!=k&&k==0)
{
cout<<"Impossib1e!"<<endl;
}
}
return 0;
}
```
## 三、CH3 重複結構
1. ### ★ d490 我也愛偶數
- for
- i=i+1(i++)
- 變數初值，區塊變數 v.s. 區域變數
- 先練習1+2+3+…+n，int sum 除錯練習1
```c=
#include <iostream>
using namespace std;
int main()
{
int i,n,sum;
while(cin >> n)
{
// sum=0;
// int sum=0;
for( i=1;i<=n;i++)
{
sum=sum+i;
}
cout << sum << endl;
}
return 0;
}
```
2. ★ d074 電腦教室
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
int maxx=-1,p;
for (int i=0;i<n;i++)
{
cin >> p;
if (p>maxx)
{
maxx=p;
}
}
cout << maxx << endl;
}
return 0;
}
```
4. ### ★ a215 明明愛數數
- do_while迴圈
```c=
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin >> n >> m)
{
int sum=0,cnt=0 ;
do
{
sum+=n;
cnt++;
n++;
}while(sum<=m);
cout << cnt << endl;
}
return 0;
}
```
7. ### ★ a024 最大公因數(GCD)
- 暴力法(i++ v.s. i\-\-)
- [時間複雜度1](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AB%87%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95%E5%92%8C%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-b1f6908e4b80)、[時間複雜度2](https://jason-chen-1992.weebly.com/home/time-space-complexity)
- [輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm) (a=bq+r，則gcd(a, b) = gcd(b, r))
- 除錯練習
```c=
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin >> n >> m)
{
for(int i=min(n,m);i>=1;i--)
if(n%i==0&&m%i==0)
{
cout << i << endl;
break;
}
}
return 0;
}
```
```c=
#include <iostream>
using namespace std;
int main()
{
int a,b;
while(cin >> a >> b)
{
int r;
do
{
r=a%b;
a=b;
b=r;
}while(r>0);
cout<<a<<endl;
}
return 0;
}
```
8. ### ★ a149 乘乘樂
- 運算子優先順序 sum=sum*(n%10)
- 複合指定運算子
```c=
#include <iostream>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,sum=1;
cin>>n;
do
{
sum*=n%10;
n/=10;
}while(n>0);
cout<<sum<<endl;
```
## CH3HW
1. ### d498 我不說髒話
- for迴圈
```c=
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
for(int a=0;a<n;a++)
cout<<"I don't say swear words!"<<endl;
return 0;
}
}
```
1. ### ★ d212 東東爬階梯
- 一維陣列
- DP
- 費式數列
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
unsigned long long int f[100]={1,1}; //unsigned lon long int只能到f[92]
for(int i=2;i<100;i++)
f[i]=f[i-1]+f[i-2];
while(cin >> n)
cout << f[n] << endl;
return 0;
}
```
2. ### ★ c067 Box of Bricks
- 一維陣列
```c=
#include <iostream>
using namespace std;
int main()
{
int n,Set=1;
while(cin>>n && n>0)
{
int h[n],sum=0,ave,mov=0;
for(int i=0;i<n;i++)
{
cin >> h[i];
sum+=h[i];
}
ave=sum/n;
for (int i=0;i<n;i++)
{
if(h[i]>ave)
{
mov+=(h[i]-ave);
}
}
cout << "Set #" << Set++ << endl << "The minimum number of moves is " << mov << "." << endl << endl;
}
return 0;
}
```###### tags: `多元選修`
# 基礎程式設計
## 一、CH1 變數與運算子
1. ### d483 hello, world
```c=
#include <iostream>
using namespace std;
int main()
{
cout << "hello, world";
return 0;
}
```
2. ### ★ a001 哈囉
```c=
#include <iostream>
using namespace std;
int main()
{
string s;
while(cin >> s)
{
cout << "hello, " << s << endl;
}
return 0;
}
```
**while重複運算**
5. ### ★ d827 買鉛筆
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
cout << n/12*50+n%12*5 << endl;
}
return 0;
}
```
6. ### ★ d060 還要等多久啊？
```c=
#include <iostream>
using namespace std;
int main()
{
int m;
while(cin >> m)
{
cout <<(m<=25 ? 25-m : 85-m )<<endl;
}
return 0;
}
```
8. ### ★ d051 糟糕，我發燒了！
```c=
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int f;
while(cin >> f)
{
cout << fixed << setprecision (3) <<(f-32)/1.8<<endl;
}
return 0;
```
### ★9. b004 繩子上吃草的牛
- const
- acos(0)、sqrt()，需 #include <cmath>
- 長邊：L/2，短邊：sqrt( (L/2\*L/2)-(D/2\*D/2))，橢圓面積：pi\*長邊\*短邊
- 小數點控制printf，需 #include <cstdio>
- [printf-引數說明](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)
```c=
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
double D,L,s,l;
const double PI=2*acos(0);
while (cin >> D >> L )
{
l=L/2;
s=sqrt((L/2)*(L/2)-(D/2)*(D/2));
printf("%.3lf\n",PI*l*s);
}
return 0;
}
```
### ★10. d039 11044 - Searching for Nessy
- 邊界可不計代表除不盡可捨棄
- 輸入的第一行有一個整數t，代表測試筆數
```c=
#include <iostream>
using namespace std;
int main()
{
int t,m,n;
cin >>t;
while(t--)
{
cin >> m >>n;
cout << (n/3)*(m/3) <<endl;
}
return 0;
}
```
```c=
#include <iostream>
using namespace std;
int main()
{
long long int N;
while(cin >> N)
{
cout << 6*(((N+1)/2)*((N+1)/2))-9 << endl;
}
return 0;
}
```
3. ### ★ d065三人行必有我師
- &&
```c=
#include <iostream>
using namespace std;
int main()
{
int a,b,c;
while(cin >> a >> b >> c)
{
if( a>b && a>c)
{
cout << a << endl;
}
else
{
if(b>c)
{
cout << b << endl;
}
else
{
cout << c << endl;
}
}
}
return 0;
}
```
4. ### ★ a053 Sagit's 計分程式
- 多項選擇
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
if(n>=0 && n<=10)
{
cout << 6*n << endl;
}
else if(n<20)
{
cout << 60+(n-10)*2 << endl;
}
else if(n<40)
{
cout << 80+(n-20) << endl;
}
else
{
cout << 100 << endl;
}
}
return 0;
}
```
6. ### ★ d984 棄保效應
```c=
#include <iostream>
using namespace std;
int main()
{
unsigned int a,b,c;
while(cin >> a >> b >> c)
{
if(a>b+c || b>a && a>c && a+c>b || c>a && a>b && a+b>c )
{
cout << "A" << endl;
}
else if(b>a+c || a>b && b>c && b+c>a || c>b && b>a && a+b>c)
{
cout << "B" << endl;
}
else
{
cout << "C" << endl;
}
}
return 0;
}
```
7. ### ★ a004 文文的求婚
- 閏年為可被4整除且不被100整除，或可被400整除
```c=
#include <iostream>
using namespace std;
int main()
{
int y;
while(cin >> y)
{
if(y%4==0 && y%100!=0 || y%400==0 )
{
cout << "¶|¦~" << endl;
}
else
{
cout << "¥¦~" << endl;
}
}
return 0;
}
```
1. ### d064 ㄑㄧˊ 數？
- 比較運算子
- ==(等於)
- !=(不等於)
```c=
#include <iostream>
using namespace std;
int main()
{
int i,a;
while (cin >> a)
{
i=a%2;
if(i==1)
{
cout << "Odd" <<endl;
}
else
{
cout << "Even" <<endl;
}
}
return 0;
}
```
2. ## d066 上學去吧！
- 巢狀if
- 亦可將時化為分
```c=
#include <iostream>
using namespace std;
int main()
{
int hh,mm;
while (cin >> hh >> mm)
{
0<=hh<=24;
0<=mm<=60;
if(hh==7 && mm==30 || hh>7 && hh<17 )
{
cout << "At School" <<endl;
}
else
{
cout << "Off School" <<endl;
}
}
return 0;
}
```
3. ### d460 山六九之旅
- 多項選擇
```c=
#include <iostream>
using namespace std;
int main()
{
int a;
while(cin >> a)
{
if(a<6)
{
cout << "0" << endl;
}
else if(6<=a&&a<=11)
{
cout << "590" << endl;
}
else if(12<=a&&a<=17)
{
cout << "790" << endl;
}
else if(18<=a&&a<=59)
{
cout << "890" << endl;
}
else if(a>=60)
{
cout << "399" << endl;
}
}
return 0;
}
```
4. ### a273 小朋友下樓梯
- 小心n或k等於0的情形
```c=
#include <iostream>
using namespace std;
main()
{
int n,k;
while(cin>>n>>k)
{
if(k>0&&n!=k)
{
if(n%k==0)
{
cout<<"Ok!"<<endl;
}
else if(n%k!=0)
{
cout<<"Impossib1e!"<<endl;
}
}
else if(n==k)
{
cout<<"Ok!"<<endl;
}
else if(n!=k&&k==0)
{
cout<<"Impossib1e!"<<endl;
}
}
return 0;
}
```
1. ### ★ d490 我也愛偶數
- for
- i=i+1(i++)
- 變數初值，區塊變數 v.s. 區域變數
- 先練習1+2+3+…+n，int sum 除錯練習1
```c=
#include <iostream>
using namespace std;
int main()
{
int i,n,sum;
while(cin >> n)
{
// sum=0;
// int sum=0;
for( i=1;i<=n;i++)
{
sum=sum+i;
}
cout << sum << endl;
}
return 0;
}
```
2. ★ d074 電腦教室
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
int maxx=-1,p;
for (int i=0;i<n;i++)
{
cin >> p;
if (p>maxx)
{
maxx=p;
}
}
cout << maxx << endl;
}
return 0;
}
```
4. ### ★ a215 明明愛數數
- do_while迴圈
```c=
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin >> n >> m)
{
int sum=0,cnt=0 ;
do
{
sum+=n;
cnt++;
n++;
}while(sum<=m);
cout << cnt << endl;
}
return 0;
}
```
7. ### ★ a024 最大公因數(GCD)
- 暴力法(i++ v.s. i\-\-)
- [時間複雜度1](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AB%87%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95%E5%92%8C%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-b1f6908e4b80)、[時間複雜度2](https://jason-chen-1992.weebly.com/home/time-space-complexity)
- [輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm) (a=bq+r，則gcd(a, b) = gcd(b, r))
- 除錯練習
```c=
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin >> n >> m)
{
for(int i=min(n,m);i>=1;i--)
if(n%i==0&&m%i==0)
{
cout << i << endl;
break;
}
}
return 0;
}
```
```c=
#include <iostream>
using namespace std;
int main()
{
int a,b;
while(cin >> a >> b)
{
int r;
do
{
r=a%b;
a=b;
b=r;
}while(r>0);
cout<<a<<endl;
}
return 0;
}
```
8. ### ★ a149 乘乘樂
- 運算子優先順序 sum=sum*(n%10)
- 複合指定運算子
```c=
#include <iostream>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,sum=1;
cin>>n;
do
{
sum*=n%10;
n/=10;
}while(n>0);
cout<<sum<<endl;
```
1. ### d498 我不說髒話
- for迴圈
```c=
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
for(int a=0;a<n;a++)
cout<<"I don't say swear words!"<<endl;
return 0;
}
```
2. ### c022 10783 - Odd Sum
- 累加
```c=
#include<iostream>
using namespace std;
int main()
{
int T,a,b,sum,f=0;
while(cin>>T)
{
for(int i=0;i<T;i++)
{f++;
sum=0;
cin>>a>>b;
for(int n=a;n<=b ;n++)
{
if(n%2!=0)
sum+=n;
}
cout<<"Case "<<f<<':'<<' '<<sum<<endl;
}
}
}
```
7. ### a038 數字翻轉
- while
- 不斷取個位數加入翻轉數字
```c=
#include<iostream>
using namespace std;
int main()
{
int e;
while( cin >> e )
{
int abcde = 0;
while( e )
{
abcde *= 10;
abcde += e % 10;
e /= 10;
}
cout << abcde << endl;
}
return 0;
}
```
## 四、CH4 陣列
1. ### ★ d212 東東爬階梯
- 一維陣列
- DP
- 費式數列
```c=
#include <iostream>
using namespace std;
int main()
{
int n;
unsigned long long int f[100]={1,1}; //unsigned lon long int只能到f[92]
for(int i=2;i<100;i++)
f[i]=f[i-1]+f[i-2];
while(cin >> n)
cout << f[n] << endl;
return 0;
}
```
2. ### ★ c067 Box of Bricks
- 一維陣列
```c=
#include <iostream>
using namespace std;
int main()
{
int n,Set=1;
while(cin>>n && n>0)
{
int h[n],sum=0,ave,mov=0;
for(int i=0;i<n;i++)
{
cin >> h[i];
sum+=h[i];
}
ave=sum/n;
for (int i=0;i<n;i++)
{
if(h[i]>ave)
{
mov+=(h[i]-ave);
}
}
cout << "Set #" << Set++ << endl << "The minimum number of moves is " << mov << "." << endl << endl;
}
return 0;
}
```
3. ### a693: 吞食天地
- 每次都重算會TLE
- S[-1]陣列除錯
#include <stdio.h>
```c=
int main()
{
int a[1000000];
int b;
int c;
int d;
int e;
int f;
int i;
int g;
while(scanf("%d",&b)!=EOF){
scanf("%d",&c);
for(i=0;i<b;i++){
scanf("%d",&a[i]);
}
for(i=0;i<c;i++){
scanf("%d",&d);
scanf("%d",&e);
for(g=d-1;g<e;g++){
f=f+a[g];
}
printf("%d\n",f);
f=0;
}
}
}
```
4. ### a020: 身份證檢驗
- 以陣列將英文代號轉為數字
```c=
#include <iostream>
#include <string>
using namespace std;
int main()
{
long long int a[26]={1,10,19,28,37,46,55,64,39,73,82,2,11,20,48,29,38,47,56,65,74,83,21,3,12,30};
string b;
while (cin >> b) {
int c, d[9]={0}, num=0, ans;
c=a[b[0]-65];
for (int i=1;i<10;i++) {
if (i==9) {
d[num]=b[i]-48;
break;
}
d[num]=(b[i]-48)*(9-i); num++;
}
ans=c+d[0]+d[1]+d[2]+d[3]+d[4]+d[5]+d[6]+d[7]+d[8];
ans%10==0 ? cout << "real" << endl : cout << "fake" << endl;
}
}
```
5. ### b139: NOIP2005 2.校门外的树
```c=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int l,m,x,y,r,sum;
while(cin>>l>>m)
{
sum=0;
int n[l+1]={0};
for(int i=0;i<m;i++)
{
cin>>x>>y;
for(int j=x;j<=y;j++) n[j]=1;
}
for(int i=0;i<l+1;i++) if(n[i]==0) sum++;
cout<<sum<<endl;
}
}
```
6. ### ★ a104: 排序
- [思考排序的演算法](https://zh.wikipedia.org/wiki/十三張)
- [insertion sort1](https://kopu.chat/2017/06/22/插入排序insertion-sort/)
- [insertion sort2](http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php)
- [insertion sort3](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)
- [bubble sort](https://pjchender.blogspot.com/2017/09/bubble-sort.html)
```c=
// insertion sort
for(int i=1;i<n;i++)
{
int key=s[i],j=i-1;
while(........) // key前面的元素(s[?])大於它，j沒有超出邊界
{
........ // key前面的元素(s[?]往右移
........ // j減1
}
s[....]=key;
}
```
7. ### ★ d452: 二、直線最小距離和
- 排序後求中位數，中位數與數組各數的距離和最小
- swap()
- 其它排序演算法實作
* [exchange sort](http://it-easy.tw/sorting-algorithm/)
* [selection sort1](https://openhome.cc/Gossip/AlgorithmGossip/SelectionInsertionBubble.htm)
* [selection sort2](https://kopu.chat/2017/06/20/選擇排序-selection-sort/)
```c=
// selection sort
for(int i=0;i<n-1;i++)
{
int minIdx=i;
for(........) // 從i的右邊開始找最小值的index
{
if(s[....]<s[....])
minIdx=j;
}
swap(........); // 把最小值(minIdx的值)和i的數值交換
}
```
8. ### ★ d153: 六、智力测验
- 時間複雜度O(n^2^)的排序法會TLE
- (n-1)+(n-2)+….+1=n(n-1)/2=n2/2-n/2，當n很大時，如1百萬時，500,000,000,000-500,000=499,999,500,000(n/2可以忽略)
- 其它排序演算法觀念
* [merge sort](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
* [quick sort1](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php)
* [quick sort2](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR)
- 排序演算法比較
* [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
* [Comparison Sorting Algorithms](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
```c=
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int s[n];
for(int i=0;i<n;i++)
{
cin >> s[i];
}
sort(s,s+n);
cout<<(n%2==1?s[n/2]:s[n/2-1])<<endl;
}
return 0;
}
```
9. ### d478: 共同的數 - 簡易版
- 依序比較兩數列
- C++ IO加速
``` javascript
ios::sync_with_stdio(false);
cin.tie(0);
```
```c=
#include <stdio.h>
#include <iostream>
#include <deque>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
while(n--){
deque<long long int> a,b;
int ans=0;
for(int i=0;i<m;i++){
long long int temp;
cin>>temp;
a.push_back(temp);
}
for(int i=0;i<m;i++){
long long int temp;
cin>>temp;
b.push_back(temp);
}
while(a.size()!=0 && b.size() !=0){
if(a.front()==b.front()){
ans++;
a.pop_front();
b.pop_front();
}
else if(a.front()<b.front())
a.pop_front();
else
b.pop_front();
}
cout<<ans<<endl;
}
return 0;
}
```
Sign in with Wallet
Connect another wallet