---
tags: 成大高階競技程式設計 2021
image: https://i.imgur.com/IIj9BcL.png
---
# 2021 高階競程 Contest #1 - 題解
## [鮪魚吃蛋糕](https://judge.csie.ncku.edu.tw/problems/89)
- Task Provider: leo
- Task Setter: leo
### 首殺 team21_24 (00:13)
### 解法說明
你可以把所有蛋糕依照好吃度 $d$ 與價錢 $c$ 的比值，由大到小排序。
接著依序拿蛋糕直到錢不夠為止。
時間複雜度為排序的 $O(N\log N)$。
實作上需要特別注意一些問題：
- 雖然這題因為是浮點數除法，基本上不太會遇到這問題，
不過在寫根據比值排序的 compare 時，
儘量不要用除的，因為分母有可能為 $0$，下方提供範例。
浮點數則因為除以 $0$ 會變成 `inf` 所以不太會出問題，
不過還是可能被一些浮點數精度的問題影響到。
:::spoiler 範例
```cpp
struct cake{
int d, c;
};
// Suggest
bool compare1(const cake &a, const cake &b){
return (long long)a.d * b.c > (long long)b.d * a.c;
}
// Not suggest
bool compare2(const cake &a, const cake &b){
return (double)a.d / a.c > (double)b.d / b.c;
}
```
:::
<br>
- 因為題目採用相對誤差的比對方式，
所以其實可以儘量輸出很多位數，以求較精確的輸出，
請參考下方標準程式
- 如果 $K$ 為 $0$ 時不能直接跳出去，因為蛋糕可能也是 $0$ 元
如果題目改成蛋糕不可分割的話，這種依照 CP 值的 greedy 方法是不行的，
詳細原因與解法會在第七週的課程教到，如果有興趣的話可以先自己想想看為什麼。
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct cake{
int d, c;
bool operator<(const cake &a)const{
return (long long)d * a.c > (long long)a.d * c;
}
} a[200000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
double ans = 0;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i].d >> a[i].c;
sort(a, a + n);
for(int i = 0; i < n && (k > 0 || a[i].c == 0); k -= a[i].c, i++)
if(k >= a[i].c || a[i].c == 0)
ans += a[i].d;
else
ans += a[i].d * (double(k) / a[i].c);
cout << fixed << setprecision(12) << ans << "\n";
}
```
:::
## [零二](https://judge.csie.ncku.edu.tw/problems/90)
- Task Provider: arashi87
- Task Setter: arashi87
### 首殺 team21_34 (00:38)
### 解法說明
題目要求你將 $N$ 分解為 $K$ 個二的幂次，其實就是單純的二進制分解而已，我們可以很容易的知道下面兩種情況會無法分解。
- 第一種是 $K \gt N$，當發生這種情況即使將 $N$ 通通分解成 $2^0$ 也會不夠
- 第二種是當 $N$ 轉換的二進制裡 `1` 的個數大於 $K$ 時也會無法分解，因為能夠分解的最少數字，其數量已經大於 $K$ 了。
而剩下就是如何分解而已，這邊我們利用 priority queue 可以自動找出最大值的功能，先將 $N$ 做二進制分解並將分解出來的數字都放進 `pq` 裡，如果數量小於 $K$ 的話就從 `pq` 取出最大的數除以 $2$，生成兩個數字，並且放回 `pq`，這樣做一次可以使得 $pq.size$ 增加 $1$，如此只需要一直重複直到 $pq.size = K$。時間複雜度為 priority queue 單次操作的 $O(\log K)$ 乘上總操作次數 $O(K)$，複雜度為 $O(K\log K)$。
總複雜度為分解 $N$ 的 $O(\log N)$ 加上後面 priority queue 的 $O(K\log K)$，因此為 $O(\log N+K\log K)$。
下方的解法 2 是複雜度 $O(K+\log N)$ 的做法，比起上面的解法又更快了一點，有興趣的可以自己研究看看。
### 標準程式
:::spoiler 解法 1
```cpp
#include <queue>
#include <stdio.h>
using namespace std;
int n, k, base = 1;
priority_queue<int> pq;
int main() {
scanf("%d%d", &n, &k);
if (k > n) return puts("NO"), 0;
while (n) {
if (n & 1) pq.push(base);
n >>= 1, base <<= 1;
}
if (pq.size() > k) return puts("NO"), 0;
while (pq.size() < k) {
int tmp = pq.top(); pq.pop();
pq.push(tmp >> 1), pq.push(tmp >> 1);
}
puts("YES");
while(!pq.empty())
printf("%d ", pq.top()), pq.pop();
printf("\n");
}
```
:::
:::spoiler 解法 2
```cpp
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, a[64] = {}, cnt = 0;
bool flag = 0;
cin >> n >> k;
for(long long i = 0, tmp = 1; i < 64; tmp <<= 1, i++)
if(tmp & n)
a[i] = 1, cnt++;
if(cnt > k || n < k)
return cout << "NO\n", 0;
for(int i = 63; i > 0; i--)
if(cnt < k){
int tmp = min(k - cnt, a[i]);
a[i] -= tmp;
a[i - 1] += tmp * 2;
cnt += tmp;
}
cout << "YES\n";
for(long long i = 0, tmp = 1; i < 64; tmp <<= 1, i++)
for(int j = 0; j < a[i]; j++){
if(flag)
cout << " ";
else
flag = 1;
cout << tmp;
}
cout << "\n";
}
```
:::
## [BNT](https://judge.csie.ncku.edu.tw/problems/91)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee
### 首殺 team21_12 (00:02)
### 解法說明
#### Subtask 1 $O(N^3)$
因為這個子任務 $N$ 最大只有到 $100$，因此我們可以直接枚舉所有可能的長度為 $3$ 的子序列，並算出當中有多少是 BNT。
:::spoiler 參考程式
```cpp
#include <iostream>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string s;
cin >> N >> s;
int ans{0};
for (int i{0}; i < N; ++i)
for (int j{i + 1}; j < N; ++j)
for (int k{j + 1}; k < N; ++k)
if (s[i] == 'B' && s[j] == 'N' && s[k] == 'T')
++ans;
cout << ans << '\n';
return 0;
}
```
:::
#### Subtask 2 $O(N)$
#### 解法 1
我們枚舉所有的 N，對於每個找到的 N，若左邊有 $x$ 個 B 以及 $y$ 個 T，從左邊任意取一個 B 再從右邊任意取一個 T 就可以組成一個 BNT 子序列，因此對於這個 N，我們可以得到 $x \cdot y$ 個 BNT 子序列。
#### 解法 2
我們定義一個長度為 $3$ 的陣列 $cnt$，每個元素代表的意義如下：
* $cnt_0$ 代表目前遇到的 B 的個數
* $cnt_1$ 代表目前遇到的 BN 的個數
* $cnt_2$ 代表目前遇到的 BNT 的個數
因此我們只要把 $s$ 從左到右跑一次，並且維護 $cnt$ 的元素，最後的 $cnt_2$ 就是我們要的答案。
> 維護方法：
> * 每個 N 都可以接在目前遇到的 B 的後面，形成 $cnt_0$ 個 BN
> * 每個 T 都可以接在目前遇到的 BN 的後面，形成 $cnt_1$ 個 BNT
要注意答案可能會超出 `int` 的範圍，因此型別需要設為 `long long`。
### 標準程式
:::spoiler 解法 1
```cpp
#include <iostream>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string s;
cin >> N >> s;
long long x{0}, y{0}, ans{0};
for (int i{0}; i < N; ++i)
if (s[i] == 'T')
++y;
for (int i{0}; i < N; ++i) {
if (s[i] == 'B') ++x;
else if (s[i] == 'T') --y;
else ans += x * y; // s[i] == 'N'
}
cout << ans << '\n';
return 0;
}
```
:::
:::spoiler 解法 2
```cpp
#include <iostream>
#include <array>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string s;
cin >> N >> s;
array<long long, 3> cnt{};
for (int i{0}; i < N; ++i) {
if (s[i] == 'B')
++cnt[0];
else if (s[i] == 'N')
cnt[1] += cnt[0];
else // s[i] == 'T'
cnt[2] += cnt[1];
}
cout << cnt[2] << '\n';
return 0;
}
```
:::
## [遞增數列](https://judge.csie.ncku.edu.tw/problems/92)
- Task Provider: ys
- Task Setter: ys
### 首殺 team21_18 (00:26)
### 解法說明
#### 解法 1
設 $p(n, m)$ 表示上限為 $n$ 且長度為 $m$ 的遞增數列個數
首先觀察到，長度 $m$ 可由長度 $m-1$ 的遞增數列推得，其關係式為：
$$
p(n, m) = p(n, m-1) + p(n-1, m-1) + \cdots + p(1, m-1)
$$
例如 $n = 2, m = 3$ 的遞增數列 $a$ 可分為
- $a_3 = 2$：
$\textbf{2, 2}, 2$
$\textbf{1, 2}, 2$
$\textbf{1, 1}, 2$
- $a_3 = 1$：
$\textbf{1, 1}, 1$
觀察得知 $p(2, 3)$ 有以下關係式
$$
p(2, 3) = p(2, 2) + p(1, 2)
$$
> 將尾端 $a_3$ 設為 $2$ 時，$a_1, a_2$ 的可能數為 $p(2, 2)$；
將尾端 $a_3$ 設為 $1$ 時，$a_1, a_2$ 的可能數為 $p(1, 2)$
所以欲求 $p(n, m)$，
只需要依序將 $p(1, 1), p(2, 1), \cdots , p(n, 1)$ 求出來，
再將 $p(1, 2), p(2, 2), \cdots , p(n, 2)$ 求出來，
依此類推，就能得到題目所需的目標答案
實作上由於結果相當龐大，做加法時會除餘要求的 $10^9 + 7$ 如 `a = (b + c) % 1000000007`
並且設邊界 $\forall n. p(n, 0) = 1$，因為 $m = 0$ 的時候只有**一種**可能
#### 解法 2
$n-1+m$ 個格子**任選** $m$ 個格子，令**未選到的格子**為隔板
選到的格子填上數字，規則如下：
- 不超過第 $1$ 個隔板之前為 $1$
- 第 $k-1$ 個到第 $k$ 個隔板之間為 $k$
- 超過第 $n-1$ 個隔板之後為 $n$
例如 $n = 2, m = 3$ 的格子為 `_,_,_,_`，有以下可能選法：
- `|,_,_,_`
- `_,|,_,_`
- `_,_,|,_`
- `_,_,_,|`
其中 `|` 表示隔板 (未選到的格子)
根據規則將選到的格子填上數字：
- `|,2,2,2`
- `1,|,2,2`
- `1,1,|,2`
- `1,1,1,|`
格子選法數剛好為遞增數列的可能數，可用排列組合的計算方式算出
### 標準程式
:::spoiler 解法 1
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e3 + 10;
int const mod = 1000000007;
int n, m, p[maxn][25];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i][0] = 1;
for(int r = 0; r < m; r++) // r := round
for(int b = n; b >= 1; b--) { // b := bound
long long sum = 0;
for(int i = 1; i <= b; i++) sum = (sum + p[i][r]) % mod;
p[b][r+1] = sum;
}
cout << p[n][m] << endl;
return 0;
}
```
:::
:::spoiler 解法 2
```python
from math import factorial as fact
mod = 10**9 + 7
def C(n, k):
return fact(n) // (fact(k) * fact(n - k))
n, m = map(int, input().split())
print(C(n + m - 1, m) % mod)
```
:::
## [な NA](https://judge.csie.ncku.edu.tw/problems/93)
- Task Provider: raiso
- Task Setter: raiso
### 首殺 team21_15 (00:13)
### 解法說明
這題有兩個要點需要注意：
- $\text{len}(M)$ 至少為 $1$
- 只需要考慮 $\text{len}(M) = 1$ or $2$ 的情況，因為對於長度更長的 $M$，我們只需要將其同時去頭去尾後，所得到的吸引力只會大於等於還沒去頭去尾的情況。
**超越**
本題可以使用 $O(N\log N)$ 的複雜度實作
- 將比對字串的過程看成多項式相乘，枚舉所有 $M$ 得到的吸引力其實就是多項式相乘後的結果，由於多項式相乘可以使用 FFT 與 IFFT 的方式加速，在 $O(N\log N)$ 的複雜度得到答案，由於整個過程過於神奇，有興趣的人可以自行研究。
### 標準程式
:::spoiler 解法 O(N^2)
```cpp
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define Int long long
#define x first
#define y second
using namespace std;
void solve(){
int n;
cin >> n;
string str;
cin >> str;
vector<int> A(n);
for(int i = 0; i < n; i++) {
if(str[i] == 'A') A[i] = 2;
if(str[i] == 'T') A[i] = 1;
if(str[i] == 'C') A[i] = -2;
if(str[i] == 'G') A[i] = -1;
}
int ans = 0;
for(int c = 1; c <= 2; c++) {
for(int i = 1; i < n-c; i++) {
int cnt = 0, j = 1;
while((i+c-1+j) < n && (i-j) >= 0) {
int tmp = A[i+c-1+j] + A[i-j];
if(tmp == 3 || tmp == -3) cnt++;
j++;
}
ans = max(ans, cnt);
}
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t=1;
//cin >> t;
while(t--) solve();
return 0;
}
```
:::
:::spoiler 解法 O(NlogN)
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define add insert
#define Int long long
#define pdd pair<double,double>
#define pii pair<int,int>
#define pII pair<Int,Int>
#define sqr(x) ((x)*(x))
#define PI acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define x first
#define y second
using namespace std;
typedef complex<double> CD;
void FFT(vector<CD> &a, bool inv) {
//bit reversal
int n = a.size();
for(int i=0, j=0; i < n; i++) {
if(j > i) swap(a[i], a[j]);
int k = n;
while(j & (k >>=1)) j &=~k;
j |= k;
}
double pi = inv? -PI:PI;
for(int step=1; step < n; step <<= 1) {
double alpha = pi/step;
for(int k = 0; k < step; k++) {
CD omegak = exp(CD(0, alpha*k));
for(int Ek = k; Ek < n; Ek += step << 1) {
int Ok = Ek + step;
CD t = omegak * a[Ok];
a[Ok] = a[Ek] - t;
a[Ek] += t;
}
}
}
if(inv) for(int i = 0; i < n; i++) a[i] /= n;
}
inline vector<double> operator * (const vector<double>& v1, const vector<double>& v2) {
int s1 = v1.size(), s2 = v2.size(), S = 2;
while(S < s1+s2) S <<= 1;
vector<CD> a(S,0), b(S,0);
for(int i = 0; i < s1; i++) a[i] = v1[i];
for(int i = 0; i < s2; i++) b[i] = v2[i];
FFT(a, false);
FFT(b, false);
for(int i = 0; i < S; i++) a[i] *= b[i];
FFT(a, true);
vector<double> res(s1+s2-1);
for(int i = 0; i < s1+s2-1; i++) res[i] = a[i].real();
return res;
}
bool match(char a, char b) {
if(a > b) swap(a, b);
if(a == 'A' && b == 'T') return 1;
else if(a == 'C' && b == 'G') return 1;
return 0;
}
void solve(){
int n; cin >> n;
string str; cin >> str;
vector<double> A(n,0), B(n,0), res1, res2;
vector<int> res;
for(int i = 0; i < n; i++) if(str[i] == 'A') A[i] = 1.0;
for(int i = 0; i < n; i++) if(str[i] == 'T') B[i] = 1.0;
res1 = A*B;
A.clear();
B.clear();
A.assign(n, 0);
B.assign(n, 0);
for(int i = 0; i < n; i++) if(str[i] == 'C') A[i] = 1.0;
for(int i = 0; i < n; i++) if(str[i] == 'G') B[i] = 1.0;
res2 = A*B;
res.resize(res1.size());
int nn = res.size();
for(int i = 0; i < nn; i++) res[i] = int(res1[i] + res2[i]);
for(int i = 0; i < n; i++) if(match(str[i], str[i+1])) res[i*2+1]--;
int maxi = 0;
for(int i = 0; i < nn; i++) maxi = max(maxi, res[i]);
cout << maxi << endl;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t=1;
//cin >> t;
while(t--) solve();
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet