---
tags: 成大高階競技程式設計 2020
---
# 2020 高階競程 Contest #5 - 題解
## [小明的數學題](https://judge.csie.ncku.edu.tw/problems/56)
- Task Provider: [CF 1038 B](https://codeforces.com/contest/1038/problem/B)
- Task Setter: raiso
### 首殺 team20_23 (00:09)
### 解法說明
分成兩組:
$\sum\limits_{i = 1}^{n-1} {i} \Rightarrow \frac{(n)(n-1)}{2}$
$\sum\limits_{i = n}^{n} {i} \Rightarrow n$
如果 $n$ 為偶數 $\gcd = {\frac{n}{2}}$
如果 $n$ 為奇數 $\gcd = n$
### 標準程式
:::spoiler
```cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if(n > 2) {
cout << "Yes" << endl;
cout << "1 " << n-1 << endl << n << endl;
for(int i = 1; i < n; i++) cout << (i == 1? "":" ") << i;
cout << endl;
}
else cout << "No" << endl;
return 0;
}
```
:::
## [欠債5億日圓頻道](https://judge.csie.ncku.edu.tw/problems/57)
- Task Provider: Miohitokiri5474
- Task Setter: Miohitokiri5474
### 首殺 team20_33 (00:22)
### 解法說明
裸最短路尋找負環
拿 Bellman-Ford or SPFA 等演算法,假設有任意節點被更新超過 $V-1$ 次即存在負環
### 標準程式
#### Bellman-Ford
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge {
int u, v, w;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<Edge> E(m);
vector<int> s(n + 1, 1e9);
s[n-1] = 0;
for (Edge& e : E) {
cin >> e.u >> e.v >> e.w;
}
for (int i = 0; i < n-1; i++) {
for (const Edge& e : E) {
s[e.v] = min(s[e.v], s[e.u] + e.w);
}
}
bool ok = false;
for (const Edge& e : E) {
if (s[e.v] > s[e.u] + e.w) {
ok = true;
break;
}
}
cout << (ok ? "Yes" : "No") << '\n';
return 0;
}
```
:::
#### SPFA(有加入優化)
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
#define maxN 50005
#define INF 0x3f3f3f3f
typedef pair < int, int > pii;
#define pb push_back
#define F first
#define S second
vector < pii > edges[maxN];
int dis[maxN], cnt2[maxN], cnt[maxN];
bool inQ[maxN], ans;
int main(){
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, m, u, v, now;
deque < int > q;
int w, front = maxN, end = maxN;
cin >> n >> m;
while ( m-- ){
cin >> u >> v >> w;
edges[u].pb ( pii ( v, w ) );
}
memset ( dis, INF, sizeof dis );
for ( int j = 0 ; j < n ; j++ ){
if ( dis[j] != INF )
continue;
dis[j] = 0;
inQ[j] = true;
q.push_back ( j );
while ( !q.empty() ){
inQ[now = q.front()] = false;
q.pop_front();
for ( auto i: edges[now] ){
if ( dis[now] + i.S < dis[i.F] ){
dis[i.F] = dis[now] + i.S;
cnt[i.F]++;
if ( !inQ[i.F] ){
if ( cnt2[i.F] >= 2 )
q.push_front ( i.F );
else{
q.push_back ( i.F );
cnt2[i.F]++;
}
inQ[i.F] = true;
}
}
if ( cnt[i.F] >= n ){
cout << "Yes\n";
return 0;
}
}
}
}
cout << "No\n";
}
```
:::
## [城鎮賽車比賽](https://judge.csie.ncku.edu.tw/problems/58)
- Task Provider: ys
- Task Setter: ys
### 首殺 team20_18 (00:28)
### 解法說明
#### 解法 1
題目中提到賽車的路線是起點與終點相同的迴路,也就是說他是個環 :+1:
如果城鎮就只是一個環的話,那麼只須找到環中成本最小的那路段就行了;
反過來思考,也可以將路段**從大到小一個個排除**,最後那段路段就是要求的。
同理,城鎮若是複雜的連通圖,將所有路段**從大到小一個個選出**,但若**當前選出**的路段與**已選出**的路段形成環,就表示當前選出的路段要設監視器,因為他是**環中最小成本**的路段。
其實上述的過程就是在找一個連通圖中的**最大生成樹** :100:
#### 解法 2
題目中輸入的邊權重 ($c \le 1000$) 非常小,
於是基於 Counting sort 的概念,不需對邊做排序,從最大成本到最小成本使用邊即可。
### 標準程式
#### 解法 1
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e4 + 10;
struct edge { int u, v, w; };
vector<edge> E;
int n, m, group[maxn];
int Find(int v) {
if (v == group[v]) return v;
return group[v] = Find(group[v]); // Path Compression
}
void Union(int u, int v)
{ group[Find(u)] = Find(v); }
int main()
{
scanf("%d%d", &n, &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
E.push_back({a, b, c});
}
for (int v = 1; v <= n; v++) group[v] = v;
sort(E.begin(), E.end(), [&](edge x, edge y) { return x.w > y.w; });
int cost = 0;
for (edge e: E) {
int a = Find(e.u), b = Find(e.v);
if (a != b) Union(e.u, e.v);
else cost += e.w;
}
printf("%d\n", cost);
return 0;
}
```
:::
#### 解法 2
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e4 + 10;
int const maxc = 1e3 + 10;
struct edge { int u, v; };
vector<edge> E[maxc];
int n, m, group[maxn];
int Find(int v)
{ return (v == group[v])? v : group[v] = Find(group[v]); }
void Union(int u, int v)
{ group[Find(u)] = Find(v); }
int main()
{
scanf("%d%d", &n, &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
E[c].push_back({a, b});
}
for (int v = 1; v <= n; v++) group[v] = v;
int cost = 0;
for(int c = maxc-1; c >= 1; c--) {
for(edge e: E[c]) {
int a = Find(e.u), b = Find(e.v);
if (a != b) Union(e.u, e.v);
else cost += c;
}
}
printf("%d\n", cost);
return 0;
}
```
:::
## [藍的競程之旅--山姆機偶性](https://judge.csie.ncku.edu.tw/problems/59)
- Task Provider: [CF 1352 B](https://codeforces.com/contest/1352/problem/B)
- Task Setter: ian
### 首殺 team20_37 (00:38)
### 解法說明
我們的目標是把 $n$ 分成偶數或奇數,最簡單的作法就是分成 $1, 1, 1, ... 剩下的$ 或 $2, 2, 2, ... 剩下的$
$n\ k$ 可以分為幾種狀況
$n$ 偶 $k$ 奇:一定要用偶數構成
$n$ 偶 $k$ 偶:都可以,但用 $1, 1, 1, ...$ 那組可以做出更多數
$n$ 奇 $k$ 奇:一定要用奇數構成
$n$ 奇 $k$ 偶:無法構成
另外當需要使用偶數構成,且 $n < 2k$ 無法構成,當然,在任何情況下 $n < k$ 無法構成。
此外要注意使用 long long
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, m, i, j, k;
cin >> m;
while (m--) {
cin >> n >> k;
if (n < k) {
cout << "NO" << endl;
continue;
}
if (n % 2 && k % 2 == 0) {
cout << "NO" << endl;
continue;
}
if (n % 2 == 0 && k % 2) {
if (n < k * 2) {
cout << "NO" << endl;
continue;
}
cout << "YES" << endl;
while (k-- != 1) {
cout << 2 << " ";
n -= 2;
}
cout << n << endl;
} else {
cout << "YES" << endl;
while (k-- != 1) {
cout << 1 << " ";
n -= 1;
}
cout << n << endl;
}
}
return 0;
}
```
:::
## [AB 的祖先](https://judge.csie.ncku.edu.tw/problems/60)
- Task Provider: Miohitokiri5474
- Task Setter: Miohitokiri5474
### 首殺 team20_38 (00:11)
### 解法說明
就是裸 LCA(我甚至沒有包裝欸,可以回去看進階圖論那週的課程)
作法有三種,倍增法、Tarjan、輕重鍊剖分
標程是用倍增法
### 標準程式
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
#define maxN 100005
#define maxLog 20
#define pb push_back
vector < int > edges[maxN];
int dp[maxN][maxLog], D[maxN], n;
void dfs ( int d, int p, int dep ){
D[d] = dep++;
dp[d][0] = p;
for ( auto i: edges[d] )
if ( i != p )
dfs ( i, d, dep );
}
inline void buildLCA ( void ){
memset ( dp, -1, sizeof dp );
dfs ( 0, -1, 0 );
for ( int k = 1 ; k < maxLog ; k++ )
for ( int i = 0 ; i < n ; i++ )
if ( dp[i][k - 1] != -1 )
dp[i][k] = dp[dp[i][k - 1]][k - 1];
}
inline int findLCA ( int x, int y ){
if ( D[x] < D[y] )
swap ( x, y );
for ( int i = maxLog - 1 ; i >= 0 ; i-- )
if ( dp[x][i] != -1 && D[dp[x][i]] >= D[y] )
x = dp[x][i];
if ( x == y )
return x;
for ( int i = maxLog - 1 ; i >= 0 ; i-- )
if ( dp[x][i] != dp[y][i] )
x = dp[x][i], y = dp[y][i];
return dp[x][0];
}
int main(){
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int q, u, v;
cin >> n >> q;
for ( int i = 1 ; i < n ; i++ ){
cin >> u >> v;
edges[u].pb ( v );
edges[v].pb ( u );
}
buildLCA();
while ( q-- ){
cin >> u >> v;
cout << findLCA ( u, v ) << '\n';
}
}
```
:::