---
tags: 成大高階競技程式設計 2020
---
# 2020 高階競程 Contest #2 - 題解
## [藍的競程之旅--藍的夢](https://judge.csie.ncku.edu.tw/problems/25)
- Task Provider:ian
- Task Setter:ian
### 首殺 team20_23 (00:04)
### 解法說明
因為記憶體很小所以不能開陣列儲存數字,只能用 counting sort 解
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, tmp, i;
int cnt[110];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for (i = 0; i < n; i++) {
cin >> tmp;
cnt[tmp]++;
}
for (i = 100; i > 0; i--) {
while (cnt[i] --> 0) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
:::
## [數根](https://judge.csie.ncku.edu.tw/problems/26)
- Task Provider:ian
- Task Setter:ian
### 首殺 team20_49 (00:14)
### 解法說明
仔細看就會發現每九個就會重複一輪,所以就有以下的公式解
### 標準程式
:::spoiler
```cpp
#include <iostream>
using namespace std;
int main(void) {
long long int n, a, b;
cin >> n;
while (n --) {
cin >> a >> b;
cout << b + 9 * (a - 1) << '\n';
}
return 0;
}
```
:::
## [喵嗚朋友](https://judge.csie.ncku.edu.tw/problems/27)
- Task Provider:Miohitokiri5474
- Task Setter:Miohitokiri5474
### 首殺 -- (-:-)
### 解法說明
想法很簡單,先將陣列開兩倍
一個人有兩個點 $i, i + n$ ,一個是紀錄朋友用的,另外一個是敵人
所以:
1. 如果 $a, b$ 是朋友,則 $a, b$ 應該要屬於同一個集合( $a + n, b + n$ 也屬於同一個集合)
2. 如果 $a, b$ 是敵人,則 $a, b + n$ 應該要屬於同一個集合( $a + n, b$ 也屬於同一個集合)
換成 code 的話應該會變成這樣:
- 如果 $a, b$ 是朋友
- Union ( a, b ), Union ( a + n, b + n );
- 如果 $a, b$ 是敵人
- Union ( a, b + n ), Union ( a + n, b );
換個簡單的說法,只要關係線有跨過 $n$ 就算是敵人
### 標準程式
#### 解法 1
:::spoiler
```cpp
// by. MiohitoKiri5474
#include<bits/stdc++.h>
using namespace std;
#define maxN 200005
int dis[maxN], sz[maxN];
inline void init ( void ){
for ( int i = 0 ; i < maxN ; i++ )
dis[i] = i;
}
int find ( int a ){
return dis[a] == a ? a : dis[a] = find ( dis[a] );
}
inline void Union ( int a, int b ){
dis[find ( a )] = find ( b );
}
inline bool same ( int a, int b ){
return find ( a ) == find ( b );
}
int main(){
ios::sync_with_stdio ( false );
cin.tie ( 0 );
int n, m, a, b, type, an, bn;
cin >> n >> m;
init();
while ( m-- ){
cin >> type >> a >> b;
an = a + n, bn = b + n;
if ( type == 1 ){
if ( same ( a, bn ) || same ( an, b ) ){
cout << "nani\n";
continue;
}
Union ( a, b );
Union ( an, bn );
}
else if ( type == 2 ){
if ( same ( a, b ) || same ( an, bn ) ){
cout << "nani\n";
continue;
}
Union ( a, bn );
Union ( b, an );
}
else if ( type == 3 ){
if ( same ( a, b ) || same ( an, bn ) )
cout << "friend\n";
else if ( same ( an, b ) || same ( a, bn ) )
cout << "enemy\n";
else
cout << "none\n";
}
}
}
```
:::
#### 解法 2
:::spoiler
可以把 dsu 的值直接加負號如以下:
```cpp
#include<bits/stdc++.h>
// by 藍
using namespace std;
int dsu[100005];
int findroot(int x){
if(x > 0){
if(dsu[x] == x) return x;
return dsu[x] = findroot(dsu[x]);
}
else {
if(dsu[-x] == -x) return x;
dsu[-x] = findroot(dsu[-x]);
return -dsu[-x];
}
}
int main() {
int n,m;
cin.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<=n;i++) {
dsu[i]=i;
}
int a,b,c;
while(m--) {
cin>>c>>a>>b;
a++;b++;
if(c==1){
if(findroot(a) == -findroot(b)){
cout<<"nani"<<'\n';
continue;
}
findroot(a);
if(dsu[a]>0)
dsu[findroot(a)] = findroot(b);
if(dsu[a]<0)
dsu[-findroot(a)] = -findroot(b);
}
if(c==2){
if(findroot(a) == findroot(b)){
cout<<"nani"<<'\n';
continue;
}
findroot(a);
if(dsu[a]>0)
dsu[findroot(a)] = -findroot(b);
if(dsu[a]<0)
dsu[-findroot(a)] = findroot(b);
}
if(c==3){
if(findroot(a) == findroot(b)){
cout<<"friend\n";
}
else if(-findroot(a) == findroot(b)){
cout<<"enemy\n";
}
else{
cout<<"none\n";
}
}
}
return 0;
}
```
:::
## [都市滑翔](https://judge.csie.ncku.edu.tw/problems/28)
- Task Provider:leo900807
- Task Setter:leo900807
### 首殺 -- (-:-)
### 解法說明
本題要找出有幾組 $i,j,k$ 符合 $a_i>a_j>a_k$ ,也就是「三元逆序數對」。
#### Subtask 1 $\ \ \ O(N^3)$
用迴圈尋找所有的 $i,j,k$ ,並判斷是否符合 $a_i>a_j>a_k$ 。
#### Subtask 2 $\ \ \ O(N^2)$
每次 $O(N)$ 尋找有多少的 $i<j$ 且 $a_i>a_j$ 以及 $k>j$ 且 $a_j>a_k$ ,並將兩者相乘即是以 $a_j$ 為中間的三元逆序數對數量,只要枚舉所有的 $j$ 並加總即可。
#### Subtask 3 $\ \ \ O(N+N\ \log\ N)$
有了 Subtask 2 的想法後,可以將其改良,利用 merge sort 計算對於每個數字有多少比自己大的數字在前面,多少比自己小的數字在後面,最後相乘加總即可。
<font color="red">註:因為 $a_i$ 到 $10^9$,所以需離散化。</font>
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <algorithm>
#define F first
#define S second
using namespace std;
pair<int, int> a[800000];
long long tmp[800000], comb[800000][2], n;
void mergesort(int l, int r){
int i, j, k, mid;
if(l == r)
return;
mid = (l + r) / 2;
mergesort(l, mid);
mergesort(mid + 1, r);
for(i = k = l, j = mid + 1; i <= mid && j <= r;){
if(a[i] <= a[j]){
comb[a[i].F][1] += j - (mid + 1);
tmp[k++] = a[i++].F;
}
else{
comb[a[j].F][0] += mid - i + 1;
tmp[k++] = a[j++].F;
}
}
while(i <= mid){
comb[a[i].F][1] += r - (mid + 1) + 1;
tmp[k++] = a[i++].F;
}
while(j <= r)
tmp[k++] = a[j++].F;
for(i = l; i <= r; i++)
a[i].F = tmp[i];
}
inline bool restore(const pair<int, int> &a, const pair<int, int> &b){
return a.S < b.S;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
long long count = 0;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i].F, a[i].S = i;
sort(a, a + n);
for(int i = 0; i < n; i++)
a[i].F = i;
sort(a, a + n, restore);
mergesort(0, n - 1);
for(int i = 0; i < n; i++)
count += comb[i][0] * comb[i][1];
cout << count << "\n";
}
```
:::
## [和諧的圖](https://judge.csie.ncku.edu.tw/problems/29)
- Task Provider:ys
- Task Setter:raiso
### 首殺 -- (-:-)
### 解法說明
#### 解法 1
假設有點 $l < r$,$l$ 和 $r$ 相連,但 $\forall m. l < m < r$ 都沒有和 $l, r$ 相連,那麼就得把這些 $m$ 給加進圖裡 (有 $l, r$ 的這個圖)
換句話說,所有含有這種 $l, r$ 的連通塊,要和其他連通塊相連形成和諧的連通塊
例如圖中有這 5 個連通塊:
1. $1, 5, 6$
2. $2, 3$
3. $4$
4. $7, 8$
5. $9$
那麼 1 號連通塊滿足上述性質(不和諧),所以從小到大要把 $2, 3, 4$ 這幾個數字納入 1 號連通圖
接著圖就會變成:
1. $1, 2, 3, 4, 5, 6$
2.
3.
4. $7, 8$
5. $9$
這樣整個圖就和諧了。
實作上會採用 Union-Find forest 作為**不同連通塊**之間的判斷
首先一個個數字 $l$ 去檢驗,含有 $l$ 的連通塊,是否和諧?
```cpp
for(int l = 1; l <= n; l++) {
:
.
}
```
也就是對於當前 $l$ 到該連通塊中**最大的數** $r$ 中所有 $m$,判斷 $m$ 是否在連通塊中,不在的話就把 $m$ 加進去 (加 1 條邊)
```cpp
for(int m = l+1; m <= mx[Find(l)]; m++) {
if(Find(l) == Find(m)) continue;
else Union(l, m);
}
```
> `mx[Find(l)]` 為含有 $l$ 的連通塊中的最大數,也就是 $r$
> 如何維護連通塊中的最大數請參考標準程式
實作的概念大致上是這樣,可是複雜度還是*過高*
但可以觀察到:
1. $1, 2, 3, 4, 5, 6$
4. $7, 8$
5. $9$
已經把 1 號連通塊和諧了,那麼下個數就挑 $7$ (1 號中最大數 $6$ 的下個數)
然後嘗試把含有 $7$ 的 2 號連通塊和諧
> 雖然它早已和諧 :+1:
也就是說若含 $l$ 的連通塊已和諧,則下個欲選擇的連通塊可挑含 $l$ 連通塊中最大數的下個數:
```cpp
for(int l = 1, m; l <= n; l=m) {
for(m = l+1; m <= mx[Find(l)]; m++) {
if(Find(l) == Find(m)) continue;
Union(l, m);
}
}
```
### 標準程式
#### 解法 1
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 10;
int n, m, gp[maxn], mx[maxn]; // gp := group, mx := maximum of group
int Find(int v) {
if(v == gp[v]) return v;
int rt = Find(gp[v]); // rt := root of the group
mx[rt] = max(mx[rt], mx[v]);
return gp[v] = rt;
}
void Union(int u, int v) {
int a = Find(u), b = Find(v);
gp[a] = b;
mx[a] = mx[b] = max(mx[a], mx[b]);
}
int main()
{
scanf("%d%d", &n, &m);
for(int v = 1; v <= n; v++) gp[v] = mx[v] = v;
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
Union(u, v);
}
int cnt = 0;
for(int u = 1, v; u <= n; u=v)
for(v = u+1; v <= mx[Find(u)]; v++) {
if(Find(u) == Find(v)) continue;
Union(u, v);
cnt++;
}
printf("%d\n", cnt);
return 0;
}
```
:::
#### 解法 2
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> boss;
vector< pair<int, int> > bound; //定義一個連通圖的上下界
int fboss(int a) {
return boss[a] = (boss[a] == a)? a: fboss(boss[a]);
}
int main() {
cin >> n >> m;
boss.resize(n);
bound.resize(n);
for(int i = 0; i < n; i++) {
boss[i] = i;
bound[i] = make_pair(i, i);
}
for(int i = 0; i < m; i++) {
int a, b;
int ba, bb;
cin >> a >> b;
a--, b--;
ba = fboss(a);
bb = fboss(b);
boss[bb] = ba;
}
for(int i = 0; i < n; i++) {
int bs = fboss(i);
if(bs != i) bound[i].first = bound[i].second = 2e9;
bound[bs].first = min(bound[bs].first, i);
bound[bs].second = max(bound[bs].second, i);
}
int ans = 0;
sort(bound.begin(), bound.end());
for(int i = 0; i < n-1 && bound[i+1].first < 1e9; i++) {
int j = i+1;
int upperb = bound[i].second;
while(upperb >= bound[j].first) {
upperb = max(upperb, bound[j].second);
ans++, j++;
}
i = j-1;
}
cout << ans << endl;
return 0;
}
```
:::
## [母牛與農地](https://judge.csie.ncku.edu.tw/problems/30)
- Task Provider:ys
- Task Setter:raiso
### 首殺 team20_12 (02:05)
### 解法說明
#### 解法 1
明顯的,在加入一條邊之後或多或少會讓最短路更短
- 如果更短了,肯定是最短路徑用了新加的這條邊
- 如果沒有改善,那就是最短路徑沒有改走新加的邊
也就是說,只需關心**當最短路徑用了新加的邊**的狀況
那麼設此邊為 $(a, b)$ 則要讓 $1 \rightsquigarrow n$ 盡量長,
而路徑是 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 或 $1 \rightsquigarrow b \to a \rightsquigarrow n$
> 這裡 $x \rightsquigarrow y$ 是 $x$ 到 $y$ 的最短路徑
設 $d_x(y)$ 為 $x \rightsquigarrow y$ 的長度
> 則 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 的長度就是 $d_1(a) + 1 + d_n(b)$
若最短路徑是 $1 \rightsquigarrow a \to b \rightsquigarrow n$
則長度會有 $d_1(a) + 1 + d_n(b) \le d_1(b) + 1 + d_n(a)$
而任意特殊點對(邊) $(a, b)$ 都得滿足此不等式,也就是例如有點對 $(a, b), (b, c), (c, a)$
會有三個不等式要滿足,假設為
$d_1(a) + 1 + d_n(b) < d_1(b) + 1 + d_n(a)$
$d_1(b) + 1 + d_n(c) < d_1(c) + 1 + d_n(b)$
$d_1(c) + 1 + d_n(a) < d_1(a) + 1 + d_n(c)$
> 在特殊點為三個以上,就不會出現等於關係了
會發現這些不等式能化簡成
$d_1(a) - d_n(a) < d_1(b) - d_n(b)$
$d_1(b) - d_n(b) < d_1(c) - d_n(c)$
$d_1(c) - d_n(c) < d_1(a) - d_n(a)$
再化簡
$\underline{d_1(a) - d_n(a)} < d_1(b) - d_n(b) < d_1(c) - d_n(c) < \underline{d_1(a) - d_n(a)}$
會發現得得到矛盾的結論
所以須從確定的結論往前推,不失一般性的,設有
$d_1(a) - d_n(a) < d_1(b) - d_n(b) < d_1(c) - d_n(c)$
則回推的不等式為
$d_1(a) + 1 + d_n(b) < d_1(b) + 1 + d_n(a)$
$d_1(b) + 1 + d_n(c) < d_1(c) + 1 + d_n(b)$
$d_1(a) + 1 + d_n(c) < d_1(c) + 1 + d_n(a)$
所以要比較這三者的大小 $d_1(a) + 1 + d_n(b), d_1(b) + 1 + d_n(c), d_1(a) + 1 + d_n(c)$
推廣至一般狀況,若是 $d_1(a_1)-d_n(a_1) < d_1(a_2)-d_n(a_2) < \cdots < d_1(a_k)-d_n(a_k)$
則可只比較所有 $d_1(a_x) + 1 + d_n(a_y)$ 其中 $1 \le x < y \le k$
#### 解法 2
同樣只關心有加入新邊的情況
設特殊點 $a, b$ 滿足 $d_1(a) < d_1(b)$ 有雙向邊 $(a, b)$,則有三種情況需考慮﹔
- $d_1(n) < d_1(a) < d_1(b)$
最短路徑不經過 $a, b$
- $d_1(a) < d_1(n) < d_1(b)$
最短路徑不經過 $b$
- $d_1(a) < d_1(b) < d_1(n)$
$d_1(a) + 1 < d_1(b) + 1$,且 $d_n(b)$ 與 $d_n(a)$ 只相差 $1$
若是 $x \in \{a, b\}. d_1(x) + d_n(x) > d_1(n)$,則最短路徑不經過 $x$。
由上推得 $d_1(a) + 1 + d_n(b) \le d_1(b) + 1 + d_n(a)$
所以特殊點依照 BFS 的深度排列,比較所有 $d_1(a_x) + 1 + d_n(a_y)$ 其中 $1 \le x < y \le k$ 得解
### 標準程式
#### 解法 1
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 10;
int n, m, k, x, y;
vector<int> E[maxn], a;
void bfs(int s, vector<int> &d) {
queue<int> q;
set<int> vis;
q.push(s);
vis.insert(s);
d[s] = 0;
while(q.size()) {
int u = q.front(); q.pop();
for(int v: E[u]) {
if(vis.count(v)) continue;
vis.insert(v);
d[v] = d[u] + 1;
q.push(v);
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
a.resize(k);
for(int i = 0; i < k; i++) scanf("%d", &a[i]);
for(int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
E[x].push_back(y);
E[y].push_back(x);
}
vector<int> d1(n+1), dn(n+1);
bfs(1, d1);
bfs(n, dn);
sort(a.begin(), a.end(), [&](int x, int y) { return d1[x]-dn[x] < d1[y]-dn[y]; });
int ans = 0, d1_mx = 0;
for(int i = 0; i+1 < k; i++) {
d1_mx = max(d1_mx, d1[a[i]]);
ans = max(ans, d1_mx + 1 + dn[a[i+1]]);
}
printf("%d\n", min(ans, d1[n]));
return 0;
}
```
:::
#### 解法 2
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 10;
int n, m, k, a, x, y;
vector<int> E[maxn], ord; // ord := order
vector<bool> sp; // sp := special
void bfs(int s, vector<int> &d) {
queue<int> q;
q.push(s);
d.assign(n+1, -1);
d[s] = 0;
while(q.size()) {
int u = q.front(); q.pop();
if(s == 1 && sp[u]) ord.push_back(u);
for(int v: E[u]) {
if(d[v] != -1) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
sp.assign(n+1, false);
for(int i = 0; i < k; i++) scanf("%d", &a), sp[a] = true;
for(int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
E[x].push_back(y);
E[y].push_back(x);
}
vector<int> d1, dn;
bfs(1, d1);
bfs(n, dn);
int ans = 0, d1_mx = 0;
for(int i = 0; i+1 < ord.size(); i++) {
d1_mx = max(d1_mx, d1[ord[i]]);
ans = max(ans, d1_mx + 1 + dn[ord[i+1]]);
}
printf("%d\n", min(ans, d1[n]));
return 0;
}
```
:::