{%hackmd hackmd-dark-theme %}
# apcs 練題
## Introductory Problems
### Chessboard and Queens
想法: 八皇后問題

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
char maze[8][8];
bool vis[8][8];
int ans;
bool check(int x,int y) {
    for(int i=0;i<8;i++) {
        for(int j=0;j<8;j++) {
            if(vis[i][j]) {
                if(abs(x-i)==abs(y-j) || x==i || y==j) return 0;
            }
        }
    }
    return 1;
}
void dfs(int cur) {
    if(cur>7) {
        ans++;
        return;
    }
    for(int i=0;i<8;i++) {
        if(check(cur,i) && maze[cur][i]=='.') {
            vis[cur][i] = 1;
            dfs(cur+1);
            vis[cur][i] = 0;
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for(int i=0;i<8;++i) {
        string s; cin>>s;
        for(int j=0;j<8;++j) {
            maze[i][j]=s[j];
        }
    }
    dfs(0);
    cout << ans << '\n';
}

## Search and sorting
### Factory Machines
想法: 對具單調性的時間二分搜

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
vector<int>k(200005);
bool isvalid(int x) {
	int tmp=0;
	for(int i=0;i<n;i++) {
		tmp+=floor(x/k[i]);
		if(tmp>=t) break;
	}
	return tmp>=t;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>t;
	for(int i=0;i<n;i++)cin>>k[i];
	int r=1e18,l=0,ans=0;
	while(l<=r) {
		int m=l+(r-l)/2;
		if(isvalid(m)) ans=m,r=m-1;
		else l=m+1;
	}
	cout<<ans<<endl;
}

### Subarray Divisibility
想法: 計算有相同餘數的前綴數量，相減。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	vector<int>v(n);
	int presum=0;
	v[presum]=1;
	for(int i=0;i<n;i++){
		int a;cin>>a;
		presum+=a;
		v[((presum)%n+n)%n]++;
	}
	int ans=0;
	for(auto i:v) ans+=i*(i-1)/2;
	cout<<ans<<endl;
}

### Sum of Three Values
排序、枚舉每項作為中位數，就變為經典的 two-pointer 問題了

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,x;cin>>n>>x;
	vector<pair<int,int>> arr(n);
	for(int i=0;i<n;i++) {
		cin>>arr[i].first;
		arr[i].second=i+1;
	}
	sort(arr.begin(),arr.end());
	for(int i=0;i<n;i++) {
		int l=0,r=n-1,target=x-arr[i].first;
		while(l!=r) {
			if(l!=i && r!=i && arr[l].first+arr[r].first==target) {
				cout<<arr[l].second<<' '<<arr[r].second<<' '<<arr[i].second<<endl;
				return 0;
			}else if(arr[l].first+arr[r].first<target) l++;
			else r--;	
		}
	}
	puts("IMPOSSIBLE");
}

### Sum of Four values
枚舉 2 個 index，然後也是經典 two-pointer 題目

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,x;cin>>n>>x;
	vector<pair<int,int>>a(n);
	for(int i=0;i<n;++i)cin>>a[i].first,a[i].second=i+1;
	sort(a.begin(),a.end());
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int l=j+1,r=n-1;
			while(l<r){
				if(a[i].first+a[j].first+a[l].first+a[r].first==x){
					cout<<a[i].second<<' '<<a[j].second<<' '<<a[l].second<<' '<<a[r].second<<endl;
					return 0;
				}else if(a[i].first+a[j].first+a[l].first+a[r].first<x) l++;
				else r--;
			}
		}
	}
	puts("IMPOSSIBLE");
}

### Subarray Sums I、II

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
unordered_map<int,int>mp;
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,x;cin>>n>>x;
	vector<int>arr(n);
	for(int i=0;i<n;i++)cin>>arr[i];
	int cursum=0,ans=0;
	for(auto i:arr){
		cursum+=i;
		if(cursum==x) ans++;
		if(mp.find(cursum-x)!=mp.end()) ans+=mp[cursum-x];
		mp[cursum]++;
	}
	cout<<ans<<endl;
}

### Array Division
二分搜最大總和

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,k;
vector<int>a(200005);
bool valid(int x){
	int cur=0,cnt=0;
	for(auto i:a){
		if(i>x) return 0;
		if(cur+i>x)cnt++,cur=i;
		else cur+=i;
	}
	cnt+=(cur>0);
	return cnt<=k;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	int l=0,r=1e15,ans=0;
	while(l<=r) {
		int m=l+(r-l)/2;
		if(valid(m)) ans=m,r=m-1;
		else l=m+1;
	}
	cout<<ans<<endl;
}

