Try   HackMD

APCS相關演算法實例與筆記

主要是自己打給自己看的，如果有錯還請下面留言糾正我==
如果是初階高中競賽程式選手或者目標檢定可以稍微參考
這邊主要是大量程式碼示範+提供關鍵字

那些很讚的資源

Yuihuang的演算法筆記
Zerojudge
台大演算法筆記
APCSCAMP(營隊)
IOICAMP(營隊)(很進階，主攻數學的我不會去)

我參加的APCS場次心得

有我的AC CODE喔
預計下一場次（不確定ww只能說至少要六月，一月的跟清大數陪衝撞）
1.2022 10月 APCS（成績：觀念4級分/實作4級分）

防雷方法

  1. #define int long long
  2. 注意最大最小值並定義清楚
  3. #define wh_ale ios::sync_with_stdio(0)

相關重點演算法

資料結構

特殊的(抱歉啦其他的我有空再慢慢補)

set

s.find(element)代表搜尋element是否在set裡面
s.insert(element)代表插入element到set裡面
s.erase(element)代表刪除set裡面的元素element
*s.begin()代表找出set裡面最小值
*s.rbegin()代表找出set裡面最大值
CODE：











































#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	set<int> s;
	int i, n, cmd, x;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> cmd;
		if(cmd==1){
			cin >> x;
			if((s.find(x) != s.end())==false){
				s.insert(x);
			}
		}
		else if(cmd==2){
			cin >> x;
			if((s.find(x) != s.end())==false){
				cout << "error\n";
			}
			else s.erase(x);
		}
		else if(cmd==3){
			cout << s.size()<<'\n';
		}
		else if(cmd==4){
			if(s.size() != 0){
				cout << *s.begin()<<'\n';
			}
			else cout <<"error\n";
		}
		else if(cmd==5){
			if(s.size() != 0){
				cout << *s.rbegin()<<'\n';
			}
			else cout <<"error\n";
		}
	}
	return 0;
}

枚舉

排列枚舉

敘述：輸入n代表有幾個數字，接著輸入n個數字求所有排列(暴力破解)
關鍵：while(next_permutation(v.begin(), v.end())) 函數的使用方式
範例程式碼：





























#include <bits/stdc++.h>
using namespace std;
#define pkb push_back
#define ppb pop_back
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, x, i;
	vector<int> v;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> x;
		v.pkb(x);
	}
	sort(v.begin(), v.end());
	for(i=0;i<n;i++){
			cout <<v[i] <<" ";
		}
		cout <<'\n';
	while(next_permutation(v.begin(), v.end())){
		for(i=0;i<n;i++){
			cout <<v[i] <<" ";
		}
		cout <<'\n';
	}
	
	return 0;
}

字典序枚舉

敘述：給定n筆測資，每次m個數字、要取k個做字典序排列並輸出
關鍵：排序後利用遞迴的概念(放入和取出很抽象)
範例程式碼：




































#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> v, a;
void run(int i){
	if(i==n){
		if(v.size()==k){
			for(int j=0;j<k;j++){
				cout << v[j]<<" ";
			}
			cout << '\n';
		}
	}
	else{
		v.push_back(a[i]);
		 run(i+1);
		v.pop_back();
		 run(i+1);
	}
}
int main() {
	// your code goes here
int t;
cin >> t;
for(int i=0;i<t;i++){
	cin >> n >> k;
	a.resize(n);
	for(int j=0;j<n;j++){
		cin >> a[j];
	}
	sort(a.begin(),a.end());
	run(0);
}
	return 0;
}

APCS 201810 P2

敘述：點我
關鍵：遞迴枚舉
AC CODE：

























#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p, ans=0;
int t[50];
void run(int x, int m){
	if(x==n){
		if(m<p){
			ans=max(ans, m);
		}
	}else{
		run(x+1, m+t[x]);
		run(x+1, m);
	}
}
signed main() {
	cin >> n >> p;
	for(int i=0;i<n;i++){
		cin >> t[i];
	}
	run(0, 0);
	cout << ans << '\n';
	return 0;
}

