2020 高階競程 Contest #6 - 題解

三角形的春天

• Task Provider: CF1355C
• Task Setter: raiso

首殺 team20_23 (00:12)

解法說明

首先我們要先知道構成三角形需要的條件就是「最長邊

$<$ 其餘兩邊和」

這個兩邊和很重要，因為兩邊和代表一種壓縮的可能性。
誠如題目中的 Hint ，我們可以先找到短的兩邊和為

$x$ 時，有幾種組裝可能性。

接者可以列舉所有的長邊值，統計選定長邊的情況下，有幾種短邊的組合。

之後後面有提供第二種做法，那是直接計算在選定長邊的情況下，有幾種短邊的組合。

標準程式

#include <bits/stdc++.h>
using namespace std;

const int lim = 1e6;

int main() {

	int a, b, c, d;
	cin >> a >> b >> c >> d;
	vector<long long> cnt(lim + 2);
	for (int x = a; x <= b; ++x) {
		++cnt[x + b];
		--cnt[x + c + 1];
	}
	for (int i = 0; i <= lim; ++i) {
		cnt[i + 1] += cnt[i];
	}
	auto res = 0LL;
	for (int i = 0; i <= lim; ++i) {
		res += cnt[i] * max(min(d, i - 1) - c + 1, 0);
	}
	cout << res << '\n';
}

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	long long A, B, C, D;
	cin >> A >> B >> C >> D;
	long long ans = 0;

	
	for(long long z = C; z <= D; z++) {
		long long now = 0;
		if(z < 2*B && z < C+A) {
			now = (B-A+1) * (C-B+1);
			if(z >= A+B) now -= (z-A-B+1) * (z-A-B+2) / 2; 

		}
		else if(z >= 2*B-1 && z >= A+C-1) {
			now = (B+C-z) * (B+C-z+1) / 2;
			if(z > B+C) break;

		}
		else {
			long long l = B+C - z;
			long long w = l - min(C-B+1, B-A+1);
			now = l * (l+1) / 2- w * (w+1) / 2;
			now = max(0LL, now);

		}
		ans += now;
	}
 
	cout << ans << endl;
	return 0;
}

三角形的夏天

• Task Provider: CF1119E
• Task Setter: raiso

首殺 team20_18 (00:46)

解法說明

首先我們要先知道構成三角形需要的條件就是「最長邊

$<$ 其餘兩邊和」

這次是告訴你，短邊與長邊一定差一倍，其實就是跟你說，不可能有兩短一長的方式能夠分組成功。

所以就只有三個同樣能力的可以分組成功，以及兩神帶一坑可以分組成功。
之後就是統計有幾個坑，讓神去帶，就可以分完了！

標準程式

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
 
int n;
ll ans, s;
vector< ll > a;
 
 
int main() {
	cin >> n;
	a.resize(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) {
		ll pls = 0;
		if(s > 0) pls += (min(s, (a[i]/2))), s -= pls, a[i] -= (2*pls);
		ans += (pls+(a[i]/3));
		s += (a[i]%3);
	}
	cout << ans << endl;
	return 0;
}

三角數的擴張

• Task Provider: raiso
• Task Setter: raiso

首殺 team20_15 (00:24)

解法說明

使用拓展歐幾里德法，尋找整數對

$(x_1,y_1)$ 使得

$xA+yB=gcd(A,B)$，以及整數對

$(x_2,y_2)$ 使得

$xA+yB=0$，之後判斷目標

$C$ 是否為

$gcd$ 的倍數，如果不是，就代表沒辦法組裝，如果是，那就把擴展歐幾里德的整數對放大幾倍，之後再用等於

$0$ 的那組整數對加減使得

$x$ 為最小非負整數。

標準程式

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