## DP
### Dice combinations
想法: 轉移式就是扣掉 1~6 點數後方法數的總和。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	vector<int>dp(n+1);
	dp[0]=1,dp[1]=1,dp[2]=2,dp[3]=4,dp[4]=8,dp[5]=16,dp[6]=32;
	for(int i=7;i<=n;i++) {
		for(int j=1;j<=6;j++) {
			(dp[i]+=dp[i-j])%=1000000007;
		}
	}
	cout<<dp[n]%1000000007<<endl;
}

### coin combination I
想法:

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,x;cin>>n>>x;
	vector<int>v(n+1),dp(x+1);
	for(int i=1;i<=n;i++)cin>>v[i];
	dp[0]=1;
	for(int i=1;i<=x;i++){
		for(int j=1;j<=n;j++){
			if(i-v[j]>=0)(dp[i]+=dp[i-v[j]])%=1000000007;
		}
	}
	cout<<dp[x]<<endl;
}

### Removing digits
`dp[i]` 為第 i 個數字最少需要幾次操作才能歸零

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
signed main() {
    fastio;
    int n;
    cin >> n;
    vector<int> dp(1000005,1e9);
    dp[0] = 0;
    for(int i=0; i<=n; i++) {
        for(char c: to_string(i)) dp[i] = min(dp[i], dp[i-(c-'0')]+1);
    }
    cout << dp[n];
}

### Grid paths

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int mod = 1e9+7;
signed main() {
    fastio;
    int n;
    cin >> n;
    vector<vector<int> > dp(n, vector<int>(n,0));
    dp[0][0] = 1;
    for(int i=0; i<n; i++) {
        string row;
        cin >> row;
        for(int j=0; j<n; j++) {
            if(row[j] == '.') {
                if(i > 0) (dp[i][j] += dp[i-1][j]) %= mod;
                if(j > 0) (dp[i][j] += dp[i][j-1]) %= mod;
            }else dp[i][j] = 0;
        }
    }
    cout << dp[n-1][n-1] << endl;
}

### Book shop
想法: 就普通的背包問題，但一開始瘋狂 RE ，我把 `#define int long long` 那行註解掉就修好了，wtf 我還是不知道為何會發生這種事情。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
signed main() {
    fastio;
    int n, x;
    cin >> n >> x;
    vector<int> h(n+1), s(n+1);
    vector<vector<int> > dp(n+1, vector<int>(x+1, 0));
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1; i<=n; i++) cin >> s[i];
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=x; j++) {
            dp[i][j] = dp[i-1][j];
            if(j-h[i] >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-h[i]]+s[i]);
        }
    }
    cout << dp[n][x] << endl;
}

## Graph Algorithms
### Labyrinth
想法: 就 BFS 裸題，但剛開始沒檢查邊界條件，吃了兩個 RE :(

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define f first
#define s second
using namespace std;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> graph(n+1, vector<char>(m+1));
    vector<vector<bool>> vis(n+1, vector<bool>(m+1,0));
    vector<vector<int>> dist(n+1, vector<int>(m+1,0));
    vector<vector<char>> pre(n+1, vector<char>(m+1));
    pii start,end;
    for(int i=1; i<=n; i++) {
        string row;
        cin >> row;
        for(int j=1; j<=m; j++) {
            if(row[j-1] == 'A') {
                start.f = i;
                start.s = j;
            }else if (row[j-1] == '#'){
                vis[i][j] = 1;
            }
            graph[i][j] = row[j-1];
        }
    }
    queue<pii> q;
    q.push(start);
    vis[start.f][start.s] = 1;
    bool isfind = 0;
    vector<int> d{0,1,0,-1,0};
    vector<char> di{'R','D','L','U'};
    int ans = 0;
    while(!q.empty()) {
        pii cur = q.front();
        q.pop();
        vis[cur.f][cur.s] = 1;
        for(int i=0; i<4; i++) {
            int nx = cur.f+d[i];
            int ny = cur.s+d[i+1];
            if(nx>=1 && nx<=n && ny>=1 && ny<=m) {
                if((graph[nx][ny]=='.' || graph[nx][ny]=='B') && vis[nx][ny]==0) {
                    vis[nx][ny] = 1;
                    dist[nx][ny] = dist[cur.f][cur.s]+1;
                    pre[nx][ny] = i;
                    q.push({nx,ny});
                }
                if(graph[nx][ny] == 'B') {
                    isfind = 1;
                    ans = dist[nx][ny];
                    end = {nx,ny};
                    break;
                }
            }
        }
        if(isfind) break;
    }
    // cout << ans << endl;
    if(isfind) {
        cout << "YES\n" << ans << '\n';
        stack<char> paths;
        while(end != start) {
            paths.push(di[pre[end.f][end.s]]);
            end = {end.f-d[pre[end.f][end.s]], end.s-d[pre[end.f][end.s]+1]};
        }
        while(!paths.empty()) {
            cout << paths.top();
            paths.pop();
        }
        cout << '\n';
    }else {
        cout << "NO\n";
    }
}