貪心法

零錢問題

敘述：給定n個錢幣種類，每種無限且互相整除，求兌換k元的最少硬幣數
關鍵：取最大值開始嘗試，一路到最小(取mod)
範例程式碼：



















#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll i, n, k, c[10], cnt;
	cin >> n >> k;
	for(i=0;i<n;i++){
		cin >> c[i];
	}
	for(i=n-1;i>=0;i--){
		cnt += (k-k%c[i])/c[i];
		k = k%c[i];
	}
	cout << cnt <<'\n';
	return 0;
}

變形
敘述：呈上，但零錢數量有限(一開始會给定數量)
關鍵：取最大值開始嘗試，直到無法再取，一路到最小(取mod)
範例程式碼：

































#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0)
int main() {
	wh_ale;
	ll i, j, n, k, c[10], a[10], cnt=0;
	cin >> n >> k;
	for(i=0;i<n;i++){
		cin >> c[i];
	}
	for(i=0;i<n;i++){
		cin >> a[i];
	}
	for(i=n-1;i>=1;i--){
		if(k>=c[i]){
			if(k/c[i]<a[i]){
				cnt += k/c[i];
				k = k%c[i];
			}
			else{
				k -= c[i]*a[i];
				cnt += a[i];
			}
		}
	}
	if(k != 0){
		cnt += k;
	}
	cout << cnt <<'\n';
	return 0;
}

最大平均區間

敘述：給定一數列，求最大平均區間
關鍵：利用數學得知最大平均區間要碼2要碼3
範例程式碼：
































#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, a[300001], i, j, mod;
	int mx=0;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a[i];
	}
	for(i=0;i<n-1;i++){
		if(max(mx, (a[i]+a[i+1])*3) != mx) mod=2;
		mx=max(mx, (a[i]+a[i+1])*3);
	}
	for(i=0;i<n-2;i++){
	if(max(mx, (a[i]+a[i+1])*2) != mx) mod=3;
	mx=max(mx, (a[i]+a[i+1])*2);
	}
	if(mod==2){
		if(mx%2==0) cout << mx/6 <<" "<<1 <<'\n';
		else cout << mx/3 << " " <<2<<'\n';
		}
	else{
		if(mx%3==0) cout << mx/6 <<" "<<1 <<'\n';
		else cout << mx/3 << " " <<3<<'\n';
	}
	
	return 0;
}

可整除(可分割)背包問題

敘述：給定n個物品價值與重量(重量互相整除)以及一個背包的最大負重
關鍵：利用平均最大重量排序，一一放入背包
範例程式碼：





























#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
bool cmp(pii a, pii b){
	if(a.first/a.second != b.first/b.second) return a.first/a.second>b.first/b.second;
	else return a.second<b.second;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, m, i, j, cct=0;
	int cnt=0;
	pii c[200000];
	cin >> n >> m;
	for(i=0;i<n;i++){
		cin >> c[i].first >> c[i].second;
	}
	sort(c, c+n, cmp);
	for(i=0;i<n;i++){
		if(cnt+c[i].second<=m){
			cct += c[i].first*(((m-cnt)-((m-cnt)%c[i].second))/c[i].second);
			cnt += ((m-cnt)-((m-cnt)%c[i].second));
		}
	}
	cout <<cct <<'\n';
	return 0;
}

排程問題

敘述：給定一堆工作開始與結束時間，求某區段內能完成工作最大量
關鍵：利用結束時間做相關排序(結束時間越早，且越晚開始越有利)
範例程式碼：




























#include <bits/stdc++.h>
using namespace std;
struct node{
	int f;
	int s;
};
bool cmp(node a, node b){
	return a.s<b.s;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, i, j, cnt=0, l=0;
	node t[500000];
	cin >> n;
	for(i=0;i<n;i++){
		cin >> t[i].f >> t[i].s;
	}
	sort(t, t+n, cmp);
	for(i=0;i<n;i++){
		if(l>t[i].f) cnt++;
		else l=t[i].s;
	}
	cout <<n-cnt<<'\n';
	
	return 0;
}

