---
tags: 成大高階競技程式設計 2020
---
# 2020 高階競程 Contest #7 - 題解
## [Digital Firends 3](https://judge.csie.ncku.edu.tw/problems/72)
- Task Provider: raiso
- Task Setter: raiso
### 首殺 team20_23 (00:06)
### 解法說明
這題就是一棵樹去遍歷,以 $k$ 開始當作樹根,找到每個節點的父節點,就結束了。
這題的考點還有一個就是會使用輸入輸出加速,這樣你就成功了!
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 1;
int vis[maxn];
set<int> lk[maxn];
queue< pair<int, int> > Q;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q, k;
cin >> n >> m >> q >> k;
for(int i = 0; i <= n; i++) vis[i] = -1;
for(int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
lk[a].insert(b);
lk[b].insert(a);
}
Q.push(make_pair(k, k));
//(pre, tar)
while(!Q.empty()) {
auto nw = Q.front(); Q.pop();
int tar = nw.second;
int pre = nw.first;
if(vis[tar] != -1) continue;
vis[tar] = pre;
for(auto i: lk[tar]) if(vis[i] == -1) Q.push(make_pair(tar, i));
}
for(int nw,i = 0; i < q; i++) {
cin >> nw;
cout << (i==0? "": " ") << vis[nw];
}
cout << endl;
return 0;
}
```
:::
## [藍的競程之旅--欸可是 our](https://judge.csie.ncku.edu.tw/problems/73)
- Task Provider: Ian
- Task Setter: Ian
### 首殺 team20_18 (00:07)
### 解法說明
簡單來說是做前綴和,在提示中有提到 xor 其實是在數某個 bit 的 1 到底出現過奇數次還是偶數次,也就是說 xor 運算有各種有的沒的交換結合率,並且 $(a \oplus b \oplus c \oplus d) \oplus (a \oplus b) = c \oplus d$ 也就是說可以透過再 xor 運算一次逆運算出 $c \oplus d$ 的結果
定義 $a \oplus \oplus b = X_{a} \oplus X_{a+1} \oplus ... \oplus X_{b}$
$(0 \oplus \oplus b) \oplus (0 \oplus \oplus a-1)$ 其實就等於 $a \oplus \oplus b$ 也就是消去掉 $0 \oplus \oplus a-1$ 的部分
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
int data[100010];
int quian[100010];
int main() {
int n, m, i, j, k;
quian[0] = 0;
cin >> n >> m;
for (i = 0; i < n; i++) {
cin >> data[i];
}
for (i = 1; i <= n; i++) {
quian[i] = quian[i - 1] ^ data[i - 1];
}
int a, b;
while (m--) {
cin >> a >> b;
cout << (quian[b] ^ quian[a - 1]) << endl;
}
return 0;
}
```
:::
## [次小生成樹](https://oj.leo900807.tw/problems/74)
- Task Provider: MiohitoKiri5474
- Task Setter: MiohitoKiri5474
### 首殺 team20_23 (01:24)
### 解法說明
次小,代表權重和為第二小
所以觀察一下剩下還沒有用到的邊,檢查這個邊加進去現有的 MST 中,所形成的環拿掉最小的邊的權重和,是否為除了 MST 以外、最小的生成樹
所以步驟會像是這樣:
1. 做 MST
2. 對 MST 做倍增(或剖分,反正能用來找 LCA 的東西皆可)
3. 查詢沒有用到的點鐘, $w_i - LCA ( u_i, v_i )$ 的最小值
另外 $LCA ( u_i, v_i )$ 是代表在 MST 上,$u_i, v_i$ 的路徑上所經過的邊的最大值
dp 表單的 first 就是存標準倍增法的節點
而 second 是存點 $i$ 到第 $2 ^ {k - 1}$ 個祖先之間,以及 $2 ^ {k - 1}$ 的祖先到 $2 ^ { k }$ 之間,最大的邊
所以倍增轉移式如下
$$dp[i][k].first = dp[dp[i][k - 1].first][k - 1].first$$
$$dp[i][k].second = \max ( dp[i][k - 1].second, dp[dp[i][k - 1].first][k - 1].second )$$
### 標準程式
:::spoiler
```cpp
// by. MiohitoKiri5474
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define INF 0x3f3f3f3f
#define maxN 200005
#define maxLog 20
typedef pair < int, int > pii;
#define F first
#define S second
struct bri{
int u, v, w;
};
inline bool cmp ( bri a, bri b ){
return a.w < b.w;
}
vector < bri > edges;
vector < pii > mst[maxN];
int ma, dis[maxN], n, D[maxN];
pii dp[maxN][maxLog];
vector < int > LOG;
inline void Init ( void ){
for ( int i = 0 ; i < maxN ; i++ )
dis[i] = i;
}
inline int find ( int d ){
return dis[d] == d ? d : dis[d] = find ( dis[d] );
}
inline void Union ( int a, int b ){
dis[find ( a )] = find ( b );
}
inline bool same ( int a, int b ){
return find ( a ) == find ( b );
}
inline void dfs ( int d, int p, int dep ){
D[d] = dep++;
dp[d][0].F = p;
for ( auto i: mst[d] ){
if ( i.F == p )
continue;
dp[i.F][0] = pii ( d, i.S );
dfs ( i.F, d, dep );
}
}
inline void buildLCA ( void ){
memset ( dp, -1, sizeof dp );
memset ( D, 0, sizeof D );
dfs ( 0, -1, 0 );
for ( int k = 1 ; k < maxLog ; k++ ){
for ( int i = 0 ; i < n ; i++ ){
if ( dp[i][k - 1].F == -1 )
continue;
dp[i][k].F = dp[dp[i][k - 1].F][k - 1].F;
dp[i][k].S = max ( dp[i][k - 1].S, dp[dp[i][k - 1].F][k - 1].S );
}
}
}
inline void 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].F != -1 && D[dp[x][i].F] >= D[y] ){
ma = max ( ma, dp[x][i].S );
x = dp[x][i].F;
}
}
if ( x == y )
return;
for ( int i = maxLog - 1 ; i >= 0 ; i-- ){
if ( dp[x][i].F != dp[y][i].F ){
ma = max ( ma, max ( dp[x][i].S, dp[y][i].S ) );
x = dp[x][i].F, y = dp[y][i].F;
}
}
ma = max ( ma, max ( dp[x][0].S, dp[y][0].S ) );
}
int main(){
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int m, t = 1, ans, swp = 0, u, v, w;
vector < int > unUsed;
for ( int i = 0 ; i < maxLog ; i++ ){
LOG.pb ( t );
t <<= 1;
}
t = 1;
cin >> n >> m;
Init();
ans = INF;
ma = -1;
for ( int i = 0 ; i < m ; i++ ){
cin >> u >> v >> w;
edges.pb ( bri { u, v, w } );
}
sort ( edges.begin(), edges.end(), cmp );
for ( int i = 0 ; i < m ; i++ ){
if ( same ( edges[i].u, edges[i].v ) ){
unUsed.pb ( i );
continue;
}
Union ( edges[i].u, edges[i].v );
mst[edges[i].u].pb ( pii ( edges[i].v, edges[i].w ) );
mst[edges[i].v].pb ( pii ( edges[i].u, edges[i].w ) );
swp += edges[i].w;
}
buildLCA();
for ( auto i: unUsed ){
ma = -1;
findLCA ( edges[i].u, edges[i].v );
ans = min ( ans, edges[i].w - ma );
}
cout << ans + swp << '\n';
}
```
:::
## [丸亀製麺買一送一](https://oj.leo900807.tw/problems/75)
- Task Provider: ys
- Task Setter: ys
### 首殺 team20_05 (00:16)
### 解法說明
- 令 $x$ 為 $m$ 個人過來**前**,桌子上目前**佔最多**人的人數
- 令 $k$ 為題目要求的最多人的那桌的**最小**解
若先去坐 $x$ 人的那個桌子,$k$ 會變大,所以 $m$ 個人應先分配到其他桌子上
於是求除了 $x$ 人的桌子外,還**剩下**多少位置(`rem`)
```cpp
for (int i = 0; i < N; i++) rem += x-a[i];
```
若 $m \le \text{rem}$ 則顯然 $k = x$
若 $m > \text{rem}$ 就將部份人分配到剩下的位置中(此時桌子人數都為 $x$),
接著將剩餘的人 $(m-\text{rem})$ 平均分配到每張桌子上,$k = x + \lceil {m - \text{rem}\over N} \rceil$
### 標準程式
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxN = 110;
int N, m, a[maxN];
int main() {
scanf("%d%d", &N, &m);
for(int i = 0; i < N; i++) scanf("%d", &a[i]);
int x = *max_element(a, a+N), rem = 0; // remainder
for(int i = 0; i < N; i++) rem += x-a[i];
if(m > rem) printf("%d", x + (m-rem)/N + !!((m-rem)%N));
else printf("%d", x);
return 0;
}
```
:::
## [【潤羽るしあ】新衣装と新ゲーム【ホロライブ】](https://judge.csie.ncku.edu.tw/contests/11/problems/76)
- Task Provider: leo900807
- Task Setter: leo900807
### 首殺 -- (-:-)
### 解法說明
#### Subtask 1 $P^m_n$
暴力匹配,每架飛機都匹配一個機場,看是否能降落,共 $P^m_n$ 種可能,最後取 $\max$ 。
#### Subtask 2 $O(NM)$
將每架飛機與機場,視為二分圖兩邊的點,對於每架飛機,將其與其航程內所有機場連邊,最後對這張圖做最大匹配即可。
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <utility>
#include <bitset>
#include <vector>
#define x first
#define y second
using namespace std;
pair<int, int> p[1001], a[1001];
vector<int> v[1001];
bitset<1001> vis;
int mp[1001], mq[1001];
bool matching(int u){
vis[u] = 1;
for(int i : v[u])
if(!mq[i] || !vis[mq[i]] && matching(mq[i]))
return mq[mp[u] = i] = u, 1;
return 0;
}
int dis2(pair<int, int> a, pair<int, int> b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int main() {
int n, m, d[1001], cnt = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y >> d[i];
for(int i = 1; i <= m; i++)
cin >> a[i].x >> a[i].y;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(dis2(p[i], a[j]) <= d[i] * d[i])
v[i].push_back(j);
for(int i = 1; i <= n; i++)
if(vis.reset(), matching(i))
cnt++;
cout << cnt << "\n";
for(int i = 1; i <= n; i++)
if(mp[i])
cout << i << " " << mp[i] << "\n";
}
```
:::
## [快晴](https://oj.leo900807.tw/problems/77)
- Task Provider: ys
- Task Setter: ys
### 首殺 team20_12 (02:17)
### 解法說明
顯然這是一種找**最短路徑**的問題,當 $K = 1$ 時,直接用 BFS 算出起點到終點的最短路徑。
而 $K > 1$ 時,一個位置 $(a, b)$ 可在 $1$ 秒內飛到 $j \le K$ 遠的位置 $(na, nb)$:
```cpp
while(q.size()) {
auto [a, b] = q.front(); q.pop();
for(int i = 0; i < 4; i++) // 方向 i
for(int j = 1; j <= K; j++) {
int na = a + j*da[i], nb = b + j*db[i]; // j 單位遠的下個位置
if(maze[na][nb] != '.') break; // 該方向中途遇到障礙物
if(vis[na][nb]) continue;
q.push({na, nb});
t[na][nb] = t[a][b] + 1; // 原位置秒數加 1 秒
vis[na][nb] = true;
}
}
```
這樣複雜度為 $O(N\cdot M \cdot K)$,若飛行途中都沒遇到障礙物,則會 TLE
仔細觀察**同個方向**飛行時無障礙物的狀況,
若下個位置 $(na, nb)$ 到達時間較小,那麼從 $(na, nb)$ 開始飛會比較省時,
於是同個方向的搜尋可提早結束:
```cpp
if(t[na][nb] < t[a][b] + 1) break;
```
複雜度為 $O(N \cdot M)$
### 標準程式
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxN = 1e3 + 10;
int da[] = {1, -1, 0, 0}; // direction
int db[] = {0, 0, -1, 1};
int N, M, K, a0, b0, a1, b1, t[maxN][maxN]; // t := time
char maze[maxN][maxN];
bool vis[maxN][maxN]; // vis := visited
int main()
{
scanf("%d%d%d", &N, &M, &K);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++) cin >> maze[i][j];
scanf("%d%d%d%d", &a0, &b0, &a1, &b1);
queue<pair<int, int>> q;
q.push({a0, b0});
memset(t, 0x3f, sizeof t); // 初始無限大
memset(vis, false, sizeof vis);
t[a0][b0] = 0;
vis[a0][b0] = true;
while(q.size()) {
auto [a, b] = q.front(); q.pop();
for(int i = 0; i < 4; i++)
for(int j = 1; j <= K; j++) {
int na = a + j*da[i], nb = b + j*db[i];
if(maze[na][nb] != '.') break;
if(t[na][nb] < t[a][b] + 1) break;
if(vis[na][nb]) continue;
q.push({na, nb});
t[na][nb] = t[a][b] + 1;
vis[na][nb] = true;
}
}
printf("%d\n", vis[a1][b1]? t[a1][b1] : -1);
return 0;
}
```
:::
## [增殖序列](https://judge.csie.ncku.edu.tw/contests/11/problems/78)
- Task Provider: [TIOJ 2005](https://tioj.ck.tp.edu.tw/problems/2005)
- Task Setter: leo900807
### 首殺 -- (-:-)
### 解法說明
#### Subtask 1 $O(n)$
不會超出 long long 範圍,直接做就好。
#### Subtask 2 $O(n)$
由題目敘述可以導出遞迴式
$a_n=\begin{align}\begin{cases}1 & ,\text{ if } n=1\\a_{n-1}\times10^{\lfloor\log_{10}{n}\rfloor+1}+n & ,\text{ if }n>1\end{cases}\end{align}$
那就直接 $O(n)$ 做,要記得 $\mod{m}$。
#### Subtask 3 $O(lg\ N)$
這種線性遞迴的題目,就會想到可以用矩陣快速冪來優化,但是 $10^{\lfloor\log_{10}{n}\rfloor+1}$ 該如何處理呢?
不妨將其拆成 $0\sim9,10\sim99,100\sim999,\cdots$ 並分開進行矩陣快速冪,就能將 $10^{\lfloor\log_{10}{n}\rfloor+1}$ 視為常數,而矩陣的形式如下:
$$
A=\left[\begin{matrix}10^{\lfloor\log_{10}{n}\rfloor+1} & 1 & 0\\0 & 1 & 1\\0 & 0 & 1\end{matrix}\right],B=\left[\begin{matrix}a_n\\n\\1\end{matrix}\right]
$$
那麼
$$
AB=\left[\begin{matrix}a_{n+1}\\n+1\\1\end{matrix}\right]
$$
因此一開始若將 $B$ 設為 $\left[\begin{matrix}0\\1\\1\end{matrix}\right]$ ,那麼 $a_n=A^nB$
接著只要用上述的方法分段快速冪就可以得到答案了,要記得過程中都要 $\mod{m}$
### 標準程式
看起來很亂,其實主要都是矩陣運算,實際上程式碼不長
:::spoiler
```cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long t, n, m, lim, a[3][3], b[3], tmp[3][3], x;
cin >> t;
while(t--){
cin >> n >> m;
x = log10(n) + 1;
lim = 1;
while(x--)
lim *= 10;
b[0] = 0, b[1] = 1, b[2] = 1;
for(long long mul = 10; mul <= lim; mul *= 10){
a[0][0] = mul, a[0][1] = 1, a[0][2] = 0;
a[1][0] = 0, a[1][1] = 1, a[1][2] = 1;
a[2][0] = 0, a[2][1] = 0, a[2][2] = 1;
x = min(mul - 1, n) - mul / 10 + 1;
while(x){
if(x & 1){
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++){
tmp[i][j] = 0;
for(int k = 0; k < 3; k++)
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k] % m) % m;
}
for(int i = 0; i < 3; i++)
b[i] = tmp[i][0];
}
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++){
tmp[i][j] = 0;
for(int k = 0; k < 3; k++)
tmp[i][j] = (tmp[i][j] + a[i][k] * a[k][j] % m) % m;
}
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
a[i][j] = tmp[i][j];
x >>= 1;
}
}
cout << b[0] << "\n";
}
}
```
:::