### Building Roads
想法: DSU

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int p[100001];
int f(int x) {
    if(p[x] == x) return x;
    return p[x] = f(p[x]);
}
signed main() {
    fastio;
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        p[i] = i;
    }
    for(int i=0; i<m; i++) {
        int a,b;
        cin >> a >> b;
        if(f(a) != f(b)) p[f(a)] = p[f(b)];
    }
    vector<pair<int,int>> ans;
    for(int i=2; i<=n; i++) {
        if(f(1) != f(i)) {
            ans.push_back({f(1),f(i)});
            p[f(i)] = p[f(1)];
        }
    }
    cout << ans.size() << endl;
    for(auto i:ans) {
        cout << i.first << ' ' << i.second << endl;
    }
}

### Message Routes
想法: 建圖、BFS

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define f first
#define s second
using namespace std;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> graph[n+1], vis(n+1,0), cnt(n+1,1), pre(n+1, 0);
    while(m--) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    bool isfind = 0;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(auto i:graph[cur]) {
            if(!vis[i]) {
                vis[i] = 1;
                cnt[i] = cnt[cur]+1;
                pre[i] = cur;
                q.push(i);
                if(i == n) {
                    isfind = 1;
                    break;
                }
            }
        }
        if(isfind) break;
    }
    if(isfind) {
        cout << cnt[n] << endl;
        stack<int> ans;
        while(n!=1) {
            ans.push(n);
            n = pre[n];
        }
        ans.push(1);
        while(!ans.empty()) {
            cout << ans.top() << ' ';
            ans.pop();
        }
    }else {
        cout << "IMPOSSIBLE\n";
    }
}

### Shortest Route
想法: dijsktra 裸題

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
signed main() {
    fastio;
    int n, m;
    cin >> n >> m;
    vector<pii> edges[n+1];
    for(int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<int> dis(n+1,1e18);
    dis[1] = 0;
    pq.push({0,1});
    while(!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if(dis[cur.second] != cur.first) continue;
        for(auto i:edges[cur.second]) {
            if(dis[i.first] > dis[cur.second]+i.second) {
                dis[i.first] = dis[cur.second]+i.second;
                pq.push({dis[i.first],i.first});
            }
        }
    }
    for(int i=1; i<=n; i++) {
        cout << dis[i] << ' ';
    }
}

### Shortest Routes II
想法: 裸 Floyd Warshall

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb emplace_back
#define f first
#define s second
using namespace std;
signed main() {
    fastio;
    int n,m,q;
    cin >> n >> m >> q;
    int dis[n+1][n+1];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(i==j) dis[i][j] = 0;
            else dis[i][j] = 1e18;
        }
    }
    while(m--) {
        int a,b,c;
        cin >> a >> b >> c;
        dis[a][b] = min(dis[a][b],c);
        dis[b][a] = min(dis[b][a],c);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            for(int k=1;k<=n;k++) {
                dis[j][k] = min(dis[j][k],dis[j][i]+dis[i][k]);
            }
        }
    }
    while(q--) {
        int a,b;
        cin >> a >> b;
        cout << ((dis[a][b]>1e17)?(-1LL):(dis[a][b])) << endl;
    }
}

### Building teams
想法: 二分圖裸題

#include <bits/stdc++.h>
using namespace std;
vector<bool> color(100001,0);
vector<bool> vis(100001,0);
vector<int> edges[100001];
bool ok = 1;
void dfs(int x) {
    for(auto i:edges[x]) {
        if(!vis[i]) {
            vis[i] = true;
            color[i] = !color[x];
            dfs(i);
        }else {
            if(color[i] == color[x]) {
                ok = false;
                return;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for(int i=1;i<=n;i++) {
        if(!vis[i]) {
            vis[i] = true;
            dfs(i);
        }
    }
    if(ok) {
        for(int i=1;i<=n;i++) {
            cout << ((!color[i])?(1):2) << ' ';
        }
    }else {
        cout << "IMPOSSIBLE\n";
    }
}