$$\newcommand{\Ord}{\mathcal{O}}$$

安裝日文輸入法

根據不同的作業系統,安裝的方法會有所差異。如果不想要更動太多的設定,可以考慮使用 Google 日文輸入法,有分成瀏覽器插件以及直接安裝在電腦中的版本

Windows 10

  • 開始功能表、時間與語言、地區與語言,新增語言:日本語

Windows 7

  • 輸入法圖示按右鍵、設定
  • 新增語言
  • 選擇日語

MacOS

  • 系統偏好設定、語言與地區、加入日語即可

Ubuntu

sudo apt-get install mozc

使用 Google 輸入工具 (Chrome專用)

點我安裝 Google 輸入工具

  • 右鍵選項,進入設定
  • 新增日本語
  • 左鍵選日本語,變成藍色就表示可以用了

使用 Google 日文輸入法

點我安裝 Google 日文輸入法

安裝他,電腦就會多一個日文的輸入法

基本技巧

解釋 按鍵 輸出
平假名 a
平假名 wo
拗音 sha しゃ
拗音 xyu
daxi だぃ
鼻音 nn
促音 zasshi ざっし
切換片假 Alt + CapsLock neko ネコ
切換平假 Ctrl + CapsLock neko ねき

A. 威廉伯爵的農場

題目大意

給平面座標的三個點,問圍成的三角形面積乘以一個常數 $c$,所有數字都是 int 範圍的整數,$c$ 是 2 的倍數,保證答案可以用 long long 表示

題解

Keys :

  • 向量運算
  • 數值處理

高中數學有提到,兩向量 $\vec{a}$、$\vec{b}$,圍成的平行四邊形面積是 $|\vec{a}\times \vec{b}|$ ,所以這一題的答案就是 $\frac{1}{2}\times c\times |\vec{a}\times \vec{b}|$,其中 $|\vec{a}\times \vec{b}|= |x_ay_b-y_ax_b|$,此外要注意除以 2 的次序避免溢位的問題。

B. ⼤樓彩繪

題目大意

有 $m$ 角柱,角柱的側邊每個面都有 $n\times n$的網格,每個網格有 $c$ 種顏色可以選擇,問有幾種著色方法

題解

Keys :

  • 排列組合
  • Burnside’s lemma
  • 快速冪

一個很顯然的事情是一個面有 $c^{n^2}$ 種不同的塗法,這個數字姑且稱為 $p$ ,那如何計算有多少的塗法呢?

如果知道 Burnside’s lemma 的話就有

$$\frac{1}{m}\sum_{i=1}^{m} p^{\operatorname{gcd}(m,i)}$$

C. 金坷垃運輸網

題目大意

給一張無向圖,問 $a$、$b$ 兩點之間是否存在兩個獨立的路徑,即如果任意地把圖中的一條邊移除, $a$、$b$依舊連通

題解

Keys :

  • Tarjan’s algorithm for Bridge
  • 橋連通分量 BCC

D. 金金金坷垃

題目大意

排一個大小是$n$的「金」

題解

Keys :

  • IO

會寫星星樹就會這題了吧?

E. 農業基地的密碼

題目大意

請輸出一個字串的 Burrows-Wheeler 變換。

題解

Keys :

  • 後綴數組 Suffix Array

$BWT[i]=\begin{cases}T[SA[i]-1], & \text{if }SA[i]>1\\\$&\text{otherwise}\end{cases}$

F. 我們的金坷垃

題目大意

請輸出一個字串最短補成回文的字串中,第$k$大的解

題解

Keys :

  • DP
  • 解答回朔

連結:https://tioj.ck.tp.edu.tw/problems/1497

題目大意

給一個字串,求一個字串的Suffix Array。

題解

AC Code

使用 std::Sort

複雜度為$\Ord(|S|\log^2|S|)$

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
#include<bits/stdc++.h>
using namespace std;

