# 2025/01/03

## Scoreboard

:::spoiler **scoreboard**
:::

**被搶了兩題深綠**

## **題目**

### **各題連結**

* **[SA 中譯](/@sa072686/r161tW4Lkx)**

* **[pA - AtCoder abc268_c - Chinese Restaurant](https://atcoder.jp/contests/abc268/tasks/abc268_c)**
* **[pB - AtCoder keyence2019_b - KEYENCE String](https://atcoder.jp/contests/keyence2019/tasks/keyence2019_b)**
* **[pC - AtCoder abc312_c - Invisible Hand](https://atcoder.jp/contests/abc312/tasks/abc312_c)**
* **[pD - AtCoder abc354_c - AtCoder Magics](https://atcoder.jp/contests/abc354/tasks/abc354_c)**

### **pA**

:::success
**旋轉盤子**
**隨便你轉，只要讓菜色 $i$ 與人 $i$、$i-1$、$i+1$ 配對最大即可**
**問你配對最大多少**
:::

::::spoiler **想法 + code**
:::warning
**將旋轉刻度當作答案儲存**
**只要將旋轉刻度++，最大的就是答案**
**阿為什麼匹配到 $i+1$ 跟 $i$ 和 $i-1$ 不用分開存?**
**因為旋轉不會影響到**
**我不會證明，但想想就差不多那樣**
:::
:::danger

**CODE**

#include <iostream>
using namespace std;
int v[int(2e5+87)];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v[(a-i+n)%n]++;
        v[(a-i+1+n)%n]++;
        v[(a-i-1+n)%n]++;
    }
    int mx = 0;
    for(int i = 0; i < n; i++)
        mx = max(mx, v[i]);
    cout << mx << '\n';
}

:::
::::

:::info
**因為這題跟 $charhao$ 寫過，所以沒打算那麼快去搶首殺**
**但其實也有一部分原因是因為我忘記我當初的想法是什麼了**
:::

### **pB**

:::success
**給你一個字串 $S$**
**問你能不能刪掉一段連續字串**
**使得剩下來的字串可以組成 $keyence$**
**$7 \le \vert S \vert \le 100$**
:::

::::spoiler **想法+code**
:::warning
**水題**
**枚舉兩邊界即可**
:::

:::danger

**CODE**

#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    bool ok = (s == "keyence");
    for(int i = 0; i < s.size(); i++) {
        for(int j = 0; j < s.size(); j++) {
            if(s.substr(0, i) + s.substr(j+1) == "keyence") {
                ok = true;
            }
        }
    }
    if(ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

:::
::::

### **pC**

:::success
**有 $N$ 個買家**
**有 $M$ 個賣家**
**求一數 $X$ 最小**
**使得可以用 $X$ 元出售的人 $>=$ 可以用 $X$ 元購買的人**
:::

::::spoiler **想法 + code**
:::warning
**二分搜裸題**
:::
:::danger

**CODE**

#include <iostream>
using namespace std;
int a[int(2e5+5)], b[int(2e5+87)];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int j = 0; j < m; j++) {
        cin >> b[j];
    }
    int l = 0, r = 1e9+87;
    while(l < r) {
        int mid = (l+r)>>1;
        int cnta = 0, cntb = 0;
        for(int i = 0; i < n; i++) {
            if(a[i] <= mid) {
                cnta++;
            }
        }
        for(int j = 0; j < m; j++) {
            if(b[j] >= mid) {
                cntb++;
            }
        }
        if(cnta >= cntb) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    cout << l << '\n';
}

:::
::::

:::info
**結果看不懂題目的意思，大輸光**
:::

### **pD**

:::success
**有 $N$ 個東西**
**每個東西都有數字 $A$ 跟數字 $C$**
**接著你要找兩數 $i, j$ 使得 $A_i > A_j and C_i < C_j$**
**然後把 $j$ 丟掉**
**求剩下來的集合**
:::

::::spoiler **題解 + code**
:::warning
**看起來就單調性的問題**
**所以先sort!**
**然後就會發現**
**假如我們按照 $A$ 的大到小走**
**每次看 $C$ 有沒有比走過的最小值 $C$ 還大即可**
:::

:::danger

**CODE**

#include <iostream>
#include <algorithm>
using namespace std;
int a[int(2e5+87)], c[int(2e5+87)], id[int(2e5+87)], ans[int(2e5+87)];
bool cmp(int l, int r) {
    return a[l] > a[r];
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> c[i];
        id[i] = i;
    }
    sort(id, id+n, cmp);
    int cnt = 0, mn = 1e9;
    for(int i = 0; i < n; i++) {
        if(c[id[i]] < mn) {
            ans[cnt] = id[i];
            mn = c[id[i]];
            cnt++;
        }
    }
    sort(ans, ans+cnt);
    cout << cnt << '\n';
    cout << ans[0]+1;
    for(int i = 1; i < cnt; i++) {
        cout << ' ' << ans[i]+1;
    }
    cout << '\n';
}

:::
::::

## 整體來說

**對於高二期末考難度，應該算是偏簡單了**
**實作量不高，裸題很多**
**算是手下留情了(?**