---
tags: 成大高階競技程式設計 2020
---
# 2020 高階競程 Contest #6 - 題解
## [三角形的春天](https://judge.csie.ncku.edu.tw/problems/61)
- Task Provider: [CF1355C](https://codeforces.com/contest/1355/problem/C)
- Task Setter: raiso
### 首殺 team20_23 (00:12)
### 解法說明
首先我們要先知道構成三角形需要的條件就是「最長邊 $<$ 其餘兩邊和」
這個兩邊和很重要,因為兩邊和代表一種壓縮的可能性。
誠如題目中的 Hint ,我們可以先找到短的兩邊和為 $x$ 時,有幾種組裝可能性。
接者可以列舉所有的長邊值,統計選定長邊的情況下,有幾種短邊的組合。
之後後面有提供第二種做法,那是直接計算在選定長邊的情況下,有幾種短邊的組合。
### 標準程式
:::spoiler
```cpp
#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';
}
```
```cpp
#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;
}
```
:::
## [三角形的夏天](https://judge.csie.ncku.edu.tw/problems/62)
- Task Provider: [CF1119E](https://codeforces.com/contest/1119/problem/E)
- Task Setter: raiso
### 首殺 team20_18 (00:46)
### 解法說明
首先我們要先知道構成三角形需要的條件就是「最長邊 $<$ 其餘兩邊和」
這次是告訴你,短邊與長邊一定差一倍,其實就是跟你說,不可能有兩短一長的方式能夠分組成功。
所以就只有三個同樣能力的可以分組成功,以及兩神帶一坑可以分組成功。
之後就是統計有幾個坑,讓神去帶,就可以分完了!
### 標準程式
:::spoiler
```cpp
#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;
}
```
:::
## [三角數的擴張](https://judge.csie.ncku.edu.tw/problems/63)
- 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$ 為最小非負整數。
### 標準程式
:::spoiler
```cpp
#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;
}
```
:::
## [藍的競程之旅--三角形的秋天](https://judge.csie.ncku.edu.tw/problems/64)
- Task Provider: ian
- Task Setter: ian
### 首殺 team20_46 (00:48)
### 解法說明
因為本題需求精度很高,推薦使用 python 內建大數作答,不過使用 c++ 還是可以通過的,python 的解答利用 pow(11,31) 來精確算出 pow(1.1,31) 的值,再利用 fake 算出假的值用以推算答案位數,並且由於 $1.1^31 \times 兩百萬以內的數$ 不可能為整數,所以直接將答案加一。
這裡提供第三筆測資,供各位參考測試
:::spoiler
6
1970763
1981934
1977038
1674590
296173
1378417
:::
### 標準程式
:::spoiler
```python
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 解
:::spoiler
```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;
}
```
:::
## [應徵工作](https://judge.csie.ncku.edu.tw/problems/65)
- Task Provider: leo900807
- Task Setter: leo900807
### 首殺 -- (-:-)
### 解法說明
#### Subtask 1 $O(2^NM)$
暴力枚舉每個工作要不要做,要做就要上前面的實習課,共 $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$ 的實習課,這可以用一個有向圖來表示:
<img src="https://i.imgur.com/H1DYrZB.png" width=400>
我們需要選擇圖上的一些點,使得這些被選到的點權和最大,但是在選擇點的時候有個條件,就是當一個點被選到時,其所有指到的點都要被選到。
這時我們就能使用最小割來解決這題,但是要經過一些轉化,先加上源點及匯點,以及將點權轉化為割的容量,如果我們要選擇一個點,則將其放在源點這端,否則放在匯點端,接著考慮頂點的選擇狀況:
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$ 設成無限大就好。
題目經轉化會變成下圖
<img src="https://imgur.com/7Bu0tPx.png" width=700>
最後題目所求就變成「所有工作的報酬總和」減掉「最小割容量」,這題的最小割容量為 $12$ ,因此答案為 $(5+3+7)-12=3$ 。
### 標準程式
:::spoiler
```cpp
#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";
}
```
:::