---
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 範例

    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

#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

#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

#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 參考程式

#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

#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

#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

#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

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)

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

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

:::