---
# System prepended metadata

title: 【題解】第九屆高一生程式設計排名賽
tags: [競程, 題解]

---

【題解】第九屆高一生程式設計排名賽
===



### A. 獅子的野望 (yabo)
題目要求求出 $\lceil \frac{L}{K} \rceil$，然後在找出序列 $a$ 中差距最小的元素即可。

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6+10;

int n, k, l, a;

signed main()
{
    cin >> l >> k >> n;

    int mid=0, mv=1e18;
    for (int i=1; i<=n; i++)
    {
        cin >> a;
        if (mv > abs((l-1)/k+1-a))
        {
            mv = abs((l-1)/k+1-a);
            mid = i;
        }
    }
    cout << mid << '\n';
}

```



### B. 爆音爆音 (boing)
####  Subtask 1

用 `next_permutation` 枚舉每一種排列方式即可，複雜度 $O(N!)$

####  Subtask 2

用依序加入元素的方式來製造排列 $p$，$sum$ 為目前總和也就是 $a_{p_1}+...+a_{p_k}$。每次加入 $i$ 時，若 $a_i \leq sum$ 加入後最終答案只會更差，因此只考慮 $i$ 使 $a_i > sum$；接著選擇符合的 $a_i$ 中最小的，答案不會更差。

因此，紀錄一個 $sum$ 代表目前已選擇元素的總和，每次遍歷所有元素。從尚未挑選過的元素且大於 $sum$ 中選擇最小的，並加入 $sum$。直到不存在任何一個元素大於 $sum$，剩下未被挑選的元素任意排列即可。時間 $O(N^2)$ 。

####  Subtask 3&4

"每次遍歷所有元素。從尚未挑選過的元素且大於 $sum$ 中選擇最小的" 可以以 `set` 在 $O(logN)$ 實現。時間 $O(NlogN)$。

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6+10;

int n;
set<int> s;

signed main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        s.insert(x);
    }

    int sum = 0, cnt = 0;
    for (int i=1; i<=n; i++)
    {
        auto x = s.upper_bound(sum);
        if (x == s.end())
            break;
        sum += *x;
        s.erase(x);
        cnt++;
    }
    cout << cnt << endl;
}
```



### C. 手指餅乾 (yubi)

#### Subtask 1

可以以 $O(2^N)$ 枚舉每個餅乾要不要補上麵團。

#### Subtask 2

$a_i$ 只有兩種可能，$1$ 或 $2$。若 $a_i$ 為 $1$ 則補上麵團，則每個手指餅乾都會是 $2$。

#### Subtask 3&4

以 $O(\sqrt{N})$ 可以枚舉一個數字的所有因數。枚舉 $a_i$ 和 $a_i+1$ 的所有因數，對 $a_2, .., a_N$ 檢查補上麵團或不補上麵團否至少一個被該因數整除。

時間 $O(N \sqrt{N})$ 。

#### Subtask 5

可以從 Subtask 2 獲得啟發，只要把每個數字補成偶數即可。**用 Subtask 3&4 的作法，枚舉到的第一個因數就會是 $2$，也可通過此子題 OwO。**

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6+10;

int n, a[N];

signed main()
{
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
	for (int i=1; i<=n; i++)
        if (a[i]&1) a[i]++;
	for (int i=1; i<=n; i++)	
        cout << a[i] << "\n "[i+1<=n];
}
```



### D. 大型貼貼現場 (teetee)

####  Subtask 1

若 $a_{i,j} \leq 0$ 就全部不要連，否則每個人都跟對面的人連，答案即為 $max(0,N \times a_{i,j})$

#### Subtask 2

也就是第一排的人跟第二排的哪個人連都沒有區別。因此第一排的人都優先考慮連自己正對面的人，若 $a_{i,j} \leq 0$ 則第 $i$ 人不參與配對即可。

#### Subtask 3

暴力枚舉第一排的人要跟第二排的哪個人配對，複雜度 $O(N!)$ 。

#### Subtask 4

考慮動態規劃，$dp[i][j]$ 代表第一排的 $[i,N]$ 和第二排 $[j,N]$ 參與配對。

轉移情況有三種：

1. 第一排第 $i$ 人不參與配對
2. 第二排第 $j$ 人不參與配對
3. 第一排第 $i$ 人和第二排第 $j$ 人配對，產生 $a_{i,j}$ 價值

因此轉移為 $dp[i][j] = max( dp[i+1][j], dp[i][j+1], dp[i+1][j+1]+a[i][j])$。

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2001;

int a[N][N], n, dp[N][N];

signed main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
       	for (int j=1; j<=n; j++)
            cin >> a[i][j];
    for (int i = n; i>0; i--)
        for (int j=n; j>0; j--)
            dp[i][j] = max(max(dp[i+1][j], dp[i][j+1]), dp[i+1][j+1]+a[i][j]);
    cout << dp[1][1] << endl;
}
```



