2025/01/03

Scoreboard

scoreboard

被搶了兩題深綠

題目

各題連結

pA

旋轉盤子
隨便你轉，只要讓菜色

$i$ 與人
$i$ 、
$i - 1$ 、
$i + 1$ 配對最大即可
問你配對最大多少

想法 + code

將旋轉刻度當作答案儲存
只要將旋轉刻度++，最大的就是答案
阿為什麼匹配到

$i + 1$ 跟
$i$ 和
$i - 1$ 不用分開存?
因為旋轉不會影響到
我不會證明，但想想就差不多那樣

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

因為這題跟

$c h a r h a o$ 寫過，所以沒打算那麼快去搶首殺
但其實也有一部分原因是因為我忘記我當初的想法是什麼了

pB

給你一個字串

$S$
問你能不能刪掉一段連續字串
使得剩下來的字串可以組成
$k e y e n c e$

$7 \leq | S | \leq 100$

想法+code

水題
枚舉兩邊界即可

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

有

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

想法 + code

二分搜裸題

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

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

pD

有

$N$ 個東西
每個東西都有數字
$A$ 跟數字
$C$
接著你要找兩數
$i, j$ 使得
$A_{i} > A_{j} a n d C_{i} < C_{j}$
然後把
$j$ 丟掉
求剩下來的集合

題解 + code

看起來就單調性的問題
所以先sort!
然後就會發現
假如我們按照

$A$ 的大到小走
每次看
$C$ 有沒有比走過的最小值
$C$ 還大即可

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

整體來說

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