vector<int> sa(string str)
{
int len = str.size();
vector<int> rank(len), sa(len), tmp(len);
for(int i=0;i<len;++i)
{
rank[i] = str[i];
sa[i] = i;
}
sort(sa.begin(), sa.end(), [&](int s, int e){
return rank[s]<rank[e];
});
for(int i=1;i<=len;i*=2)
{
auto val = [&] (int s) { return make_pair( rank[s], s+i<len?rank[s+i]:-1 ); };
sort(sa.begin(), sa.end(), [&](int s, int e){
return val(s) < val(e);
});
tmp[sa[0]]=0;
for(int j=1;j<len;++j)
if( val(sa[j]) == val(sa[j-1]) ) tmp[sa[j]] = tmp[sa[j-1]];
else tmp[sa[j]] = tmp[sa[j-1]] + 1;
rank.swap(tmp);
}
return sa;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string str;

getline(cin, str);
for(int i:sa(str)) cout<<i<<'\n';
}

使用 Radix Sort

複雜度為$\Ord(|S|\log |S|)$

1
//TODO

題目

考慮一張無向的加權圖 $G=\{V,E,w(s,t)\}$,求 $G$ 的生成樹中,權重非嚴格第二大的生成樹。

演算法

  1. 先找出 $G$ 的最小生成樹 $G_{M}=\{V_M,E_M,w_M(s,t)\}$
  2. 設 $S=\emptyset$
  3. 對於所有的邊 $e = \{s,t\} \in E-E_M$
    1. 找到 $G_M$ 中,點 $s$ 到點 $t$ 的路徑上,邊長最長的邊 $e’$
    2. 將 $G_M-e’-e$ 加入至集合 $S$ 中
  4. $S$ 中權重和最小的樹即為所求

證明

先考慮一個樸素作法,因為次小生成樹與最小生成樹至少有一條邊不一樣,因此,可以枚舉最小生成樹的邊,將其刪除之後,再求最小生成樹,那次小生成樹必然會是這$V-1$顆樹中的其中一種。

接下來,可以證明刪掉一條邊的圖,存在一個最小生成樹,與原來的最小生成樹只有一條相異的邊。考慮 Kruskal 演算法,如果把第 $i$ 個加入最小生成樹的邊 $e_i = (s_i, t_i)$ 刪除的話,並不影響加入第 $i$ 條邊之前的決策。接下來,將原來最小生成樹第 $i+1$ 條邊到 $V-1$ 條邊加入這一個新的樹中,那會得到兩個獨立的兩個連通塊 (原來MST砍掉 $s$ 到 $t$ 的邊 ),此時再找到一條最小的邊 $e’$ 將這兩個連通塊接在一起,就形成了一個最小生成樹,且這顆樹只有一條邊與原來的樹不一樣。

為什麼會是最小生成樹呢?因為 $e’$ 必然是 Kruskal 在 $e_i$ 以後才被考慮的邊,且 $e’$ 不會影響加入這一條邊之後的決策。考慮這兩條邊之間的其他邊 $e_m$ 的決策過程:

  1. 如果 $e_m$ 的兩端點不連接 $s_i$, $t_i$ 的連通塊的話,那這條邊的決策就不被影響
  2. 如果 $e_m$ 的兩端點連接 $s_i$, $t_i$ 的連通塊的話,那這條邊就是比 $e’$ 更小連接方法,那與 $e’$ 的定義矛盾,因此不存在這種情形。

因此這個方法會是 Kruskal 的決策過程,故作出來的樹是最小生成樹。因此就可以推出存在一的次小生成樹,是與其最小生成樹相差一條邊的樹。

時間複雜度

  • 步驟 1 若使用 Kruskal’s algorithm,複雜度為 $\Ord(E\log E)$
  • 步驟 3.1 若使用 最近公共祖先 (Lowest Common Ancestor, LCA) 的倍增法,單次可以在 $\Ord(\log V)$ 的時間求出 $e’$
  • 集合 $S$ 實作上,只需要紀錄加入及刪除哪一條邊即可,都可以在 $\Ord(1)$ 時間完成

