前言：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;
}