### E. 裝水 (water)

#### Subtask 1

首先必須觀察出，擴大水桶的步驟全部做完再把水倒入鍋釜，是比較好的。

因此先從 $1$ 到 $N$ 枚舉需要消耗多少魔力擴大多少次水桶，每次再算出需要消耗多少體力倒入鍋釜，取相加最小值，複雜度 $O(N^2)$。

#### Subtask 2

擴大 $i$ 次水桶後的水桶容量，即為 $1+(1+2+3+...+i)$，將 $1+2+3+...+i$  用 $\frac{(1+i) \times i}{2}$  公式計算可以優化到 $O(N)$。

#### Subtask 3

當擴大水桶後的容量至少為 $N$，只要消耗一體力倒入鍋釜。因此只要枚舉擴大次數 $i$ 直到 $1+(1+2+3+...+i) > N$ 即可，由上面的公式可以得知枚舉不超過 $\sqrt{2N}$ 次。複雜度 $O(\sqrt{N})$

#### Subtask 4
$f(i)$ 為擴大$i$ 次的總體力+魔力消耗，$f(i) \approx  i + \frac{2N}{i(i+1)}$，$f(i+1) - f(i) = 1-\frac{4N}{i^3+3i^2+2i}$，因此當 $i \geq  (4N)^\frac13$ 時 $f(i+1) - f(i)$  會 $\geq 0$，因此答案出現在 $i \leq (4N)^\frac13$

另一個不嚴謹的證明是，把 $i+1$ 當成 $i$ 做算幾，當 $\frac{i}{2} = \frac{2N}{i^2}$ 時有最小值。


```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int n;
    cin >> n;

    int ans = 9e18;
    for (int i=1; i<=10000000; i++)
    {
        int k = i*(i+1)/2+1;
        ans = min(ans, (n-1)/k+1+i);
    }
    cout << ans << endl;
}
```



### F.七彩繽紛銀河麵 (udon)

#### subtask1
無論怎麼配都不會損失美味程度，所以把每個調味料配給跟他絕配的麵當中，美味程度最高的就好了。

複雜度$O(N)$。

#### subtask2
因為$N$很小，暴力去試每一種組合，再取美味程度最大的組合。

複雜度$O(N!)$。

#### subtask3, 4
我們可以把題目轉換成二分圖最大權匹配，直接套km。
對於地獄組合的負邊權，只要把他們都加上一個數$x$，使得他們的邊權都變成正的，然後輸出的時候記得再減掉$N*x$就可以了。

複雜度$O(N^3)$。

#### subtask5
跟subtask1一樣，先把每個調味料配給跟他絕配的麵當中，美味程度最高的配給他。

而對於剩下沒被配到的麵，可以分成兩種case : 
1. 剩下的麵當中，都不和同一個調味料產生地獄組合。
    這時候一定找的到一種配法，使得剩下的麵都不會配到會跟自己產生地獄組合    的調味料，所以直接輸出跟subtask1作法一樣的答案就好了。

2. 剩下的麵當中，都會和同一個調味料產生地獄組合。
    一個最直觀的想法就是把損失最少美味程度的麵配給那個調味料。
    但這不一定會是最大的美味程度，這時候把先前已經配對過的麵，拿來配那個調味料，如果拿來配對的麵不會跟調味料產生地獄組合，就可以使損失的美味程度變成0，美味程度總和可能會更大。
    所以就枚舉把每個先前已經被配到的麵配給那個調味料，並且把配那個麵的調味料中，美味程度次高的麵配給他，然後再取max。

複雜度$O(N)$。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
const ll mx = 5e5+5;
 