多個字串結合湊出最小字典序

敘述：給定多個字串，求出最小結合字典序排列
關鍵：利用C++方便的字典序直接比較功能return a+b<b+a;當成cmp函數做排序
範例程式碼：



















#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(string a, string b){
	return a+b<b+a;
}
int main(){
	string s[100001];
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> s[i];
	}
	sort(s, s+n, cmp);
		for(int j=0;j<n;j++){
		cout << s[j];
	}
}

APCS2017.10物品堆疊

敘述：給定物品重量與數量做堆疊，求最少移動次數
關鍵：利用特殊條件做交換性排序
範例程式碼：



































#include <bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0)
#define ll long long
//William
struct turtle{
	int w;
	int f;
	
};
bool cmp(turtle a, turtle b){
	//麻煩到別人越高放越下面
	return a.w*b.f>a.f*b.w;
}
int main() {
	wh_ale;
	turtle t[100000];
	ll n, i, j, sum=0, ans=0;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> t[i].w;
		sum += t[i].w;
	}
	for(i=0;i<n;i++){
		cin >> t[i].f;
	}
	sort(t, t+n, cmp);
	for(i=0;i<n;i++){
		ans += (sum-t[i].w)*t[i].f;
		sum -= t[i].w;
	}
	cout << ans <<'\n';
	return 0;
}

圖論

BFS

敘述：廣度優先搜尋遍歷一張圖
關鍵：小細節(是否重複搜尋原點，要先確認有沒有越界在更新陣列)
範例程式碼(方格式BFS問題)：


























































#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, s, t, i, j;
	pii pr;
	int cs[500][500];
	int dx[4]={1,0,-1,0};
	int dy[4]={0,-1,0,1};
	queue<pii> q;
	char c;
	cin >> n >> m;
	cin >> s >> t;
	s--;
	t--;
	for(i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> c;
						if(c=='X'){
				cs[i][j]=-1;
			}
			else if(i==s and j==t){
				cs[i][j]=0;
			}

			else cs[i][j] =-2;
		}
	}
	q.push({s, t});
	while(!q.empty()){
		pr=q.front();
		q.pop();
		for(i=0;i<4;i++){
			if(0<=pr.first+dx[i] and pr.first+dx[i]<n and 0<=pr.second+dy[i] and pr.second+dy[i]<m){
				if(cs[pr.first+dx[i]][pr.second+dy[i]]==-2){
				cs[pr.first+dx[i]][pr.second+dy[i]]=cs[pr.first][pr.second]+1;
				q.push({pr.first+dx[i],pr.second+dy[i]});
				}
			}
		}
	}
		for(i=0;i<n;i++){
		for(int j=0;j<m-1;j++){
			if(cs[i][j] != -2){
			cout << cs[i][j]<<" ";
			}
			else cout << -1 << " ";
		}
		
		if(cs[i][m-1]!=-2) cout << cs[i][m-1]<<'\n';
		else cout << -1 <<'\n';
	}
	return 0;
}

(線段式BFS十分雷同類似，但要注意是否重物搜尋原點的條件)
(APCS某年歷屆AC CODE)






























#include <bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);
//William
int main() {
	wh_ale;
	int n, s[1000000], i, j, dx[2], p, cnt[1000000]={}, now;
	queue<int> q;
	bool y=false;
	cin >>  n >> p >> dx[0] >> dx[1];
	dx[0]=0-dx[0];
	for(i=0;i<n;i++){
		cin >> s[i];
	}
	q.push(0);
	while(!q.empty()){
		now=q.front();
		q.pop();
		for(i=0;i<2;i++){
			if(s[now+dx[i]]!=0 and 0<s[now+dx[i]] and s[now+dx[i]]<n and cnt[s[now+dx[i]]]==0){
				q.push(s[now+dx[i]]);
				cnt[s[now+dx[i]]]=cnt[now]+1;
			}
		}
	}
	if(cnt[p]==0) cout << -1 <<'\n';
	else cout <<cnt[p]<<'\n';
	return 0;
}

