2021 高階競程 Contest #1 - 題解

鮪魚吃蛋糕

Task Provider: leo
Task Setter: leo

首殺 team21_24 (00:13)

解法說明

你可以把所有蛋糕依照好吃度

d

與價錢

c

的比值，由大到小排序。
接著依序拿蛋糕直到錢不夠為止。
時間複雜度為排序的

O (N \log N)

。

實作上需要特別注意一些問題：

雖然這題因為是浮點數除法，基本上不太會遇到這問題，
不過在寫根據比值排序的 compare 時，
儘量不要用除的，因為分母有可能為

0

，下方提供範例。
浮點數則因為除以

0

會變成 inf 所以不太會出問題，
不過還是可能被一些浮點數精度的問題影響到。

範例

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

因為題目採用相對誤差的比對方式，
所以其實可以儘量輸出很多位數，以求較精確的輸出，
請參考下方標準程式
如果
$K$ 為
$0$ 時不能直接跳出去，因為蛋糕可能也是
$0$ 元

如果題目改成蛋糕不可分割的話，這種依照 CP 值的 greedy 方法是不行的，
詳細原因與解法會在第七週的課程教到，如果有興趣的話可以先自己想想看為什麼。

標準程式

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

零二

Task Provider: arashi87
Task Setter: arashi87

首殺 team21_34 (00:38)

解法說明

題目要求你將

N

分解為

K

個二的幂次，其實就是單純的二進制分解而已，我們可以很容易的知道下面兩種情況會無法分解。

第一種是
$K > N$ ，當發生這種情況即使將
$N$ 通通分解成
$2^{0}$ 也會不夠
第二種是當
$N$ 轉換的二進制裡 1 的個數大於
$K$ 時也會無法分解，因為能夠分解的最少數字，其數量已經大於
$K$ 了。

而剩下就是如何分解而已，這邊我們利用 priority queue 可以自動找出最大值的功能，先將

N

做二進制分解並將分解出來的數字都放進 pq 裡，如果數量小於

K

的話就從 pq 取出最大的數除以

2

，生成兩個數字，並且放回 pq，這樣做一次可以使得

p q . s i z e

增加

1

，如此只需要一直重複直到

p q . s i z e = 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)

的做法，比起上面的解法又更快了一點，有興趣的可以自己研究看看。

標準程式

解法 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");
}

解法 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

Task Provider: D4nnyLee
Task Setter: D4nnyLee

首殺 team21_12 (00:02)

解法說明

Subtask 1
$O (N^{3})$

因為這個子任務

N

最大只有到

100

，因此我們可以直接枚舉所有可能的長度為

3

的子序列，並算出當中有多少是 BNT。

參考程式

#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

的陣列

c n t

，每個元素代表的意義如下：

$c n t_{0}$ 代表目前遇到的 B 的個數
$c n t_{1}$ 代表目前遇到的 BN 的個數
$c n t_{2}$ 代表目前遇到的 BNT 的個數

因此我們只要把

s

從左到右跑一次，並且維護

c n t

的元素，最後的

c n t_{2}

就是我們要的答案。

維護方法：

每個 N 都可以接在目前遇到的 B 的後面，形成
$c n t_{0}$ 個 BN

每個 T 都可以接在目前遇到的 BN 的後面，形成
$c n t_{1}$ 個 BNT

要注意答案可能會超出 int 的範圍，因此型別需要設為 long long。

標準程式

解法 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;
}

解法 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;
}

遞增數列

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) + \dots + p (1, m - 1)

例如

n = 2, m = 3

的遞增數列

a

可分為

$a_{3} = 2$ ：

$2, 2, 2$

$1, 2, 2$

$1, 1, 2$
$a_{3} = 1$ ：

$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), \dots, p (n, 1)

求出來，
再將

p (1, 2), p (2, 2), \dots, 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,|

格子選法數剛好為遞增數列的可能數，可用排列組合的計算方式算出

標準程式

解法 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;
}

解法 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

Task Provider: raiso
Task Setter: raiso

首殺 team21_15 (00:13)

解法說明

這題有兩個要點需要注意：

$len (M)$ 至少為
$1$
只需要考慮
$len (M) = 1$ or
$2$ 的情況，因為對於長度更長的
$M$ ，我們只需要將其同時去頭去尾後，所得到的吸引力只會大於等於還沒去頭去尾的情況。

超越
本題可以使用

O (N \log N)

的複雜度實作

將比對字串的過程看成多項式相乘，枚舉所有
$M$ 得到的吸引力其實就是多項式相乘後的結果，由於多項式相乘可以使用 FFT 與 IFFT 的方式加速，在
$O (N \log N)$ 的複雜度得到答案，由於整個過程過於神奇，有興趣的人可以自行研究。

標準程式

解法 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;
}

解法 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;
}

2021 高階競程 Contest #1 - 題解

鮪魚吃蛋糕

首殺 team21_24 (00:13)

解法說明

標準程式

零二

首殺 team21_34 (00:38)

解法說明

標準程式

BNT

首殺 team21_12 (00:02)

解法說明

Subtask 1 O(N3)

Subtask 2 O(N)

解法 1

解法 2

標準程式

遞增數列

首殺 team21_18 (00:26)

解法說明

解法 1

解法 2

標準程式

な NA

首殺 team21_15 (00:13)

解法說明

標準程式

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory

Subtask 1
$O (N^{3})$

Subtask 2
$O (N)$