ll n, match_id[mx], match_val[mx], match_val2[mx], hateid[mx], hatev[mx];
bool matched[mx];
 
signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
 
    // 輸入並對每種調味料找到與之形成絕配中美味程度最高與次高的
    for(int i = 1, soft, v; i <= n; i++){
        cin >> soft >> v;
        if(v > match_val[soft]){
            match_id[soft] = i;
            match_val2[soft] = match_val[soft];
            match_val[soft] = v;
        }
        else if (v > match_val2[soft]){
            match_val2[soft] = v;
        }
    }
 
    // 看剩下的那些麵團與哪一種調味料形成地獄組合
    for(int i = 1; i <= n; i++){
        cin >> hateid[i] >> hatev[i];
    }
    ll cur = 0;
    for(int i = 1; i <= n; i++){
        matched[match_id[i]] = 1;
        cur += match_val[i];
    }
 
    bool all_hate_same = 1;
    ll be_hated = -1, mn = 1e18;
    for(int i = 1; i <= n; i++){
        if(!matched[i]){
            if(hateid[i] == 0){
                all_hate_same = 0;
                break;
            }
            if(be_hated == -1) be_hated = hateid[i], mn = hatev[i];
            else{
                if(hateid[i] != be_hated) all_hate_same = 0;
                else{
                    mn = min(hatev[i], mn);
                }
            }
        }
    }
    
    // 沒有調味料會形成地獄組合 or 不是與同一種調味料產生地獄組合 or 會產生地獄組合的調味料有人配對了
    if(be_hated == -1 || match_val[be_hated] > 0 || !all_hate_same){
        cout << cur << '\n';
        return 0;
    }
 
    ll ans = cur - mn;
    
    // 枚舉配對完成的麵團中，誰要被換下來與會使所有麵團產生地獄組合的調味料配對。
    for(int i = 1; i <= n; i++){
        if(match_id[i] != 0){
            int id = match_id[i];
            ll loss = match_val[i] - match_val2[i];
            if(hateid[id] == be_hated){
                loss += min(hatev[id], mn);
            }
            ans = max(ans, cur - loss);
        }
    }
 
    cout << ans << '\n';
}
```



---

### G.爆炸吧現充 (imhorny)

#### subtask1
枚舉兩個人都使用砲台，兩個人都不使用砲台，其中一個人使用砲台的情況。

複雜度$O(1)$。

#### subtask2
使用最短路。

把每個座標$i$跟$i+1$及$i-1$連一個邊權為1的邊，每個砲台跟降落點$(x_i \pm d_i)$連一個邊權為0的邊。
做完最短路再去枚舉每個點兩人的最短路，並且取min。

複雜度$O(LlogL)$。

#### subtask3
因為$L$太大，所以沒辦法使用$O(LlogL)$，最多只能用$O(L)$的做法。
參考subtask2的建圖方式，會發現邊權只有0和1，所以其實可以用01bfs去做。

01bfs跟一般bfs不一樣之處在於一般bfs時保證讓queue當中的點，距離從前到後為非嚴格遞增。
但如果有邊權為0的邊，這時候從那條邊去更新其他點，並把它放進queue的最後方，可能會失去距離從前到後為非嚴格遞增這項性質。

這時候可以發現，最前面的點一定是在queue中距離最小者，而從邊權為0的邊所更新的點距離跟他一樣，是queue當中距離最小的，那只要把他塞進queue的頭就可以維護上述的性質了。

而c++有deque可以支援從頭或尾插入，所以把queue改成deque去做01bfs就可以了。

複雜度$O(L)$。

#### subtask4
也是最短路，但因為$L$太大，要改變建點跟建邊的方式。

我們可以將每個砲台所在的座標建成一個點，每個砲台的降落點座標也建成一個點。
把每個砲台跟他的降落點建一條邊權為0的邊，並把每個砲台跟他左右的兩個點建一條邊權為其距離的邊，之後去做最短路得出到每個點的距離。
再來去枚舉每兩個相鄰的點，算出如果在這兩個點的區間上見面所需的最少時間，然後再取min。

複雜度$O(NlogN)$。

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mxN = 5e5 + 5;
int L, N, x[mxN], d[mxN], dis[mxN * 3][2];
vector<pair<int,int>> g[mxN * 3];

void dijkstra(int st) {
	int type = 0;
	if(st != 0) type = 1;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	dis[st][type] = 0;
	pq.push({0, st});
	while(!pq.empty()) {
		auto [d, u] = pq.top(); pq.pop();
		if(dis[u][type] < d) continue;
		for(auto [v, w] : g[u]) {
			if(dis[v][type] > d + w) {
				dis[v][type] = d + w;
				pq.push({dis[v][type], v});
			}
		}
	}
}

signed main() {
        cin >> L >> N;
        vector<int> tmp;
        tmp.push_back(0); tmp.push_back(L);
        for(int i = 0; i < N; i++) {
            cin >> x[i] >> d[i];
            tmp.push_back(x[i]);
            if(x[i] - d[i] > 0) tmp.push_back(x[i] - d[i]);
            if(x[i] + d[i] < L) tmp.push_back(x[i] + d[i]);
        }
        sort(tmp.begin(), tmp.end());
        tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
        for(int i = 0; i < N; i++) {
            int id = lower_bound(tmp.begin(), tmp.end(), x[i]) - tmp.begin();
            int tl = -1, tr = -1;
            if(x[i] - d[i] >= 0) tl = lower_bound(tmp.begin(), tmp.end(), x[i] - d[i]) - tmp.begin();
            if(x[i] + d[i] <= L) tr = lower_bound(tmp.begin(), tmp.end(), x[i] + d[i]) - tmp.begin();
            if(tl != -1) g[id].push_back({tl, 0});
            if(tr != -1) g[id].push_back({tr, 0});
        }
        for(int i = 1; i < tmp.size(); i++) {
            g[i].push_back({i-1, tmp[i] - tmp[i-1]});
            g[i-1].push_back({i, tmp[i] - tmp[i-1]});
        }
        memset(dis, 0x3f, sizeof dis);
        dijkstra(0);
        dijkstra(lower_bound(tmp.begin(), tmp.end(), L) - tmp.begin());
        int ans = (L + 1) / 2;

        for(int i = 0; i < tmp.size(); i++) {
            if(i) {
                int td = tmp[i] - tmp[i-1];
                if (td >= abs(dis[i][0] - dis[i-1][1]))
                    ans = min(ans, max(dis[i][0], dis[i-1][1]) + ((td - abs(dis[i][0] - dis[i-1][1]) + 1) / 2));
                if (td >= abs(dis[i][1] - dis[i-1][0]))
                    ans = min(ans, max(dis[i][1], dis[i-1][0]) + ((td - abs(dis[i][1] - dis[i-1][0]) + 1) / 2));
            }
            ans = min(ans, max(dis[i][0], dis[i][1]));
            g[i].clear();
        }
        cout << ans << '\n';
}
```



