牛客小白月赛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" ;elsecout << "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 ++;elsecnt2 ++;}int t = min(cnt1, cnt2);cnt1 -= t;cnt2 -= t;if(cnt1 % 2)cnt1 = 1;elsecnt1 = 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;
}