故可以在 $\Ord(E\log E)$ 的時間求出次小生成樹

連結:https://tioj.ck.tp.edu.tw/problems/1445

題目大意

求連接所有元件的方法中,第一小與第二小的代價是多少,如果不存在輸出$-1$。

題解

求最小生成樹與次小生成樹。最小生成樹很簡單,Kruskal 一下就好了,所以關鍵在如何求次小生成樹。

可以證明存在一個次小生成樹 $T’$ 是最小生成樹 $T$ 加上一條邊 $e’$ 之後,再將形成的環刪除除了 $e’$ 之外的最長邊。

詳細演算法參考這邊:次小生成樹演算法與證明

要如何求一顆樹任兩點間的邊長的最大值呢?可以考慮 LCA的倍增法,在 dp 的同時,也記錄下目前區間的邊長最大值就好了。

該實作時間複雜度為 $\Ord(E\log E+E\log V)$

AC Code

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int N,M;
vector<tuple<int,ll>> V[1001];
vector<tuple<ll,int,int,bool>> E;

int dis[1001], groups;
void init(int n)
{
for(int i=1;i<=n;++i)
dis[i]=i;
groups=n;
}
int find(int a)
{
if( dis[a]==a ) return a;
return dis[a]=find(dis[a]);
}
void U(int a,int b)
{
dis[find(a)]=find(b);
groups--;
}

ll mst()
{
sort(E.begin(), E.end());
init(N);
ll ans=0;
for(auto &[w,s,t,b]:E)
{
if( find(s)!=find(t) )
{
ans+=w;
U(s,t);
b=true;
V[s].emplace_back(t,w);
V[t].emplace_back(s,w);
}
}
if( groups==1 ) return ans;
return -1;
}

const int lgN = 11;
int dp[1001][lgN];
ll mx[1001][lgN];
ll dep[1001];

void dfs(int v, int fa, int ew)
{
dp[v][0]=fa;
mx[v][0]=ew;
for(auto [e,w]:V[v])
{
if( e==fa ) continue;
dep[e]=dep[v]+1;
dfs(e, v, w);
}
}

void build()
{
dep[1]=0;
dfs(1, -1, 0);
for(int i=0;i<lgN-1;++i)
for(int j=1;j<=N;++j)
{
mx[j][i+1] = mx[j][i];
if( dp[j][i+1]==-1 ) dp[j][i] = -1;
else {
mx[j][i+1] = max( mx[j][i+1], mx[dp[j][i]][i] );
dp[j][i+1] = dp[dp[j][i]][i];
}
}
}

int jump(int v, int d, ll &ans)
{
for(int i=0;i<lgN;++i)
{
if( (d>>i)&1 )
{
ans=max(ans, mx[v][i]);
v=dp[v][i];
}
}
return v;
}

ll path(int s, int e)
{
ll ans = 0;
if( dep[s]<dep[e] ) swap(s,e);
s = jump( s, dep[s]-dep[e], ans);
if( s!=e )
{
for(int i=lgN-1;i>=0;--i)
{
if( dp[s][i]!=dp[e][i] )
{
ans = max( ans, mx[s][i] );
ans = max( ans, mx[e][i] );
s = dp[s][i];
e = dp[e][i];
}
}
ans = max({ans, mx[s][0], mx[e][0]});
}
return ans;
}

ll smst(ll mstw)
{
if( (int)E.size() == N-1 ) return -1;
build();
ll ans = LLONG_MAX;
ll tmp;

for(auto &[w,s,t,b]:E)
{
if(b) continue;
tmp = path(s,t);
ans = min( ans, mstw-tmp+w );
}

return ans;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

cin>>N>>M;
int s,t;
ll w, ans1, ans2;
while(M--)
{
cin>>s>>t>>w;
E.emplace_back(w,s,t,false);
}

ans1 = mst();
if( ans1 == -1 ) ans2 = -1;
else ans2 = smst(ans1);

cout<<ans1<<' '<<ans2<<'\n';
}