int main() {
	ll A, B, C, n;
	bool sw = 0;
	cin >> A >> B >> C;
	vector<ll> R, x, y;
	R.push_back(max(A, B));
	R.push_back(min(A, B));
	
	if(A < B) sw = 1;
	for(int i = 1; R[i]; i++) R.push_back(R[i-1]%R[i]);

	n = R.size();
	x.resize(n);
	y.resize(n);
	x[0] = y[1] = 1;
	for(int i = 2; i < n; i++) {
		x[i] = x[i-2];
		y[i] = y[i-2];
		x[i] -= (R[i-2]/R[i-1])*x[i-1];
		y[i] -= (R[i-2]/R[i-1])*y[i-1];
	}
	if(sw == 1) swap(x, y);
	ll gcd_n = R[n-2];
	if(C % gcd_n) {
		cout << "N" << endl;
		return 0;
	}

	ll X = x[n-2] * (C / gcd_n), Y = y[n-2] * (C / gcd_n);

	if(x[n-1] < 0) x[n-1] = -x[n-1], y[n-1] = -y[n-1];
	if(X >= (x[n-1]) || X < 0) {
		X = (X%x[n-1] + x[n-1]) % x[n-1];
		Y = (C-X*A) / B;
	}
	cout << "Y" << endl;
	cout << X << " " << Y << endl;

	return 0;
}

藍的競程之旅–三角形的秋天

• Task Provider: ian
• Task Setter: ian

首殺 team20_46 (00:48)

解法說明

因為本題需求精度很高，推薦使用 python 內建大數作答，不過使用 c++ 還是可以通過的，python 的解答利用 pow(11,31) 來精確算出 pow(1.1,31) 的值，再利用 fake 算出假的值用以推算答案位數，並且由於

${1.1}^{3}1\times \mathrm{兩}\mathrm{百}\mathrm{萬}\mathrm{以}\mathrm{內}\mathrm{的}\mathrm{數}$ 不可能為整數，所以直接將答案加一。

這裡提供第三筆測資，供各位參考測試

6
1970763
1981934
1977038
1674590
296173
1378417

標準程式

t = int(input())
a = pow(11, 31)
fake_a = pow(1.1, 31)
for i in range(0, t):
    b = int(input())
    fake = int(fake_a * b / 2)
    ans = a * b >> 1
    ans_len = len(str(fake))
    ans = int(str(ans)[:ans_len]) + 1
    print(ans)

CPP 解

// 利用上課所教的方法進行作答
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long t, a, b, i, j, k;
    long double ld;

    cin >> t;
    while (t--) {
        cin >> b;
        ld = pow(1.1, 31) * b / 2;
        if (abs(ld - (long long)(ld)) <= ld * 1e-14) {
            cout << (long long)(ld) << endl;
        } else {
            cout << (long long)(ld + 1) << endl;
        }
    }

    return 0;
}

應徵工作

• Task Provider: leo900807
• Task Setter: leo900807

首殺 – (-:-)

解法說明

Subtask 1

$O(2^{N}M)$

暴力枚舉每個工作要不要做，要做就要上前面的實習課，共

$O(2^N)$ 種組合，每次

$O(M)$ 把要上的實習課的代價加總，最後用工作的報酬減掉代價，最後取

$max$ 。

Subtask 2

$O(N)$

因為至多參加一堂實習課，因此只要工作報酬比實習課的花費還多，或是工作不需要上實習課，就可以做那份工作，只要將這些工作報酬加總減掉實習課花費就能有最大獲利。

Subtask 3

$O(N+M)$

因為實習課不重複，因此只要稍微擴展一下 Subtask 2 的算法即可。

Subtask 4

$O(M\sqrt{N})$

其實這題最後是決定要做哪些工作，因為要上哪些實習課是由做哪些工作決定，以題目敘述來說，要做

$B$ 工作就需要參加

$a,d$ 的實習課，這可以用一個有向圖來表示：

我們需要選擇圖上的一些點，使得這些被選到的點權和最大，但是在選擇點的時候有個條件，就是當一個點被選到時，其所有指到的點都要被選到。