DFS

敘述：深度優先搜尋遍歷一張圖
關鍵：小細節(把賦值也寫成dfs函數的變數)
範例程式碼(本題是求圖有幾塊)：


































#include <bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
vector<int> v[100001];
int cg[100001]={};
int n, cnt=-1;
void dfs(int x){
	cg[x]=1;
	for(int i=0;i<v[x].size();i++){
		if(cg[v[x][i]]==0){
			dfs(v[x][i]);
		}
	}
}
int main() {
	wh_ale;
	int m, i, j, a, b;
	cin >> n >> m;
	for(i=0;i<m;i++){
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
	}
	for(i=1;i<=n;i++){
		if(cg[i] == 0){
			cnt++;
			dfs(i);
		}
	}
	cout << cnt <<'\n';
	return 0;
}

DJS併查集

敘述：用各種輸入操作DJS的合併，查詢，大小，組合數
關鍵：小細節(要把指向寫清楚，大合併小(除非題目有特例))
範例程式碼：


























































#include <bits/stdc++.h>
using namespace std;
#define int long long
int g[1000001], k[1000001], ib[1000001]={};
int n, m;
int fp(int x){
	if(g[x]==x) return x;
	else return fp(g[x]);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int i, j, x, y;
	cin >> n >> m;
	for(i=1;i<=n;i++){
		g[i]=i;
		k[i]=1;
		ib[i]=1;
	}
	int cmd, cnt=0;
	while(m--){
		cin >> cmd;
		if(cmd==1){
			cin >> x >> y;
			x=fp(x);
			y=fp(y);
			cnt += k[x]*k[y];
			if(k[x]>k[y]){
				g[y]=g[x];
				k[x]+=k[y];
				k[y]=k[x];
				
			}
			else{
				ib[x]=1;
				g[x]=g[y];
				k[x]+=k[y];
				k[y]=k[x];
			}
		}
		else if(cmd==2){
			cin >> x >> y;
			if(fp(x)==fp(y)) cout << "Yes\n";
			else cout << "No\n";
		}
		else if(cmd==3){
			cin >> x;
			cout << k[fp(x)] <<'\n';
		}
		else{
			
			cout << cnt <<'\n';
		}
	}
	return 0;
}

拓樸排序

敘述：每次拔掉一個節點，以此為順序直到結束對圖的動作
關鍵：記得統計大小，方向不要搞混就好
範例程式碼(本題是求圖有幾塊)：












































#include <bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define pb push_back
signed main (){
	wh_ale;
	int n, m, i, j;
	vector<int> v[100001];
	cin >> n >> m;
	int x, y;
	int d[100001]={};
	for(i=0;i<m;i++){
		cin >> x >> y;
		v[x].pb(y);
		d[y]++;
	}
	queue<int> q, qq;
	for(i=1;i<=n;i++){
		if(d[i]==0){ 
			q.push(i);
		}
	}
	while(!q.empty()){
		x=q.front();
		q.pop();
		qq.push(x);
		for(i=0;i<v[x].size();i++){
			d[v[x][i]]--;
			if(d[v[x][i]]==0) q.push(v[x][i]);
		}
	}
	if(qq.size()!=n) cout << "IMPOSSIBLE\n";
	else{
		cout << "POSSIBLE\n";
		while(qq.size()!= 1){
			cout << qq.front() <<" ";
			qq.pop();
		}
		cout << qq.front();
	}
    return 0;
}

MST最小生成樹

敘述：求最小生成樹
關鍵：排序邊長，利用併查集檢查環
範例程式碼：














