連結:https://tioj.ck.tp.edu.tw/problems/1037

題目大意

再二維$N\times M$的格子中,有一個起點與終點,今天要從起點走$K$步,每步的距離為$d_i$,方向上下左右任選,如果走超出格子就循環的走,問是否存在一種方法可以走到終點。

題解

一個很暴力的$\Ord(KNM)$動態規劃,因為複雜度看起來很危險,但時間挺寬鬆的,所以對細節做了一些優化,然後就過了,而且還頗快的

AC Code

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
#include<bits/stdc++.h>
using namespace std;

bool dp[2][100][100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int N,M,T,d1,d2;
int sx,sy,ex,ey;
cin>>N>>M>>sx>>sy>>ex>>ey;
cin>>T;

dp[0][sx][sy]=1;

#define add(x,y,n) ( x+y<n?x+y:x+y-n )
#define del(x,y,n) ( x-y>=0?x-y:x-y+n )
for(int k=1;k<=T;++k)
{
cin>>d1;
d2=d1%M;
d1%=N;
for(int i=0;i<N;++i)
for(int j=0;j<M;++j)
dp[k&1][i][j] = dp[(k-1)&1][add(i,d1,N)][j] |
dp[(k-1)&1][del(i,d1,N)][j] |
dp[(k-1)&1][i][add(j,d2,M)] |
dp[(k-1)&1][i][del(j,d2,M)] ;
}

if(dp[T&1][ex][ey])cout<<"YES\n";
else cout<<"NO\n";
}

連結:https://tioj.ck.tp.edu.tw/problems/2037

題目大意

題目寫得很亂,總結一下:給一張二分圖,問最小點覆蓋是多少,即要最少要選幾個點,才能使每一條邊至少有一端點被選中。

題解

二分圖上有
$$\text{最大匹配}=\text{最小點覆蓋}$$

證明待補,完整的證明我有用到cut。可以直接用匈牙利演算法 (Kőnig’s theorem) 簡單的求出最大匹配。

AC Code

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
#include<bits/stdc++.h>
using namespace std;
vector<int> V[100001];
int m[100001];

int P,Q,K,T,s,t;

bool used[100001];
bool dfs(int v)
{
for(int e:V[v])
{
if(used[e])continue;
used[e]=true;
if( m[e]==-1 || dfs(m[e]) )
{
m[e]=v;
return true;
}
}
return false;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

cin>>T;
while(T--)
{
cin>>P>>Q>>K;
for(int i=1;i<=P;++i)V[i].clear();
for(int i=1;i<=Q;++i)m[i]=-1;
while(K--)
{
cin>>s>>t;
V[s].emplace_back(t);
}

int ans = 0;
for(int i=1;i<=P;++i)
{
memset(used,0,Q+1);
if(dfs(i))ans++;
}
cout<<ans<<'\n';
}
}

連結:https://tioj.ck.tp.edu.tw/problems/1443

題目大意

$$F(n)=\begin{cases}0&\text{if }n=0\\F([\frac{n}{2}])+n-2[\frac{n}{2}]&\text{otherwise}\end{cases}$$

給定$n$,問$F(0),F(1)\dots, F(n)$中的最大值為何。

題解

如果仔細觀察一下,$F(n)$的結果是$n$寫成二進位時有多少$1$,因此這題要問的答案就很明顯了,就是到數字$n$二進位最多有幾個$1$。答案等於$\lfloor\log_2{(N+1)}\rfloor$。

這裡做法有點懶惰,直接用python大數算,速度跟自己開大數模板差不多。

AC Code

1
2
import math
print(math.floor(math.log(int(input())+1,2)))

連結:https://tioj.ck.tp.edu.tw/problems/1704

