第一部分:基礎複習
bmi計算
#include <iostream>
using namespace std;
int main()
{
float kg,cm,bmi,b_kg;
cout<<"cm"<<endl;
cin>>cm;
cout<<"kg"<<endl;
cin>>kg;
bmi = kg/((cm/100)*(cm/100));//計算bmi
b_kg = 21*((cm/100)*(cm/100));//理想體重
cout<<"bmi "<<bmi<<endl;
if(b_kg>kg) {cout<<"+"<<b_kg-kg<<"kg"<<endl;}
else if(b_kg<kg) {cout<<"-"<<kg-b_kg<<"kg"<<endl;}
else {cout<<"great"<<endl;}
return 0;
}7科加權平均
#include <iostream>
using namespace std;
int main()
{
int a[2][7],sum=0,i,val=0;
float avg;
cout<<"輸入7科成績"<<endl;
for(i=0;i<7;i++){
cin>>a[0][i];
}
cout<<"輸入7科權數"<<endl;
for(i=0;i<7;i++){
cin>>a[1][i];
val+=a[1][i];
}
for(i=0;i<7;i++){
sum+=a[0][i]*a[1][i];
}
avg=sum/val;
cout<<"sum:"<<sum<<endl;
cout<<"avg:"<<avg<<endl;
return 0;
}聖誕樹星星
#include <iostream>
using namespace std;
int main()
{
int n;//層數
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n-i;j++){
cout<<" ";
}
for(int j=0;j<2*(i+1)-1;j++){
cout<<"*";
}
cout<<endl;
}
return 0;
}執行結果
手動猜數字
#include <iostream>
using namespace std;
int main()
{
int ans,up=100,down=1,guess;
cout<<"input code"<<endl;
while(cin>>ans){
if(ans>0&&ans<=100) break;
else cout<<"out of range"<<endl;;
}
while(guess!=ans){//猜到的不等於答案
cout<<"guess a number between 1~100"<<endl;
cin>>guess;
if(guess>ans){
up=guess;
cout<<"range: "<<down<<"~"<<up<<endl;
}
if(guess<ans){
down=guess;
cout<<"range: "<<down<<"~"<<up<<endl;
}
}
cout<<"good"<<endl;
return 0;
}第二部分 基礎程式設計
大樂透抽獎
題目敘述：從1~49號球中抽出6顆不重複的球並印在畫面上
題目思路：要使用亂數函式產生數字，也要處理抽出來的數字重複的問題
第一種：檢查是否抽過
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
srand(time(NULL));
int a[6]={};
int temp,now_i;
for(int i=0;i<6;i++){
temp=rand()%42;//隨機抽數
now_i=i;
//檢查是否有重複
for(int j=0;j<i;j++){
if(temp==a[j]){
i--;
break;
}
}
if(now_i==i){
a[i]=temp;//如果沒有重複加入陣列
}
}
for(int i=0;i<6;i++){
cout<<a[i]<<endl;
}
return 0;
}第二種：標記已抽過號碼
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
srand(time(NULL));
int temp;
int a[42]={0};//沒抽過->0
for(int i=0;i<6;i++){
temp=rand()%42;
if(!a[temp])//如果抽到的球標記不為1
{
a[temp]=1;//抽過了標記1
cout<<temp+1<<endl;
}else
{
i--;//這次不算
}
}
return 0;
}第三種：動態陣列
#include <bits/stdc++.h>
using namespace std;
int main()
{
srand(time(NULL));
vector<int> v;
int temp;
for(int i=0;i<42;i++) v.push_back(i);
for(int i=0;i<6;i++){
temp=rand()%v.size();//隨機抽陣列的位置->隨機抽數
cout<<v[temp]<<endl;
v.erase(v.begin()+temp);//抽過就從陣列中移除
}
return 0;
}第四種：打亂陣列
和第五種類似，是第五種函式的實作版
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
srand(time(NULL));
int a[42],num=0;
for(int i=1;i<=42;i++) a[i]=i;
//從第0到陣列長度位置，每個都和陣列隨機的位置的數交換，可以產生亂數陣列
for(int i=0;i<42;i++){
num=rand()%42;
swap(a[i],a[num]);
}
for(int i=0;i<6;i++) cout<<a[i]<<endl;
return 0;
}第五種：random shuffle
第四題的引用內建函式版
隨機座位
安排班級的隨機座位，將座號結果按相對位置列印。
第一種：正常座位
#include <bits/stdc++.h>
using namespace std;
int main()
{
int r,c,mr=5,mc=5,k,lim=22;//lim:實際人數
cin>>r>>c>>lim;
int rc=r*c;//總座位數
int a[rc];//紀錄座號陣列
srand(time(NULL));
for(int i=0;i<rc;i++){
a[i]=i+1;
}
for(int i=0;i<rc-lim;i++){
a[rc-i-1]=0;
}
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cout<<a[i*r+j]<<" ";
}
cout<<endl;
}
for(int i=0;i<rc;i++) swap(a[i],a[rand()%rc]);
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cout<<a[i*r+j]<<" ";
}
cout<<endl;
}
return 0;
}執行結果
第二種：梅花座
#include <bits/stdc++.h>
using namespace std;
int main()
{
int r=5,c=5,k=0,lim=9;
cin>>r>>c>>lim;
int rc=r*c/2+r*c%2;//座位總數
int a[rc];
srand(time(NULL));
//產生亂數陣列程式
for(int i=0;i<rc;i++) a[i]=i+1;
for(int i=0;i<rc-lim;i++) a[rc-i-1]=0;//0表示無人座位
for(int i=0;i<rc;i++) swap(a[i],a[rand()%rc]);
//--------
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(i%2!=j%2) printf(" ");//行列奇偶不同->空座位
else{
printf("%4d",a[k]);/填入亂數陣列
k++;
}
}
cout<<endl;
}
return 0;
}執行結果
其實可以將以上兩個程式結合，用一個簡易的選單讓使用者決定要哪種排列方式，但因為時間不足，所以尚未製作，最終版的學習歷程會更新上去。
這個程式並沒有實作使用者亂輸入的限制，所以亂輸入的話程式執行可能會壞掉。
泡沫排序法
學習內容：排序法
#include <iostream>
using namespace std;
int main()
{
int a[9]={9,4,5,7,8,2,1,6,3};
int len=sizeof(a)/sizeof(int);
for(int i=0;i<len;i++){
for(int j=0;j<len-i;j++){
if(a[j+1]<a[j]) swap(a[j],a[j+1]);//如果後項大於前項->交換
}
}
for(int i=0;i<len;i++) cout<<a[i]<<endl;
}分組(TOI新手賽)
學習內容
題目敘述： 某國正在進行世界錦標賽，吸引了各國好手前來參加。每個選手會被官方打 上戰力指數，指數必為介於 0 到 9 的一位數，數字愈高代表官方人員覺得這位選 手越有潛力。 假設有 4 位選手，A 的戰力指數是 0，B 是 4、C 是 0、D 是 3。經過抽籤後， 選手的分組序列為 BCDA。分組時依序列由右往左分組。若一組有三人，選手 A、 D 和 C 會編在第一組，此組的戰力總和為 0+3+0=3；選手 B 會編在第二組，此 組的戰力總和為 4。 請你撰寫一個程式，依據每組人數以及參賽者的戰力指數來分析出戰力總和 最高的組別編號和該戰力總和值。 輸入格式： 每一行輸入含有兩個數字 N (1≤ N≤ 8) 和 P，其中 P 為參賽者依分組序列將 個別戰力指數組成的數字。已知最多不會超過 9 位參賽者，且最少會分出 2 組隊 伍。保證序列最左邊選手的戰力指數絕對不會是 0。 輸出格式： 輸出分組完後戰力總和最高的組別編號與這個組別的戰力指數總和，兩個 數字之間以一個空白隔開。如果有多個組別戰力指數總和相同，則輸出組別數 字較大的那一組。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,sum=0,maxn=-10e9,maxnum;
string P;
cin>>N>>P;
int j=N,num=1;
for(int i=P.size()-1;i>=0;i--){
j--;
sum+=P[i]-'0';//利用ASCII碼轉出數字，再求出該隊戰力總和
if(j==0){
if(sum>=maxn){
maxn=sum;//目前隊伍戰力最大值
maxnum=num;//隊伍戰力最大值編號
}
j=N;
sum=0;
num++;
}
}
//比較最後一隊
if(sum>=maxn){
maxn=sum;
maxnum=num;
}
cout<<maxnum<<" "<<maxn<<endl;
return 0;
}尋找回文
本次學習內容：函式的使用
題目敘述：尋找一個英文字當中最長的回文，如thisisaradar中的radar
#include <bits/stdc++.h>
using namespace std;
is_palindrome(string s,int st,int ed){
int state=1;
//從第一個和最後一個向內找
for(int i=0;i<(ed-st+1)/2;i++){
//如果前不等於後就跳出
if(s[st+i]!=s[ed-i]){
state=0;
break;
}
}
return state;//回傳子字串是不是回文
}
int main()
{
string s;
int maxn=-10e9,st,ed;
cin>>s;
//由i~j分別代表子字串的頭和尾，逐一掃瞄每個子字串並丟到函式判斷
for(int i=0;i<s.size()-1;i++){
for(int j=i+1;j<s.size();j++){
if(is_palindrome(s,i,j)){
if(j-i>maxn){//如果回文更長就更新最大值
st=i;
ed=j;
maxn=j-i;
}
}
}
}
for(int i=st;i<ed+1;i++){
cout<<s[i];
}
return 0;
}執行結果：
這個程式在速度上不是最快的，在計算較小的子字串的時候可能可以把結果存起來，等到較大的子字串就能省去很多的時間。
第三部分 進階程式設計
二維點排序
本次學習內容：struct的使用，sort的使用
題目敘述：給你n個點座標，請依x座標當作第一關鍵字，y座標為第二關鍵字，由小到大排序。
#include <bits/stdc++.h>
using namespace std;
struct point{
int x;
int y;
};
//結構宣告，會成為一個資料型態
bool cmp(point a,point b){
if(a.x==b.x){
return a.y<b.y;//如果兩項的x相等就比較y
}else
{
return a.x<b.x;//如果兩項x不同就比較x
}
}
int main()
{
int N;
cin>>N;
point pos[N];//宣告資料型態為point的陣列
for(int i=0;i<N;i++){
cin>>pos[i].x>>pos[i].y;
}
sort(pos,pos+N,cmp);//對所有點按照自訂函式排序
for(int i=0;i<N;i++){
cout<<pos[i].x<<" "<<pos[i].y<<endl;
}
return 0;
}自訂比較函式的寫法：
會傳入兩個原本排序容器的兩個相鄰值(這題是point a和point b)可以用類似泡沫排序法個邏輯思考，如果後面的小於前面的就交換，交換後小的數字在前，大的數字在後，可以使最終結果由小排到大。因為我並不知道這個sort函式背後的運作原理(有考慮之後來看)，所以沒有更深入的了解。
矩形內的點(Uva 00476 - Points in Figures: Rectangles)
學習內容：struct的使用
題目敘述：
在x-y平面上，給你一些矩形和一些點，請你回答這些點落在哪些矩形內（如果有的話）。另外，在這個問題中，剛好落在邊上的點不視為落在該矩形內。
首先是矩形的資料，每個矩形一列，第1個字元代表圖形的類別（r 代表矩形），接下來有4個數值分別代表該矩形左上角及右下角的座標。矩形的個數不會超過10個。
以一列僅含有一個*代表矩形資料結束。
接下來的每列為一個點的座標，也就是要測試的點。若點座標為9999.9 9999.9代表輸入結束（此點不需輸出）
對每一個測試的點，若其落在某矩形內，則輸出下列格式的訊息：
Point i is contained in figure j 如果某個點沒有落在任何矩形內，則輸出：
Point i is not contained in any figure
#include <bits/stdc++.h>
using namespace std;
float maxn=9999.9;
struct rec{
float lx;
float uy;
float rx;
float dy;
};
int main()
{
char state;
rec re[10];
int i=0;
while(cin>>state){
if(state=='*') break;//輸入星號就結束輸入迴圈
cin>>re[i].lx>>re[i].uy>>re[i].rx>>re[i].dy;
i++;
}
float x,y;
int cnt=1;
while(cin>>x>>y){
if(x==maxn&&y==maxn) break;//如果輸入9999.9就跳出迴圈
int stat=0;
for(int j=0;j<=i;j++){
//點的x座標介於該矩形的上下界之間，y座標介於該矩形的左右界之間，就輸出
if((re[j].lx<x&&x<re[j].rx)&&(re[j].dy<y&&y<re[j].uy)){
cout<<"Point "<<cnt<<" is contained in figure "<<j+1<<endl;
stat=1;
}
}
if(stat==0){
//如果完全沒有在任何矩形(stat==0)才輸出
cout<<"Point "<<cnt<<" is not contained in any figure"<<endl;
}
cnt++;
}
return 0;
}在撰寫這個程式時，我們在輸入9999.9結束程式的部分一直出錯，原本的判斷式是if(x==9999.9&&y==9999.9) break;輸入了數字卻無法跳出，後來我將數字設為變數，並和變數比較，如上面的程式，就成功跳出迴圈，我認為是直接在程式內打的數字不一定會用精確值儲存起來，使比對時的值不符合。以上只是推測，我並沒有深入的查詢資料。
迷路的小龜
學習內容：pair的使用
題目敘述：
#include <bits/stdc++.h>
using namespace std;
bool cmp1(pair<int,int> a,pair<int,int> b){
return a.first<b.first;
}
bool cmp2(pair<int,int> a,pair<int,int> b){
return a.second<b.second;
}
float distan(int x,int y){
return pow((pow(x,2)+pow(y,2)),0.5);
}
int main()
{
int N,maxpos,minpos;
float maxn=-10e9,minn=10e9,dis;
cin>>N;
pair<int,int> p[N];//pair的宣告
for(int i=0;i<N;i++){
cin>>p[i].first>>p[i].second;//pair內容的存取
dis=distan(p[i].first,p[i].second);
if(dis>=maxn){
maxn=dis;
maxpos=i;
}
if(dis<=minn){
minn=dis;
minpos=i;
}
}
printf("最遠為第%d點:(%d,%d) 距離: %.2f\n",maxpos+1,p[maxpos].first,p[maxpos].second,maxn);
printf("最遠為第%d點:(%d,%d) 距離: %.2f\n",minpos+1,p[minpos].first,p[minpos].second,minn);
sort(p,p+N,cmp1);
cout<<"x座標以小到大"<<endl;
for(int i=0;i<N;i++){
cout<<p[i].first<<" "<<p[i].second<<endl;
}
sort(p,p+N,cmp2);
cout<<"y座標以小到大"<<endl;
for(int i=0;i<N;i++){
cout<<p[i].first<<" "<<p[i].second<<endl;
}
return 0;
}執行結果：
4
2 5
3 4
5 6
2 9
最遠為第4點:(2,9) 距離: 9.22
最遠為第2點:(3,4) 距離: 5.00
x座標以小到大
2 5
2 9
3 4
5 6
y座標以小到大
3 4
2 5
5 6
2 9
Process returned 0 (0x0) execution time : 18.284 s
Press ENTER to continue.pair vs struct
這次的程式中我們學習到了pair的用法，使用的情境和之前使用的struct有些地方類似，兩者都能把數據綁在一起，這樣在操作時能一起排序，一起刪除，儲存兩筆相關的資料很方便。pair的優點是本身就是容器，可以直接宣告就用，在sort時也不用另外寫比較函式（但只能比first項），但比起struct也有劣勢存在。struct可以把兩個以上的變數綁在一起，還能分別命名，這在需要比較長時間編寫的專案可讀性就較高。此外struct宣告的是資料型態，比pair容易塞到其他容器裡。整體來說，pair會比較適合在只寫一次的競程裡用，struct則用在一般程式專案中。
棍子切割（APCS 20210109）
學習內容：set的使用
題目敘述：
有一根長度為 L 的棍子，你會把這個棍子切割 n 次。
假設一開始棍子左端放在數線上 0 的位置，棍子的右端放在數線上 L 的位置，每次的切割會給定一個介於 0 到 L 的數字表示要切割的位置，你要把穿過個這位置的棍子切成兩段，而所需的花費就等於所切割的棍子的長度。
第一行有兩個整數 n,L。
接下來 n 行每行有兩個整數 x,i，表示 x 位置被切過一刀，而這刀是全部的切割中的第 i 刀，保證 i 是介於 [1,n] 的整數且不會重複。
輸出一個整數表示總共的切割費用，答案可能超過2的31次方但不會超過2的60次方。
解題想法：
每次切割費用等於離切割位置最近的已完成左切割點和右切割點。
#include <bits/stdc++.h>
using namespace std;
struct pos{
int pos;
int th;
};
bool cmp(pos a,pos b){
return a.th<b.th;
}
void print(vector<int> v){
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
cout<<endl;
}
int main()
{
long long int n,L,sum=0;
cin>>n>>L;
vector<pos> cut(n);//儲存原始資料
vector<int> log;//
for(int i=0;i<n;i++){
cin>>cut[i].pos>>cut[i].th;
}
sort(cut.begin(),cut.end(),cmp);//將切割依照順序排列
log.push_back(0);
log.push_back(L);
vector<int>::iterator low;
for(int i=0;i<cut.size();i++){
low=lower_bound(log.begin(),log.end(),cut[i].pos);//尋找切點所處位置
sum+=*low-*(low-1);//費用=右切割點-左切割點
log.insert(low,cut[i].pos);//插入vector->已經切割
}
cout<<sum<<endl;
return 0;
}使用set和pair的做法
set特性:放入資料會即時排序，同一個資料只能存在1個。
set常用語法
find:尋找查詢資料在set內的位置，回傳一個指標，找不到則回傳指向尾巴的指標。
insert:將一個資料放入set當中
erase:輸入一個指標或要刪除的資料（或是區間），將它從set中刪除。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,L,sum=0;
cin>>N>>L;
set<int> s={0,L};
pair<int,int> p[N];//儲存原始資料
for(int i=0;i<N;i++){
cin>>p[i].second>>p[i].first;
}
sort(p,p+N);//將切割依照順序排列
for(int i=0;i<N;i++){
s.insert(p[i].second);
auto it=s.find(p[i].second);
sum+=*next(it)-*prev(it);
}
cout<<sum;
return 0;
}印刷機
題目敘述：
現有n本書需印刷裝訂。每一本書必須先印刷再裝訂。工廠有n 台裝訂機但只有一台印刷機。印刷機同時只 能印一本書，而且必需印完一本書後才能印下一本書。現給定每一本書的印刷時間和裝訂時間，請計算所有書最快要多久才能印刷裝訂完畢。
輸入第一行為n，即書的數目(1 <= n <= 1000)。 以下n行每行代表一本書，每行有兩個數字。第一個數字代表書的印刷時間，第二個數字代表書的裝訂時 間，時間都介於1到1000 之間。
解題想法：
觀察例子可以發現造成最長時間有兩種情況，一種是相加印刷時間再加最短的裝訂時間，另一種是抹本書的印刷加裝訂大於前一項的時間。所以先假設最長時間為第二種，計算第一種在和它比較
解題心得：
再做這題時我發現到關鍵的語法如果不會用（make_pair）就需要繞很遠的路把內容補回來。也發現pair的first,second在使用時的確會混淆我的判斷，struct還是有好處。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,t1,t2;
cin>>N;
priority_queue<pair<int,int>> pq;
for(int i=0;i<N;i++){
cin>>t1>>t2;
pq.push(make_pair(t2,t1));//原來可以樣用
}
int ans=pq.top().first+pq.top().second;
//cout<<ans<<endl;
int print=pq.top().second;
for(int i=0;i<N-2;i++){
//cout<<"i="<<i<<endl;
pq.pop();
//printf("pq.top().first %d pq.top().second %d\n",pq.top().first,pq.top().second);
print+=print+pq.top().second;
ans=max(ans,print+pq.top().first);
//cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}結果：
3
5 3
4 2
3 9
14
Process returned 0 (0x0) execution time : 4.904 s
Press ENTER to continue.Add all
學習內容：貪婪演算法，priority queue的使用
題目敘述：
給定一些數字要相加，一次操作只能相加兩個數字，定義操作的相加代價為該次相加的答案，求出總相加代價的最小值。
解題想法：
觀察幾個例子可以發現如果先把最小的兩個數字相加起來會使總價值最小，所以用priority queue儲存要相加的數字，每次拔出top兩個數字，相加完累加相加代價再放回去，重複直到所有數字都被相加完畢。
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long N;
long long temp;
long long sum=0;
long long cost=0;
//設置一個top為最小值的priority queue
priority_queue<long long,vector<int>,greater<int>> pq;
while(cin>>N){
if(N==0) break;
for(int i=0;i<N;i++){
scanf("%lld",&temp);
pq.push(temp);
}
sum+=pq.top();
pq.pop();
for(int i=0;i<N-1;i++){
sum+=pq.top();
pq.pop();
cost+=sum;
}
cout<<cost<<endl;
}
return 0;
}Map容器練習
例題：zerojudge d518: 文字抄寫 II
第四部分 其它自行練習題目
考拉茲猜想路徑長（未完成）
題目敘述：
考拉茲猜想：如果它是奇數，則對它乘3再加1，如果它是偶數，則對它除以2，如此循環，最終都能夠得到1。
假設給定n=6，會經歷過6,3,10,5,16,8,4,2後回到1，總共9個數字，定義6的考拉茲猜想路徑長=9。
請問路徑長64的數字有幾個？
第一種解法 暴搜
#include <iostream>
#include <vector>
using namespace std;
int dp[200000]={};
int find(long int a,int b){
int ans=1;
//迴圈內實際執行考拉茲猜想的步驟，超過64步就結束
while(a>1&&ans<=b){
if(a%2==0){
a=a/2;
ans++;
}else{
a=3*a+1;
ans++;
}
}
if(ans<=b){
return ans;
}else{
return 0;
}
}
int main(){
int a;
//暴搜一億以內的數字
for(int i=1;i<100000000;i++){
a=find(i,64);
if(a) dp[a]++;
}
for(int i=0;i<=64;i++){
cout<<i<<": "<<dp[i]<<endl;
}
}結果
0: 0
1: 2
2: 1
3: 1
4: 1
5: 1
6: 2
7: 2
8: 4
9: 4
10: 6
11: 6
12: 8
13: 10
14: 14
15: 18
16: 24
17: 29
18: 36
19: 44
20: 58
21: 72
22: 91
23: 113
24: 143
25: 179
26: 227
27: 287
28: 365
29: 459
30: 577
31: 718
32: 911
33: 1098
34: 1407
35: 1793
36: 2061
37: 2656
38: 3071
39: 3778
40: 4917
41: 5045
42: 6674
43: 8808
44: 8606
45: 11531
46: 10433
47: 14263
48: 19391
49: 16738
50: 23227
51: 20488
52: 26417
53: 37038
54: 28511
55: 40841
56: 58054
57: 42904
58: 62295
59: 42972
60: 63683
61: 93517
62: 62378
63: 93572
64: 71605
Process returned 0 (0x0) execution time : 26.438 s
Press ENTER to continue.總共花了大約26秒完成，由於只計算到1億個數字的考拉茲路徑長，顯示暴搜並不可行
第二種解法 dp
#include <bits/stdc++.h>
using namespace std;
int dp[20000]={};
void test(long int a,int b){
if(b<64){
if((a-1)%3==0&&a%2==0){
test((a-1)/3,b+1);//3n+1的情況
}
dp[b]++;//該路徑長次數+1
test((2*a),b+1);//2n的情況
}
}
int main()
{
dp[1]=1;
dp[2]=1;
dp[3]=1;
test(8,4);
for(int i=0;i<64;i++) cout<<i<<": "<<dp[i]<<endl;
//for(int i=0;i<64;i++) cout<<dp[i]<<", ";
return 0;
}這次的寫法解說如下圖（圖還沒有做完）
結果
0: 0
1: 1
2: 1
3: 1
4: 1
5: 1
6: 2
7: 2
8: 4
9: 4
10: 6
11: 6
12: 8
13: 10
14: 14
15: 18
16: 24
17: 29
18: 36
19: 44
20: 58
21: 72
22: 91
23: 113
24: 143
25: 179
26: 227
27: 287
28: 366
29: 460
30: 578
31: 732
32: 926
33: 1174
34: 1489
35: 1879
36: 2365
37: 2988
38: 3780
39: 4788
40: 6049
41: 7628
42: 9635
43: 12190
44: 15409
45: 19452
46: 24561
47: 31025
48: 39229
49: 49580
50: 62680
51: 79255
52: 100144
53: 126542
54: 159930
55: 202085
56: 255455
57: 322869
58: 408002
59: 515542
60: 651407
61: 823238
62: 1040490
63: 1315036
Process returned 0 (0x0) execution time : 0.054 s
Press ENTER to continue.輸出的內容到路徑長64都是正確的，而且花了不到1秒的時間就完成，在時間複雜度上有很大的進步。
排列組合（中區資訊學科能力競賽相關）
題目敘述：給定一組數字，當中第奇數個數字代表其後一個數字的個數。如 3 1 2 2 ，代表接下來生成的數字由3個1和2個2組成。輸出所有生成數字可能組合。
解題思路：利用遞迴處理（還沒寫完）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll total;
struct p{
int cnt;
int num;
};
ll factorial(int num){
ll ans = 1;
for(int i=2;i<=num;i++){
ans*=i;
}
return ans;
}
int print(vector<p> v){
for(int i=0;i<v.size();i++) cout<<"cnt "<<v[i].cnt<<" num "<<v[i].num<<" ";
cout<<endl;
}
int permutations(vector<p> v,int num){
if(v.size()>0){
for(int i=0;i<v.size();i++){
if(v[i].cnt==1){
p temp=v[i];
int add=v[i].num;
v.erase(v.begin()+i);
//print(v);
permutations(v,num*10+add);
v.insert(v.begin()+i,temp);
//print(v);
}else
{
v[i].cnt--;
permutations(v,num*10+v[i].num);
v[i].cnt++;
}
}
}else
{
cout<<num<<endl;
}
}
int main()
{
vector<p> v(2);
v[0].cnt=1;
v[0].num=3;
v[1].cnt=2;
v[1].num=2;
permutations(v,0);
cout<<"total= "<<total<<endl;
ll estimated = factorial(5)/(factorial(2)*factorial(2));
cout<<"estimated= "<<estimated<<endl;
return 0;
}這題我在競賽當下是沒有解出的，主要是因為那題的其他部分因為忘記語法而做不出來，就沒有花時間再想。
箭頭謎題（未完成）
題目敘述： 在箭頭謎題這個⼩遊戲中，有 N 個箭頭由左⾄右排成⼀列。每個箭頭⼀開始可能會是向上 或是向下的，每當你點擊⼀個箭頭，該箭頭以及與其相鄰的所有箭頭的狀態都會被反轉，也就 是說，如果某個箭頭是向下的，那麼直接點擊該箭頭或是點擊任何與其相鄰的箭頭都會使得它 變為向上，反之亦然。遊戲⽬標是在經過⼀系列的點擊操作之後，使得所有箭頭都是向上的。 現在告訴你所有箭頭的初始狀態（向上或是向下），請你幫 OET 快速辨別他是否有可能完 成這局遊戲，也就是讓所有箭頭都是向上的狀態。
第⼀⾏有⼀個正整數 N ，表⽰箭頭的數量。 第⼆⾏有⼀個⻑度 N 的 01 字串 S 表⽰所有箭頭的初始狀態，S i = 0 表⽰第 i 個箭頭的狀 態是向上的，S i = 1 則表⽰第 i 個箭頭的狀態是向下的。
請輸出 Yes 或 No，代表 OET 是否有可能完成這局遊戲，也就是讓所有箭頭都是向上的狀 態。
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n;
string I;
scanf("%lld",&n);
long long l[n];
cin >>I;
for (long long i=0;i<n;i++)
{
l[i]=(int)I[i]-(int)'0';
}
if (n%3==2)
{
long long t=0;
for (long long i=0;i<n;i++) if(l[i]==1) if(i%3!=2) t++;
if (t%2) printf("No");
else printf("Yes");
}
else printf("Yes");
return 0;
}字串路徑條件限制版（未完成）
題目敘述： 在殿壬三歲⼜六個⽉⼤時，他在地板上撿到⼀組字串 A, B。 因為 A, B 兩個字串⻑的不⼀樣，所以愛好平等的殿壬就很⽣氣，決定要把 B 經由⼀系列 的操作變成 A。 他每次會選定 B 字串上的⼀個字元，並且把他刪掉。也就是說，他每次會選定 i 使得 0 ≤ i < |B|，令 B ′ = B 0 B 1 B 2 · · · B i−1 B i+1 B i+2 · · · B |B|−1 ，然後把 B 變成 B ′ 。 已知殿壬永遠找得到⼀個⽅法把 B 變成 A，現在殿壬想知道，在把 B 變成 A 的所有⽅法 中，若將所有過程中出現的字串蒐集起來，究竟有多少種⻑的不⼀樣的字串呢？ 字串 X, Y ⻑的不⼀樣，若且唯若 |X| ̸ = |Y | 或存在 0 ≤ i < |X|, X i ̸ = Y i 。 因為可能有太多種了，所以殿壬只想知道答案除以 998244353 之後的餘數。
輸⼊的第⼀⾏有⼀個由⼩寫字⺟組成的字串 A。輸⼊的第⼆⾏有⼀個由⼩寫字⺟組成的字 串 B。
輸出只有⼀⾏僅包含⼀個⾮負整數，代表答案除以 998244353 之後的餘數。
例子
殿壬將 aba 變成 a 的過程中可以是下列三種的其中⼀種： • aba → aa → a • aba → ab → a • aba → ba → a 不同的字串有 a, aa, ab, ba, aba，共 5 種。
#include <bits/stdc++.h>
using namespace std;
vector<string> ways[10001];
long long ans=0;
long long maxn=998244353;
int find_repeat(string a){
for(string item:ways[a.size()]){
if(item==a){
return 1;
break;
}
}
}
int count_alphabet(string a,string b){
size_t found = b.find(a);
int repeat=find_repeat(b);
if(found!=string::npos&&repeat!=1){
ways[b.size()].push_back(b);
string temp;
for(int i=0;i<b.size();i++){
temp=b;
temp.erase(temp.begin()+i);
count_alphabet(a,temp);
}
}
}
int main()
{
string A,B;
cin>>A>>B;
count_alphabet(A,B);
for(int i=1;i<=B.size();i++){
ans+=ways[i].size();
}
cout<<ans%maxn <<endl;
return 0;
}第五部分 python模擬程式
程式說明：這是一個物理模擬程式，是為了物理探究實作的比賽而寫的，主要探討膠囊掉落反彈實的動態模擬。其中慶勳老師有和我討論並幫忙修改部分程式和數學邏輯上的錯誤，如果沒有老師的幫助，我可能要花長很多的時間才能完成這個程式。
GlowScript 3.1 VPython
# 單位 長度cm 質量g 時間s rad
Mh = 2/3#圓柱質量 單位 克
Rh = 0.6#圓柱直徑 單位 公分
Ms = 2*2/3#球質量 單位 克
Rs = 0.5#球半徑 單位 公分
M = Mh + Ms #膠囊總質量
l = Rh + Rs*2 #膠囊總長度
g = 60 # 地球重力加速度 cm/s2
v = vector(0,0,0) #膠囊初速
t = 0 # 計算時間用參數
dt = 0.0001#時間間隔
w = 0 #膠囊初角速度
theta = radians(45) #初始角度要用正的
Ih = Mh*(3*Rs*Rs+Rh*Rh)/12 #圓柱轉動慣量
Is = 2*Ms*Rs*Rs/5+Ms*(Rh/2)*(Rh/2)+0.375*Rs*Ms*Rh #半球轉動慣量
I = 2*Is+Ih
print('I =',I )
h = 30
e = 1
n = vector(0,1,0)
th_impact = 0
R = 0 #膠囊質心到碰撞點距離
th_temp = 0
width = 30
ReboundHeight = []
L = []
#RH_Color = [vector(1,1,0),vector(1,0.6,)]
scene2 = canvas(width=1366, height=720,center=vector(0,0,0),background=color.white)
ground = curve(pos=vector(-width,0,0),vector(width,0,0),color=color.blue)
#pointer = arrow(pos=vector(-10,0,0),axis=vector(5,0,0), shaftwidth=1)
StartLine =curve(pos=vector(-width,h,0),vector(width,h,0),color=color.green)
init = 'initial height='+str(h)+'cm '+'theta='+str(degrees(theta))+'degree'
initial_height = label(pos=vector(-10,h,0),text=init, xoffset=0,yoffset=0, space=30,height=16, border=4)
rod = cylinder(pos=vector(0,0,0),axis=vector(Rh,0,0),radius=Rs)
ball1 = sphere(pos=vector(Rh,0,0),radius=Rs)
ball2 = sphere(pos=vector(0,0,0),radius=Rs)
capsule = compound([rod,ball1,ball2])
capsule.color = color.red
capsule.pos = vector(0,h,0)
capsule.rotate(angle=theta,axis=vector(0,0,10))
#scene2.camera.follow(capsule)
i=0
i_limit = 4
Para=True
while i<i_limit:
v.y-=g*dt
rate(1/dt/3)
theta+=w*dt
capsule.rotate(angle=w*dt,axis=vector(0,0,1))
capsule.pos+=v*dt
if(capsule.pos.y > h and Para):
print('第',i,'次反彈後超過起始高度')
Para=False
R = sqrt(pow((Rs*abs(sin(theta))+Rh/2),2)+pow(Rs*abs(cos(theta)),2))
th_temp = acos((pow(R,2)+pow(Rs,2)-pow(Rh/2,2))/(2*R*Rs))
if((theta%pi)<=pi/2):
th_impact = pi/2-th_temp
else:
th_impact =2*pi- (pi/2+th_temp)
if(capsule.pos.y<(R*abs(sin(th_impact)))):
capsule.pos.y=(R*abs(sin(th_impact)))
if((theta%pi)<=pi/2):
vap1 = v+cross(vector(0,0,w),vector(-R*cos(th_impact),-R*sin(th_impact),0))
else:
vap1 = v+cross(vector(0,0,w),vector(-R*cos(th_impact),R*sin(th_impact),0))
#print("vap1=",vap1)
#pointer.axis = vap1/10
j = -1*(1+e)*dot(vap1,n)/( (1/M) + (pow(R*cos(th_impact),2)/I))
dv = j*n/M
v = v+dv
#v.x+=-1*vap1.x
w = w-R*j*cos(th_impact)/I
#sleep(1)
i+=1 #碰撞次數
print("第幾次碰撞完i=",i,'角速度w=',w,"撞擊點相對速度vap1=",vap1,"正向力衝量j=",j,"v=",v,'撞擊角th_impact=',th_impact)
Height = (v.y*v.y/2/g)+R*abs(sin(th_impact))
show_text = 'bounce '+str(i)+' height='+str(round(Height*1000)/1000)+'cm'
#上面那行要改函式
ReboundHeight.append(curve(pos=vector(-width,Height,0),vector(width,Height,0),color=color.rgb_to_hsv(vector(i/i_limit,1,1))))
L.append(label(pos=vector(10,Height,0),text=show_text, xoffset=0,yoffset=0, space=30,height=16, border=4))
t+=dt線上演示連結（強烈建議使用電腦）：