---

### H.兔田迷宮 (usadamaze)

#### subtask1
$N$超小，而且他有給你測資，所以用手解。

#### subtask2,3
可以發現，如果在$i$及$i+1$之間安裝一個傳送器，就會使目前在$i$的朋友跟在$i+1$的朋友位置交換。
而題目的要求是使得交換後朋友們的順序是按照$e_i$由小排到大，這就很容易聯想到Bubble sort，這時候傳送器的數目就相當於時間複雜度。
Bubble sort的時間複雜度為$O(N^2)$，而題目的$N \leq 1000$，並且傳送器數量最多可以到$2*10^6$，所以用把朋友們依照$e_i$做Bubble sort，並在每次交換時都標記成在兩者之間安裝一個傳送器就可以了。

或者你覺得$N$最多只有1000太少了，用手解也是可以(X)。

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1010;

vector<int> ans;
int a[N], ord[N], n;

void mswap (int j)
{
    swap(a[j], a[j+1]);
    ans.push_back(j);
}

signed main()
{
    string useless;
    int cid;

    cin >> useless >> cid >> n;
    
    for (int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        ord[x] = i;
        a[i] = i;
    }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n-1; j++)
            if (ord[a[j]] > ord[a[j+1]]) mswap(j);

    cout << "#Case " << cid << endl;
    cout << ans.size() << endl;
    for (auto y: ans) cout << y << ' ';
    cout << endl;
}
```

