TFcis t27 寒訓 + 台南一中 115&116資訊讀書會 練習賽 (div 2) 題解

pA - 爬樓梯

author : blame
problem setter : blame

first kill : wonderhoi

subtask 1 (1/100) 1 <= N <= 8

只要用心一點，寫一寫暴力解，即可拿到這一分

subtask 2 (2/100) M = 0

用數學可以算得出來

subtask 3 (3/100) M = 1

將走樓梯分成上下部分，每個部份使用 subtask 2 的方法計算

subtask 4 (26/100) + subtask 5 (100/100)

subtask 4 只差在有沒有取模而已

正解大概只要有學過DP都會吧(?

#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9+7;
int main() {
    int n, m; cin >> n >> m;
    vector<int> dp(n+1, -1);
    for(int i = 0; i < m; i++) {
        int a; cin >> a;
        dp[a] = 0;
    }
    dp[0] = 1;
    for(int i = 1; i <= n; i++) if(dp[i] == -1) {
        dp[i] = 0;
        for(int j = 1; j <= min(i, 8); j++)
            dp[i] = (dp[i] + dp[i-j])%mod;
    }
    cout << dp[n] << '\n';
}

複雜度

$O(8N)$

pB - 快樂線段樹

author : sa
solution : paul
problem setter : blame

first kill : wonderhoi

subtask 1 (12/100) 1 <= N <= 2000, 1 <= Q <= 2000

暴力做

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, q; cin >> n >> q;
    vector<int> v(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    while(q--) {
        int l, r; cin >> l >> r;
        bool ok = true;
        while(ok && l < r) 
            ok = ok && (v[l] == v[++l]);
        cout << (ok ? "Yes" : "No") << '\n';
    }
}

複雜度

$O(QN)$

subtask 2 (22/100) Ai ∈ 1, 2, 3

將 1 2 3 拆成三個不同的陣列
使用前綴和去維護

但記得開IO優化

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, q; cin >> n >> q;
    vector<vector<int> > v(3, vector<int> (n+1));
    for(int i = 1; i <= n; i++) {
        int a; cin >> a;
        v[a-1][i]++;
        for(int j = 0; j < 3; j++) v[j][i] += v[j][i-1];
    }
    while(q--) {
        int l, r; cin >> l >> r;
        bool ok = false;
        for(int j = 0; j < 3; j++)
            ok = ok || (v[j][r]-v[j][l-1] == r-l+1);
        cout << (ok ? "Yes" : "No") << '\n';
    }
}

複雜度

$O(3N)$

subtask 3 (100/100)

稍微觀察一下就會發現，其實我們只要每次都記錄當格最左邊(或最右邊)的邊界即可
科朵莉樹(?
科朵莉樹因為用到了set 所以複雜度是

$O(Nlog(N)+Qlog(N))$
不足以通過這個子題
我們可以透過觀察，發現只要

$A_i\ne A_{i-1}$ 時，則

$A_j(i\le j)$ 的左界肯定會

$\ge i$
透過簡單的維護就可以做到

$O(N+Q)$ 解

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, q; cin >> n >> q;
    vector<int> L(n+1);
    int ls = 0;
    for(int i = 1; i <= n; i++) {
        int a; cin >> a;
        if(!i || ls != a) ls = a, L[i] = i;
        else L[i] = L[i-1];
    }
    while(q--) {
        int l, r; cin >> l >> r;
        cout << (L[r] <= l ? "Yes" : "No") << '\n';
    }
}

pC - 快跑，買宵夜

problem setter : blame

first kill : DB0917

subtask 1 (100/100)

抄過來的
還把它變簡單了
這題寫不出來應該是沒在刷CSES吧?

bonus by DB0917

賽跑

pD - N-1個人的公因數

author : blame
problem setter : blame

subtask 1 (87/100) 1 <= Ai <= 2×10^4

可以使用奇奇怪怪的因數篩下去做

subtask 2 (100/100)

稍微觀察一下就會發現
我們可以用前綴與後綴去達成這題

記得開 long long 跟IO優化

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n; cin >> n;
    vector<long long> v(n+1, 1), pre(n+1), suf(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    pre[1] = v[1], suf[n] = v[n];
    for(int i = 2; i <= n; i++) pre[i] = __gcd(pre[i-1], v[i]);
    for(int i = n-1; i >= 1; i--) suf[i] = __gcd(suf[i+1], v[i]);
    long long ans = max(pre[n], suf[1]);
    for(int i = 2; i <= n-1; i++)
        ans = max(ans, __gcd(pre[i-1], suf[i+1]));
    cout << ans << '\n';
}

