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

## pA - 爬樓梯

**author : blame**
**problem setter : blame**

**first kill : wonderhoi**

:::spoiler **subtask 1 (1/100) 1 <= N <= 8**
**只要用心一點，寫一寫暴力解，即可拿到這一分**
:::

:::spoiler **subtask 2 (2/100) M = 0**
**用數學可以算得出來**
:::

:::spoiler **subtask 3 (3/100) M = 1**
**將走樓梯分成上下部分，每個部份使用 subtask 2 的方法計算**
:::

:::spoiler **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**

:::spoiler **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)$**
:::

:::spoiler **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)$**
:::

:::spoiler **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**

:::spoiler **subtask 1 (100/100)**
[**抄過來的**](https://cses.fi/problemset/task/1194)
**還把它變簡單了**
**這題寫不出來應該是沒在刷CSES吧?**
:::

**bonus by DB0917**

**賽跑**

## pD - N-1個人的公因數

**author : blame**
**problem setter : blame**

:::spoiler **subtask 1 (87/100) 1 <= Ai <= 2×10^4**
**可以使用奇奇怪怪的因數篩下去做**
:::

:::spoiler **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**

:::spoiler **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(\vert \sum^N_{i=1} A_i \vert lg(\vert \sum^N_{i=1} A_i \vert) + \vert \sum^Q_{j=1} S_j \vert lg(\vert \sum^Q_{j=1} S_j \vert))$**
:::

## pF - 簡單的線段樹

**author : blame**
**problem setter : blame**

:::spoiler **subtask 1 (10/100) 只有操作2**
**基礎的線段樹查詢**
**用 sparse table 也可以做**
**分塊會炸開**
:::

:::spoiler **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)$**
:::

:::spoiler **subtask 3 (87/100)**
**幾乎正解了**
:::

:::spoiler **subtask 4 (100/100)**
**相比 subtask 3，卡了一點點複雜度**
**有些是常數，有些是因為你的線段樹沒有build函式**
**有些人覺得剛開始輸入進來直接用單點修改就行**
**但其實build函式會省很多空間 + 時間**
**$O(Nlg(N))$ 跟 $O(4N)$ 其實差很多**
**當然，這題也可以用 zkw 壓一下複雜度**
:::

## pG - 採金礦

**problem setter : blame**

**first ac : ⫛魔⫛ • Blameazu**

:::spoiler **subtask 1 (100/100)**
[**這裡抄過來的**](https://tlx.toki.id/problems/troc-40/E)

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

## pH - APMO初選第0.5階段

**author : paul**
**problem setter : blame**

**first kill : wonderhoi**

:::spoiler **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(腦袋運轉次數)$**
:::

:::spoiler **subtask 2 (12/100) -1000 <= (n, m) <= 1000**
**暴力窮舉**
**複雜度 $O(2000^2)$**
:::

:::spoiler **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})$**
:::