第九屆高一生程式設計排名賽題解
===
### 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$超小，而且他有給你測資，所以用手解。
#### suntask2,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;
}
```
{%hackmd Bk4uKyJJY %}
Sign in with Wallet
Connect another wallet