牛客小白月赛117

前言：solveABCF相对简单，D题思路简单但是实现麻烦，F题郭老师神力b(￣▽￣)。

A. 好字符串

题目大意：给定字符串s，里面的字母必须大小写同时出现。

【解题】：没什么好说的，直接模拟就行。

code：

#include <iostream>
#include <unordered_map>using namespace std;
int n; string s; 
unordered_map<char, int> mp;bool check()
{for(int i = 0; i < n; i++){char ch1 = s[i];char ch2;if(isupper(ch1))  ch2 = tolower(ch1);else ch2 = toupper(ch1);if(!mp.count(ch2)) return 0;}return 1;
}int main()
{cin >> n >> s;for(int i = 0; i < n; i++) mp[s[i]]++;if(check()) cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

---

B. 平均数

题目大意：给定一个由0 1 -1 组成的数组，0代表该元素等于平均数，1代表大于，-1代表小于。

问给出的数组是否合法。

【解题】：合法的情况：

• 全是0
• 1 -1 同时出现（不用管次数）

code：

#include <iostream>
#include <unordered_map>using namespace std;
unordered_map<int, int> mp;
int n;
int main()
{cin >> n;for(int i = 1; i <= n; i++) {int x; cin >> x;mp[x]++;}if((mp.count(-1) && mp.count(1)) || (!mp.count(-1) && !mp.count(1))) cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

---

C. 质数

题目大意：对于l到r的数，可以分配到s1，s2两个集合内，集合至少一个元素，且gcd(s1) = 1，gcd(s2) != 1，问|len1 - len2|的最小值。

【解题】：不难发现：如果把连续的偶数给s2可以保证gcd(s2)至少是2，把奇数给s1又保证了gcd(s1) = 1，这样又均分了l，r之间的元素，可以使得|len1 - len2|最小。

code：

#include <iostream>using namespace std;typedef long long LL;int main()
{int q; cin >> q;while(q--){LL l, r; cin >> l >> r;LL n = r - l + 1;if(n <= 1) cout << -1 << endl;else if(n == 2){if(l == 1) cout << 0 << endl;else cout << -1 << endl;}else {cout << n % 2 << endl;}}return 0;
}

---

F. 种类数

题目大意：长度为n的数组a，每次操作将所有的ai <-max(0， ai - cnt)其中cnt是a的种类数。问经过多少次操作可以使数组种类数变为1。

【解题】：对于开始种类数是一的情况直接输出0就行，对于开始不是1的情况，由于他们的差值只有再ai变为0的情况下才会改变，所有最终结果是全变为零的操作次数，为此我们不妨每个数只存一遍，我们需要知道第k次操作的种类数，减的总数以及当前数组的最小值。

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
priority_queue<LL, vector<LL>, greater<LL>> heap;
unordered_map<LL, LL> mp;int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){LL x; cin >> x;mp[x]++;}if (mp.size() == 1){cout << 0 << endl;return 0;}LL k = mp.size();LL ans = 0, now = 0;for (auto t : mp){heap.push(t.first);}bool flag = false;  // 用于处理0的特殊情况while (heap.top() == 0){heap.pop();flag = true;}while (heap.size()){while (heap.size() && now >= heap.top()){heap.pop();if (!flag){// 这里0是第一次出现，所以k不能--flag = true;continue;}k--;}if (heap.size()){LL x = heap.top();LL t = (x - now) / k;if(t == 0) t++;now += t * k;ans += t;}}cout << ans << endl;return 0;
}

---

D. 众数

题目大意：给定长度为n的数组a，必须执行下面操作一次：

选择两个不同位置i，j使得ai=ai + 1， aj=aj - 1，问众数出现的所有可能。

【解题】：本题的题眼其实是数据范围，它只有1e3所有我们是可以设计一个n^2或者n^2logn的算法的，n^2其实停留在枚举所有的ij上，所有我们只能用O(1) or O(logn)的时间找出每次ij的众数，这样就需要维护一个内部有序的数据结构，我们借助set维护。

code：

#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;const int M = 1e6 + 1, N = 2e3 + 10;int a[N];
struct node
{int num, cnt;bool operator< (const node& b) const{if (cnt != b.cnt) return cnt < b.cnt;return num < b.num;}
};
map<int, int> mp;
set<node> tmp;
set<int> ans;
int cnt[M];void add(int val)
{auto it = tmp.lower_bound({ val, cnt[val] });cnt[val]++;if (it->num == val){tmp.erase(it); // 需要重新插入，不能直接--tmp.insert({ val, cnt[val] });}else // 第一次出现{tmp.insert({ val, 1 });}
}void del(int val)
{auto it = tmp.lower_bound({ val, cnt[val] });cnt[val]--;tmp.erase(it);if (cnt[val] >= 1) // 还存在{tmp.insert({ val, cnt[val] });}
}int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];add(a[i]);}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i == j) continue;del(a[i]);add(a[i] + 1);del(a[j]);add(a[j] - 1);ans.insert(tmp.rbegin()->num);add(a[i]);del(a[i] + 1);add(a[j]);del(a[j] - 1);}}for (auto it = ans.begin(); it != ans.end(); it++) cout << *it << " ";return 0;
}

---

G. 中位数

题目大意：对于长度为n的排列，求下面式子对于所有n的排列的累乘对1610612741取模后的结果。

【解题】：组合数学 + 贡献法转化枚举对象

code：

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
#define endl '\n'
const int N = 6e3 + 10;
const int MOD = 1610612741;
const int PM = MOD - 1;
typedef pair<LL, LL> PII;
LL fac_len[N];
LL gac_glen[N];
LL f[N];
int n; 
LL C[N][N];LL qpow(LL a, LL b, LL MOD)
{LL ret = 1;while(b){if(b & 1) ret = ret * a % MOD;b >>= 1;a = a * a % MOD;}return ret;
}void init()
{fac_len[0] = 1;for(int i = 1; i <= n; i++) fac_len[i] = fac_len[i - 1] * i % PM;// vector<LL, vector<LL>> C(n + 1, vector<LL>(n + 1));for(int i = 0; i <= n; i++){C[i][0] = 1;for(int j = 1; j <= i; j++){C[i][j] =(C[i - 1][j] + C[i - 1][j - 1]) % PM;}}for(int mid = 1; mid <= n; mid++){for(int len = 1; len <= n; len++){// if(len % 2 == 1) f[mid] = (f[mid] + (C[mid - 1][len / 2] * C[n - mid][len / 2] % PM * fac_len[len] % PM * fac_len[n - len] % PM * (n - len + 1) % PM)) % PM;f[mid] = (f[mid] + (C[mid - 1][len / 2] * C[n - mid][len - (len / 2) - 1] % PM * fac_len[len] % PM * fac_len[n - len] % PM * (n - len + 1) % PM)) % PM;}}	
}void solve() 
{cin >> n;init();LL ans = 1;// for(int i = 0;i <= n; i++) cout << gac_glen[i] << " ";for(int mid = 1; mid <= n; mid++){ans = (ans * qpow(mid, f[mid], MOD)) % MOD;}cout << ans << endl;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while(T--){solve();}return 0;
}