<style>
html, body, .ui-content {
background-color: #333;
color: #fff;
}
</style>

# 2024/05/03 期中考
### **選修期中考**

# Scoreboard
### **意外的快XD**
:::spoiler scoreboard
:::

# 考試過程
**原本想說從$pA$寫到$pD$**
**結果$pA$太麻煩就直接由後寫到前了:)**
**$8$ $mins$ $pD$ <font color = "green">$AC$</font>**
**$12$ $mins$ $pC$ <font color = "green">$AC$</font>**
**$14$ $mins$ $pB$ <font color = "green">$AC$</font>**
**$20$ $mins$ $pA$ <font color = "green">$AC$</font>**
**$Total$ : $20$ $mins$**
<font color = "green">**$4$ $AC$**</font>$\space\space$ <font color = "red">**$0$ $WA$**</font>

# [題目](https://hackmd.io/@sa072686/ByEOV0gMA/%2F%40sa072686%2FKattis_orderedproblemset)
* [**pA**](https://open.kattis.com/problems/orderedproblemset)

:::success
**題意 :**
**給一數 $N$ 表示接下來會有 $N$ 個數字$(1 \leq d \leq N)$且數字皆不相同**
**把$N$ 分成 $K$ 個集合 $(1 \leq K \leq N \space \cap \space K \times t = N)$**
**符合 $i < j$ 則 第 $i$ 個集合的數字皆小於第 $j$ 個集合的數字**
:::

:::warning
**想法 :**
**觀察而得 : 在第 $i$ 段的集合中**
**符合題目要求的集合 必只有$(i-1) \times (n/k)+1$ ~ $(i-1) \times (n/k) + (n/k)$ 的數字**
**所以每次只要看 $k$ 個集合有沒有都符合題意就行**
:::

:::spoiler <font color = "gold">**code**</font>

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    int main() {
        ios::sync_with_stdio(false), cin.tie(0);

        int n; cin >> n;
        vector<int> v(n);
        for(int &d : v) {cin >> d;}

        bool ans = false;
        for(int k = 2; k <= n; k++) {
            if(n % k ==0) {
                bool ok = true;
                for(int i = 0; i < n; i++) {
                    if(v[i] > i-i%(n/k)+n/k) {ok = false;}
                }
                if(ok) {cout << k << '\n'; ans = true;}
            }
        }

        if(!ans) {cout << "-1\n";}


    }

:::

:::info
**心得 :**
**需要耐心觀察的題目**
**~~但是我先跑去搶 $pD$ 首殺~~**
**這題最重要的是~通靈~出解題思路**
**實作不難 (但我卡在```i-i%(n/k)+n/k```這行XD**
:::

* [**pB**](https://atcoder.jp/contests/abc203/tasks/abc203_a?lang=en)

:::success
**題意 :**
**給三數 $A$ $B$ $C$**
**假如有兩數相同則輸出另外一數**
**沒有則輸出 $0$**
:::

:::warning
**思路 :**
**if elseif elseif else**
:::

:::spoiler <font color = "gold">**code**</font>

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long 
    int main() {
        ios::sync_with_stdio(false), cin.tie(0);

        int a, b, c; cin >> a >> b >> c;
        if(a == b) {
            cout << c << '\n';
        } else if(b == c) {
            cout << a << '\n';
        } else if(c == a) {
            cout << b << '\n';
        } else {
            cout << "0\n";
        }
    }

:::

:::info
**心得 :**
**abc_a水題**
:::

* [**pC**](https://atcoder.jp/contests/abc214/tasks/abc214_b?lang=en)

:::success
**題意 :**
**給兩數 $S \space \space T$**
**求$(x,y,z)$ 滿足 $x+y+z \leq S$ 和 $x \times y \times z \leq T$ 有多少組可能**
**$(1 \leq S \leq 100)$**
:::

:::warning
**思路 :**
**$S^3 \leq 10^6$**
**暴力就行 (但其實 $10^6$ 在一些比較古早的環境下會 $TLE$)**
**我有稍微壓一下複雜度以免出事XD**
**但很多人 $S^3$ 過了 就很玄**
:::

:::spoiler <font color = "gold">**code**</font>

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long 
    int main() {
        ios::sync_with_stdio(false), cin.tie(0);

        ll s, t; cin >> s >> t;
        int ans = 0;
        for(int i = 0; i <= s; i++) {
            for(int j = 0; j <= s-i; j++) {
                for(int k = 0; k <= s-i-j; k++) {
                    if((ll)i * j * (k)<=t) {ans++;} 
                }
            }
        }
        cout << ans << '\n';
    }

:::

:::info
**心得 :**
**應該又是一題水題:D**
:::

* [**pD**](https://atcoder.jp/contests/abc072/tasks/arc082_a?lang=en)

:::success
**題意 :**
**給一數 $N$ 代表一陣列有 $N$ 個數**
**你可以對陣列的每一個數做以下操作 :**
**把 $A_i$ 變成 {$A_i - 1$ or $A_i$ or $A_i + 1$}**
**求這個陣列最多同樣的數字有多少個**
:::

:::warning
**思路 :**
**每一行(直的三格)必不相同**
**代表我這個數字出現多少次就是在陣列裡面能出現的最多次**
**-> 找所有可能的數字的最多出現次數**
**1. 開一個陣列然後暴搜$1$ ~ $10^5+5$ ($1 \leq A_i \leq 10^5$) 複雜度 : $O(10^5+4)$**
**2. map 複雜度 : $O(n \times 3)$**
:::

:::spoiler <font color = "gold">**code**</font>

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long 
    int main() {
        ios::sync_with_stdio(false), cin.tie(0);

        map<int, int> mp;
        int n; cin >> n;

        for(int i = 0; i < n; i++) {
            int a; cin >> a;
            mp[a]++;
            mp[a-1]++;
            mp[a+1]++;
        }
        int mx = 0;
        for(auto &d : mp) {
            mx = max(mx, d.second);
        }
        cout << mx << '\n';
    }

:::

:::info
**心得**
**當下就真的感覺是這樣寫**
**然後就 $AC$ 證明法**
**感覺我好毒瘤XD**
:::