# 陳梓睿的zerojudge解題紀錄
## 基礎題
### a005. Eva 的回家作業
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
int in[t][6];
for(int j=0;j<t;j++){
for(int i=0;i<4;i++){
cin >> in[j][i];
}
}
for(int j=0;j<t;j++){
for(int i=1;i<3;i++){
if(in[j][i]-in[j][i-1]==in[j][i+1]-in[j][i]){
in[j][4]=in[j][3]+(in[j][i+1]-in[j][i]);
}
else if(in[j][i]/in[j][i-1]==in[j][i+1]/in[j][i]){
in[j][4]=in[j][3]*(in[j][i]/in[j][i-1]);
}
}
}
for(int j=0;j<t;j++){
for(int i=0;i<5;i++){
cout << in[j][i] << " ";
}
cout << '\n';
}
return 0;
}
```
### a006. 一元二次方程式
**code:**
```c=1
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int a,b,c,x1,x2,k;
cin >> a >> b >> c;
k=b*b-(4*a*c);
if(k<0){
cout<<"No real root"<<endl;
return 0;
}
x1=(-b+sqrt(k))/(2*a);
x2=(-b-sqrt(k))/(2*a);
if(k>0){
cout<<"Two different roots x1="<<x1<<" , x2="<<x2;
}
else if(k==0){
cout<<"Two same roots x="<<x1;
}
return 0;
}
```
### a009. 解碼器
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
string s;
getline(cin,s);
for(int i=0;i<s.size();i++){
s[i]=s[i]-7;
}
for(int i=0;i<s.size();i++){
cout << s[i];
}
return 0;
}
```
### a010. 因數分解
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,i,count=0;
cin >> n;
i=2;
while(i<=n){
while(n%i==0){
n=n/i;
count = count +1;
}
if(count>1&&n!=1){
cout << i << "^" << count << " * ";
}
else if(count==1&&n!=1){
cout << i << " * ";
}
else if(count>1&&n==1){
cout << i << "^" << count <<'\n';
}
else if(count==1&&n==1){
cout << i <<'\n';
}
count = 0;
i++;
}
return 0;
}
```
### a013. 羅馬數字
#### 把輸入字串的每個字元換成阿拉伯數字
```c=1
int num(string &s){
int sum=0;
for(int i=0;i<s.size();i++){
if(s[i]=='I') sum=sum+1;if(s[i]=='V') sum=sum+5;if(s[i]=='X') sum=sum+10;
if(s[i]=='L') sum=sum+50;if(s[i]=='C') sum=sum+100;if(s[i]=='D') sum=sum+500;
if(s[i]=='M') sum=sum+1000;
}
for(int i=0;i<s.size()-1;i++){
if(s[i]=='I'&&s[i+1]=='V') sum=sum-2;if(s[i]=='I'&&s[i+1]=='X') sum=sum-2;
if(s[i]=='I'&&s[i+1]=='L') sum=sum-2; if(s[i]=='X'&&s[i+1]=='L') sum=sum-20;
if(s[i]=='X'&&s[i+1]=='C') sum=sum-20; if(s[i]=='C'&&s[i+1]=='D') sum=sum-200;
if(s[i]=='C'&&s[i+1]=='M') sum=sum-200;
}
return sum;
}
```
#### code:
```c=1
#include <iostream>
#include<stdlib.h>
using namespace std;
int num(string &s){
int sum=0;
for(int i=0;i<s.size();i++){
if(s[i]=='I') sum=sum+1;if(s[i]=='V') sum=sum+5;if(s[i]=='X') sum=sum+10;
if(s[i]=='L') sum=sum+50;if(s[i]=='C') sum=sum+100;if(s[i]=='D') sum=sum+500;
if(s[i]=='M') sum=sum+1000;
}
for(int i=0;i<s.size()-1;i++){
if(s[i]=='I'&&s[i+1]=='V') sum=sum-2;if(s[i]=='I'&&s[i+1]=='X') sum=sum-2;
if(s[i]=='I'&&s[i+1]=='L') sum=sum-2; if(s[i]=='X'&&s[i+1]=='L') sum=sum-20;
if(s[i]=='X'&&s[i+1]=='C') sum=sum-20; if(s[i]=='C'&&s[i+1]=='D') sum=sum-200;
if(s[i]=='C'&&s[i+1]=='M') sum=sum-200;
}
return sum;
}
int main() {
string s1,s2;
while(cin >> s1 && s1!="#"){
cin >> s2;
int total=abs(num(s1)-num(s2));
//再把阿拉伯數字轉換成羅馬數字，如下:
if(total==0){
cout << "ZERO" << endl;
}
else{
if(total>=1000){
for(int i=0;i<total/1000;i++)
cout << "M";
total=total%1000;
}
if(total>=900){
for(int i=0;i<total/900;i++)
cout << "CM";
total=total%900;
}
if(total>=500){
for(int i=0;i<total/500;i++)
cout << "D";
total=total%500;
}
if(total>=400){
for(int i=0;i<total/400;i++)
cout << "CD";
total=total%400;
}
if(total>=100){
for(int i=0;i<total/100;i++)
cout << "C";
total=total%100;
}
if(total>=90){
for(int i=0;i<total/90;i++)
cout << "XC";
total=total%90;
}
if(total>=50){
for(int i=0;i<total/50;i++)
cout << "L";
total=total%50;
}
if(total>=40){
for(int i=0;i<total/40;i++)
cout << "XL";
total=total%40;
}
if(total>=10){
for(int i=0;i<total/10;i++)
cout << "X";
total=total%10;
}
if(total>=9){
for(int i=0;i<total/9;i++)
cout << "IX";
total=total%9;
}
if(total>=5){
for(int i=0;i<total/5;i++)
cout << "V";
total=total%5;
}
if(total>=4){
for(int i=0;i<total/4;i++)
cout << "IV";
total=total%4;
}
if(total>=1){
for(int i=0;i<total/1;i++)
cout << "I";
total=total%1;
}
cout << endl;
}
}
return 0;
}
```
### a020. 身分證檢驗
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
string s;
int ans=0;
cin >> s;
for(int i=0;i<s.size();i++){
if(s[i]>=65&&s[i]<=72){
s[i]=s[i]-55;
}
if(s[i]>=74&&s[i]<=78){
s[i]=s[i]-56;
}
if(s[i]>=80&&s[i]<=86){
s[i]=s[i]-57;
}
if(s[i]=='I'){
s[i]=s[i]-39;
}
if(s[i]=='O'){
s[i]=s[i]-44;
}
if(s[i]=='W'){
s[i]=s[i]-55;
}
if(s[i]=='X'){
s[i]=s[i]-58;
}
if(s[i]=='Y'){
s[i]=s[i]-58;
}
if(s[i]=='Z'){
s[i]=s[i]-57;
}
if(s[i]>=48&&s[i]<=57){
s[i]=s[i]-48;
}
}
for(int i=8;i>=1;i--){
ans=ans+s[9-i]*i;
}
ans=ans+s[9]+(s[0]/10)+(s[0]%10)*9;
if(ans%10==0){
cout << "real" << '\n';
}
else{
cout << "fake" << '\n';
}
return 0;
}
```
### a038. 數字翻轉
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
int a; cin >> a;
if(a==0){//要注意 cin >> 000000的輸出要是 0，並在此結束執行
cout << 0;
return 0;
}
while(a%10==0){//因為 0%10恆等於 0，所以會一直在這裡跑迴圈
a=a/10;
}
while(a>10){//到個位數即結束cout
cout << a%10;
a=a/10;
}
cout << a;//補上沒cout的 a(個位數)
return 0;
}
```
### a054. 電話客服中心
**code:**
```c=1
#include <bits/stdc++.h>
using namespace std;
int sss(int x,string &v){
string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char tmp[26];
for(int i=0;i<s.size();i++){
tmp[i]=s[i];
}
for(int i=0;i<s.size();i++){
if(s[i]>=65&&s[i]<=72){
s[i]=s[i]-55;
}
if(s[i]=='I'){
s[i]=s[i]-39;
}
if(s[i]>=74&&s[i]<=78){
s[i]=s[i]-56;
}
if(s[i]=='O'){
s[i]=s[i]-44;
}
if(s[i]>=80&&s[i]<=86){
s[i]=s[i]-57;
}
if(s[i]=='W'){
s[i]=s[i]-55;
}
if(s[i]=='X'){
s[i]=s[i]-58;
}
if(s[i]=='Y'){
s[i]=s[i]-58;
}
if(s[i]=='Z'){
s[i]=s[i]-57;
}
}
for(int i=0;i<s.size();i++){
s[i]=(s[i]/10)+(s[i]%10)*9;
if(x==s[i]){
v.push_back(tmp[i]);//將包含的字元儲存到另一個string做排序
}
}
}
int main(){
string c;
string y;
int ans=0;
cin >> c;
for(int i=0;i<c.size();i++){//輸入字元轉成ASCII值
if(c[i]>=48&&c[i]<=57){
c[i]=c[i]-48;
}
}
for(int i=0;i<=7;i++){
ans=ans+c[i]*(8-i);
}//ans代表輸入字串前8項的和
int word;
int i=0;//c[8]是檢查碼
while(word<=83){
word=((10-c[8])+10*i)-ans;//將題目的[檢查碼=10-((ans+word)%10)]移項
sss(word,y);
i++;
}
//注意要依字母順序輸出
sort(y.begin(),y.end());
for(int i=0;i<y.size();++i){
cout << y[i];
}
cout << endl;
return 0;
}
```
### a224. 明明愛明明
**字串中出現字元數量為奇數者最多只能出現一次，而偶數則不管出現幾次都可以**
**code:**
```c=1
#include <bits/stdc++.h>
using namespace std;
bool c;//判斷是否已滿足同一個字元出現奇數次
int main(){
string s;
while(cin >> s){//注意構成迴文的條件
c=false;
string a;
for(int i=0;i<s.size();i++){
if(s[i]>=65&&s[i]<=90){
a.push_back(s[i]);
}
if(s[i]>=97&&s[i]<=122){//大小寫ASCII值相差32
a.push_back(s[i]-32);
}
}
sort(a.begin(),a.end());
int count=0,cc=0;//少算一次，所以從開始加
for(int i=1;i<=a.size();i++){
if(a[i-1]==a[i]){
count++;
}
else{
count++;
if(count%2!=0){
c=true;
cc++;
}
count=0;
}
}
if(c){
if(cc==1){
cout << "yes !" << endl;
}
else{
cout << "no..." << endl;
}
}
else{
cout << "yes !" << endl;
}
}
return 0;
}
```
### a225. 明明愛排列
**code:**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
int a1=a[j]%10;
int a2=a[j+1]%10;
if(a1>a2){
swap(a[j],a[j+1]);
}
}
}
for(int j=0;j<n-1;j++){
for(int i=0;i<n-1-j;i++){
if(a[i]%10==a[i+1]%10){
if(a[i]<a[i+1]){
swap(a[i],a[i+1]);
}
}
}
}
for(int i=0;i<n;i++){
cout << a[i] << " ";
}
cout << endl;
}
return 0;
}
```
### a414. 位元運算之進位篇
**code**
```c=1
#include <stdio.h>
using namespace std;
int main(){
int n,count;
while(scanf("%d",&n) && n!=0){
count=0;
while(n%2!=0){
count++;
n=n/2;
}
printf("%d\n",count);
}
return 0;
}
```
### a417. 螺旋矩陣
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int t,n,b;
cin >> t;
for(int i=0;i<t;i++){
cin >> n >> b;
int dp[n][n];
int k=1,j=0;
while(k<=n*n){
for(int i=j;i<n-j;i++){//往右
dp[j][i]=k;
k++;
}
for(int i=j+1;i<n-j;i++){//往下
dp[i][n-1-j]=k;
k++;
}
for(int i=n-2-j;i>=j;i--){//往左
dp[n-1-j][i]=k;
k++;
}
for(int i=n-2-j;i>=j+1;i--){//往上
dp[i][j]=k;
k++;
}
j++;
}
if(b==1){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout << setw(5) << dp[i][j];
}
cout << endl;
}
}
else{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout << setw(5) << dp[j][i];
}
cout << endl;
}
}
}
return 0;
}
```
### a524. 手機之謎
**code:**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
int a[n],b[n];
for(int i=n;i>0;i--){
a[i-1]=i;
b[i-1]=i;
}
while(true){
int count=0;
prev_permutation(a,a+n);//排列[從大到小]
for(int i=0;i<n;i++){
if(b[i]==a[i]){
count++;
}
}
if(count==n){
for(int i=0;i<n;i++){
cout << a[i];
}
cout << endl;
break;
}
else{
for(int i=0;i<n;i++){
cout << a[i];
}
cout << endl;
}
}
}
return 0;
}
```
### a915. 二维点排序
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
long long dp[n][2];
for(int i=0;i<n;i++){
cin >> dp[i][0] >> dp[i][1];
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){//注意x，y軸要同時移動
if(dp[j][0]>dp[j+1][0]){//先比x軸
swap(dp[j][0],dp[j+1][0]);
swap(dp[j][1],dp[j+1][1]);
}
else if(dp[j][0]==dp[j+1][0]){
if(dp[j][1]>dp[j+1][1]){
swap(dp[j][1],dp[j+1][1]);
}
}
}
}
for(int i=0;i<n;i++){
cout << dp[i][0] << " " << dp[i][1] << endl;
}
return 0;
}
```
### b374. [福州19中]众数
**code:**
```c=1
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int N,count;
cin >> N;
int a[N-1];
int out[N-1][2];
for(int i=0;i<N;i++){
cin >> a[i] ;
}
sort(a,a+N);
int k=0;
count=0;
for(int i=0;i<N;i++){
if(a[i]!=a[i+1]){
count++;
out[k][0]=a[i];
out[k][1]=count;
count=0;
k++;
}
else{
count++;
}
}
int max=0;
for(int i=0;i<k;i++){
if(out[i][1]>max){
max=out[i][1];
}
}
for(int i=0;i<k;i++){
if(max==out[i][1]){
cout << out[i][0] << " " << out[i][1] <<'\n';
}
}
return 0;
}
```
### d584. 技能點數skill
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
int role,lv,ed;
while(cin >> role >> lv && lv>=1 && lv<=200){
ed=0;
if(role==0){
cout << 0 << endl;
}
else if(role==2){
if(lv>=120){
ed=ed+(lv-120)*3;
lv=120;
ed=ed+3;
}
if(lv>=70){
ed=ed+(lv-70)*3;
lv=70;
ed=ed+1;
}
if(lv>=30){
ed=ed+(lv-30)*3;
lv=30;
ed=ed+1;
}
if(lv>=8){
ed=ed+(lv-8)*3;
ed=ed+1;
}
cout << ed << endl;
}
else{
if(lv>=120){
ed=ed+(lv-120)*3;
lv=120;
ed=ed+3;
}
if(lv>=70){
ed=ed+(lv-70)*3;
lv=70;
ed=ed+1;
}
if(lv>=30){
ed=ed+(lv-30)*3;
lv=30;
ed=ed+1;
}
if(lv>=10){
ed=ed+(lv-10)*3;
ed=ed+1;
}
cout << ed << endl;
}
}
return 0;
}
```
### d732. 二分搜尋法
**code**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,k,low,high,mid;
cin >> n >> k;
int a[n];
int b[k];
for(int i=0;i<n;i++){
cin >> a[i];
}
for(int i=0;i<k;i++){
cin >> b[i];
}
for(int i=0;i<k;i++){
low=0;
high=n-1;
bool c=1;
while(low<=high){
mid=(low+high)/2;
if(b[i]==a[mid]){
cout << mid+1 << "\n";
c=0;
break;
}
else if(b[i]<a[mid]){
high=mid-1;
}
else if(b[i]>a[mid]){
low=mid+1;
}
}
if(c){
cout << 0 << "\n";
}
}
}
```
### e343. BMI 計算 (c++想法)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int w,h;
cin >> w >> h;
float d,H;
H=float(h)/100;
d=w/pow(H,2);
float k=round(d*10)/10;
int m=round(d*10);
if(m%10==0){//要注意有一橫的輸出要72.0
cout << k << ".0" << endl;
}
else{
cout << k << endl;
}
return 0;
}
```
### f698. 後序運算式 (stack練習)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
stack<int> v;
int a,b;
while(cin >> s){//由於題目規定輸入有"有號整數"(像是"-5")因此就針對每次輸入做以下討論
if(s=="+"){
a=v.top();v.pop();
b=v.top();v.pop();
v.push(a+b);
}
else if(s=="-"){
a=v.top();v.pop();
b=v.top();v.pop();
v.push(b-a);
}
else if(s=="*"){
a=v.top();v.pop();
b=v.top();v.pop();
v.push(a*b);
}
else if(s=="/"){
a=v.top();v.pop();
b=v.top();v.pop();
v.push(b/a);
}
else{
v.push(stoi(s));//對字串裡的數字改成integer形式
}
}
a=v.top();
cout << a << "\n";
return 0;
}
```
## APCS練習題
### b964. 第 1 題 成績指標
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,f1=-1,p1=101;
cin >> n;
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
if(a[i]>=f1&&a[i]<60){
f1=a[i];
}
if(a[i]<=p1&&a[i]>=60){
p1=a[i];
}
}
sort(a,a+n);
for(int i=0;i<n-1;i++){
cout << a[i] << " ";
}
cout << a[n-1] << endl;
if(f1==-1){
cout << "best case" << endl;
}
else{
cout << f1 << endl;
}
if(p1==101){
cout << "worst case" << endl;
}
else{
cout << p1 << endl;
}
return 0;
}
```
### c290. APCS 2017-0304-1秘密差
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int a=0,b=0;
for(int i=s.size()-1;i>=0;i=i-2){
s[i]=s[i]-'0';
a=a+s[i];
if(i-1<0){
continue;
}
else{
s[i-1]=s[i-1]-'0';
b=b+s[i-1];
}
}
cout << abs(a-b) << endl;
return 0;
}
```
### j605. 1. 程式考試
**code:**
```c=1
int main(){
int k,count=0,max=0,out;
cin >> k;
int dp[k][2];
for(int i=0;i<k;i++){
cin >> dp[i][0] >> dp[i][1];
}
for(int i=0;i<k;i++){
if(dp[i][1]==-1){
count++;
}
}
for(int i=0;i<k;i++){
if(max<dp[i][1]){
max=dp[i][1];
}
}
for(int i=0;i<k;i++){
if(max==dp[i][1]){
out=dp[i][0];
break;
}
}
int score=max-k-(count*2);
if(score<0){
score=0;
}
cout << score << " " << out;
return 0;
}
```
### g595. 1. 修補圍籬
**code:**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,count=0;
cin >> n;
int a[n-1];
for(int i=0;i<n;i++){
cin >> a[i] ;
}
for(int i=0;i<n;i++){
if(a[i]==0){
if(i==0&&a[i]==0){
count=count+a[i+1];
continue;
}
if(i==n-1&&a[i]==0){
count=count+a[i-1];
continue;
}
count=count+min(a[i+1],a[i-1]);
}
}
cout << count << " ";
return 0;
}
```
### h026. 202001_1 猜拳
**code:**
```c=1
#include <bits/stdc++.h>
using namespace std;
bool draw(int x,int y){//判斷是否平手
if(x==y){
return true;
}
else{
return false;
}
}
int win(int x){//遇到連續兩輪出了一樣的拳時
int tmp;
if(x==0){
tmp=5;
}
else if(x==2){
tmp=0;
}
else if(x==5){
tmp=2;
}
return tmp;
}
int com(int x,int y){//X哥哥，Y絲絲
if(x==0){
if(y==2){
cout << ": Won at round ";
}
else if(y==5){
cout << ": Lost at round ";
}
}
if(x==2){
if(y==0){
cout << ": Lost at round ";
}
else if(y==5){
cout << ": Won at round ";
}
}
if(x==5){
if(y==0){
cout << ": Won at round ";
}
else if(y==2){
cout << ": Lost at round ";
}
}
}
int main(){
int f,n;
cin >> f >> n;
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
if(draw(a[0],f)){//先判斷第一輪是否贏
cout << f << " ";
if(n==1){
cout << ": Drew at round " << n << endl;
return 0;
}
f=a[0];
if(draw(a[1],f)){//再判斷第二輪
cout << f << " ";
if(n==2){
cout << ": Drew at round " << n << endl;
return 0;
}
for(int i=2;i<n;i++){
if(a[i-1]==a[i-2]){
f=win(a[i-1]);
}
else{
f=a[i-1];
}
if(draw(a[i],f)){
cout << f << " ";
if(i==n-1){
cout << ": Drew at round " << n << endl;
}
}
else{
cout << f << " ";
com(f,a[i]);
cout << i+1 << endl;
break;
}
}
}
else{
cout << f << " ";
com(f,a[1]);
cout << 2 << endl;
}
}
else{
cout << f << " ";
com(f,a[0]);
cout << 1 << endl;
}
return 0;
}
```
### k731. 1. 路徑偵測
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int k=1,n,l=0,r=0,re=0;//k代表上一格座標時的所在方位
cin >> n;
int a[101][2];
cin >> a[0][0] >> a[0][1];
for(int i=1;i<n;i++){
cin >> a[i][0] >> a[i][1];//0代表x座標，1代表y座標
if(k==1){//向右
if(a[i][0]==a[i-1][0]){
if(a[i][1]>a[i-1][1]){
l++;
k=2;
}
else if(a[i][1]<a[i-1][1]){
r++;
k=4;
}
}
else if(a[i][0]<a[i-1][0]){
k=3;
re++;
}
}
else if(k==2){//向上
if(a[i][1]==a[i-1][1]){
if(a[i][0]>a[i-1][0]){
r++;
k=1;
}
else if(a[i][0]<a[i-1][0]){
l++;
k=3;
}
}
else if(a[i][1]<a[i-1][1]){
re++;
k=4;
}
}
else if(k==3){//向左
if(a[i][0]==a[i-1][0]){
if(a[i][1]>a[i-1][1]){
r++;
k=2;
}
else if(a[i][1]<a[i-1][1]){
l++;
k=4;
}
}
else if(a[i][0]>a[i-1][0]){
k=1;
re++;
}
}
else{//向下
if(a[i][1]==a[i-1][1]){
if(a[i][0]>a[i-1][0]){
l++;
k=1;
}
else if(a[i][0]<a[i-1][0]){
r++;
k=3;
}
}
else if(a[i][1]>a[i-1][1]){
re++;
k=2;
}
}
}
cout << l << " " << r << " " << re << "\n";
return 0;
}
```
### c291. APCS 2017-0304-2小群體
**code**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,count=0;
cin >> n;
int a[n];
bool fg[n]={};
for(int i=0;i<n;i++){
cin >> a[i];
}
for(int i=0;i<n;i++){
if(fg[i]==0){
int tmp=a[i];
for(int j=0;j<n;j++){
if(tmp==j){
fg[j]=1;
tmp=a[j];
if(tmp==i){
fg[i]=1;
count++;
break;
}
j=0;
}
}
}
else{
continue;
}
}
cout << count << endl;
return 0;
}
```
### c295. APCS-2016-1029-2最大和
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,sum=0,max=0;
cin >> n >> m;
int dp[n][m];
vector<int> v;
bool c=true;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> dp[i][j];
if(dp[i][j]>max){
max=dp[i][j];
}
}
v.push_back(max);
sum=sum+max;
max=0;
}
cout << sum << endl;
int count=0;
for(int i=0;i<v.size();i++){
if(sum%v[i]==0){
c=false;
if(count>0){
cout << " ";
}
cout << v[i];
count++;
}
}
if(c){
cout << -1;
}
return 0;
}
```
### e287. 機器人的路徑
**code**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,m,x,y,min=1000000,sum=0,t1,t2;
cin >> n >> m;
int a[n][m];
bool b[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> a[i][j];
b[i][j]=1;
if(a[i][j]<min){
min=a[i][j];
x=i;
y=j;
}
}
}
b[x][y]=0;//0表示被走過
sum=sum+a[x][y];
bool c[4];
while(1){
min=1000000;
if(x-1>=0){//上
if(b[x-1][y]){
if(a[x-1][y]<min){
min=a[x-1][y];
t1=x-1;
t2=y;
}
c[0]=0;
}
else{
c[0]=1;
}
}
else{
c[0]=1;
}
if(x+1<=n-1){//下
if(b[x+1][y]){
if(a[x+1][y]<min){
min=a[x+1][y];
t1=x+1;
t2=y;
}
c[1]=0;
}
else{
c[1]=1;
}
}
else{
c[1]=1;
}
if(y-1>=0){//左
if(b[x][y-1]){
if(a[x][y-1]<min){
min=a[x][y-1];
t1=x;
t2=y-1;
}
c[2]=0;
}
else{
c[2]=1;
}
}
else{
c[2]=1;
}
if(y+1<=m-1){//右
if(b[x][y+1]){
if(a[x][y+1]<min){
min=a[x][y+1];
t1=x;
t2=y+1;
}
c[3]=0;
}
else{
c[3]=1;
}
}
else{
c[3]=1;
}
int cou=0;
for(int i=0;i<4;i++){
if(c[i]){
cou=cou+1;
}
}
if(cou==4){
break;
}
else{
x=t1;
y=t2;
sum=sum+a[x][y];
b[x][y]=0;
}
}
cout << sum << "\n";
}
```
### j606. 2. 造字程式
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int k,q,r;
string a,b;
cin >> k >> q >> r;
cin >> a;
int dp[q][k];
char ep[q][k];//ep當輸出用
for(int i=0;i<q;i++){
for(int j=0;j<k;j++){
cin >> dp[i][j];
b[dp[i][j]-1]=a[j];
}
for(int j=0;j<k;j++){
ep[i][j]=b[j];
}
for(int j=0;j<k;j++){
a[j]=b[j];
}
}
for(int i=0;i<r;i++){
for(int j=0;j<q;j++){
cout << ep[j][i];
}
cout << endl;
}
return 0;
}
```
### b965. 第 2 題 矩陣轉換
**如題目所述:A陣列轉換後得B，今天題目給你B要求A**
**code:**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int r,c,m;
while(cin >> r >> c >> m){
int re[m];
int input[11][11];
int ans[11][11];
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin >> input[i][j];
}
}
for(int i=0;i<m;i++){
cin >> re[i];
}
for(int k=m-1;k>=0;k--){//要將旋轉與翻轉的操作順序給反過來
if(re[k]==1){
for(int i=0;i<c;i++){
for(int j=0;j<r;j++){
ans[r-1-j][i]=input[j][i];
}
}
if(k>0){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
input[i][j]=ans[i][j];
}
}
}
}
else if(re[k]==0){//因為題目要還原起始矩陣，所以原本的順時針旋轉要變成逆時針旋轉
for(int i=0;i<c;i++){
for(int j=0;j<r;j++){
ans[i][j]=input[j][c-1-i];
}
}
swap(r,c);
if(k>0){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
input[i][j]=ans[i][j];
}
}
}
}
}
cout << r << " " << c << endl;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){//輸出的最後一格不能空格
if(j==c-1){
cout << ans[i][j];
}
else{
cout << ans[i][j] << " ";
}
}
cout << endl;
}
}
return 0;
}
```
### h027. 202001_2 矩陣總和
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int s,t,n,m,r,tmp;
int st[100][100];
int nm[100][100];
cin >> s >> t >> n >> m >> r;
int total=0;
for(int i=0;i<s;i++){
for(int j=0;j<t;j++){
cin >> st[i][j];
total=total+st[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> nm[i][j];
}
}
int sum,cou=0,min=999;
for(int k=0;k<=n-s;k++){
for(int l=0;l<=m-t;l++){
sum=0,tmp=0;
for(int i=0;i<s;i++){
for(int j=0;j<t;j++){
if(st[i][j]!=nm[k+i][l+j]){
tmp++;
}
sum=sum+nm[k+i][l+j];
}
}
if(tmp<=r){
cou++;
int x=abs(total-sum);
if(x<min){
min=x;
}
}
}
}
if(cou==0){
cout << cou << "\n" << "-1";
}
else{
cout << cou << "\n" << min;
}
}
```
### f313. 2. 人口遷移
**code**
```c=1
#include<bits/stdc++.h>
using namespace std;
int main(){
int r,c,k,m;
cin >> r >> c >> k >> m;
int a[100][100],b[100][100];
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin >> a[i][j];
b[i][j]=0;
}
}
while(m--){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(a[i][j]!=-1){
if(i-1>=0){//上
if(a[i-1][j]!=-1){
b[i][j]=b[i][j]-(a[i][j]/k);
b[i-1][j]=b[i-1][j]+(a[i][j]/k);
}
}
if(i+1<=r-1){//下
if(a[i+1][j]!=-1){
b[i][j]=b[i][j]-(a[i][j]/k);
b[i+1][j]=b[i+1][j]+(a[i][j]/k);
}
}
if(j-1>=0){//左
if(a[i][j-1]!=-1){
b[i][j]=b[i][j]-(a[i][j]/k);
b[i][j-1]=b[i][j-1]+(a[i][j]/k);
}
}
if(j+1<=c-1){//右
if(a[i][j+1]!=-1){
b[i][j]=b[i][j]-(a[i][j]/k);
b[i][j+1]=b[i][j+1]+(a[i][j]/k);
}
}
}
}
}
for(int i=0;i<r;i++){//過完一天各城市人口數要變動
for(int j=0;j<c;j++){
a[i][j]=a[i][j]+b[i][j];
b[i][j]=0;
}
}
}
int max=-99,min=99;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(a[i][j]>max){
max=a[i][j];
}
if(a[i][j]<min&&a[i][j]!=-1){
min=a[i][j];
}
}
}
cout << min << endl << max;
}
```
### f580. 2. 骰子
**有利用立體圖形理解:
https://www.tinkercad.com/things/cbfakaIFnYi-dice**
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,a,b,tmp;
cin >> n >> m;
int v[20][7];
for(int i=1;i<=n;i++){
for(int j=1;j<7;j++){
v[i][j]=j;
}
}
for(int i=0;i<m;i++){
cin >> a >> b;
if(b==-1){//轉動換的是位置，直接用數字指定會搞混
tmp=v[a][1];//設v[a][1]是最上面的位置
v[a][1]=v[a][3];
v[a][3]=v[a][6];
v[a][6]=v[a][4];
v[a][4]=tmp;
}
else if(b==-2){
tmp=v[a][1];
v[a][1]=v[a][5];
v[a][5]=v[a][6];
v[a][6]=v[a][2];
v[a][2]=tmp;
}
else{
for(int j=1;j<7;j++){
swap(v[a][j],v[b][j]);
}
}
}
for(int i=1;i<=n;i++){
cout << v[i][1] << " ";
}
}
```
### f606. 2. 流量
**當陣列a[l][j]的l=j時，代表流量傳輸在相同的城市裡(每單位流量需要花 1 塊錢)**
**所以該寫成:**
```c=1
for(int l=0;l<m;l++){
for(int j=0;j<m;j++){
if(l==j){
sum+=a[l][j];
}
}
}
```
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,k,tmp;
cin >> n >> m >> k;
int dp[51][51],a[m][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> dp[i][j];
}
}
for(int i=0;i<m;i++){//由於題目要求將單一城市有重複的伺服器的每一次相同路徑加總在計算錢
for(int j=0;j<m;j++){//所以就再令一個陣列
a[i][j]=0;
}
}
int min=INT_MAX,sum;
for(int i=0;i<k;i++){
sum=0;
for(int j=0;j<n;j++){
cin >> tmp;
for(int t=0;t<m;t++){
a[tmp][t]+=dp[j][t];
}
}
for(int l=0;l<m;l++){
for(int j=0;j<m;j++){
if(l==j){
sum+=a[l][j];
}
else{
if(a[l][j]<=1000){
sum+=(a[l][j])*3;
}
else{//超出1000的部分*2
sum+=(a[l][j]-1000)*2;
sum+=3000;
}
}
a[l][j]=0;
}
}
if(sum<min){
min=sum;
}
}
cout << min;
}
```
### i400. 2. 字串解碼
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> v;
int n,m,cou,k,l;
string s,a;
cin >> m >> n;
int pos[n];//pos紀錄變化後每個字元的位置
for(int i=0;i<n;i++){
pos[i]=i;
}
while(m--){
cin >> s;
cou=0;
for(int i=0;i<n;i++){
if(s[i]=='1'){
cou++;
}
}
if(cou%2!=0){
if(n%2==0){
for(int i=0;i<n/2;i++){
swap(pos[i],pos[i+n/2]);
}
}
else{
for(int i=0;i<n/2;i++){
swap(pos[i],pos[i+n/2+1]);
}
}
}
k=0;
l=n-1;
for(int i=0;i<n;i++){
if(s[i]=='0'){
v.push_back(pos[k]);
k++;
}
else{
v.push_back(pos[l]);
l--;
}
}
for(int i=0;i<n;i++){
pos[i]=v[i];
}
v.clear();
}
cin >> a;
for(int i=0;i<n;i++){
s[pos[i]]=a[i];//將變換後的順序變成01234....
}
cout << s;
}
```
### b966. 第 3 題 線段覆蓋長度
**code**
```c=1
#include <bits/stdc++.h>
#define pll pair <int,int>
using namespace std;
int main(){
vector<pll> v;
pll t;
int n,a,b,sum=0;
cin >> n;
while(n--){
cin >> t.first >> t.second;
v.push_back(t);
}
sort(v.begin(),v.end());
a=v[0].first;
b=v[0].second;
for(int i=1;i<v.size();i++){
if(v[i].first>b){
sum=sum+b-a;
a=v[i].first;
b=v[i].second;
}
else{
if(v[i].second>b){
b=v[i].second;
}
}
}
sum=sum+b-a;
cout << sum << endl;
return 0;
}
```
### c292. APCS2017-0304-3數字龍捲風
**code**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,t;
cin >> n >> t;
int a[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> a[i][j];
}
}
int x=n/2;
int y=x;
int k=1;
int tmp;
cout << a[x][y];
if(t==0){
while(1){
for(int i=1;i<=2*k-1;i++){//左
if(x==n-1&&y-i==0){
cout << a[x][y-i];
tmp=i;
break;
}
cout << a[x][y-i];
tmp=i;
}
if(x==n-1&&y-tmp==0){
break;
}
y=y-tmp;
for(int i=1;i<=2*k-1;i++){//上
cout << a[x-i][y];
tmp=i;
}
x=x-tmp;
for(int i=1;i<=2*k;i++){//右
cout << a[x][y+i];
tmp=i;
}
y=y+tmp;
for(int i=1;i<=2*k;i++){//下
cout << a[x+i][y];
tmp=i;
}
x=x+tmp;
k++;
}
}
else if(t==1){
while(1){
for(int i=1;i<=2*k-1;i++){//上
if(x-i==0&&y==0){
cout << a[x-i][y];
tmp=i;
break;
}
cout << a[x-i][y];
tmp=i;
}
if(x-tmp==0&&y==0){
break;
}
x=x-tmp;
for(int i=1;i<=2*k-1;i++){//右
cout << a[x][y+i];
tmp=i;
}
y=y+tmp;
for(int i=1;i<=2*k;i++){//下
cout << a[x+i][y];
tmp=i;
}
x=x+tmp;
for(int i=1;i<=2*k;i++){//左
cout << a[x][y-i];
tmp=i;
}
y=y-tmp;
k++;
}
}
else if(t==2){
while(1){
for(int i=1;i<=2*k-1;i++){//右
if(x==0&&y+i==n-1){
cout << a[x][y+i];
tmp=i;
break;
}
cout << a[x][y+i];
tmp=i;
}
if(x==0&&y+tmp==n-1){
break;
}
y=y+tmp;
for(int i=1;i<=2*k-1;i++){//下
cout << a[x+i][y];
tmp=i;
}
x=x+tmp;
for(int i=1;i<=2*k;i++){//左
cout << a[x][y-i];
tmp=i;
}
y=y-tmp;
for(int i=1;i<=2*k;i++){//上
cout << a[x-i][y];
tmp=i;
}
x=x-tmp;
k++;
}
}
else{
while(1){
for(int i=1;i<=2*k-1;i++){//下
if(x+i==n-1&&y==n-1){
cout << a[x+i][y];
tmp=i;
break;
}
cout << a[x+i][y];
tmp=i;
}
if(x+tmp==n-1&&y==n-1){
break;
}
x=x+tmp;
for(int i=1;i<=2*k-1;i++){//左
cout << a[x][y-i];
tmp=i;
}
y=y-tmp;
for(int i=1;i<=2*k;i++){//上
cout << a[x-i][y];
tmp=i;
}
x=x-tmp;
for(int i=1;i<=2*k;i++){//右
cout << a[x][y+i];
tmp=i;
}
y=y+tmp;
k++;
}
}
cout << "\n";
}
```
## 額外補充題
### h658. 捕魚 (Fishing)
**code:**
```c=1
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
int x,y,N;int dp[100][2];
cin >> x >> y;
cin >> N;int a[N-1];
if(x,y>=0&&x,y<=500&&N>=1&&N<=100){
for(int i=0;i<N;i++){
for(int j=0;j<2;j++){
cin >> dp[i][j];
if(dp[i][j]<0&&dp[i][j>500]){
return 0;
}
}
}
for(int i=0;i<N;i++){
a[i]=pow(x-dp[i][0],2)+pow(y-dp[i][1],2);
}
sort(a, a + N);
for(int i=0;i<N;i++){
if(a[0]==pow(x-dp[i][0],2)+pow(y-dp[i][1],2)){
cout << dp[i][0] << " " << dp[i][1];
}
}
}
return 0;
}
```
### a286. 難道這就是命中注定
**code:**
```c=1
#include<iostream>
#include<stdlib.h>
using namespace std;
int calculate(int x){
int count=0;
while(x/10!=0){
count=count+(x%10);
x=x/10;
}
count=count+x;
return count;
}
int main(){
int a,b,c;int total;
while(cin >> a >> b >> c){
total=calculate(a)+calculate(b)+calculate(c);
while((total/10)!=0){
total=calculate(total);
}
int n;
cin >> n;
int dp[n][3];
int man[n];
for(int i=0;i<n;i++){
cin >> dp[i][0] >> dp[i][1] >> dp[i][2];
}
for(int i=0;i<n;i++){
man[i]=calculate(dp[i][0])+calculate(dp[i][1])+calculate(dp[i][2]);
}
for(int i=0;i<n;i++){
while((man[i]/10)!=0){
man[i]=calculate(man[i]);
}
man[i]=abs(total-man[i]);
}
int min=1000;
for(int i=0;i<n;i++){
if(min>man[i]){
min=man[i];
}
}
for(int i=0;i<n;i++){
if(min==man[i]){
cout<< i+1 << endl;
break;
}
}
}
return 0;
}
```
### d128. 三、速算游戏
**要注意a b c三個數的順序不能調換**
**code**
```c=1
#include <iostream>
using namespace std;
int main(){
int a,b,c;
while(cin >> a >> b >> c){
int ans[4];
int max2=-1;
//1次運算
//ab_c
ans[0]=max((10*a+b)*c,(10*a+b)+c);
//a_bc
ans[1]=max((10*b+c)*a,(10*b+a)+a);
//2次運算
//a_b_c
ans[2]=max(a+b+c,a+b*c);
ans[3]=max(a*b+c,a*b*c);
for(int i=0;i<4;i++){
if(max2<ans[i]){
max2=ans[i];
}
}
cout << max2 << endl;
}
return 0;
}
```
### g797. 洗牌 (Cards)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
int k=n/2;
int a[n];
int ans[n];
for(int i=0;i<n;i++){
cin >> a[i] ;
}
for(int j=0;j<m;j++){
for(int i=0;i<k;i++){
ans[i*2]=a[i];
ans[i*2+1]=a[i+k];
}
for(int i=0;i<n;i++){//要注意每一次洗牌要先互換一次位置
a[i]=ans[i];
}
}
for(int i=0;i<n;i++){
cout << ans[i] << " " ;
}
cout << endl;
return 0;
}
```
### e798. p5. 卷積神經網路
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int dp[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> dp[i][j];
}
}
for(int k=0;k<n;k=k+2){//y
for(int j=0;j<n;j=j+2){//x
int a=max(dp[k][j],dp[k][j+1]);
int b=max(dp[k+1][j],dp[k+1][j+1]);
cout << max(a,b) <<" ";
}
cout << endl;
}
return 0;
}
```
### e796. p3. 站牌廣告
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int b,p;
cin >> b >> p;
int x[p],y[p],bus[b]={};
for(int i=0;i<p;i++){
cin >> x[i] >> y[i];
x[i]=x[i]-1;
y[i]=y[i]-1;
if(x[i]>y[i]){
swap(x[i],y[i]);
}
for(int j=x[i];j<=y[i];j++){
bus[j]++;
}
}
int max=0,min=200,minp,maxp;
for(int i=0;i<b;i++){
if(max<=bus[i]){//因為要記錄max所在的最大站牌位置，所以"<="
max=bus[i];
maxp=i+1;
}
if(min>bus[i]){//因為要記錄min所在的最小站牌位置，所以"<"
min=bus[i];
minp=i+1;
}
}
cout << minp << " " << maxp << endl;
return 0;
}
```
### j536. 不穩定的礦石 (Ore)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,A,p;
cin >> N >> A;
int a[N];
int max=-1;
for(int i=0;i<N;i++){
cin >> a[i];
if(max<a[i]){
max=a[i];
}
}
for(int i=0;i<N;i++){
if(max==a[i]){
p=i;//先知道最大礦石的位置
break;
}
}
int x=A/2;//x代表更動後的 A/2
int l=A/2,r=A/2;
if(p-(A/2)<0){
x=(A/2)+abs(p-(A/2));
}
if(p+(A/2)>N-1){
x=(A/2)+abs((A/2)+p)-(N-1);//注意要 N-1
}
//更動後
if(p-x<0){//注意left(l) and right(r)要到哪裡
l=p;
}
else{
l=x;
}
if(p+x>N-1){
r=N-1-p;
}
else{
r=x;
}
for(int i=1;i<=l;i++){
a[p]=a[p]+a[p-i];
a[p-i]=0;
}
for(int i=1;i<=r;i++){
a[p]=a[p]+a[p+i];
a[p+i]=0;
}
cout << a[p] << " ";
a[p]=0;
int sum=0;
for(int i=0;i<N;i++){
sum=sum+a[i];
}
cout << sum << endl;
return 0;
}
```
### b534. 質因數、最大公因數
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,tmp,i,r,j,count,N,C=0; cin >> N;
while(C<N){
cin >> a >> b;
r=a;i=2;
while(i<=r){
count=0;
while(r%i==0){
r=r/i;
count=count+1;
}
if(count>1){
cout << i << "^" << count ;
if(r!=1) cout << "*" ;
else{cout << " , ";}
}
else if(count ==1){
cout << i;
if(r!=1) cout << "*" ;
else{cout << " , ";}
}
i++;
}
while(b!=0){
tmp=b;
b=a%b;
a=tmp;
}
cout << a << " , ";
if(a==1) cout << "N" << endl;
else{
count=0;
j=2;
while(j<a){
if(a%j==0){
count=count+1;
}
j++;
}
if(count==0) cout << "Y" << endl;
else{cout << "N" << endl;}
}
C++;
}
return 0;
}
```
### b565. 5.採蘑菇攻略問題
**code**
```c=1
#include <iostream>
using namespace std;
int main(){
int n,sum,j,max;
while(cin >> n){
max=0;
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
for(int i=0;i<n;i++){
if(a[i]>0){
sum=a[i];
j=i+1;
while(sum>0&&j<n){
sum=sum+a[j];
if(sum>max){
max=sum;
}
j++;
}
}
}
cout << max << endl;
}
return 0;
}
```
### a131. 00739 - Soundex Indexing
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cout << "NAME SOUNDEX CODE" << endl;
while(cin >> s){
cout << " " << setw(25)<< left << s;//輸出格式，靠左對齊
string a;
a.push_back(s[0]);
for(int i=0;i<s.size();i++){
if(s[i]=='B'||s[i]=='P'||s[i]=='F'||s[i]=='V'){
a.push_back('1');
}
else if(s[i]=='C'||s[i]=='S'||s[i]=='K'||s[i]=='G'||s[i]=='J'||s[i]=='Q'||s[i]=='X'||s[i]=='Z'){
a.push_back('2');
}
else if(s[i]=='D'||s[i]=='T'){
a.push_back('3');
}
else if(s[i]=='L'){
a.push_back('4');
}
else if(s[i]=='M'||s[i]=='N'){
a.push_back('5');
}
else if(s[i]=='R'){
a.push_back('6');
}
else{
a.push_back('0');
}
}
for(int i=2;i<a.size();i++){
if(a[i-1]==a[i]&&a[i-2]=='0'){//拆散連續編碼
a[i]='0';
}
else if(a[i-1]==a[i]){
a[i]='0';
}
}
a[1]='0';
string b;
for(int i=0;i<a.size();i++){
if(a[i]=='0'){
continue;
}
else{
b.push_back(a[i]);
}
}
if(b.size()>=4){
for(int i=0;i<4;i++){
cout << b[i];
}
}
else{
for(int i=0;i<4;i++){
b.push_back('0');
}
for(int i=0;i<4;i++){
cout << b[i];
}
}
cout << endl;
}
cout << " END OF OUTPUT" << endl;
return 0;
}
```
### c039. 00100 - The 3n + 1 problem
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
bool c;//判斷輸出是否要倒數
int main(){
int a,b;
while(cin >> a >> b){
c=false;
if(a>b){
swap(a,b);
c=true;
}
int max=0;
for(int i=a;i<=b;i++){
int tmp=i;
int count=0;
while(tmp!=1){
if(tmp%2==0){
tmp=tmp/2;
count=count+1;
}
else{
tmp=(tmp*3)+1;
count=count+1;
}
}
count=count+1;//因為前面的 tmp!=1 會讓count少計算一次
if(max<count){
max=count;
}
}
if(c){
cout << b << " " << a << " ";
}
else{
cout << a << " " << b << " ";
}
cout << max << endl;
}
return 0;
}
```
### d182. 00256 - Quirksome Squares
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int c(int x){//判斷幾位數 [前面補0用]
int t=x;
int count=0;
while(t>=10){
t=t/10;
count++;
}
return count+1;
}
int qui(int x,int y,int n){//是否符合quirksome number
int k=pow(x,2);
if(k==y){
if(c(y)<n){//前面補0
for(int j=0;j<n-c(y);j++){
cout << 0;
}
}
cout << y << endl;
}
}
int main(){
int n;
while(cin >> n){
int d=pow(10,n/2);
int sum=0;
for(int i=0;i<n;i++){
sum=sum+9*(pow(10,i));
}
for(int i=0;i<=sum;i++){
int tmp=i;
if(tmp<d){
qui(tmp,tmp,n);
}
else{
int l=tmp/d;
int r=tmp%d;
int tol=l+r;
qui(tol,tmp,n);
}
}
}
return 0;
}
```
### d235. 10929 - You can say 11
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int out(string &x){
for(int i=0;i<x.size();i++){
x[i]=x[i]+'0';
cout << x[i];
}
}
int main(){
string s;//用string可以解決位數太大的問題
while(cin >> s && s!="0"){
for(int i=0;i<s.size();i++){
s[i]=s[i]-'0';
}
int sum=0;
for(int i=0;i<s.size();i=i+2){
sum=sum+s[i];
}
for(int i=1;i<s.size();i=i+2){
sum=sum-s[i];
}
sum=abs(sum);
out(s);
if(sum%11==0 || sum==0){
cout << " is a multiple of 11." << endl;
}
else{
cout << " is not a multiple of 11." << endl;
}
}
return 0;
}
```
### e563. 12694 - Meeting Room Arrangement (greedy演算法練習)
想法:
先將每個活動的結束時間由小排到大，並觀察**下個活動**的開始時間是否小於**本次活動**
的結束時間，如果小於就不算，如果大於，就接續下一個比較。
由上圖的範例可知，最多有四種彼此不交集的活動可安排
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
#define pll pair<int,int>
bool cmp(pll x,pll y){//將pair每個元素的second做排序
return x.second < y.second;
}
int main(){
pll a;
int n,cou,r;
vector<pll> v;
cin >> n;
while(n>0){
cin >> a.first >> a.second;
if(a.first==0&&a.second==0){
n--;
cou=1;
sort(v.begin(),v.end(),cmp);//將pair每個元素的second做排序
r=v[0].second;
for(int i=0;i<v.size()-1;i++){
if(r<=v[i+1].first){
cou++;
r=v[i+1].second;
}
}
cout << cou << "\n";
v.clear();
}
else{
v.push_back(a);
}
}
return 0;
}
```
### b304. 00673 - Parentheses Balance (stack練習)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
string s;
cin >> n;
getline(cin,s);//這題因為輸入有空字串，所以讀入字串要用 getline(cin,s);
while(n--){
bool c=0;
stack<char> v;
getline(cin,s);
for(int i=0;i!=s.size();i++){
if(s[i]=='('){
v.push(s[i]);
}
else if(s[i]=='['){
v.push(s[i]);
}
else if(s[i]==')'){
if(v.size()==0){
c=1;
break;
}
if(v.top()=='('){
v.pop();
}
else{
v.push(s[i]);
}
}
else if(s[i]==']'){
if(v.size()==0){
c=1;
break;
}
if(v.top()=='['){
v.pop();
}
else{
v.push(s[i]);
}
}
}
if(c){
cout << "No\n";
}
else{
if(v.size()==0){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
}
return 0;
}
```
### c123. 00514 - Rails (stack練習)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k;
int a[1001];
while(cin >> n){
if(n==0){
break;
}
while(1){
stack<int> sta;//分為兩個stack做討論，分別為停在車站的sta
stack<int> A;//和仍在A處的A
cin >> a[0];
if(a[0]==0){
break;
}
bool c=0;
for(int i=1;i<n;i++){
cin >> a[i];
}
for(int i=n;i>0;i--){
A.push(i);
}
for(int i=0;i<n;i++){
if(A.size()==0&&a[i]!=sta.top()){
c=1;//如果A已無車廂，sta的最上層又無目標車廂，則直接跳出迴圈
break;
}
if(sta.size()!=0&&a[i]==sta.top()){
sta.pop();//先觀察停在車站的最上層車廂是否==a[i]
}
else{//如果無，就從A裡一個個找
while(A.size()!=0){
if(a[i]==A.top()){
A.pop();
break;
}
else{
sta.push(A.top());
A.pop();
}
}
}
}
if(c){
cout << "No\n";
}
else{
cout << "Yes\n";
}
}
}
return 0;
}
```
## 圖論練習
### f668. FJCU_109_Winter_Day1_Lab3 Adjacency Matrix 和 Adjacency List 練習
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);//怕TLE。先io優化
int n,m,s,t;
cin >> n >> m;
vector<int> v[11];
for(int i=0;i<m;i++){
cin >> s >> t;
v[s].push_back(t);//因為是無向圖，所以相連的兩邊都要push
v[t].push_back(s);
}
for(int i=1;i<=n;i++){
cout << i << ": ";
sort(v[i].begin(),v[i].end());
for(int j=0;j<v[i].size();j++){
cout << v[i][j] << " ";
}
cout << "\n";
}
}
```
### a290. 新手訓練系列 ~ 圖論 (BFS解法)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
int n,m,a,b,A,B,tmp;
while(cin >> n >> m){
bool ans=1;//紀錄該輸出"Yes!!!"還是"No!!!"
vector<int> v[801];
while(m--){
cin >> a >> b;
v[a].push_back(b);
}//圖的儲存[由上題延伸而來]
cin >> A >> B;
queue<int> q;//BFS
q.push(A);
while(!q.empty()){
tmp=q.front();
q.pop();
if(tmp==B){
ans=0;
break;
}
for(int i=0;i<v[tmp].size();i++){
q.push(v[tmp][i]);
}
}
if(ans){
cout << "No!!!\n";
}
else{
cout << "Yes!!!\n";
}
}
}
```
### f673. FJCU_109_Winter_Day2_Lab1 樹高(DFS練習)
**code**
```c=1
#include <bits/stdc++.h>
using namespace std;
int maxH=0;
void dfs(int i,int h,vector<int> v[]){
for(int j=0;j<v[i].size();j++){
if(v[i][j]==-1){
if(h>maxH){
maxH=h;
}
h=0;
break;
}
dfs(v[i][j],h+1,v);
}
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
int n,u,a,b;
cin >> n;
vector<int> v[31];
while(n--){
cin >> u >> a >> b;
v[u].push_back(a);
v[u].push_back(b);
}
dfs(0,0,v);
cout << maxH << "\n";
}
```
Sign in with Wallet
Connect another wallet