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

A. 獅子的野望 (yabo)

題目要求求出

$\lceil \frac{L}{K}\rceil$，然後在找出序列

$a$ 中差距最小的元素即可。

#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\le sum$ 加入後最終答案只會更差，因此只考慮

$i$ 使

$a_i>sum$；接著選擇符合的

$a_i$ 中最小的，答案不會更差。

因此，紀錄一個

$sum$ 代表目前已選擇元素的總和，每次遍歷所有元素。從尚未挑選過的元素且大於

$sum$ 中選擇最小的，並加入

$sum$。直到不存在任何一個元素大於

$sum$，剩下未被挑選的元素任意排列即可。時間

$O(N^2)$ 。

Subtask 3&4

"每次遍歷所有元素。從尚未挑選過的元素且大於

$sum$ 中選擇最小的" 可以以 set 在

$O(logN)$ 實現。時間

$O(NlogN)$。

#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。

#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}\le 0$ 就全部不要連，否則每個人都跟對面的人連，答案即為

$max(0,N\times a_{i,j})$

Subtask 2

也就是第一排的人跟第二排的哪個人連都沒有區別。因此第一排的人都優先考慮連自己正對面的人，若

$a_{i,j}\le 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])$。

#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\ge (4N{)}^{\frac{1}{3}}$ 時

$f(i+1)-f(i)$ 會

$\ge 0$，因此答案出現在

$i\le (4N{)}^{\frac{1}{3}}$

另一個不嚴謹的證明是，把

$i+1$ 當成

$i$ 做算幾，當

$\frac{i}{2}=\frac{2N}{i^2}$ 時有最小值。

#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\ast x$就可以了。

複雜度

$O(N^3)$。

subtask5

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

而對於剩下沒被配到的麵，可以分成兩種case :

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

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

複雜度

$O(N)$。

#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)$。

#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\le 1000$，並且傳送器數量最多可以到

$2\ast {10}^6$，所以用把朋友們依照

$e_i$做Bubble sort，並在每次交換時都標記成在兩者之間安裝一個傳送器就可以了。

或者你覺得

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

#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;
}

hiehaehasdhasdhasdhasdhasdhasdhasdhasdhasdh