題目大意

今天有$N$個橘子,每個橘子都有相異的重量。今天要挑出一些橘子,由重量小到大吃掉這些橘子。已知第 $i$ 在第 $j$ 順位吃掉的話,那就有$A_{i,j}$的飽足感。問至少要吃幾顆橘子才能有至少$k$的飽足感

題解

可以考慮動態規劃。先將橘子由小到大排序,用$p_i$表示排完序後的橘子,原來的編號是什麼,設$dp[i][j]$表示全部吃了$j$個橘子,且最後一顆是$p_i$的最大飽足度,那可以很輕鬆地發現

$$dp[i][j] = A_{p_i,j} + \max_{j=1,2,\dots i-1}\{dp[i-1][j]\}$$

因為max的部分可以在$O(1)$時間解決掉,故該方法可以在$O(N^2)$的時間找出滿足條件答案。

AC Code

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
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> d;

int m[2001][2001];
int dp[2001];

int calc(int N, int K)
{
for(int j=1;j<=N;++j)
{
int mx = dp[j-1];
for(int i=j;i<=N;++i)
{
int tmp = dp[i];
dp[i] = mx + m[ d[i-1].second ][j];
mx = max(mx, tmp);
if( dp[i] >=K ) return j;
}
}
return -1;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int N,K,W;
cin>>N>>K;
for(int i=1;i<=N;++i)
{
cin>>W;
d.emplace_back(W,i);
}
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
cin>>m[i][j];
sort(d.begin(), d.end());
cout<<calc(N, K)<<'\n';
}

連結:https://tioj.ck.tp.edu.tw/problems/1418

題目大意

有$N$位同學要每三個人湊成一組,每湊成一組可以計算出一個雷度,問要怎麼湊才能使整體雷度最低。

題解

這題目名稱感覺挺容易起爭議的,而且這題時限我覺得設計的很差,只有特定的實作才能過最後一筆。

如果不記最後一筆,可以很簡單的用位元DP處裡掉,因為可以任選三人,DP時因此可以固定先選一人,再任選兩人,讓枚舉的複雜度變低,可以再$O(N^2 2^N)$的時間完成。

$$dp[S]=\begin{cases}0 & \text{if }S=\emptyset \\ \min\{dp[S-\{i,j,k\}]+v[i][j]+v[j][k]+v[k][i]\}&\text{otherwise}\end{cases}$$

其中 $i,j,k\in S$

要過最後一筆,我試過先提出可以用行的數字放在新的陣列中處裡,不過這樣反而讓其他的優化處理變差。然後參考網路上有的實作,DP變成向後更新數字,然後就過了,我覺得很莫名。約有4倍的速度差,我個人認為是這樣處裡能留下的快取比向前的還要來的多,不過一般出題卡這種細節我覺得不太行。

AC Code

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
#include<bits/stdc++.h>
using namespace std;
int dp[1<<21];
int R[21][21];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int T,N;
cin>>T;

while(T--)
{
cin>>N;
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
cin>>R[i][j];

int ans = (1<<N)-1;
#define test_bit(a,b) ((a)&(1<<(b)))
#define pw(a) (1<<(a))
#define pr(i,j,k) (pw(i)|pw(j)|pw(k))
int i,j,k;
memset(dp, 0x3f, sizeof(int)*(1+ans));
dp[0]=0;
for(int v=0;v<ans;++v)
{
if(dp[v]==0x3f3f3f3f)continue;
i=__builtin_ctz(~v);

for(j=i+1;j<N;++j)
if( !test_bit(v,j) )
{
for(k=j+1;k<N;++k)
if( !test_bit(v,k) )
if( dp[v|pr(i,j,k)] > dp[v]+R[i][j]+R[j][k]+R[k][i] )
dp[v|pr(i,j,k)] = dp[v]+R[i][j]+R[j][k]+R[k][i];
}
}
cout<<dp[ans]<<'\n';
}
}