#include<bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int unsigned long long
struct e{
    int x, y, cost;
};
bool cmp(e x, e y){
    return x.cost < y.cost;
}
int p[2000001], n, m, j, k, c, ans;
vector <e> v;
int find(int a){
    if (p[a] == a) return a;
    else {
        p[a] = find(p[a]);
        return p[a];
    }
}
signed main() {
	wh_ale;
    cin >> n >> m;
        if (n == 0 && m == 0) ans = 0;
        
        v.clear();
        for (int i = 1; i <= n; i++){
            p[i] = i;
        }
        for (int i = 0; i < m; i++){
            cin >> j >> k >> c;
            v.push_back({j, k, c});
        }
        sort(v.begin(), v.end(), cmp);
        for (e tmp:v){
            j = find(tmp.x);
            k = find(tmp.y);
            if (j == k) continue;
            p[k] = j;
            ans += tmp.cost;
            n--;
        }
        
         cout << ans << "\n";
    
}

Dijktra最短路徑

敘述：求有向圖最短路徑
關鍵：每次都用dp更新距離
範例程式碼：





















































#include<bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define INF 1e18
#define pii pair<int, int>
#define psb push_back
vector<pii> g[100009];
int dis[100009];
int n, m, s, t;
pii r;
int pt;
int vis[100009]={};
priority_queue<pii, vector<pii>, greater<pii>> pq;
queue<int> q;
signed main(){
	wh_ale;
	cin >> n >> m;
	int i;
	for(i=1;i<=n;i++){
		dis[i]=INF;
	}
	int a, b, c;
	while(m--){
		cin >> a >> b >> c;
		g[a].psb({c, b});
	}
	cin >> s >> t;
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty()){
		for(i=0;i<g[q.front()].size();i++){
			if(dis[g[q.front()][i].second]>dis[q.front()]+g[q.front()][i].first){
			dis[g[q.front()][i].second]=dis[q.front()]+g[q.front()][i].first;
			pq.push({dis[g[q.front()][i].second], g[q.front()][i].second});
		}
		}
		q.pop();
		r=pq.top();
		while(vis[r.second]!=0 and pq.size() != 0){
			pq.pop();
			r=pq.top();
		}
		if(vis[r.second]==0)q.push(r.second);
		vis[r.second]=1;
		pq.pop();
	}
	if(dis[t]<INF) cout << dis[t] <<'\n';
	else cout << -1 <<'\n';
	return 0;
}

動態規劃

1D樓梯問題

敘述：樓梯問題國小競賽數學
關鍵：費氏數列
範例程式碼：



















#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define MOD 1000000007
int main() {
	wh_ale;
	int n, i, j;
	ll dp[5000001]={};
	dp[0]=1;
	dp[1]=1;
	cin >> n ;
	for(i=2;i<=n;i++){
		dp[i]=(dp[i-1]+dp[i-2])%MOD;
	}
	cout << dp[n] <<'\n';
	return 0;
}

2D樓梯問題

敘述：平面版樓梯問題
關鍵：駐馬法
範例程式碼



























































#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 1000000000000000000
#define MOD 1000000007
int main() {
	wh_ale;
	int n, m, i, j, q, a, b;
	bool t=true;
	cin >> n >> m >> q;
	ll g[1000][1000], dp[1000][1000];
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			cin >> g[i][j];
		}
	}
	for(i=0;i<n;i++){
		if(g[i][0]==0) dp[i][0]=1;
		else{
			
		break;
		t=false;
		}
	}
	if(t==false){
	for(j=i;j<n;j++){
		dp[j][0]=0;
	}
	}
	t=true;
	for(i=0;i<m;i++){
		if(g[0][i]==0) dp[0][i]=1;
		else{
			
		 break;
		 t=false;
		}
	}
	if(t==false){
	for(j=i;j<m;j++){
		dp[0][j]=0;
	}
	}
	for(i=1;i<n;i++){
		for(j=1;j<m;j++){
			if(g[i][j]==0){
				dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
			}
			else dp[i][j]=0;
		}
	}
	for(i=0;i<q;i++){
		cin >> a >> b;
		cout << dp[a][b] <<'\n';
	}
	return 0;
}

