出题人题解
A题
题意：判断字符串 是否为好字符串，需要满足每个字母的大小写形式要么一起出现要么都不出现，每个字母的条件互相独立。
题解：正常枚举 到
这
个小写字母是否都是好字符即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1e9 + 7;
void solve() {
int n; cin >> n;
string s; cin >> s;
vector<int> c0(26), c1(26);
for (auto c : s) {
if (c >= 'a' && c <= 'z') c0[c - 'a'] = 1;
else c1[c - 'A'] = 1;
}
for (int i = 0; i < 26; i++) {
if (c0[i] != c1[i]) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
B题
题意：对于给定的 个数
，表示第
个同学的数是否大于（1）/等于（0）/小于（-1）它们原本所有数值的平均数。
题解：首先全 情况，一定是满足的，其次
和
必须要么出现或者要么不出现，因为假设某个数大于平均数了，如果没有一个小于平均数的数来去平衡这个大于平均数的数的差值，就无法满足平均数的定义。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1e9 + 7;
void solve() {
int n; cin >> n;
int sum = 0, sum2 = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (x == -1) sum = 1;
else if (x == 1) sum2 = 1;
}
if (sum == sum2) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
C题
题意：将区间 内的数分别分到两个集合里面去，集合的
为集合内所有数的
值，需要满足两个集合
的值分别为
和非
。
题解：
首先特判 的情况，输出答案
；其次若区间长度小于等于
的，则没有一种情况满足要求，直接输出
-1。
现在对于其他情况，我们只需要把奇数放一堆，偶数放一堆，就能得到满足条件的情况，因为相邻奇数的 ，所以一定为
，而偶数一定都共同拥有一个
的因子，所以如果区间长度为偶数，答案为
，否则为
。
时间复杂度：
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1e9 + 7;
void solve() {
int q; cin >> q;
for (int i = 1; i <= q; i++) {
i64 l, r; cin >> l >> r;
if (l == r) {
cout << "-1\n";
continue;
}
if (r - l + 1 == 2) {
cout << (l == 1 ? 0 : -1) << '\n';
continue;
}
cout << (r - l + 1) % 2 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
D题
没想到这道模拟题过的比 题少，验题的时候有群友提醒了，当时想当然了，放到
题去了，感觉可能
与
交换下会好些。
题意：对于一个数组 ，找出对于所有可能的操作能够得到哪些不同众数。
题解： 枚举所有操作，然后用一个
容器存入每个数字当前操作出现的次数，最后取
容器最后一个元素，即是最大的众数，然后标记一下即可，最后升序输出即可。
另外，这题初始时只需要存入 最多
个数，如果将
个数都存入可能会导致
太大，
掉。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1e9 + 7;
typedef pair<int, int> pi;
int a[100005], sum[1000005], vis[1000005];
set<pi> s;
void add(int x) {
if (sum[x] > 0) s.erase({sum[x], x});
sum[x]++;
s.insert({sum[x], x});
}
void sub(int x) {
s.erase({sum[x], x});
sum[x]--;
if (sum[x] > 0) s.insert({sum[x], x});
}
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[a[i]]++;
}
for (int i = 1; i <= 1000000; i++) {
if (sum[i]) s.insert({sum[i], i});
}
for (int i = 1; i <= n; i++) {
sub(a[i]); add(a[i] + 1);
for (int j = 1; j <= n; j++) {
if (i == j) continue;
sub(a[j]); add(a[j] - 1);
vis[(*s.rbegin()).second] = 1;
sub(a[j] - 1); add(a[j]);
}
sub(a[i] + 1); add(a[i]);
}
for (int i = 0; i <= 1000001; i++) {
if (vis[i]) {
cout << i << ' ';
}
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
E题
题意：通过多少次操作，可以使得数组 变为全相同数的数组，每次操作是将数组
中所有数减去当前数组
的种类数。
题解：特判下初始时数组中每个数都一样的情况；否则可以发现，只有数组 中所有数变为
才会使得所有数一样，又可以发现，种类数是递减的，最多变化
次，且越小的数越先变为
，所以我们只需要排序去重一下，然后从小到大依次遍历，将当前数减去之前所减的数值，并且依次更新种类数
，直到全变为
为止。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1e9 + 7;
void solve() {
int n; cin >> n;
vector<i64> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
if (a.size() == 1) {
cout << "0\n";
return;
}
i64 ans = 0, sum = 0, cnt = 0;
for (int i = 0; i < a.size(); i++) {
if (a[i] - sum <= 0) {
cnt = 1;
continue;
}
i64 m = a.size() - i + cnt;
a[i] -= sum;
i64 d = (a[i] + m - 1) / m;
ans += d;
sum += d * m;
cnt = 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
F题
题解：可以发现我们的 的值只会有
到
这
种情况，那么对于每种情况，我们分别处理，而每种情况，我们可以发现如果区间长度一样，那么对应的当前
的出现次数也是一样的，而这部分可以直接组合数求解，如果区间长度为
，且有
个数比
小，
个数比
大，那么就有当前
出现次数
，但是我们求的是
，而这个
可能会爆
，所以需要对次幂进行欧拉降幂处理，即
，最后将所有数值乘积取模
即可。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1610612741;
const i64 mod_phi = mod - 1;
int add(i64 x, i64 y, i64 p) {
int ans = (x + y) % p;
return ans;
}
int qp(i64 a, i64 b, i64 p) {
int res = 1;
while (b) {
if (b & 1) res = 1LL * res * a % p;
a = a * a % p; b >>= 1;
}
return res;
}
int C[6005][6005], fac[6005];
void init() {
fac[0] = 1;
for (i64 i = 1; i <= 6001; i++) fac[i] = 1LL * fac[i - 1] * i % mod_phi;
for (int i = 0; i <= 6001; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = add(C[i - 1][j], C[i - 1][j - 1], mod_phi);
}
}
}
void solve() {
int n; cin >> n;
int ans = 1;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++) {
int x = i - 1, y = n - i;
int u = j / 2, v = j - 1 - u;
int res = 1LL * C[x][u] * C[y][v] % mod_phi * fac[j] % mod_phi * fac[n - j] % mod_phi * (n - j + 1) % mod_phi;
cnt = add(cnt, res, mod_phi);
}
ans = 1LL * ans * qp(i, cnt, mod) % mod;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
init();
// cin >> _;
while (_--) {
solve();
}
return 0;
}
投递牛客等公司