牛客小白月赛98

骰子魔术

• jackle 会拿出一枚骰子，骰子的表面分别写上了从 1∽5001\backsim 5001∽500 的数字，朋友会随便说一个 1∽5001\backsim 5001∽500 之间的点数，jackle 都能保证百分之百的掷出这个点数。

当然 jackle 有备而来，他准备了 nnn 枚特殊的骰子，第 iii 枚特殊骰子，可以保证每次掷出的点数都为 aia_iai​。
jackle 想问你，他能不能只拿出一枚事先准备好的特殊骰子，成功完成这次魔术。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    bool f = false;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        if(x == k)
            f = true;
    }
    if(f)
        cout << "YES" ;
    else
        cout << "NO";
    return 0;
}

最少剩几个？

给定一个长度为 𝑛 的序列 𝑎, 如果当前序列长度至少为 2

• 选择 i,j (i≠j)，如果满足 ai+aj是奇数，那么你可以同时删除 ai,aj​。
• 选择 i,j (i≠j)，如果满足 ai×aj是奇数，那么你可以同时删除 ai,aj​。

最少剩几个数？

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int cnt1 = 0, cnt2 = 0;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        if(x & 1)
            cnt1 ++;
        else
            cnt2 ++;
    }
    int t = min(cnt1, cnt2);
    cnt1 -= t;
    cnt2 -= t;
    if(cnt1 % 2)
        cnt1 = 1;
    else
        cnt1 = 0;
    cout << cnt1 + cnt2 << endl;
    return 0;
}

两个函数

他有 Q 次询问，每次给定 a,x，请你计算 g(x)mod  998244353的结果。C/C++ 1秒。

#include<bits/stdc++.h>
using namespace std;

#define MOD 998244353
using int128 = __int128;

istream& operator>>(istream& is, int128& val) {
    string str;
    is >> str;
    val = 0;
    bool neg = false;
    if (str[0] == '-') {
        neg = true;
        str = str.substr(1);
    }
    for (char& c : str) {
        val = val * 10 + (c - '0');
    }
    if (neg) {
        val = -val;
    }
    return is;
}

ostream& operator<<(ostream& os, int128 val) {
    if (val < 0) {
        os << '-';
        val = -val;
    }
    string s;
    do {
        s += char(val % 10 + '0');
        val /= 10;
    } while (val);
    reverse(s.begin(), s.end());
    return os << s;
}

void solve() {
    int128 a, x;
    cin >> a >> x;
    int128 res;
    if (x == 1) {
        res = a % MOD;
    } else {
        int128 a2 = (a * a) % MOD;
        int128 sum_x = (x * (x - 1) / 2) % MOD;
        res = (a2 * sum_x) % MOD;
    }
    cout << res << endl;
}

int main() {
    int n;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        solve();
    }
    return 0;
}

切割 01 串 2.0

长度n 的 01 串，只要满足切割条件，最多可以切割多少次？

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, L, R;
    cin >> n >> L >> R;
    string s;
    cin >> s;
    
    vector<int> p(n + 1, 0); // p[i] 表示前 i 个字符中 0 的数量
    vector<int> q(n + 1, 0); // q[i] 表示前 i 个字符中 1 的数量
    
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] + (s[i - 1] == '0');
        q[i] = q[i - 1] + (s[i - 1] == '1');
    }
    
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) {
                int C0 = p[k] - p[i];
                int C1 = q[j] - q[k];
                int absDiff = abs(C0 - C1);
                if (L <= absDiff && absDiff <= R) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + 1);
                }
            }
        }
    }
    
    cout << dp[0][n] << endl;
    return 0;
}

and xor or

长度为 𝑛 的序列 𝑎,有多少个区间 [𝑙,𝑟]