走迷宮取得最大值

敘述：給定平面迷宮，從左上到右下(每格都有點數)，取最大點數總和
關鍵：利用轉移式dp[i][j]=max(dp[i-1][j], dp[i][j-1])+g[i][j]
範例程式碼：




































#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 1000000000000000000
int main() {
	wh_ale;
	int n, m, i, j, cx, cy;
	cin >> n >> m;
	vector<ll> g[100001], dp[100001];
	for(i=0;i<=n;i++){
		g[i].resize(m+1);
		dp[i].resize(m+1);
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin >> g[i][j];
		}
	}
	for(i=0;i<=m;i++){
		dp[0][i]=0;
	}
	for(i=0;i<=n;i++){
		dp[i][0]=0;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			dp[i][j]=max(dp[i-1][j], dp[i][j-1])+g[i][j];
		}
	}
	
	
	cout << dp[n][m] <<'\n';
	return 0;
}

塗色dp

敘述：給定數列，每次同色不能相鄰，三種顏色分別是不同的乘法運算
關鍵：三階段轉換並且最後比大小
範例程式碼：

























#include <bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
int main() {
    ll n, dp[1000001][3], i, j, a[1000001][3], mx;
    cin >> n;
    dp[0][0]=0;
    dp[0][1]=0;
    dp[0][2]=0;
    for(i=1;i<=n;i++){
    	for(j=0;j<=2;j++){
    	cin >> a[i][j];
    	}
    }
    for(i=1;i<=n;i++){
    	for(j=0;j<=2;j++){
    		dp[i][j]=a[i][j]+max(dp[i-1][(j+2)%3], dp[i-1][(j+1)%3]);
    	}
    }
    mx=max({dp[n][0], dp[n][1], dp[n][2]});
    cout << mx <<'\n';
    return 0;
}

01背包問題

敘述：要馬拿要馬不拿的背包問題
關鍵：滾動式，由大到小跑
範例程式碼：






















#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main() {
	wh_ale;
	int n, i, j, w;
	ll dp[100001]={};
	int a[100], v[100];
	cin >> n >> w;
	for(i=0;i<n;i++){
		cin >> a[i] >> v[i];
	}
	for(j=0;j<n;j++){
	for(i=w;i>=a[j];i--){
		dp[i]=max(dp[i-a[j]]+v[j], dp[i]);
	}
	}
	cout << dp[w] <<'\n';
	return 0;
}

編輯距離

敘述：給兩字串求編輯距離
關鍵：轉移式有點複雜，背下來(看程式碼就懂了)
範例程式碼：






























#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main() {
	string s, t;
	int l, r, k;
	int n, i, j, dp[2001][2001];
	cin >> s >> t;
	l=s.size();
	r=t.size();
	dp[0][0]=0;
    for(i=1;i<=l;i++){
		dp[i][0]=dp[i-1][0]+1;
	}
	for(i=1;i<=r;i++){
		dp[0][i]=dp[0][i-1]+1;
	}
	for(i=1;i<=l;i++){
		for(j=1;j<=r;j++){
				if(s[i-1]==t[j-1]){
					dp[i][j]=min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]});
				}
				else dp[i][j]=min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1});
		}
	}
	cout << dp[l][r];
	return 0;
}

LIS最大遞增子序列

敘述：最大遞增子序列
關鍵：從後往前DP
範例程式碼：




























#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main() {
	wh_ale;
	int n, i, j;
	ll dp[5000]={};
	ll a[5000], mx=1, b[5000];
	cin >> n ;
	dp[n-1]=1;
	for(i=0;i<n;i++){
		cin >> a[i];
	}
	for(i=n-2;i>=0;i--){
		dp[i]=1;
		b[i]=1;
		for(j=i+1;j<n;j++){
			if(a[i]<a[j]){
				dp[i]=max(dp[i], b[i]+dp[j]);
			}
		}
		mx=max(dp[i], mx);
	}
	cout << mx <<'\n';
	return 0;
}

