心得
因為11月要去比北市賽
今天解了去年北市賽的題目
（早自習30分鐘+午休30分鐘+四節下課10分鐘+無數的上課思考）
不過五題只解了四題 第五題還沒看（11/1已補）
距離北市賽 還有37天！ 希望有機會進全國賽
第一題： 出戰順序 (Arrangement)
TIOJ 2169:
https://tioj.ck.tp.edu.tw/problems/2169
有練過不少題目的人應該都知道有個問題叫做「約瑟夫斯問題」
這個問題有很多不同的解法
有的人可能用Treap之類的資料結構來達到 $O(n log n)$的解
不過這個問題有線性的 $O(n)$ 解1
2
3
4int tmp = 0;
for(int i = 2;i <= n;i++){
tmp = (tmp+t)%i;
}
題目的要求為 給予一個最後的數字 問 $m$ 應為多少
這題的範圍是 $1 \leq n,k \leq 10^4$
而 $m$ 則為 $2 \leq m \leq 3 \times 10^4$
因此我們可以暴搜找出 $m$ 值
複雜度: $O(30000 \times k)$
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
signed main(){
fastio
int n,k;
cin >> n >> k;
for(int t = 2;t <= 30000;t++){
int tmp = 0;
for(int i = 2;i <= n;i++){
tmp = (tmp+t)%i;
}
tmp++;
if(tmp==k){
cout << t << "\n";
return 0;
}
}
cout << 0 << "\n";
}
第二題：地圖編修 (Map)
TIOJ 2170:
https://tioj.ck.tp.edu.tw/problems/2170
這一題第一眼看上去，以為是向量投影
不過仔細想一想，這題從題目的說明上看來
其實只要解模方程 題目給了 $n$ 個方程式
1 | 2 101 2 101 |
因此我們有了一個一元模方程組
要用電腦解方程式有很多作法
用矩陣的解法
$\begin{bmatrix}3 & 2 \\ 1 & 2\end{bmatrix} \begin{bmatrix}x \\ y \end{bmatrix} = \begin{bmatrix}5 \\ 3 \end{bmatrix}$
或者克拉瑪公式
以及這題需要使用的高斯消去法
高斯消去法是基於加減消去法 運用矩陣的列運算來求解
$\begin{bmatrix}3(x) & 2(y) & 5 \\ 1(x) & 2(y) & 3 \end{bmatrix}$
只要我們能夠用列運算將原本的矩陣化為
$\begin{bmatrix}1(x) & 0(y) & x \\ 0(x) & 1(y) & y \end{bmatrix}$
最後一行就會是所有我們要求解的變數了
而使用高斯消去法解模方程就只是在運算時去執行模運算而已
至於如何進行列運算來轉化矩陣 就是留給讀者的練習了
複雜度： $O(n^3logm)$ （備註：$logm$是因為求模逆元）
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using namespace std;
const int N = 105;
int MOD;
int fastpow(int n, int p){
int res = 1;
while(p){
if(p&1) res = (res * n)%MOD;
n = (n*n)%MOD;
p>>=1;
}
return res;
}
int arr[N][N];
signed main(){
fastio
int n;
cin >> n >> MOD;
for(int i = 1;i <= n+1;i++){
for(int j = 1;j <= n;j++){
cin >> arr[j][n-i+2];
}
}
for(int i = 1;i <= n;i++){
if(!arr[i][i]){
//若arr[i][i]為0 與其他行交換 將arr[i][i]變為其他數字
bool ok = true;
int row = 0;
for(int j = i+1;j <= n+1;j++){
if(arr[j][i]){
ok = false;
row = j;
break;
}
}
if(ok) continue;
for(int j = 1;j <= n+1;j++){
swap(arr[i][j],arr[row][j]);
}
}
int tmp = arr[i][i];
//將這一行同除arr[i][i] 使arr[i][i]變為1
for(int j = i;j <= n+1;j++){
arr[i][j] = arr[i][j] * fastpow(tmp,MOD-2)%MOD;
}
for(int j = 1;j <= n;j++){
if(i==j) continue;
tmp = arr[j][i];
for(int k = 1;k <= n+1;k++){
arr[j][k] = ((arr[j][k]%MOD - arr[i][k]%MOD*tmp%MOD)%MOD+MOD)%MOD;
}
}
}
for(int i = n;i;i--) cout << (arr[i][n+1]+MOD)%MOD << " ";
}
第三題：打卡遊戲 (Checkin)
TIOJ 2171:
https://tioj.ck.tp.edu.tw/problems/2171
圖論題
這題目其實我看了一陣子才理解
題目給的是一張有$A+B$ 個節點與 $k$ 條邊的圖（不一定完全連通）
而 $S,M$ 的數值對於這題來說其實完全用不到
要用最少車資完成遊戲 我們可以推得
距離和不論怎麼做都不會改變
因此我們可以將題目的「最少車資」改為「搭乘最少數量」
而我們要找尋搭乘的最少數量
我們可以很輕易的知道 如果有 $n$ 個連通塊
我們至少要做 $n$ 次才能走完所有邊
而每個連通塊需要的次數 我們可以由「一筆畫定理」得知
因此本題的答案就是
複雜度 $O(A+B+K)$
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
const int N = 1005;
vector<int> adj[N];
int ans = 0, visited[N];
int odd = 0;
void dfs(int u){
visited[u] = 1;
if(adj[u].size()&1) odd++;
for(auto v : adj[u]){
if(!visited[v]) dfs(v);
}
}
signed main(){
fastio
int a,b,s,m,k;
cin >> a >> b >> s >> m >> k;
for(int i = 0;i < k;i++){
int u,v,w;
cin >> u >> v >> w;
//v starts from a+1
adj[u].push_back(a+v);
adj[a+v].push_back(u);
}
for(int i = 1;i <= a+b;i++){
if(visited[i]||adj[i].size()==0) continue;
odd = 0;
dfs(i);
ans += max(odd/2,1);
}
cout << ans << "\n";
}
第四題：物種演化 (Evolution)
TIOJ 2172:
https://tioj.ck.tp.edu.tw/problems/2172
這題是非常裸的樹上兩點最短距離
就用倍增法或樹壓平找LCA
之後用 $d = dep[u] - 2*dep[lca(u,v)] + dep[v]$就是答案
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
const int N = 1e5+5;
vector<int> adj[N];
int dep[N], fa[N][25];
void dfs(int u, int par){
for(int v : adj[u]){
if(v==par) continue;
dep[v] = dep[u]+1;
fa[v][0] = u;
dfs(v,u);
}
}
int lca(int x, int y){
if(dep[x] < dep[y]) swap(x,y);
int diff = dep[x]-dep[y];
for(int i = 20;~i;i--){
if((1<<i)&diff){
x = fa[x][i];
}
}
if(x==y){
return x;
}
for(int i = 20;~i;i--){
if(fa[x][i]!=fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
x = fa[x][0];
return x;
}
signed main(){
fastio
int n,m;
cin >> n >> m;
for(int i = 1;i < n;i++){
int u,v;
cin >> u >> v;
u++,v++;
adj[u].push_back(v);
adj[v].push_back(u);
}
dep[1] = 0;
dfs(1,1);
for(int i = 1;i <= 20;i++){
for(int j = 1;j <= n;j++){
fa[j][i] = fa[fa[j][i-1]][i-1];
}
}
while(m--){
int x,y;
cin >> x >> y;
x++,y++;
cout << dep[x]+dep[y]-2*dep[lca(x,y)] << "\n";
}
}
第五題：搜集寶藏（Treasure）
TIOJ 2173:
https://tioj.ck.tp.edu.tw/problems/2173
(11/1 補)
這題是一個兩條路徑的DP問題，因此，我們要思考如何去紀錄兩條路線拿到寶藏的最大值，我們可以設 $dp[t][i][j]$ 為在時間 $t$ 的時候，第一個人的縱座標在 $i$，第二個人的縱座標在 $j$，然後我們就可以從前一個時間轉移到現在這個時間（這個條件使得我們可以用滾動DP來加速，是說沒有那個必要就是了）
1 |
|