複雜度

$O(4N)$

pE - 排列組合字串

author : sa
problem setter : blame

first kill : ⫛魔⫛ • Blameazu

subtask 1 (100/100)

簡單的sort + 二分搜的題目

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const pair<string, string> &a, const pair<string, string> &b) {
	if(a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}
bool cmp2(const pair<string, string> &a, const pair<string, string> &b) {
    return a.first < b.first;
}
int main() {
    int n, q; cin >> n >> q;
    vector<pair<string, string> > v(n);
    for(int i = 0; i < n; i++) {
        string s; cin >> s;
        v[i].second = s;
        sort(s.begin(), s.end());
        v[i].first = s;
    }
    sort(v.begin(), v.end(), cmp);
    while(q--) {
        string s; cin >> s;
        sort(s.begin(), s.end());
        auto lb = lower_bound(v.begin(), v.end(), make_pair(s, ""), cmp2);
        if(lb->first == s) cout << lb->second << '\n';
        else cout << "-1\n";
    }
}

複雜度

$O(|\sum _{i=1}^N{A}_i|lg(|\sum _{i=1}^N{A}_i|)+|\sum _{j=1}^Q{S}_j|lg(|\sum _{j=1}^Q{S}_j|))$

pF - 簡單的線段樹

author : blame
problem setter : blame

subtask 1 (10/100) 只有操作2

基礎的線段樹查詢
用 sparse table 也可以做
分塊會炸開

subtask 2 (12/100) 1 <= N, Q <= 2000

暴力做
記得開long long

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, q; cin >> n >> q;
    vector<long long> v(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    while(q--) {
        int c; cin >> c;
        if(c == 1) {
            int l, r, x; cin >> l >> r >> x;
            while(l <= r) v[l++] += x;
        } else {
            int l, r; cin >> l >> r;
            long long mx = v[l];
            while(l <= r) mx = max(mx, v[l++]);
            cout << mx << '\n';
        }
    }
}

複雜度

$O(QN)$

subtask 3 (87/100)

幾乎正解了

subtask 4 (100/100)

相比 subtask 3，卡了一點點複雜度
有些是常數，有些是因為你的線段樹沒有build函式
有些人覺得剛開始輸入進來直接用單點修改就行
但其實build函式會省很多空間 + 時間

$O(Nlg(N))$ 跟

$O(4N)$ 其實差很多
當然，這題也可以用 zkw 壓一下複雜度

pG - 採金礦

problem setter : blame

first ac : ⫛魔⫛ • Blameazu

subtask 1 (100/100)

這裡抄過來的

覺得這題非常的好，所以抄過來

pH - APMO初選第0.5階段

author : paul
problem setter : blame

first kill : wonderhoi

subtask 1 (10/100) a = 0

$$mn=m+n+0$$

$$mn-m=n$$

$$m(n-1)=n$$

$$m(n-1)-n=0$$

$$m(n-1)-(n-1)=1$$

$$(m-1)(n-1)=1$$

$$(m,n)=(2,2)\vee (0,0)$$

#include <iostream>
using namespace std;
int main() {
    cout << "2\n";
}

複雜度

$O(\mathrm{腦}\mathrm{袋}\mathrm{運}\mathrm{轉}\mathrm{次}\mathrm{數})$

subtask 2 (12/100) -1000 <= (n, m) <= 1000

暴力窮舉
複雜度

$O({2000}^2)$

subtask 3 (100/100)

其實剛剛只要推理出 subtask 1 就會滿分解了

$$mn=m+n+a$$

$$mn-m=n+a$$

$$m(n-1)=n+a$$

$$m(n-1)-n=a$$

$$m(n-1)-(n-1)=a+1$$

$$(m-1)(n-1)=a+1$$

所以只要找出

$a+1$ 的因數個數再

$\times 2$ 即可

#include <iostream>
using namespace std;
int main() {
    int a; cin >> a, a++;
    int ans = 0;
    for(int i = 1; i*i <= a; i++) ans += (a%i==0)*(a/i==i ? 1 : 2);
    cout << ans*2 << '\n';
}

複雜度

$O(\sqrt{a+1})$