數列合併最小值

敘述：給定數列，每次合併都要花費兩堆總和，求最小合併花費總和
關鍵：轉移式很奇怪，dp[i][j]記錄左界右界合併最小值
範例程式碼：


































#include <bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define int long long
#define INF 99999999999999999
signed main() {
	wh_ale;
    int n, i, j;
    ll a[501], cc[501]={}, dp[501][501]={};
    cin >> n;
    for(i=1; i<=n; i++) {
        cin >> a[i];
        cc[i] = cc[i-1] + a[i];
    }
    for(i=1; i<=n; i++){
        for(j = 1; j <= n; j++){
            dp[i][j] = INF;
        }
    }
    for(i=1;i<=n;i++){
    	dp[i][i]=0;
    }
    for(i=1; i<n; i++){
        for(j=1; j<=n-i; j++){
            for(int k=j; k<j+i; k++)
            dp[j][j+i] = min(dp[j][k] + dp[k+1][j+i], dp[j][j+i]);
            dp[j][j+i] += cc[j+i]-cc[j-1];
            
        }
    }
    cout << dp[1][n] << endl;
}

LCS最常共同子序列

敘述：給兩字串求最長共同子序列
關鍵：DP…
範例程式碼：





























#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int maxn=5001;
string s1, s2;
int dp[maxn][maxn];
 
int main() {
    int l1, l2;
    while (cin >> s1 >> s2) {
        l1 = (int)s1.length();
        l2 = (int)s2.length();
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=l1; i++) {
            for (int j=1; j<=l2; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        cout << dp[l1][l2] << endl;
    }
    return 0;
}

二分搜

bound函數們

利用於以排序資料
lower_bound是取大於等於，upper_bound必然是大於
範例CODE：























#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while(cin>>n){
        vector <int> up;
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            up.push_back(a);
        }
        sort(up.begin(),up.end());
        int find;
        cin>>find;
        int ans=upper_bound(up.begin(),up.end(),find)-up.begin();//減去begin()是為了取得vector中的位置
        cout<< ans <<endl;
    }
}

主函數

主要利用在想暴力解時的優化方式
類似遊戲終極密碼的概念
利用某個chk函數去確認是否符合答案
範例CODE：






  while(r - l > 1) {
    int m = (l + r)/2;
    if(chk(m) == true) r = m;
    else l = m;
  }

以為這樣就結束了嗎?NoNoNo
其實是要看情況去撰寫、重新定義上下界的

example

這是apcs基地台問題我的AC CODE





































#include<bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
int n, k;
int a[200001];
bool chk(int x) {
	int i, j, cnt=0, e=-1;
	for (i = 0; i < n; i++) {
		if (a[i] > e) {
			cnt++;
			e = a[i] + x;
		}
	}
	if (cnt <= k) return true;
	else return false;
}
signed main() {
	wh_ale;
	cin >> n >> k;
	int i, j;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int l = 0, r = a[n - 1], mid;
	while (l < r) {
		mid = l + (r - l) / 2;
		if (chk(mid) == true) {
			r = mid;
		}
		else l = mid + 1;
	}
	cout << l << '\n';
	return 0;
}
Last changed by 
 
林晉宇
0
947

Read more

SECCON CTF 2024 紀錄

這場那時候忘記在模考還是段考，反正沒打到QwQ

Dec 2, 2024
實中資研社社課 滲透測試從 0 到 1

我們很多機器都是透過他們的vps架設的image

Oct 2, 2024
Project Sekai CTF 2024 Writeup by ICEDTEA

Tagless

Aug 25, 2024
Encrypted Pastebin on Hacker101CTF

image

Aug 11, 2024
Read more from 林晉宇
Published on HackMD