# C++ JMJudge writeup
題目來源: [JMJUDGE](https://jmj.cmgsh.tp.edu.tw/UserStatistic)
```111那屆``` y1w3n
ID: 早‧還沒睡飽‧安
---
==以下防雷，解題記錄用，建議還是自己先思考過題目==
---
# 高一資訊科技
b001. 小學生的三角形面積計算
```cpp=
#include<iostream>
using namespace std;
int main(){
float a, h;
cin>>a>>h;
cout<<float(h*a/2);
}
```
b002. BMI值計算機
```cpp=
#include<iostream>
using namespace std;
float BMI(float w,float h){
h=h/100;
float BMI=w/(h*h);
return BMI;
}
int main(){
float h,w;
cin>>h>>w;
cout<<BMI(w,h);
}
```
b004. 小學生的梯形面積計算
```cpp=
#include<iostream>
using namespace std;
int main(){
float a, b, c;
cin>>a>>b>>c;
cout<<float (a+b)*c/2;
}
```
b005. 高中生的三角形面積與周長
```cpp=
#include<iostream>
#include<math.h> //函式庫<math.h>，宣告許多跟數學計算相關的函數
using namespace std;
int main(){
float a, b, c, s, d;
cin>>a>>b>>c;
s=(a+b+c)/2;
d=s*(s-a)*(s-b)*(s-c);
cout<<sqrt(d)<<endl<<(a+b+c); //sqrt(a)是開根號
}
```
b006. 高中生的一元二次方程式的根
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
float a, b, c, s;
cin>>a>>b>>c;
s=sqrt(b*b-4*a*c);
cout<<(-b+s)/(2*a)<<endl<<(-b-s)/(2*a);
}
```
b007. 你過胖了嗎
```cpp=
#include<iostream>
using namespace std;
int main(){
float a, b, c;
cin>>a>>b;
c=b/((a/100)*(a/100));
if (c<18.5){
cout<<"過輕";
}
else if(18.5<=c&&c<24){
cout<<"健康";
}
else if(24<=c&&c<27){
cout<<"過重";
}
else{
cout<<"肥胖";
}
}
```
b008. 決戰520
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
if(a==b){
cout<<"Draw";
}
else if(2==a&&b==5||0==a&&b==2||5==a&&b==0){
cout<<"A win";
}
else{
cout<<"B win";
}
}
```
b009. 國中生的一元二次方程式
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int a,b,c;
float D;
cin>>a>>b>>c;
D=(b*b)-(4*a*c);
if(D>0){
float e,f;
e=(-1*b+sqrt(D))/(2*a);
f=(-1*b-sqrt(D))/(2*a);
cout<<float(e)<<endl<<float(f);
}
else if(D==0){
float e;
e=(-1*b+sqrt(D))/(2*a);
cout<<float(e);
}
else{
cout<<"no solution";
}
}
```
b010. 星星直角三角形_靠左對齊版
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,a,b;
cin>>n; //三角形的高(行數)
for(a=1;a<=n;a++){ //a=1>>從第一行開始
for(b=0;b<a;b++){ //第幾行就輸出幾個*
cout<<"*";
}
cout<<endl;
}
}
```
b011. 我想要學分嗚嗚
```cpp=
#include<iostream>
using namespace std;
int main(){
float N, M, c;
cin>>N>>M;
c=(N+M)/2;
if (c<60){
cout<<"No";
}
else{
cout<<"Yes";
}
}
```
b012. 星星直角三角形_靠右對齊版
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,a,b;
cin>>n;
for(a=1;a<=n;a++){ //a=1>>從第一行開始
for(b=n;b>a;b--){ //空白數遞減
cout<<" ";
}
for(b=1;b<=a;b++){
cout<<"*";
}
cout<<endl;
}
}
```
b013. 星星等腰三角形
```cpp=
//考慮每行輸入的空格數和*數與行數的關係
//*的個數是1,3,5……的關係及行數的兩倍減一(2n-1)
//空格數是總行數-1並逐行遞減
#include<iostream>
using namespace std;
int main(){
int n,a,b;
cin>>n;
for(a=1;a<=n;a++){
for(b=n-a;b>0;b--){
cout<<" ";
}
for(b=1;b<=2*a-1;b++){
cout<<"*";
}
cout<<endl;
}
}
```
b014. 星星菱形
```cpp=
//上半:空格遞減 *遞增
//下半:空格遞增 *遞減
#include<iostream>
using namespace std;
int main(){
int n,a,b;
cin>>n;
for(a=1;a<=n;a++){ //上半部(等腰
for(b=n-a;b>0;b--){
cout<<" ";
}
for(b=1;b<=2*a-1;b++){
cout<<"*";
}
cout<<endl;
}
for(a=n-1;a>0;a--){ //下半部
for(b=n-a;b>0;b--){
cout<<" ";
}
for(b=1;b<=2*a-1;b++){
cout<<"*";
}
cout<<endl;
}
}
```
b016. 雞兔同籠
```cpp=
#include <iostream>
using namespace std;
int main(){
int m,n;
cin >> m >> n;
for(int i = 0; i <=m; i++){
int x = i;
int y = m-i;
if(2*x+4*y == n){
cout << x <<" "<< y << endl;
}
}
}
```
b017. 找因數
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,a;
cin>>n;
a=1;
while(n>=a){
if(n%a==0){
cout<<a<<endl;
}
a=a+1;
}
}
```
b019. 誰是學霸
```cpp=
#include <iostream>
using namespace std;
int main(){
int n, score;
cin >> n;
int max_score = -1;
for(int i = 1; i<=n; i++){
cin >> score;
if(score > max_score){
max_score = score;
}
}
cout << max_score << endl;
}
```
法二 by遞迴
```cpp=
#include <iostream>
using namespace std;
const int MAXN=55;
int max_score(int A[],int n,int id){
if(id==n-1){
return id;
}
int max_back=max_score(A,n,id+1);
if(A[id]>max_back){
return A[id];
}
else{
return max_back;
}
}
int main() {
int n;
int id=0;
cin>>n;
int A[MAXN]={};
for(int i=0;i<n;i++){
cin>>A[i];
}
cout<<max_score(A,n,id)<<endl;
}
```
b020. 成績公布-2
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[41]={ };
for(int i= 0; i<n; i++){
cin>>a[i];
}
int p;
cin>>p;
cout<<a[p-1];
}
```
b021. 誰是學霸之到底是誰
```cpp=
#include<iostream>
using namespace std;
int main(){
int n, score,a;
a=1;
cin >> n;
int max_score = -1;
for(int i = 1; i<=n; i++){
cin >> score;
if(score > max_score){
max_score = score;
a=i;
}
}
cout << a << endl;
}
```
b022. 成績公布
```cpp=
#include<iostream>
using namespace std;
int main(){
int a[11]={85,35,65,27,68,94,20,100,58,78};
int p;
cin>>p;
cout<<a[p-1];
}
```
b023. 算平均
```cpp=
#include<iostream>
using namespace std;
int main(){
float c=0;
float n, i;
cin>>n;
for(int i=0;i<n;i++){
int b;
cin>>b;
c=c+b;
}
cout<<float(c/n);
}
```
法二 by自訂義
```cpp=
#include <bits/stdc++.h>
using namespace std;
float S(float n,int b){
float S=0;
for(int i=0;i<n;i++){
cin>>b;
S=S+b;
}
return S/n;
}
int main() {
float n, i;
float c=0;
int b;
cin>>n;
cout<<S(n,b);
}
```
b024. 低空飛過
```cpp=
#include<iostream>
using namespace std;
int main(){
int c=0;
int n, s,h;
h=0;
cin>>n;
int ms=101;
for(int i=1;i<=n;i++){
cin>>s;
if (s<ms&&s>=60){
ms=s;
}
if(s>h){
h=s;
}
}
if(h<60){
cout<<"QQ";
}
else {
cout<<ms;
}
}
```
b025. 小華買午餐
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
if ((a+b)<150){
cout<<"訂購";
}
}
```
b026. 午餐要不要配飲料
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
if ((a+b)<150){
cout<<"訂購";
}
else{
cout<<"不買飲料";
}
}
```
b027. 午餐的抉擇
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
if(a+b>200){
cout<<"離開";
}
else if(150<a+b&&a+b<=200){
cout<<"不買飲料";
}
else if(a+b<=0){
cout<<"錯誤";
}
else if ((a+b)<=150){
cout<<"訂購";
}
}
```
b028. 恭喜你可以參加複試
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
if (a>=b){
cout<<"恭喜你可以參加複試";
}
}
```
b029. 大雨大雨一直下
```cpp=
#include<iostream>
using namespace std;
int main(){
float a;
cin>>a;
if (a<80){
cout<<"一般";
}
else if(80<=a&&a<200){
cout<<"大雨";
}
else if(200<=a&&a<350){
cout<<"豪雨";
}
else if(350<=a&&a<500){
cout<<"大豪雨";
}
else{
cout<<"超大豪雨";
}
}
```
b030. 愛你幾次都可以
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, i;
cin>>a;
for(i=0;i<a;i++){
cout<<"我愛你"<<endl;
}
}
```
b031. 輪值的日期
```cpp=
#include<iostream>
using namespace std;
int main(){
int c,e,h,i;
h=0;
cin>>c>>e;
for(int i=c;i<=e;i++){
cout<<i<<endl;
}
}
```
b032. 小朋友學數數
```cpp=
#include<iostream>
using namespace std;
int main(){
int n, a, b;
cin>>n>>a>>b;
for(int i=n;i<=a;i=i+b){
cout<<i<<endl;
}
}
```
b033. 在平均之上
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,t;
t=0;
float a,b;
cin>>n;
int s[41]={ };
for(int i= 0; i<n; i++){
cin>>s[i];
a=a+s[i];
}
b=a/n;
for(int i= 0; i<n; i++){
if(s[i]>=b){
t=t+1;
}
}
cout<<t;
}
```
b034. 平均之上的平均
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
float t=0;
float c=0;
float a,b;
cin>>n;
int s[41]={ };
for(int i= 0; i<n; i++){
cin>>s[i];
a=a+s[i];
}
b=a/n;
for(int i= 0; i<n; i++){
if(s[i]>=b){
t=t+s[i];
c=c+1;
}
}
cout<<float(t/c);
}
```
b035. 發糖果囉(基本題)
```cpp=
#include<iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
cout<<int(a/b)<<endl<<(a%b);
}
```
b036. 老師請飲料
```cpp=
#include<iostream>
using namespace std;
int main(){
int c=0,h=0;
int n,s,a[40];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if (a[i]>=80){
h=h+1;
}
}
cout<<h;
}
```
b039. 發糖果囉！
```cpp=
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout << a << " = " << b << " * " << a/b << " + " << a-(a/b*b);
}
```
b043. 九九乘法表(簡化版)
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,i;
cin>>n;
for(int i=1;i<=n;i++){
cout<<i<<" * "<<i<<" = "<<(i*i)<<endl;
}
}
```
# 未分類題庫
a001. 哈囉
```cpp=
#include<iostream>
using namespace std;
int main(){
string a;
cin>>a;
cout<<"hello, "<<a;
}
```
a004. 經濟大恐荒
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,money,a[1000];
cin >> n;
money=0;
for(int i = 1; i<=n; i++){
cin>>a[i];
}
for(int j = 1; j<=n; j++){
money=money+(j*a[j]);
}
cout << money << endl;
}
```
a007. K-I-S-S-I-N-G
```cpp=
#include<iostream>
using namespace std;
int main(){
string g,b;
getline(cin,g); //讓輸入不被空格打斷
getline(cin,b);
cout<<g<<" and "<<b<<" sitting in the tree";
}
```
a012. Johnny B. Goode
```cpp=
#include<iostream>
using namespace std;
int main(){
string n;
getline(cin,n);
cout<<"Go, "<<n<<", go go";
}
```
a013. You can say that again!
```cpp=
#include<iostream>
using namespace std;
int main(){
string n;
getline(cin,n);
for(int i=0;i<2;i++){
cout<<n<<" ";
}
}
```
a011. 加減乘除
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int n,b;
char a;
while(cin>>n){ //while(規則)
cin>>a>>b; //符合規則就執行
if(a=='+'){
cout<<n+b<<endl;
}
if(a=='-'){
cout<<n-b<<endl;
}
if(a=='*'){
cout<<n*b<<endl;
}
if(a=='/'){
cout<<n/b<<endl;
}
}
}
```
a014. 中華民國萬歲！
```cpp=
#include<iostream>
using namespace std;
int main(){
int y;
cin>>y;
cout<<y-1911;
}
```
a015. 妳那裡現在幾點了？
```cpp=
#include<iostream>
using namespace std;
int main(){
int t,USA;
cin>>t;
USA=t-15;
if(USA<0){
cout<<24+USA;
}
else{
cout<<USA;
}
}
```
a016. 糟糕，我發燒了！
```cpp=
輸入僅有一行，含有一個整數 f (-460 ≤ f ≤ 2147483647)，代表華氏溫度。
輸出計算所得的攝氐溫度，精確到小數點以下三位。
#include<iostream>
#include<iomanip>//用於操作C++程序輸出的庫
using namespace std;
int main(){
long double c;
long double f;//因為最大值有2147483647，所以用long duble 記憶體空間大，精度也高。
cin>>f;
c=(f-32)*5/9;
cout << setiosflags(ios::fixed) << setprecision(3) << c << endl;
//setprecision(3)代表取三位數；前面加上fixed就變成取小數點後三位數
}
```
a017. BASIC 的 SGN 函數 -- 板橋高中教學題
```cpp=
#include<iostream>
using namespace std;
int main(){
int i;
cin>>i;
if (i==0){
cout<<"0";
}
else if(i>0){
cout<<"1";
}
else{
cout<<"-1";
}
}
```
a018. 還要等多久啊？
```cpp=
#include <iostream>
using namespace std;
int main(){
int a;
cin >> a;
if(a<=25){
cout << 25-a << endl;
}
else{
cout << 85-a << endl;
}
}
```
a019. 0 與 1
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
cout<<(n-1)*-1;
}
```
a020. ㄑㄧˊ 數？ -- 板橋高中教學題
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int i;
cin>>i;
if (i%2==0){;
cout<<"Even";
}
else{
cout<<"Odd";
}
}
```
a021. 三人行必有我師
```cpp=
#include <iostream>
using namespace std;
int main(){
int a,b,c,big;
cin >> a >> b >> c;
big = a; //先把第一個假設為最大的
if(b>big){ //如果第二個比較大就取代
big = b;
}
if(c>big){
big = c;
}
cout << big << endl;
}
```
a022. 上學去吧！
```cpp=
#include<iostream>
using namespace std;
string school(int h,int m){ //自定義函數
if(h>=17) return "Off School";
else if(h<7) return "Off School";
if(h==7 && m<30) return "Off School";
else return "At School";
}
int main(){
float h,m;
cin>>h>>m;
cout<<school(h,m);
}
```
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int h,m;
cin>>h>>m;
if(h>=17) {
cout<<"Off School";
}
else if(h<7){
cout<<"Off School";
}
else if(h==7 && m<30){
cout<<"Off School";
}
else{
cout<<"At School";
}
}
```
a023. 閏年判斷
```cpp=
#include <iostream>
using namespace std;
int main(){
int n,f;
cin >> n;
if(n%400==0){
f = 1;
}
else if(n%100==0){
f = 0;
}
else if(n%4==0){
f = 1;
}
if(f == 1){
cout << "a leap year" << endl;
}
else{
cout << "a normal year" << endl;
}
}
```
a024. 該減肥了！
```cpp=
#include<iostream>
using namespace std;
int main(){
int w;
cin>>w;
if(w>50){
cout<<w-1;
}
else{
cout<<w;
}
}
```
a025. 文文的求婚--續集 (n 行版)
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
while(cin>>n){
int y[n];
for(int i=0; i<n; ++i){
cin>>y[i];
}
for(int i=0; i<n; ++i){
if(y[i]%4==0 && y[i]%100!=0 || y[i]%400==0){
cout<<"a leap year"<<endl;
}
else {
cout<<"a normal year"<<endl;
}
}
}
}
```
a026. 文文的求婚--續集 (0 尾版) -- 板橋高中教學題
```cpp=
#include<iostream>
using namespace std;
int main(){
int y;
while(cin>>y&&y!=0){
if(y%4==0&&y%100!=0){
cout<<"a leap year"<<endl;
}
else if(y%400==0){
cout<<"a leap year"<<endl;
}
else{
cout<<"a normal year"<<endl;
}
}
}
```
a027. 文文的求婚--續集 (EOF 版) -- 板橋高中教學題
```cpp=
#include<iostream>
#include <string> //來建立字串，像是字串指定、串接等
using namespace std;
int main(){
int y;
string a,s1;
while(cin>>y&&s1!="EOF"){
if(y%4==0&&y%100!=0){
cout<<"a leap year"<<endl;
}
else if(y%400==0){
cout<<"a leap year"<<endl;
}
else{
cout<<"a normal year"<<endl;
}
std::string s1 = std::to_string(y); //整數轉字串
}
}
```
a028. 文文的求婚--續集 (Case 版)
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,a;
a=1;
while(cin>>n){
int y[n];
for(int i=0; i<n; ++i){
cin>>y[i];
}
for(int i=0; i<n; ++i){
if(y[i]%4==0 && y[i]%100!=0 || y[i]%400==0){
cout<<"Case "<<a<<": "<<"a leap year"<<endl;
a=a+1;
}
else {
cout<<"Case "<<a<<": "<<"a normal year"<<endl;
a=a+1;
}
}
}
}
```
a029. 分組報告
```cpp=
#include<iostream>
#include<cmath>// C++ 中一些有用的內建的數學函式
using namespace std;
int main(){
float n;
cin>>n;
n=n/3;
cout<<std::ceil(n);//小數無條件進位
}
```
a030. 電腦教室
```cpp=
//同b019
#include <iostream>
using namespace std;
int main(){
int n, s;
cin >> n;
int max = -1;
for(int i = 1; i<=n; i++){
cin >> s;
if(s > max){
max = s;
}
}
cout << max << endl;
}
```
a031. 山六九之旅 -- 板橋高中教學題
```cpp=
#include<iostream>
using namespace std;
int main(){
int a;
cin>>a;
if(a>=60){
cout<<"399";
}
else if(18<=a&&a<60){
cout<<"890";
}
else if(12<=a&&a<18){
cout<<"790";
}
else if (6<=a&&a<12){
cout<<"590";
}
else{
cout<<"0";
}
}
```
a032. 班際籃球賽 – 板橋高中教學題
```cpp=
#include <iostream>
using namespace std;
int time(int n){
if (n == 1){
return 0;
}
else if(n%2==0){
return n / 2 + time(n/2);
}
else{
return n / 2 + time(n / 2 + 1);
}
}
int main() {
int n;
cin>>n;
int t=time(n);
cout<<t;
}
```
a033. hello, world
```cpp=
#include<iostream>
using namespace std;
int main(){
cout << "hello, world" ;
}
```
a034. 我愛偶數
```cpp=
//將 a,b 調整成偶數 (a 如果是奇數 + 1,b 如果是奇數 - 1)，計算 2 個偶數間的偶數
#include<iostream>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b;
cout<<((b - (b%2) )-(a + (a%2) ))/2+1;
}
```
a035. 伏林的三角地
```cpp=
#include<iostream>
using namespace std;
int Heron(int a,int b,int c){
int s=(a+b+c)/2;
return (s*(s-a)*(s-b)*(s-c));
}
int main(){
float a,b,c;
cin>>a>>b>>c;
cout<< Heron(a,b,c);
}
```
a036. 我也愛偶數 -- 板橋高中教學題
```cpp=
#include <iostream>
using namespace std;
int main() {
int a,b;
cin>>a>>b;
int t=0;
for (int i=a;i<=b;i++){
if(i%2==0){
t=t+i;
}
}
cout<<t;
}
```
a037. 我也愛偶數 (swap 版) -- 板橋高中教學題
```cpp=
#include <iostream>
using namespace std;
int main() {
int a,b;
cin>>a>>b;
int c=a;
int t=0;
if(a>b){
a=b;
b=c;
}
for (int i=a;i<=b;i++){
if(i%2==0){
t=t+i;
}
}
cout<<t;
}
```
a038. 我不說髒話 -- 板橋高中教學題
```cpp=
#include<iostream>
using namespace std;
int main(){
int n, i;
cin>>n;
for(i=0;i<n;i++){
cout<<"I don't say swear words!"<<endl;
}
}
```
a039. 小明的作業
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a,b,c;
int p=0;
for(int i = 1; i<=5; i++){
cin>>a>>b>>c;
int ar[3]={a,b,c};
sort(ar,ar+3);
if(ar[0]+ar[1]>ar[2]){
p=p+1;
}
}
cout<< p;
}
```
a040. 文文的求婚 (三) -- 板橋高中教學題
```cpp=
#include <iostream>
using namespace std;
int main() {
int a,b;
cin>>a>>b;
int t=0;
for (int i=a;i<=b;i++){
if(i%4==0&&i%100!=0){
t=t+1;;
}
else if(i%400==0){
t=t+1;;
}
}
cout<<t;
}
```
a042. 買鉛筆 -- 板橋高中教學題
```cpp=
#include<iostream>
using namespace std;
int main(){
int a;
cin>>a;
cout<<a*5-10*(a/12);
}
```
a043. 棄保效應 -- 板橋高中教學題
```cpp=
#include <iostream>
using namespace std;
int main() {
long long int a,b,c;
while(cin>>a>>b>>c){
if(c>b && c>a && c>a+b){ //c最大
cout<<"C"<<endl;
}
else if (c>b && c>a && c<a+b){
if(a>b){
cout<<"A"<<endl;
}
else{
cout<<"B"<<endl;
}
}
if(b>c && b>a && b>a+c){ //b最大
cout<<"B"<<endl;
}
else if (b>c && b>a && b<a+c){
if(a>c){
cout<<"A"<<endl;
}
else{
cout<<"C"<<endl;
}
}
if(a>b && a>c && a>c+b){ //a最大
cout<<"A"<<endl;
}
else if (a>b && a>c && a<c+b){
if(b>c){
cout<<"B"<<endl;
}
else{
cout<<"C"<<endl;
}
}
}
}
```
a044. 蛋糕師傅
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int make=0,bake=0;
int o,m,b;
for(int i=0;i<n;i++){
cin>>o>>m>>b;
if(o>make){
make=o+m;
}else{
make+=m;
}
if(make>bake){
bake=make+b;
}else{
bake+=b;
}
cout<<bake<<'\n';
}
}
```
a054. 出來打球
```cpp=
#include<iostream>
using namespace std;
long long J(int n,int N){
if(n<=N){
return n*J(n+1,N);
}
else{
return 1;
}
}
int main(){
int n,r;
cin>>n>>r;
int N=n;
n=n-r+1;
cout<<J(n,N);
}//nFr
```
a057. 牛肉萬歲
```cpp=
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
for(int j=0;j<t;j++){
int n;
cin>>n;
int cnt=0;
for(int i=2;i<n;i++){
if(n%i==0){
cnt++;
}
if(cnt>0){
break;
}
}
if(cnt==0 && n !=1){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
return 0;
}
```
a058. 請支援找零
```cpp=
#include <iostream>
using namespace std;
int main(){
int a,money,c50,c10,c5,c1;
cin >> a;
money = 100-a;
c50 = money/50;
money = money%50;
c10 = money/10;
money = money%10;
c5 = money/5;
money = money%5;
c1 = money;
cout << c50 <<" "<< c10 <<" "<< c5 <<" "<< c1;
}
```
a059. 請支援找零－找到沒零
法一
```cpp=
#include<iostream>
using namespace std;
int main(){
int a,n,money,c50,c10,c5,c1;
cin >> a >>n;
money = 100-a;
if(n==50){
c10 = money/10;
money = money%10;
c5 = money/5;
money = money%5;
c1 = money;
cout << 0 <<" "<< c10 <<" "<< c5 <<" "<< c1;
}
if(n==10){
c50 = money/50;
money = money%50;
c5 = money/5;
money = money%5;
c1 = money;
cout << c50 <<" "<< 0 <<" "<< c5 <<" "<< c1;
}
if(n==5){
c50 = money/50;
money = money%50;
c10 = money/10;
money = money%10;
c1 = money;
cout << c50 <<" "<< c10 <<" "<< 0 <<" "<< c1;
}
}
```
法二
```cpp=
#include<iostream>
using namespace std;
int main(){
int a,n,money;
cin >> a >>n;
money = 100-a;
int c[4]={};
int d[4]={50,10,5,1};
for(int i=0;i<4;i++){
if(n!=d[i]){
c[i] = money/d[i];
money=money%d[i];
}
cout<<c[i]<<" ";
}
}
```
a060. 三角行不行
```cpp=
#include <iostream>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
if(a+b>c && b+c>a && a+c>b){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
```
a061. 振興三倍券到底...省了多少錢
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int seven=n+(n/500)*500+((n%500)/200)*100;
int hi=n+(n/500)*200;
int ok=n+(n/500)*100+((n%500)/200)*20;
cout<<seven<<endl<<hi<<endl<<ok;
}
```
a062. 這個月有幾天
```cpp=
#include<iostream>
using namespace std;
int main(){
int a;
cin>>a;
if(a==2){
cout<<"28";
}
else if(a%2==0&&a<8){
cout<<"30";
}
else if(a%2!=0&&a>8){
cout<<"30";
}
else{
cout<<"31";
}
}
```
a063. 考拉茲的猜想
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
while(n!=1){
cout<<n<<endl;
if (n%2==0){
n=n/2;
}
else {
n=(3*n)+1;
}
}
cout<<"1"<<endl;
}
```
a064. 最大公因數
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b>>c;
int gcd=1;
int p=2;
while(p<=a && p<=b && p<=c){
while(a%p==0 && b%p==0 && c%p==0){
a=a/p;
b=b/p;
c=c/p;
gcd=gcd*p;
}
p++;
}
cout<<gcd;
return 0;
}
```
a065. RD的危機
```cpp=
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
for(int j=0;j<t;j++){
int n;
cin>>n;
int cnt=0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
cnt++;
}
if(cnt>0){
break;
}
}
if(cnt==0 && n !=1){
cout<<1;
}
else{
cout<<0;
}
}
return 0;
}
//a057
```
a066. 今年的第幾天
```cpp=
#include<iostream>
using namespace std;
int main(){
int m,d;
int a[13]={0,0,31,59,90,120,151,181,212,243,273,304,334};
cin>>m>>d;
cout<<a[m]+d;
}
```
a068. 三隊拚輸贏
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
int maxn=-1;
int w=-1;
char who[3]={'A','B','C'};
for (int i=0;i<3;i++){
cin>>n;
if(n>maxn){
maxn=n;
w=i;
}
}
cout<<who[w];
}
```
a072. 啊就階乘，簡單吧>.0
```cpp=
#include <bits/stdc++.h>
using namespace std;
int J(int n){
if(n==0){
return 1;
}
else{
return n*J(n-1);
}
}
int main() {
int n;
cin>>n;
cout<<J(n);
}
```
a077. 深水炸彈
```cpp=
#include <iostream>
using namespace std;
int main() {
int a,b,c,d,e,f,g;
cin>>a>>b>>c>>d>>e>>f>>g;
int w=a*b*d;//原本的水
int v=e*f*g;//磚塊
int ans=(w+v)/(a*b);//後來
if(a*b==e*f && g>=c){ //完全密合導致沒水
ans=0;
}
else if(d==0){//本來就沒水
ans=0;
}
else if(g>ans){//凸出來但有水
ans=(a*b*d)/((a*b)-(e*f));
}
if(ans>c){ //溢出來
ans=c;
}
cout<<ans;
}
```
a078. 我討厭偶數
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
while(n%2==0){
n=n/2;
}
cout<<n;
}
```
a084. 偉晉的考驗
```cpp=
#include<iostream>
using namespace std;
int J(int n){
if(n==0){
return 1;
}
else{
return n*J(n-1);
}
}
int main(){
int a,b;
cin>>a>>b;
int c=J(a)/(J(b)*J(a-b));
cout<<c;
}
```
```cpp=
#include<iostream>
using namespace std;
int C(int n,int r){
if(r==0||n==r){
return 1;
}
return C(n-1,r)+C(n-1,r-1);
}
int main(){
int n,r;
cin>>n>>r;
cout<<C(n,r);
}
```
a087. 在家中的美勞課
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
if(n>=sqrt(m)*4){
cout<<"yes";
}
else{
cout<<"no";
}
}
```
a091. 括號配段[中小版]
```cpp=
#include <iostream>
#include <stack>//堆疊引入的函式庫
using namespace std;
int main(){
int n;
cin>>n;
string str;
cin >> str;
stack<char> s;
int cnt = 0; // 記錄式子中有幾對括號
for(int i = 0; i < n; i++){
if(str[i] == '(' || str[i] == '[') // 遇到左括弧，一律推入堆疊
s.push(str[i]);
else{ // 遇到右括弧
if(!s.empty()){ // 堆疊不是空的，才能移走一個左括弧
if((str[i] == ')' && s.top()=='(') || (str[i] == ']' && s.top()=='[')){
s.pop();
cnt++;
}
}
else{ // 否則，式子中的括號必定有誤
cnt = 0;
break;
}
}
}
// 堆疊裡可能殘留剩下的左括弧！
// 堆疊空的才合理
if(s.empty()&&cnt!=0) cout <<"yes "<< cnt << endl;
else cout <<"no "<< 0 << endl;
return 0;
}
```
a095. 一起玩數織
```cpp=
#include <iostream>
using namespace std;
const int MAXN=155;
int main(){
int n=0;
int l[MAXN]={};
while(cin>>l[n]){//ctrl+D 結束
n++;
}
l[n]=2;
n++;
int cnt =1;
for(int i=1;i<n;i++){
if(l[i]==l[i-1]){//跟前面一->直接+1
cnt++;
}
else{ //跟前面不一樣->結算重新開始
cout<<cnt<<" ";
cnt=1;
}
}
cout<<endl;
}
```
a096. 大物流時代
```cpp=
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
if(n%7==0){
cout << "Boss" << endl;
}
if(n%3==0){
cout << "Mei" << endl;
}
if(n%2==0){
cout << "Peter" << endl;
}
if(n%7!=0 && n%3!=0 && n%2!=0){
cout << "Boss" << endl;
}
}
```
a100. 數數數
```cpp=
#include <iostream>
using namespace std;
int main(){
int a,n,d;
cin >> a >> n >> d;
for(int i=a;i<=n;i+=d){
cout << i << endl;
}
}
```
a103. 小考總分
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
int s;
int t=0;
for(int i=0;i<n;i++){
cin>>s;
t=t+s;
}
cout<<t;
}
```
a104. 列印成績單
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
int yes[11]={};
int num,score;
for(int i=1;i<=n;i++){
cin>>num>>score;
yes[num]=score;
}
for(int i=1;i<=10;i++){
cout<<yes[i]<<"\n";
}
}
```
a107. 誰沒交作業
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
int yes[11]={};
int num,score;
for(int i=1;i<=n;i++){
cin>>num>>score;
yes[num]=num;
}
for(int i=1;i<=10;i++){
if(yes[i]==0){
cout<<i<<"\n";
}
}
}
```
a108. 作業亂了
```cpp=
#include <iostream>
using namespace std;
int main() {
int yes[11]={};
int score;
for(int i=10;i>=1;i--){
cin>>score;
yes[i]=score;
}
for(int i=1;i<=10;i++){
cout<<i<<" "<<yes[i]<<endl;
}
}
```
a109. 小瑛拼單字
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
char a[10000];
char s;
for(int i=0;i<n;i++){
cin>>s;
a[i]=s;
}
for(int i=n-1;i>=0;i--){
cout<<a[i];
}
}
```
a110. 存款提款
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
int how[505];
int md[505];//定存
int md_t=0;
int mh[505];//活存
int mh_t=0;
int money;
for(int i=0;i<n;i++){
cin>>how[i]>>money;
if(how[i]==0){
mh[mh_t]=money;
mh_t++;
}
else{
md[md_t]=money;
md_t++;
}
}
for(int i=0;i<mh_t;i++){
cout<<"活存 "<<mh[i]<<endl;
}
for(int i=0;i<md_t;i++){
cout<<"定存 "<<md[i]<<endl;
}
}
```
a111. 自助收銀機
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,t; //n:物品單價，t:總價
t=0;
while(cin>>n&&n!=-1){
t=t+n;
}
cout<<t;
}
```
a112. 杰克‧A‧布萊克
```cpp=
#include<iostream>
using namespace std;
int main(){
int s=0;
int card =0;
cin >>card;
s+=card;
while(s<=16){
cin >> card;
s+=card;
}
if(s>21){
cout << "Lose" <<endl;
}
else{
cout << s <<endl;
}
}
```
a113. 最小公倍數
```cpp=
#include<iostream>
using namespace std;
int main(){
long long int a; //因為數字超過2147483648時不能用int存所以用long long
long long int b;
cin >>a>>b;
long long int c=a; //變數c 最小公倍數
while (c%b!=0){ //c整除b時為最小公倍數，否則遞加a
c=c+a; //a以倍數放大
}
cout<<c;
}
```
a118. 芒果季
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
int m;
int bad_m[100000];
int bt=0;//badtotal
while(m!=-1){
cin>>m;
if(m<60 && m!=-1){
bad_m[bt]=m;
bt++;
}
}
if(bt==0){
cout<<"All pass"<<endl;
}
else{
for(int i;i<bt;i++){
cout<<bad_m[i]<<endl;
}
}
}
```
a121. 智慧叫貨販賣機
```cpp=
#include <iostream>
using namespace std;
int main() {
int n ;
cin>>n;
int how_many[25]={};
for(int i=1;i<=n;i++){
cin>>how_many[i];
}
int buy;
while(buy!=-1){
cin>>buy;
if(buy==-1){
break;
}
else{
how_many[buy]--;
}
}
for(int i=1;i<=n;i++){
if(how_many[i]<3){
cout<<i<<" ";
}
}
}
```
a122. 地頭蛇
```cpp=
#include <iostream>
using namespace std;
int main() {
int A[105][105]={0};
int r,c;
cin>>r>>c;
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cin>>A[i][j];
}
}
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
if (A[i][j]>A[i-1][j] and A[i][j]>A[i+1][j] and A[i][j]>A[i][j-1] and A[i][j]>A[i][j+1]){
cout<<A[i][j]<<endl;
}
}
}
}
```
a123. 小老師的困擾
```cpp=
#include<iostream>
using namespace std;
int main(){
int t,n;
cin>>t>>n;
int s[55][55]={};
for(int i=0;i<t;i++){
for(int j=0;j<n;j++){
cin>>s[i][j];
}
}
for(int i=0;i<n;i++){
int ans=0;
int min=101;
for(int j=0;j<t;j++){
for(int k=0;k<t;k++){
if(s[k][i]<=min){
min=s[k][i];
}
}
ans+=s[j][i];
}
cout<<(ans-min)/(t-1)<<" ";
}
}
```
a124. 西洋棋彩繪
```cpp=
#include <iostream>
using namespace std;
int main() {
int h,w,k;
cin>>h>>w>>k;
int board[505][505]={};
int di[8]={-1,+0,+1,+0,-1,-1,+1,+1};
int dj[8]={+0,-1,+0,+1,-1,+1,-1,+1};
while(k--){
int t,c,r;
cin>>t>>c>>r;
board[r][c]=1;
if(t==0){
continue;
}
else if(t==1){
for(int k=0 ;k<8;k++){
int i=r+di[k];
int j=c+dj[k];
while(i>=0 and i<h and j>=0 and j<w){
if(board[i][j]==1){
break;
}
board[i][j]=1;
i+=di[k];
j+=dj[k];
}
}
}
else if(t==2){
for(int k=4 ;k<8;k++){
int i=r+di[k];
int j=c+dj[k];
while(i>=0 and i<h and j>=0 and j<w){
if(board[i][j]==1){
break;
}
board[i][j]=1;
i+=di[k];
j+=dj[k];
}
}
}
else if(t==3){
for(int k=0 ;k<4;k++){
int i=r+di[k];
int j=c+dj[k];
while(i>=0 and i<h and j>=0 and j<w){
if(board[i][j]==1){
break;
}
board[i][j]=1;
i+=di[k];
j+=dj[k];
}
}
}
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cout<<board[i][j]<<" ";
}
cout<<endl;
}
}
```
a125. 紙牌配對
```cpp=
#include <iostream>
using namespace std;
int main() {
int n,a[100001]={};
cin>>n;
for (int i=0;i<n;i++){
cin>>a[i];
}
int po[101]={};
for(int p=1 ;p<=100;p++){
po[p]=-1;
}
for(int i=0 ;i<n;i++){
if(po[a[i]]==-1){
po[a[i]]=i;
}
else{
cout<<i<<" "<<po[a[i]]<<" "<<a[i]<<endl;
po[a[i]]=-1;
}
}
}
```
a127. 騎士的巡禮-1
```cpp=
#include<iostream>
using namespace std;
const int MAXN=105; //const:固定的 -> 變成常數
const int MAXM=MAXN*MAXN;
int main(){
int n,m;
cin>>n>>m;
int b[MAXN][MAXN]={};
int r[MAXM],c[MAXM];
for(int i=1;i<=m;i++){
cin>>r[i]>>c[i];
b[r[i]][c[i]]=i*10000;
}
bool can_move[MAXM]={};
int mi[9]={0,-2,-1,1,2,2,1,-1,-2};
int mj[9]={0,1,2,2,1,-1,-2,-2,-1};
int step=1;
int alive=m;
for (int i=1;i<=m;i++){
can_move[i]=true;
}
while (alive>0){ //還沒結束的話
for(int i=1;i<=m;i++){
if(!can_move[i]){
continue;
}
can_move[i]=false;
for(int k =1 ;k<=8;k++){
int nr=r[i]+mi[k],nc=c[i]+mj[k];
if (nr>=0 && nr<n && nc>=0 && nc<n && b[nr][nc]==0){
r[i]=nr;
c[i]=nc;
b[r[i]][c[i]]=i*10000+step;
can_move[i]=true;
break;
}
}
if(!can_move[i]){
alive--;
}
}
step++;
}
for (int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<b[i][j]<<" \n"[j==n-1];
}
}
}
```
a129. 自動平衡蹺蹺板
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,w[2050];
cin>>n;
for(int i=0;i<n;i++){
cin>>w[i];
}
int finish=0;
int t=0;
while(finish==0){
for(int i=0;i<n;i++){
int r=0;
int l=0;
for(int k=0;k<n;k++){
if(k<i){
r+=w[k]*(i-k);
}
else if(k>i){
l+=w[k]*(k-i);
}
}
if(r==l){
finish=1;
for(int m=0;m<n;m++){
if(m==i){
cout<<"v"<<" ";
}
else{
if(m==n-1){
cout<<w[m];
}
else{
cout<<w[m]<<" ";
}
}
}
}
}
swap(w[t],w[n-1-t]);
t++;
}
}
```
a145. 競技場
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int main(){
int n;
cin>>n;
int A[MAXN]={},B[MAXN]={};
for(int i=0;i<n;i++){
cin>>A[i];
B[i]=A[i];
}
sort (A,A+n);
for(int i=0;i<n;i++){
int l=0,r=n-1;
while(l<r){//跑到剩一個候選為止
int mid=(l+r+1)/2;
if(A[mid]==B[i]){
l=mid;
}
else if(A[mid]<B[i]){
l=mid+1;
}
else{
r=mid-1;
}
}
cout<<n-l<<" ";
}
}
```
a158. 長腿阿馨爬樓梯
```cpp=
#include<iostream>
using namespace std;
int stair(int n){
if(n==1){
return 1;
}
if(n==2){
return 2;
}
if(n==3){
return 4;
}
return stair(n-1)+stair(n-2)+stair(n-3);
}
int main(){
int n;
cin>>n;
cout<<stair(n)<<endl;
}
```
法二
```cpp=
#include<iostream>
using namespace std;
const int MAXN=100;
int dp[MAXN]={0,1,2,4};
int stair(int n){
if(dp[n]!=0){
return dp[n];
}
dp[n]=stair(n-1)+stair(n-2)+stair(n-3);
return dp[n];
}
int main(){
int n;
cin>>n;
cout<<stair(n)<<endl;
}
//用list存版
//動態規劃(dp)，遞迴+表格
```
法三
```cpp=
#include<iostream>
using namespace std;
const int MAXN=100;
int dp[MAXN]={0,1,2,4};
int main(){
int n;
cin>>n;
for(int i=4;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
cout<<dp[n]<<endl;
}
//用for迴圈 : Bottom up
```
a160. 小妮爬樓梯（總次數上限版）
```cpp=
#include<iostream>
using namespace std;
int stair(int n,int k){
if(n==1){
return 1;
}
if(n==2){
if(k==0){
return 1;
}
else{
return 2;
}
}
if(k==0){
return stair(n-1,k);
}
return stair(n-1,k)+stair(n-2,k-1);
}
int main(){
int n,k;
cin>>n>>k;
cout<<stair(n,k)<<endl;
}
```
a161. 小湊爬樓梯（連續次數上限版）
```cpp=
#include<iostream>
using namespace std;
int stair(int n,int k,int K){
if(n==1){
return 1;
}
if(n==2){
if(k==K){
return 1;
}
else{
return 2;
}
}
if(k==K){
return stair(n-1,0,K);
}
return stair(n-1,0,K)+stair(n-2,k+1,K);
}
int main(){
int n,K;
cin>>n>>K;
cout<<stair(n,0,K)<<endl;
}
```
a167. 算平均(一行輸入版)
```cpp=
#include<iostream>
using namespace std;
int main(){
float n;
cin>>n;
float s;
float t=0;
for (int i=0;i<n;i++){
cin>>s;
t=t+s;
}
cout<<t/n;
}
```
a170. 單科平均分數
```cpp=
//二維陣列
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
float t;
string b;
t=0;
float a[4][5]={};
for (int i=0;i<4;i++){
for(int j=0;j<5;j++){
cin>>a[i][j];
}
}
cin>>b;
if(b=="c"){
t=a[0][0]+a[1][0]+a[2][0]+a[3][0];
}
if(b=="e"){
t=a[0][1]+a[1][1]+a[2][1]+a[3][1];
}
if(b=="m"){
t=a[0][2]+a[1][2]+a[2][2]+a[3][2];
}
if(b=="s"){
t=a[0][3]+a[1][3]+a[2][3]+a[3][3];
}
if(b=="n"){
t=a[0][4]+a[1][4]+a[2][4]+a[3][4];
}
cout<<float(t/4);
}
```
a172. 法國代購
```cpp=
#include<iostream>
using namespace std;
int main(){
int t,f;
cin>>f;
t=f+6;
if(t>=24){
cout<<t-24;
}
else{
cout<<t;
}
}
```
a173. 預算控制
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n;
int t=0;
for(int i=0;i<n;i++){
cin>>m;
t+=m;
}
cout<<t/n;
}
```
a176. 自動回覆機器人
```cpp=
#include<iostream>
using namespace std;
int main(){
string n;
getline(cin,n);
cout<<n<<" 你好"<<endl<<"你的暱稱將設為 "<<n;
}
```
a177. 小美的年齡
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int h,d;
cin>>d;
h=d*4;
cout<<(d/10)+((h%10)*10);
return 0;
}
```
a180. 分組
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n ;
cin>>n;
if(n%3==0){
cout<< 3;
}
else if (n%3==2){
cout<<2;
}
else if (n%3==1){
cout<<1;
}
}
```
a181. 請輸入預設密碼
```cpp=
#include<iostream>
using namespace std;
int main(){
string pwd;
cin>>pwd;
if(pwd=="000000"){
cout<< "登入成功";
}
else {
cout<< "密碼錯誤";
}
}
```
a182. 判斷正數
```cpp=
#include<iostream>
using namespace std;
int main(){
int n ;
cin>>n;
if(n>0){
cout<< "yes";
}
else{
cout<<"no";
}
}
```
a184. 百貨周年慶
```cpp=
#include<iostream>
using namespace std;
int main(){
int n ;
cin>>n;
if(n>10000){
cout<< "1000";
}
else if (n>5000){
cout<<"600";
}
else if (n>2000){
cout<<"200";
}
}
```
a185. 籃球明星賽
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int M,W,m=0,w=0;
for(int i=0;i<2;i++){
cin>>M>>W;
if(M>W){
m=m+1;
}
else if(M<W){
w=w+1;
}
}
if(m==w){
cout<<"平手";
}
else if(m>w){
cout<<"夢幻隊";
}
else if(m<w){
cout<<"王者隊";
}
return 0;
}
```
a186. 調整總分
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int c=0;
int n,s,a[1000];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cout<<int( sqrt(a[i])*10)<<endl;
}
}
```
a187. 清倉價格
```cpp=
#include<iostream>
using namespace std;
int main(){
int c=0;
int n,a[1000];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cout<<int((a[i])*0.64)<<endl;
}
}
```
a189. 瓜甜?理下!
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin>>w;
if(w>=500){
cout<<"A+";
}
else if(w>=400){
cout<<"A";
}
else if(w>=200){
cout<<"B";
}
else {
cout<<"C";
}
return 0;
}
```
a209. 二分搜尋-終極密碼
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,ans;
cin>>n>>ans;
int k=(1+n)/2;
int finish=0;
int t=1;
int low=0,high=n+1;
while (finish==0){
if (k>ans){
cout<<k<<" is too big"<<endl;
high=k;
k=(low+high)/2;
t++;
}
else if(k<ans){
cout<<k<<" is too small"<<endl;
low=k;
k=(low+high)/2;
t++;
}
else{
finish=1;
cout<<k<<" is correct"<<endl;
}
}
cout<<t;
}
```
a214. 最少交換次數
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int s[105]={};
for(int i=0;i<n;i++){
cin>>s[i];
}
int max;
int t=0;
for(int i=0;i<n-1;i++){
max=i;
for(int j=i+1;j<n;j++){
if(s[j]>s[max]){
max=j;
}
}
if(max!=i){
swap(s[i],s[max]);
t++;
}
}
cout<<t<<'\n';
for(int i=0;i<n;i++){
cout<<s[i]<<' ';
}
}
```
a224. 四面體數
<法一> 數學解
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
cout<<((n+1)*(n+2)*n)/6;
}
```
a225. 選擇排序法之跟著影片做
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int num[105]={};
for(int i=0;i<n;i++){
cin>>num[i];
}
for(int i=0;i<k;i++){
for(int j=i+1;j<n;j++){
if(num[j]<num[i]){
swap(num[i],num[j]);
}
}
}
for(int i=0;i<n;i++){
cout<<num[i]<<' ';
}
}
```
a226. 升旗妙事
```cpp=
#include<iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int h[105]={};
for(int i=0;i<n;i++){
cin>>h[i];
}
sort(h,h+n);
int t=n;
if(n%2!=0){
t++;
}
for(int i=0;i<t/2;i++){
if(i==n-i-1){
cout<<h[i];
}
else{
cout<<h[i]<<" "<<h[n-i-1]<<" ";
}
}
}
```
a230. 氣泡排序法—反序數量
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int num[105]={};
for(int i=0;i<n;i++){
cin>>num[i];
}
int t=0;
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
if(num[j]<num[j+1]){
swap(num[j],num[j+1]);
t++;
}
}
}
cout<<t<<'\n';
for(int i=0;i<n;i++){
cout<<num[i]<<' ';
}
}
```
a249. 二分搜尋法-陣列中搜尋
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[10005];
for(int i=0;i<n;i++){
cin>>a[i];
}
int f;
cin>>f;
int time=1;
//↑ 輸入，↓ 處理
int l=0,r=n-1;
int found=0;
while(l<=r){
int now=(l+r+1)/2;
if(a[now]==f){
cout<<now+1<<endl<<time;
found=1;
break;
}
else{
time++;
if(a[now]<f){
l=now+1;
}
else{
r=now-1;
}
}
}
if(found==0){
cout<<"0"<<endl<<time-1;
}
}
```
```
0 1 2 3 4 5 6
陣列 [a b c d e f g]
現狀 l n r
太大 l n r
太小 l n r
```
a271. 煩人的多項式習題
:::success
``pow`` : 次方運算，格式pow(x，y)
:::
```cpp=
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int n,x;
cin>>n>>x;
int ans=0;
int num;
for(int i=n;i>=0;i--){
cin>>num;
ans+=num*(pow(x,i));
}
cout<<ans;
}
```
a272. 三分搜尋法-終極密碼
```cpp=
#include<iostream>
using namespace std;
int main(){
int l,r,ans;
cin>>l>>r>>ans;
int t=0;
int finish=0;
while (finish==0){
int d=(r-l)/3;
int mid1=l+d,mid2=r-d;
cout<<mid1<<" "<<mid2<<'\n';
if(mid1==ans || mid2==ans){
finish=1;
t++;
}
else if (mid1>ans && mid2>ans){
r=mid1-1;
t++;
}
else if(mid1<ans && mid2<ans){
l=mid2+1;
t++;
}
else if(mid1<ans && mid2>ans){
l=mid1+1;
r=mid2-1;
t++;
}
}
cout<<t;
}
```
# 競賽題庫
a050. pA 懼高症 -- CPTC2020
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int main(){
int n,m,q;
cin>>n>>m>>q;
n=n*m;
long long int A[MAXN]={};
for(int i=0;i<n;i++){
cin>>A[i];
}
sort (A,A+n+1);
for(int i=0;i<q;i++){
long long int h;
cin>>h;
int l=0,r=n;
while(l<r){//跑到剩一個候選為止
int mid=(l+r+1)/2;
if(A[mid]>h){
r=mid-1;
}
else{
l=mid;
}
}
cout<<l<<endl;
}
}
```
a099. 供五停二 -- 110年景美女中學科能力競賽
```cpp=
#include <bits/stdc++.h> //萬用函式庫
using namespace std;
int main() {
ios::sync_with_stdio(0);//讓程式跑更快(以下2行)
cin.tie(0);
int n,m,d;
string a[10];
int month[20]={0,0,31,59,90,120,151,181,212,243,273,304,334};
cin >> n;
for (int i=0; i<n; i++){
cin>>m>>d;
if ((month[m]+d)%7+4==9||(month[m]+d)%7+4==10){
a[i]="A";
}
else if((month[m]+d)%7+4==4||(month[m]+d)%7+4==5) {
a[i]="B";
}
else{
a[i]="No";
}
}
for (int j=0;j<n;j++){
cout <<a[j]<<endl;
}
return 0;
}
```
s003. 3. 飲料點餐
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int use(int n,int c[],int m,int k){
if(n==0){
return 1;
}
else{
int ans=0;
for(int i=0;i<k;i++) {
if(m>=c[i]){
ans+=use(n-1,c,m-c[i],k);
}
}
return ans;
}
}
int main(){
int n,k,m;
cin>>n>>k>>m;
int c[10];
for(int i=0;i<n;i++){
cin>>c[i];
}
sort(c,c+k);
cout<<use(n,c,m,k)<<endl;
}
//遞迴
```
s006. 1. 蝦寶的命名 - 112景美女中資訊學科能力競賽
```cpp=
#include <iostream>
using namespace std;
int main() {
int k,j;
cin>>k>>j;
int n;
cin>>n;
for (int i=0;i<n;i++){
int b,c;
cin>>b>>c;
if((b+c)%k==0 && b%j!=0 && c%j!=0){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
}
```
# Toi 練習賽
a148. 捕魚 (Fishing)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int X,Y,N,A,B,min=1000000,mina,minb;
cin>>X>>Y>>N;
for(int i=0;i<N;i++){
cin>>A>>B;
if((A-X)*(A-X)+(B-Y)*(B-Y)<min){
min=(A-X)*(A-X)+(B-Y)*(B-Y);
mina=A;
minb=B;
}
}
cout<<mina<<" "<<minb;
}
```
a149. 計程車(Taxi) -- TOI練習賽202203新手組3.
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int K,W,S,E;//公里數、車輛延滯時間(以分鐘為單位)、乘客上車以及下車的時間點(以小時為單位)。
int money=0;
cin >>K>>W>>S>>E;
int sum=0;
if(K>=2){
sum =sum+20+(K-2)*5;
}
else{
sum =sum+20;
}
sum=sum+W*60/120*5;
while(E>=19 && E<=23 && E>S){
sum+=(E+E-1)/(2*1.0)*10;
E=E-1;
}
cout<<(sum);
return 0;
}
```
a150: 躲避球 (Dodgeball)--『toi練習賽』
```cpp=
#include<iostream>
using namespace std;
int main(){
int X,R,V,N,P,S;
cin >> X >> R >>V>>N;
for(int i = 1; i<=N; i++){
cin>> P >> S;
if(X==P){
X=X-15;
}
else if((X+R)>=P&&(X-R)<=P&&V>=S){
X=P;
}
else if((X+R)>=P&&(X-R)<=P&&V<S){
if(X<P){
X=X-15;
}
else{
X=X+15;
}
}
}
cout<<X;
}
```
a152: 岩石觀察 （Stones）–『toi練習賽』
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n, stone[100],stone_origin[100],total=0,average=0,min=0,max=0,temp=0;
cin >> n;
for(int i=0;i<n;i++){
cin >> stone[i];
total=total+stone[i];
stone_origin[i] = stone[i];
}
average = float(total/n);
sort(stone,stone+n);
min = stone[0];
max = stone[n-1];
temp = max - average;
for(int j=0; j<n; j++){
if (stone_origin[j] == min){
cout << stone_origin[j] + temp;
}
else if (stone_origin[j] == max){
cout << stone_origin[j] - temp;
}
else{
cout << stone_origin[j];
}
if (j != n-1){
cout << " ";
}
}
return 0;
}
```
a194. 戰備存糧 (Food) -- TOI練習賽202210新手組
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,e;
while(1==1){
int day=0;
cin>>n>>e;
int total=n*e,s=n,now=total;
if(n==0&&e==0){
break;
}
else{
while(now>0){
if(s>0){
now=now-s;
s=n-(total-now)/e;
}
day++;
}
cout<<day<<endl;
}
}
}
//a194
```
a211. 開心農場 (Farm)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N,X,Y,R,L,W=0,q=0;
int totalx=0,totaly=0,x[105],y[105];
cin>>N;
for(int i=0;i<N;i++){
cin>>x[i];
}
for(int i=0;i<N;i++){
cin>>y[i];
}
cin>>R>>L;
for (int i=0;i<N;i++){
totalx=totalx+x[i];
totaly=totaly+y[i];
if (totalx>=R && totaly>=L){
cout<<i+2;
q=q+1;
break;
}
}
if(q==0){
cout<<"-1";
}
}
```
拍七(Seven)-2023 3月 TOI
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int S,E,B,K,t=0;
cin>>S>>E>>B>>K;
for(int i=S;i<=E;i++){
if(i%B==0){ //倍數
t=t+1;
}
else if(i%10==B){ //前面有B
t=t+1;
}
else if((i/10)%10==B){
t=t+1;
}
else if((i/100)%10==B){
t=t+1;
}
if(t==K){
cout<<i;
break;
}
}
if(t<K){
cout<<"-1";
}
}
```
鑿井取水 (water)-2023 3月 TOI
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N,W,wat=0,use=0,M,X,a;
cin>>N>>W;
for(int i=1;i<=N;i++){
cin>>M;
wat=wat+W;
for(int j=0;j<M;j++){
cin>>X;
use=use+X;
}
wat=wat-use;
if(wat<0){
a=i;
cout<<a;
break;
}
use=0;
}
if(wat>=0){
cout<<"-1";
}
}
```
庫存清理 (Stock)-2023 3月 TOI
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T,S,P,t=0,a;
cin>>T>>S>>P;
a=T;
for(int i=1;i<=S;i++){
if(T>=(a*0.8)){
t=t+(P*0.5);
}
else if(T>=(a*0.6)){
t=t+(P*0.6);
}
else if(T>=(a*0.4)){
t=t+(P*0.8);
}
else if(T>=(a*0.2)){
t=t+(P*0.9);
}
T=T-1;
}
cout<<t;
}
```
成績分析 (Analysis)-2023 4月 TOI
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int N,M;
cin>>N>>M;
int S[1005][1005]={};
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin>>S[i][j];
}
}
int good_s=0,bad_s=0,progress=0,regress=0,max_p=0,max_r=0;
for(int i=0;i<N;i++){
for(int j=0;j<M-1;j++){
if(S[i][j]-S[i][j+1]<0){
progress=progress+S[i][j+1]-S[i][j];
if(progress>max_p){
good_s=i+1;
max_p=progress;
}
}
else{
regress=regress+S[i][j]-S[i][j+1];
if(regress>max_r){
bad_s=i+1;
max_r=regress;
}
}
}
progress=0;
regress=0;
}
cout<<good_s<<endl<<bad_s;
}
```
分班 (Class)2023-4月 TOI
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin>>N;
int C[1005]={};
int M[1005]={};
int cC[1005],cM[1005],c=0,m=0;
for(int i=0;i<N;i++){
cin>>C[i];
}
for(int i=0;i<N;i++){
cin>>M[i];
}
int a=0,b=0;
for(int j=0;j<N;j++){
if(C[j]-M[j]>0){
cC[a]=j+1;
c=c+1;
a=a+1;
}
else{
cM[b]=j+1;
m=m+1;
b=b+1;
}
}
if(c==0){
cout<<-1<<endl;
}
else{
for(int i=0;i<a;i++){
cout<<cC[i]<<" ";
}
cout<<endl;
}
if(m==0){
cout<<-1<<endl;
}
else{
for(int i=0;i<b;i++){
cout<<cM[i]<<" ";
}
}
}
```
煲仔飯 (Clay Pot Rice)2023-10月 TOI
```cpp=
#include <iostream>
using namespace std;
int main() {
int T,G,W,E,B;
cin>>T>>G>>W>>E>>B;
int time=G+W+E+B;
if(time<=T){
cout<<time;
}
else{
cout<<"-1";
}
}
```
烤肉 (BBQ)2023-10月 TOI
```cpp=
#include <iostream>
using namespace std;
int main() {
int N,M,X,Y;
cin>>N>>M>>X>>Y;
int yes=0;
for (int i=0;i<=M;i++){
int B=i;
int P=M-i;
if(X*P+Y*B==N){
cout<<P<<" "<<B;
yes=1;
}
}
if(yes==0){
cout<<"-1"<<" "<<"-1";
}
}
```
超市排隊 (Supermarket)2023-10月 TOI
```cpp=
#include <iostream>
using namespace std;
int main() {
int A,B,C;
cin>>A>>B>>C;
int ta=2*(A-1);
int tb=2*(B-1);
int tc=2*(C-1);
int K;
for (int i=0;i<A;i++){
cin>>K;
ta=ta+3*K;
K=0;
}
for (int i=0;i<B;i++){
cin>>K;
tb=tb+3*K;
K=0;
}
for (int i=0;i<C;i++){
cin>>K;
tc=tc+3*K;
K=0;
}
if(ta<tb && ta<tc){
cout<<"1"<<" "<<ta;
}
else if(tb<ta && tb<tc){
cout<<"2"<<" "<<tb;
}
else{
cout<<"3"<<" "<<tc;
}
}
```
a263. 狼人殺 (Werewolves) -- TOI練習賽202311新手組第1題
```cpp=
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[20]={};
int p=0;//平民
int g=0;//神職
int w=0;//狼人
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==0){
p++;
}
else if(a[i]==1){
g++;
}
else{
w++;
}
}
int finish=0;
int out=-1;
while(out!=0){
cin>>out;
if(out==0){
break;
}
if(a[out]==2){
cout<<"Wrong";
finish=1;
break;
}
else{
if(a[out]==0){
p--;
}
else if(a[out]==1){
g--;
}
else{
w--;
}
a[out]=2;
}
}
if(finish==0){
if(w>0){
cout<<"Werewolves";
}
else{
cout<<"Townsfolk";
}
}
}
```
a264. 書房 (Study) -- TOI練習賽202311新手組第2題
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a[1005]={};
int b;
for(int i=1;i<=n;i++){
cin>>b;
a[b]=i;
}
for(int i=1;i<=m;i++){
cout<<a[i]<<" ";
}
}
```
a265. 精靈王國 (Kingdom) -- TOI練習賽202311新手組第3題
```cpp=
#include<iostream>
using namespace std;
int main(){
int k;
cin>>k;
int door[100005]={};
int num[100005]={};
int mk=-1;
for(int i=1;i<=k;i++){
cin>>door[i];
num[i]=i;
}
int next;
for(int i=1;i<=k;i++){
next=door[i];
int stop=0;
int king=1;
while(stop!=1){
//cout<<"i= "<<i<<"/ next: "<<next<<"/ door[next]: "<<door[next]<<"/ king: "<<king<<"\n";
if(next==i){
stop=1;
}
else{
king++;
next=door[next];
}
}
if(king>mk){
mk=king;
}
if(mk>k/2){
break;
}
}
cout<<mk;
}
```
a273. 搶21 (The 21 Game) -- TOI練習賽202403新手組1第1題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int t,r;
cin>>t>>r;
if(t%(r+1)>0){
cout<<"1";
}else{
cout<<"0";
}
}
```
a274. 數字旅館 (hotel) -- TOI練習賽202403新手組第2題
```cpp=
#include<iostream>
#include <math.h>
using namespace std;
int main(){
int n,k;
cin>>n;
for(int i=0;i<n;i++){
cin>>k;
if(k%3==0 && k%2==0){
cout<<"1 ";
}
else if(k%2!=0 && k%3!=0){
cout<<"2 ";
}
else if(pow(int(sqrt(k)), 2)==k || (k%2==0 && k%7!=0)){
cout<<"3 ";
}
else{
cout<<"0 ";
}
}
}
```
a304. 起司 (Cheese) -- TOI練習賽202409新手組第1題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int l, w, h, k;
cin >> l >> w >> h >> k;
if(l % k != 0 || w % k != 0 || h % k != 0){
cout << "0";
}
else{
cout << (l / k) * (w / k) * (h / k);
}
}
```
a305. 電動滑板車 (e-Scooter) -- TOI練習賽202409新手組第2題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
int nothing = t * 3;
int normal = 299, vip = 699;
if (nothing < normal){
cout << nothing;
}
else if(t <= 300){
cout << normal;
}
else if (t > 300 && t <= 750){
int normal_out = normal + (t - 300) * 3 ;
if(normal_out < vip){
cout << normal_out;
}
else{
cout << vip;
}
}
else{
int vip_out = vip + (t - 750) * 3;
cout << vip_out;
}
}
```
a306. 因數計算 (Factor) -- TOI練習賽202409新手組第3題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int count(int n){
int a=1;
int num = 0;
while(n >= a){
if(n % a == 0){
num++;
}
a=a+1;
}
return num;
}
int main(){
int x, y, max_num, max_count = 0;
cin >> x >> y;
for(int i = x; i <= y; i++){
if(count(i) > max_count){
max_num = i;
max_count = count(i);
}
}
cout << max_num << " " << max_count;
}
```
a309. 生日快樂 (Birthday) -- TOI練習賽202409新手組第1題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int m1, m2, m3, m4;
cin >> m1 >> m2 >> m3 >> m4;
int month[20]={0,0,31,59,90,120,151,181,212,243,273,304,334};
int now = month[m1] + m2;
int birthday = month[m3] + m4;
int next = birthday - now;
if(next < 0){
next += 365;
}
cout << next;
}
```
a315. 凱撒密碼 (Cipher)-- TOI練習賽202412新手組第3題
```cpp=
#include<iostream>
using namespace std;
int main(){
string s;
int n;
getline(cin,s);
cin>>n;
for(int i=0; i<s.size(); i++){
if(int(s[i])>=65 && int(s[i])<=90){
s[i]=65+(s[i]-65+n)%26;
}
else if(int(s[i])>=97 && int(s[i])<=122){
s[i]=97+(s[i]-97+n)%26;
}
cout << s[i];
}
}
```
# APCS考古題
c002. 201603_q2 矩陣轉換
```cpp=
#include <iostream>
using namespace std;
int main(){
int R,C,M;
cin>>R>>C>>M;
int B[1005][1005]={};
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
cin>>B[i][j];
}
}
int B2[1005][1005]={};
int Mm[1005]={};
for(int i=0;i<M;i++){
cin>>Mm[i];
}
for(int k=M-1;k>=0;k--){
//0 則代表旋轉，1 代表翻轉
if(Mm[k]==0){
int R2=R;
R=C;
C=R2;
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
B2[i][j]=B[j][R-i-1];
}
}
}
else{
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
B2[i][j]=B[R-i-1][j];
}
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
B[i][j]=B2[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<<B[i][j]<<endl;
}
else{
cout<<B[i][j]<<" ";
}
}
}
}
```
c005. 201610_q1 三角形辨別
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n[3]={};
int a,b,c;
for(int i=0;i<3;i++){
cin>>n[i];
}
sort(n,n+3);
a=n[0];
b=n[1];
c=n[2];
cout<<a<<" "<<b<<" "<<c<<'\n';
if(a+b<=c){
cout<<"No";
}
else if((a*a)+(b*b)<(c*c)){
cout<<"Obtuse";
}
else if((a*a)+(b*b)==(c*c)){
cout<<"Right";
}
else {
cout<<"Acute";
}
}
```
c006. 201610_q2 最大和
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int num[25][25];
int s=0;
int a[25]={};//存每群最大
for(int i=0;i<n;i++){
int mn=0;
for(int j=0;j<m;j++){
cin>>num[i][j];
if(num[i][j]>mn){
mn=num[i][j];
}
}
a[i]=mn;
}
for (int i=0;i<n;i++){
s=s+a[i];
}
cout<<s<<'\n';
int yes=0;
for(int i=0;i<n;i++){
if(s%a[i]==0){
cout<<a[i]<<" ";
yes=1;
}
}
if(yes==0){
cout<<"-1";
}
}
```
c009. 201703_q2 小群體
:::spoiler 思路
> [name=yiwen1825]因為 people 的索引(index) 代表自己,值(item)代表好友
所以 people 讀進去後這段沒問題
==然後 v 的話，都全部給 0==
拿範例二來說
3
0 2 1
people 讀 3 個值 0, 2, 1
然後 v 也開 3 個位子都是 0
==v 表示people[i]現在屬於哪個群體==
for i = 0 ; i = n ; i++ 看是從 people 的第一個位子開始找
這個時候 people[0] 的值會是 0 對吧
當 people[0] 走過一次後, 因為 v[0] 等於 0 表示 people[0] 還沒被加入群體
所以 v[0] = 1
根據說明, people[0] 裏面的值表示下一個好友的位置
people[0] 裏面的值 = 0 所以他已經形成一個圈圈
就算他只是一個點而已
這部分有少一個動作歐 先保留
然後發現 people[0] 沒有下一個對象了 所以換 people[1]
現在 people[1] = 2
然後 v[1] = 0
==然後 v[1] = 0 表示 people[1] 還沒被加入群體==
所以 v[1] = 2
因為群體中已經有 0 這個群體(編號1), 所以編號從2開始
現在有一個變數 nxt 要存 people[1] 的值
因為他要順著好友一路找下去, 最後找到指回自己的群體形成一個圈圈
所以 nxt = people[1]
nxt 會等於 2
把 nxt 的值放進去 people[nxt]
people[nxt] = people[2] = 1
這時檢查 v[2]，因為 v[2] = 0， 他又在 people[1] 所在的群體， 所以 v[2] = 2
那現在所有 v 都有非 0 的編號
v[0] = 1, v[1] = 2, v[2] = 2
就跳出迴圈 輸出 2
思路是這樣
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n=0,group=0,nxt=0,people[50000];
char v[50000] = {0};
cin >> n;
for(int i = 0; i < n; i++)
cin >> people[i];
for(int i = 0; i < n; i++){
if(v[i] == 0){
nxt = i;
do{
v[nxt] = group + 1;
nxt = people[nxt];
}
while(v[nxt]==0);
group++;
}
}
cout << group;
return 0;
}
```
c011. 201703_q4 基地台
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int main(){
int n,k;
cin>>n>>k; //n個服務點 k個基地台
int P[MAXN]={};
for(int i=0;i<n;i++){
cin>>P[i];
}
sort(P,P+n);
//二分搜:左右邊界、找的東西去對條件
int l=1,r=P[n-1]-P[0];
while(l<r){
int d=(l+r)/2;
int beg=P[0],cnt=1;
for(int i=1;i<n;i++){
if(beg+d<P[i]){
cnt++;
beg=P[i];
}
}
if(cnt<=k){
r=d;
}
else{
l=d+1;
}
}
cout<<l;
}
```
c012: 201703_q1 秘密差
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int even = 0, odd = 0;
string s;
cin >> s;
for (int i=0; i<s.size(); i++){
if (i % 2){
odd += s[i] - '0';
} else {
even += s[i] - '0';
}
}
cout << abs(even - odd) << endl;
return 0;
}
```
c014. 201710_q3 樹狀圖分析 (Tree Analyses)
```cpp=
#include<iostream>
#include<vector>
using namespace std;
const int MAXN=1e5+5;
vector<int> child[MAXN]={};
int dp[MAXN]={0};
int find_high(int root){
//不用設if終止是因為是0的話for迴圈不會跑所以沒有無窮遞迴
//然後也確保dp只會跑一次(因為從根往下)
int maxh=-1;//自己最大高度
for(int i=0;i<child[root].size();i++){
int h=find_high(child[root][i]);
if(h>maxh){
maxh=h;
}
}
return dp[root]=maxh+1;
}
int main(){
int n;
cin>>n;
int parent[MAXN]={};
for(int i=1;i<=n;i++){
int kid_num;
cin>>kid_num;
for(int j=0;j<kid_num;j++){
int k;
cin>>k;
child[i].push_back(k);
parent[k]=i;
}
}
int root=n/2;
while(parent[root]!=0){
root=parent[root];
}
find_high(root);
long long int sumh=0;
for(int i=1;i<=n;i++){
sumh+=dp[i];
}
cout<<root<<endl<<sumh;
}
```
```cpp=
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
queue<int> que;
int main(){
int n;
cin>>n;
int kid_num[MAXN]={};
int parent[MAXN]={};
for(int i=1;i<=n;i++){
cin>>kid_num[i];
if(kid_num[i]==0){
que.push(i);
}
for(int j=0;j<kid_num[i];j++){
int k;
cin>>k;
parent[k]=i;
}
}
int root=n/2;
while(parent[root]!=0){
root=parent[root];
}
int h[MAXN]={};
while(!que.empty()){
int v=que.front();
que.pop();
if(v==root){
break;
}
//用v更新parent[v]
int p=parent[v];
if(h[v]+1>h[p]){
h[p]=h[v]+1;
}
//檢查parent[v]能不能丟進queue
kid_num[p]--;
if(kid_num[p]==0){
que.push(p);
}
}
long long int sumh=0;
for(int i=1;i<=n;i++){
sumh+=h[i];
}
cout<<root<<endl<<sumh;
}
//c014
```
c016. 201710_q1 邏輯運算子 (Logic Operators)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b,ans;
cin>>a>>b>>ans;
if(a==0 && b==0){
if(ans==0){
cout<<"AND"<<endl<<"OR"<<endl<<"XOR";
}
else{
cout<<"IMPOSSIBLE";
}
}
else if(a!=0&&b!=0){
if(ans==1){
cout<<"AND"<<endl<<"OR"<<endl;
}
else if(ans==0){
cout<<"XOR";
}
else{
cout<<"IMPOSSIBLE";
}
}
else if(a!=0&&b==0){
if(ans==1){
cout<<"OR"<<endl<<"XOR"<<endl;
}
else if(ans==0){
cout<<"AND";
}
else{
cout<<"IMPOSSIBLE";
}
}
else if(a==0&&b!=0){
if(ans==1){
cout<<"OR"<<endl<<"XOR"<<endl;
}
else if(ans==0){
cout<<"AND";
}
else{
cout<<"IMPOSSIBLE";
}
}
}
```
c023. 202007_3. 圓環出口
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+5,MAXM=2e5+5;
int main(){
int n,m;
cin>>n>>m;
int P[MAXN]={};
int Q[MAXM]={};
int total=0;
for(int i=0;i<n;i++){
cin>>P[i];
total+=P[i];
}
for(int j=0;j<m;j++){
cin>>Q[j];
}
int pre_sum[MAXN]={0};
for(int i=1;i<=n;i++){
pre_sum[i]=pre_sum[i-1]+P[i-1];
}
int now =0;
for(int j=0;j<m;j++){
int key=(pre_sum[now]+Q[j])%total;
int le=0,ri=n;
while(le<ri){
int mid=(le+ri)/2;
if(pre_sum[mid]>=key){
ri=mid;
}
else{
le=mid+1;
}
}
now=le%n;
}
cout<<now<<endl;
}
```
c037. 202109_3. 幸運數字
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=3e5+5;
struct Data {
int val,index;
};
bool cmp(Data a,Data b){
return a.val<b.val; //回傳按照val由小到大
}
int main(){
int n;
cin>>n;
long long int p[MAXN]={},pre[MAXN]={};
for (int i=0;i<n;i++){
cin>>p[i];
pre[i+1]=pre[i]+p[i];
}
Data d[MAXN]={};
for(int i=0;i<n;i++){
d[i].val=p[i];
d[i].index=i;
}
sort(d,d+n,cmp);
int l=0,r=n-1;
int pos=0;
while(l<r){
int m=0;
while(d[pos].index<l || d[pos].index>r){
pos++;
}
m=d[pos].index;
//前綴和
long long int sum_l = pre[m]-pre[l];
long long int sum_r = pre[r+1]-pre[m+1];
if(sum_l>sum_r){
r=m-1;
}
else{
l=m+1;
}
}
cout<<p[l]<<endl;
}
```
c059. 1. 程式考試
```cpp=
#include <iostream>
using namespace std;
int main(){
int K;
cin >> K;
int hs=-2;
int natime=0;
int ht=0;
for (int i=0;i<K;i++){
int ti,si; //ti: 時間點，si: 分數
cin >> ti >> si;
if(si==-1){
natime++;
}
else if(si>hs){
hs=si;
ht=ti;
}
}
int totals=hs-K-natime*2; //提交紀錄中的最高分 - 總提交次數 - 總嚴重錯誤次數 * 2
if(totals<0){
totals=0;
cout << totals << " " <<ht;
}
else{
cout << totals << " " <<ht;
}
}
```
c060. 2. 造字程式
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main() {
int k,q,r;
cin>>k>>q>>r;
int a[25][25]={};
string str;
cin>>str;
char s[25]={};
for(int i=0;i<k;i++){
s[i]=str[i];
}//字串割成字元
for(int i=0;i<q;i++){
for(int j=0;j<k;j++){
cin>>a[i][j];
}
}
char ans[25][25]={};
char ns[25]={};//存新字串
for(int i=0;i<q;i++){
for(int j=0;j<k;j++){
int x=a[i][j];//索引
ns[x-1]=s[j];
}//這時候第i+1次完整的新字串搞定
for(int I=0;I<k;I++){
ans[i][I]=ns[I];//存到答案裡
s[I]=ns[I];//新字串變舊的，準備下一輪
}
}
for(int i=0;i<r;i++){
for(int j=0;j<q;j++){
cout<<ans[j][i];
}
cout<<endl;
}
}
```
c064. 2. 特殊位置
```cpp=
#include <iostream>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int a=0; //howmuch
int w[2505];//where
int c[55][55];
for (int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>c[i][j];
}
}
int k=0;//w[k]
for (int i=0;i<n;i++){
for(int j=0;j<m;j++){
int x=c[i][j];
int t=0;
for (int p=0;p<n;p++){
for (int q=0;q<m;q++){
int d=abs(i-p)+abs(j-q);//曼哈頓距離
if(d<=x){
t=t+c[p][q];
}
}
}
if (t%10==x){
w[k]=i;
w[k+1]=j;
k=k+2;
a++;
}
}
}
cout<<a<<endl;
for (int i=0;i<k;i=i+2){
cout<<w[i]<<" "<<w[i+1]<<endl;
}
}
```
c067. 1. 機械鼠
```cpp=
#include <iostream>
using namespace std;
int main() {
int x,n;
cin>>x>>n;
int right=0;
int xright=-101;
int left=0;
int xleft=101;
int a;
for (int i=0;i<n;i++){
cin>>a;
if(a>x){
right++;
if(a>xright){
xright=a;
}
}
else if(a<x){
left++;
if(a<xleft){
xleft=a;
}
}
}
if(right>left){
cout<<right<<" "<<xright;
}
else{
cout<<left<<" "<<xleft;
}
}
//c067
```
c068. 2. 卡牌遊戲
```cpp=
#include <iostream>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int a=0; //ans
int c[45][45];
for (int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>c[i][j];
}
}
int OK=0;
while (OK==0){
int C=0;//連續次數
for (int i=0;i<n;i++){ //橫
for(int j=0;j<m;j++){
int b=1;
int k=1;
while (b==1){
if (c[i][j+k]==-1 ) {
k++;
}
else if (j-k>0 && c[i][j-k]==-1) {
k++;
}
else if(c[i][j]==c[i][j+k] && c[i][j]>=0 && c[i][j+k]>=0){
a=a+c[i][j];
c[i][j]=-1;
c[i][j+k]=-1;
b=0;
C++;
}
else if(c[i][j]==c[i][j-k] && c[i][j]>=0 && c[i][j-k]>=0){
a=a+c[i][j];
c[i][j]=-1;
c[i][j-k]=-1;
b=0;
C++;
}
else{
b=0;
}
}
}
}
for (int i=0;i<n;i++){ //直
for(int j=0;j<m;j++){
int b=1;
int k=1;
while (b==1){
if (c[i+k][j]==-1){
k++;
}
else if (i-k>0 && c[i-k][j]==-1) {
k++;
}
else if(c[i][j]==c[i+k][j] && c[i][j]>=0 && c[i+k][j]>=0){
a=a+c[i][j];
c[i][j]=-1;
c[i+k][j]=-1;
b=0;
C++;
}
else if(c[i][j]==c[i-k][j] && c[i][j]>=0 && c[i-k][j]>=0){
a=a+c[i][j];
c[i][j]=-1;
c[i-k][j]=-1;
b=0;
C++;
}
else{
b=0;
}
}
}
}
if (C==0){
OK=1;
}
}
cout<<a;
}
```
c071. 1. 遊戲選角
```cpp=
#include<iostream>
using namespace std;
const int MAXN=25;
int main(){
int n;
cin>>n;
int max=-1,two=-2;
int index_max=n+2;
int index_two=n+1;
int a[MAXN]={},d[MAXN]={};
for(int i=1;i<=n;i++){
cin>>a[i]>>d[i];
int p=a[i]*a[i]+d[i]*d[i];
if(p>max){
two=max;
index_two=index_max;
max=p;
index_max=i;
}
else if(p>two){
two=p;
index_two=i;
}
}
cout<<a[index_two]<<" "<<d[index_two];
}
```
c074. 4. 合併成本
```cpp=
#include<iostream>
using namespace std;
const int MAXN=205;
const int oo=1e9+9;
int pre_sum[MAXN]={};
int sum(int p[],int l,int r){
return p[r+1]-p[l];
}
int dp[MAXN][MAXN]={};
int cut(int p[],int l,int r){
if(r==l){
return 0;
}
if(dp[l][r]!=0){
return dp[l][r];
}
int mincut=oo;
for(int i=l;i<r;i++){
int c=cut(p,l,i)+cut(p,i+1,r)+
abs(sum(p,l,i)-sum(p,i+1,r));
if(c<mincut){
mincut=c;
}
}
return dp[l][r]=mincut;
}
int main(){
int n;
cin>>n;
int a[MAXN]={};
for(int i=0;i<n;i++){//前面留一格才不會出錯
cin>>a[i];
}
for(int i=0;i<n;i++){ //前綴和，這樣sum那邊就不用跑迴圈
pre_sum[i+1]=pre_sum[i]+a[i];
}
cout<<cut(pre_sum,0,n-1)<<endl;
}
```
c083. 1. 等紅綠燈 -- 2025年1月APCS
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
int one = a + b;
int n;
cin >> n;
int t = 0;
for(int i = 0; i < n; i++){
int child, wait;
cin >> child;
int cycle = child % one;
if(cycle >= a){
wait = b - (cycle - a);
t += wait;
}
}
cout << t;
}
```
# APCS325
d012. P_2_1 不同的數
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int a[100000]={};
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int t=1;
int ans[100000]={a[0]};
for(int i=1;i<n;i++){
if(a[i]!=a[i-1]){
ans[t]=a[i];
t++;
}
}
cout<<t<<'\n';
for(int i=0;i<t;i++){
cout<<ans[i]<<" ";
}
}
```
d017. Q_2_7 互補團隊 (APCS201906)
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+5,MAXM=2e5+5;
string make_h(string s,int m){
bool has[26]={};
for(int j=0;j<s.size();j++){
has[s[j]-'A']=true;
}
string ans="";
for(int j=0;j<m;j++){
if(!has[j]){
ans+=j+'A';
}
}
return ans;
}
int main(){
int m,n;
cin>>m>>n;
string A[MAXN]={};
for(int i=0;i<n;i++){
string s;
cin>>s;
bool has[26]={};
for(int j=0;j<s.size();j++){
has[s[j]-'A']=true;
}
for(int j=0;j<m;j++){
if(has[j]){
A[i]+=j+'A';
}
}
}
sort(A,A+n);
int cnt=0;
for(int i=0;i<n;i++){
string key=make_h(A[i],m);
int le=i+1,ri=n-1;//le:每一格都往後找
bool found=false;
while(le<=ri){
int mid=(le+ri)/2;
if(A[mid]==key){
found=true;
break;
}
else if(A[mid]>key){
ri=mid-1;
}
else{
le=mid+1;
}
}
if(found){
cnt++;
}
}
cout<<cnt<<endl;
}
```
d019. P_2_6 Two-Number problem
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
int a[100000]={};
int b[100000]={};
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
sort(a,a+n);
sort(b,b+m);
int t=0;
int i=0,j=m-1;
while(i<n && j>=0){
if(a[i]+b[j]>k){
j--;
}
else if (a[i]+b[j]<k){
i++;
}
else{
t++;
i++;
j--;
}
}
cout<<t<<'\n';
}
```
d043. P_4_1 少林寺的代幣 -- Dr.Wu
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m,money,c50,c10,c5,c1;
int total[100]={};
cin >> m;
for (int i=0;i<m;i++){
cin>>money;
c50 = money/50;
money = money%50;
c10 = money/10;
money = money%10;
c5 = money/5;
money = money%5;
c1 = money;
total[i]=c50 + c10 + c5 + c1;
}
for (int j=0;j<m;j++){
cout<<total[j]<<endl;
}
}
```
d044. P_4_2 笑傲江湖之三戰 -- Dr.Wu
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long int n,win=0,bi,ai;
long long int t=0;
cin >> n;
long long int they[100005]={};
long long int our[100005]={};
for (int i=0;i<n;i++){
cin>>they[i];
}
for (int i=0;i<n;i++){
cin>>our[i];
}
sort(they,they+n);
sort(our,our+n);
ai=n-1;
bi=n-1;
while(bi>=0){
if(our[ai]>they[bi]){
win=win+1;
ai=ai-1;
bi=bi-1;
}
else{
bi=bi-1;
}
}
cout<<win;
}
```
d045. P_4_3 十年磨一劍(最少完成時間) -- Dr.Wu
```cpp=
//法一:用乘法
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long int n;
long long int t=0;
cin >> n;
long long int time[1000001]={};
for (int i=0;i<n;i++){
cin>>time[i];
t=t+time[i];
}
sort(time,time+n);
for (int j=1;j<n;j++){
t=t+time[j-1]*(n-j);
}
cout<<t;
}
```
```cpp=
//法二:用加法
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long int n;
long long int t=0;
cin >> n;
long long int time[1000001]={};
for (int i=0;i<n;i++){
cin>>time[i];
}
sort(time,time+n);
t=t+time[0];
for (int j=0;j<(n-1);j++){
t=t+time[j]+time[j+1];
time[j+1]+=time[j];
}
cout<<t;
}
```
d056. P_4_14 控制點(2D-max)
```cpp=
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
struct Point{
int x,y;
};
bool cmp(Point a,Point b){
if(a.x ==b.x){
return a.y<b.y;
}
return a.x<b.x; //從小排到大
}
int main(){
int n;
cin>>n;
Point p[MAXN];
for (int i=0;i<n;i++){
cin>>p[i].x;
}
for (int i=0;i<n;i++){
cin>>p[i].y;
}
sort(p,p+n,cmp);
int ans=1;
int maxy=p[n-1].y;
for(int i=n-2;i>=0;i--){
if(p[i].y>maxy){
maxy=p[i].y;
ans++;
}
}
cout<<ans;
}
```
d078. P_6_9 大賣場免費大搬家
```cpp=
#include<iostream>
using namespace std;
const int MAXN=1e5+5;
int dp[105][MAXN]={0};
int use(int n,int g[],int m[],int w){
//買use(n-1,g,m,w-g[i])
//不買use(n-1,g,m,w)
if(n==-1){
return 0;
}
else{
if(dp[n][w]!=0){
return dp[n][w];
}
int buy=0,not_buy=0;
if(w<g[n]){
not_buy+=use(n-1,g,m,w);
}
else{
buy+=use(n-1,g,m,w-g[n])+m[n];
not_buy+=use(n-1,g,m,w);
}
if(buy>not_buy){
return dp[n][w]=buy;
}
else{
return dp[n][w]=not_buy;
}
}
}
int main(){
int n,w;
cin>>n>>w;
int g[105];
int m[105];
int p=0;
for(int i=0;i<n;i++){
cin>>g[i];
}
for(int i=0;i<n;i++){
cin>>m[i];
}
cout<<use(n-1,g,m,w)<<endl;
}
```
d086: P_6_17 切棍子
```cpp=
#include<iostream>
using namespace std;
const int MAXN=205;
const int oo=1e9+9;
int dp[MAXN][MAXN]={};
int cut(int a[],int l,int r){
if(r-l==1){
return 0;
}
if(dp[l][r]!=0){
return dp[l][r];
}
int mincut=oo;
for(int i=l+1;i<r;i++){
int c=cut(a,l,i)+cut(a,i,r);
if(c<mincut){
mincut=c;
}
}
return dp[l][r]=mincut+a[r]-a[l];
}
int main(){
int n,L;
cin>>n>>L;
int a[MAXN]={0};
for(int i=1;i<=n;i++){//前面留一格才不會出錯
cin>>a[i];
}
a[n+1]=L;
cout<<cut(a,0,n+1)<<endl;
}
//切棍子
```
d095. P_7_1 探索距離
```cpp=
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=105;
int main(){
int n,m;
cin>>n>>m;
int s;
cin>>s;
vector<int> ne[MAXN]={};//鄰居
for(int i=0;i<m;i++){
int u,v; //這個u跟v只會在這個迴圈裡
cin>>u>>v;
ne[u].push_back(v);
}
//queue:BFS(走一格的可能性試完再往下看) 廣度優先(先進先出)
//stack:DFS(一條路走到底再回去) 深度優先(後進先出)
//在這題用queue 因為會有最佳解
queue<int>que; //存下一個用的
que.push(s);
bool visited[MAXN]={false}; //紀錄點有沒有被走過(防無窮圈)
visited[s]=true;//標記起點
int dis[MAXN]={};
int cnt=0;
int total_d=0;
while(!que.empty()){
int t=que.front();//看最上面(不丟)
que.pop();//把最上面丟掉
total_d+=dis[t];
cnt++;
for(int v : ne[t]){ // =for v in ne
if(visited[v]) continue;
visited[v]=true;
dis[v]=dis[t]+1;
que.push(v);
}
}
cout<<cnt-1<<endl<<total_d;
}
```
d096. P_7_2 開車蒐集寶物
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5*1e4+5;
int st(int v,vector<int> ne[],bool visited[],int mo[],int now){
int money=mo[now];
for(int i : ne[now]){
if(visited[i]) continue;
visited[i]=true;
money+=st(i,ne,visited,mo,i);
}
return money;
}
int main(){
int n,m;
cin>>n>>m;
int mo[MAXN]={};
for(int i=0;i<n;i++){
cin>>mo[i];
}
vector<int> ne[MAXN]={};//鄰居
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
ne[a].push_back(b);
ne[b].push_back(a);
}
bool visited[MAXN]={false}; //紀錄點有沒有被走過(防無窮圈)
int ans=0;
for(int v=0;v<n;v++){
if(visited[v]) continue;
visited[v]=true;
ans=max(ans,st(v,ne,visited,mo,v));
}
cout<<ans;
}
```
d102. Q_7_8 小寶的著色問題
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
bool bfs(int n,vector<int> ne[],int visited[],int now){
queue<int> que;
que.push(now);
visited[now]=1;
while(!que.empty()){
int t=que.front();//看最上面(不丟)
que.pop();//把最上面丟掉
for(int i : ne[t]){
if(visited[i]==visited[t]){//衝突
return false;
}
else if (visited[i]==0){
visited[i]=-visited[t];//上不同顏色
que.push(i);//放進去
}
}
}
return true;
}
bool check(int n,vector<int> ne[]){
int visited[MAXN]={};//0:沒色
for(int i=0;i<n;i++){
if(visited[i]!=0) continue;
if(!bfs(n,ne,visited,i)) return false;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
for(int T=0;T<t;T++){
int n,m;
cin>>n>>m;
vector<int> ne[MAXN]={};//鄰居
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
ne[a].push_back(b); //雙向
ne[b].push_back(a);
}
if(check(n,ne)) cout<<"yes"<<"\n";
else cout<<"no"<<"\n";
}
}
```
d111. P_8_5 自動分裝 (APCS202002)
```cpp=
#include<iostream>
using namespace std;
const int MAXN=2e5+5,MAXM=105;
int l_c[MAXN]={};//leftchild
int r_c[MAXN]={};//rightchild
int w[MAXN]={};//weight
//void : 做完但沒回傳但陣列會儲存
//int : 做完且有回傳值
/*
void get_weight(int root){
if(root>=n){
return;
}
int lc=l_c[root],rc=l_r[root];
get_weight(lc);
get_weight(rc);
w[root]=w[lc]+w[rc];
return;
}
*/
//↓=↑
int get_weight(int root){
if(l_c[root]==0){
return w[root];
}
return w[root]=get_weight(l_c[root])+get_weight(r_c[root]);
}
int main(){
int n,m;
cin>>n>>m;
//1~n-1 -> 切換器
//n~2n-1 -> 貨櫃
for(int i=n;i<2*n;i++){
cin>>w[i];
}
int good[MAXM]={};
for(int i=0;i<m;i++){
cin>>good[i];
}
for(int i=0;i<n-1;i++){
int p,s,t;
cin>>p>>s>>t;
l_c[p]=s;
r_c[p]=t;
}
get_weight(1);
for(int i=0;i<m;i++){
int g=good[i],root=1;
while(l_c[root]>0){
int l=l_c[root],r=r_c[root];
if(w[l]<=w[r]){
w[l]+=g;
root=l;
}
else{
w[r]+=g;
root=r;
}
}
cout<<root<<" ";
}
}
```
Sign in with Wallet
Connect another wallet