這時我們就能使用最小割來解決這題，但是要經過一些轉化，先加上源點及匯點，以及將點權轉化為割的容量，如果我們要選擇一個點，則將其放在源點這端，否則放在匯點端，接著考慮頂點的選擇狀況：

1. 頂點
   $u$ 被選到要花費
   $c$ ：
   假設這個點被選到了，代表這個點在源點端，因此可以從這個點對匯點連接一條邊，容量為
   $c$ ，如此一來，如果選到這個點，則需要花費
   $c$ 的代價，否則就不需要花費。
2. 頂點
   $u$ 被選到會賺到
   $c$ ：
   如果對匯點加一個容量為
   $-c$ 的邊，會讓流量是負的，這樣不太好。我們可以換個方向想，假設我們已經賺到這個
   $c$ 了，那如果不選這個點需要花費
   $c$ ，因此從源點對這個點連接一條邊，容量為
   $c$ 。
3. 選頂點
   $u$ 不選頂點
   $v$ 的話會花費
   $c$ ：
   從
   $u$ 對
   $v$ 連一條邊，容量為
   $c$ ，如果
   $u$ 被選到且
   $v$ 沒被選到，則他們屬於不同的部分，因此會增加割的花費。
4. 選頂點
   $u$ 一定要選頂點
   $v$ ：
   這可以看成上面情況的特例，只要把
   $c$ 設成無限大就好。

題目經轉化會變成下圖

最後題目所求就變成「所有工作的報酬總和」減掉「最小割容量」，這題的最小割容量為

$12$ ，因此答案為

$(5+3+7)-12=3$ 。

標準程式

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 4005, INF = 1e9;

struct MaxFlow{
    struct edge{
        int to, cap, flow, rev;
    };
    vector<edge> v[MAXN];
    int s, t, dis[MAXN], cur[MAXN];
    int dfs(int u, int cap){
        if(u == t || !cap)
            return cap;
        for(int &i = cur[u]; i < v[u].size(); i++){
            edge &e = v[u][i];
            if(dis[e.to] == dis[u] + 1 && e.flow != e.cap){
                int df = dfs(e.to, min(e.cap - e.flow, cap));
                if(df){
                    e.flow += df;
                    v[e.to][e.rev].flow -= df;
                    return df;
                }
            }
        }
        dis[u] = -1;
        return 0;
    }
    bool bfs(){
        memset(dis, -1, sizeof(dis));
        queue<int> q;
        q.push(s), dis[s] = 0;
        while(!q.empty()){
            int tmp = q.front();
            q.pop();
            for(auto u : v[tmp]){
                if(!~dis[u.to] && u.flow != u.cap){
                    q.push(u.to);
                    dis[u.to] = dis[tmp] + 1;
                }
            }
        }
        return dis[t] != -1;
    }
    int maxflow(int _s, int _t){
        s = _s, t = _t;
        int flow = 0, df;
        while(bfs()){
            memset(cur, 0, sizeof(cur));
            while(df = dfs(s, INT_MAX))
                flow += df;
        }
        return flow;
    }
    void add_edge(int st, int ed, int cap){
        v[st].push_back(edge{ed, cap, 0, v[ed].size()});
        v[ed].push_back(edge{st, 0, 0, v[st].size() - 1});
    }
} dinic;

int main() {
    int n, m, s, b, k, x, sum = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> s;
        sum += s;
        dinic.add_edge(0, i, s);
    }
    for(int i = 1; i <= m; i++){
        cin >> b;
        dinic.add_edge(i + 2000, 4004, b);
    }
    for(int i = 1; i <= n; i++){
        cin >> k;
        while(k--){
            cin >> x;
            dinic.add_edge(i, x + 2000, INF);
        }
    }
    cout << sum - dinic.maxflow(0, 4004) << "\n";
}