为啥我只写 C～F 没人看啊，是因为我太菜了吗？
A
判断除法的时候记得避免浮点数，虽然我不知道用浮点数会不会被卡。
signed main(){ios::sync_with_stdio(0), cin.tie(0);int a, b; cin >> a >> b;if(a + b == 9 || a * b == 9 || a - b == 9 || a == b * 9) cout << "Nine";else cout << "Nein"; cout << "\n";return 0;
}
B
依照题意模拟即可。大写字母转小写字母可以通过 c = c - 'A' + 'a' 实现。
signed main(){ios::sync_with_stdio(0), cin.tie(0);map<string, int> mp;int n; cin >> n;while(n --){string s; cin >> s;for(int i = 0; i < s.size(); i ++){if(s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A', s[i] += 'a';}mp[s] ++;}int ans = 0;for(auto [st, num]: mp) ans = max(ans, num);cout << ans << "\n";return 0;
}
C
拿一个 set 来维护所有的糖。每次在里面二分找到最近的那个元素，按照题意模拟即可。
set<int> s;
int n, pos, ans;signed main(){ios::sync_with_stdio(0), cin.tie(0);cin >> n;for(int i = 1; i <= n; i ++){int a; cin >> a;s.insert(a);}int pos = 0;for(int i = 1; i <= n; i ++){auto pre = s.lower_bound(pos);int res = 1e18;if(pre != s.end()) res = *pre;if(pre != s.begin()){int cur = *(-- pre);if(abs(pos - cur) <= abs(pos - res)) res = cur;}ans += abs(res - pos); pos = res;s.erase(res);}cout << ans << "\n";return 0;
}
D
全局加等效于上限减。
令当前的等效电量上限为 \(V - t_q\)，新加入电池的电量为 \(w_q - t_q\) 就好了。
这样就变成了维护一个支持「增加一个元素」、「查询最大元素」的集合，用优先队列就好了。
priority_queue<int> pq;
int v, del, org;signed main(){ios::sync_with_stdio(0), cin.tie(0);int q; cin >> q >> v; org = v;int t = 0;while(q --){int opt; cin >> opt;int tq, wq; cin >> tq;v = org - tq;if(opt == 1){cin >> wq;pq.push(wq - tq);}else{if(pq.empty()){cout << "-1\n"; continue;}int res = pq.top(); pq.pop();cout << org - max(0ll, v - res) << "\n";}}return 0;
}
E
推式子发现，\((\sum_{i = 1}^{k} b_i) ^ 2 = \sum_{i = 1}^{k} \sum_{j = 1}^{k} b_i b_j\)。
然后，考虑每一个 \(a_i ^ 2\) 的贡献和 \(a_i a_j(i < j)\) 的贡献。
前者会在一个方案中出现一次，包含她的方案数为 \(\binom{n-1}{k-1}\)，总贡献为 $ \binom{n-1}{k-1} \sum_{i=1}^{n} a_i^2$，直接计算。
后者会在一个方案里出现两次，包含她的方案数为 \(\binom{n-2}{k-2}\)，总贡献为 $ \binom{n-2}{k-2} \sum_{i < j \le n} a_i a_j$。记 \(a\) 前缀和为 \(pre_i\)，\(\sum_{i < j \le n} a_i a_j = \sum_{i=1}^{n-1} a_{i+1} pre_i\)，也可以 \(\mathcal{O}(n)\) 计算了。
signed main(){ios::sync_with_stdio(0), cin.tie(0);cin >> n >> k;for(int i = 1; i <= n; i ++) cin >> a[i];pre();int ans = 0;for(int i = 1; i <= n; i ++){int res = a[i] * a[i] % MOD;(ans += bin(n - 1, k - 1) * res) %= MOD;}int sum = 0;for(int i = 1; i <= n; i ++){int res = a[i] * sum * 2 % MOD;(ans += bin(n - 2, k - 2) * res) %= MOD;(sum += a[i]) %= MOD;}cout << ans << "\n";return 0;
}
组合数可以预处理做到 \(\mathcal{O}(1)\) 计算，这里不赘述了。
F
我们发现，长度很重要，其次是字典序。
然后由于前导 \(0\) 的限制，还不能直接贪心。
所以我们不难想到枚举第一个字符串，后面就可以贪心了。
但是这样很难算啊。我们枚举开头的目的是为了避免最长长度作开头前导 \(0\) 太多。但是显然枚举这么多事没有意义的，因为同一个长度的所有字符串中，有资格作为第一个字符串的只有字典序最大的那个。
这样就简单了，我们枚举每个长度下字典序最大的字符串，可能的开头只有 \(10\) 种。
现在定义集合 \(S\) 作为剩下的 \(k - 1\) 个字符串集合。显然地我们按照长度从高到低，其次字典序从大到小放没用过的 \(k-1\) 个进来。
这样就变成了拼数。这是一个简单的邻项交换问题，我们将 \(S\) 中的字符串按照 \(s_i + s_j > s_j + s_i\) 排序即可，容易证明这是一个严格弱序。
总复杂度是 \(\mathcal{O}(n \cdot len^2 \cdot \log k)\)。但是我的代码常数奇小，冲过去了。
const int N = 1e5 + 7;
vector<string> s[11];
int n, k;signed main(){ios::sync_with_stdio(0), cin.tie(0);cin >> n >> k;for(int i = 1; i <= n; i ++){string t; cin >> t; int sz = t.size();s[sz].push_back(t);}for(int i = 1; i <= 10; i ++){sort(s[i].begin(), s[i].end(), [](string x, string y){return x > y;});}string ans;for(int i = 1; i <= 10; i ++){if(s[i].empty()) continue;string st = s[i][0];int cnt = k - 1;vector<string> str;for(int j = 10; j >= 1; j --){if(s[j].empty()) continue;if(j != i && cnt) cnt --, str.push_back(s[j][0]);for(int k = 1; k < s[j].size(); k ++){if(cnt) cnt --, str.push_back(s[j][k]);if(!cnt) break;}if(!cnt) break;}sort(str.begin(), str.end(), [](string x, string y){return x + y > y + x;});for(string ss: str) st += ss;string res;for(int i = 0; i < st.size(); i ++){if(st[i] != '0'){res = st.substr(i); break;}}if(res.empty()) res = "0";if(res.size() > ans.size() || (res.size() == ans.size() && res > ans)) ans = res;}cout << ans << "\n";return 0;
}
G
我吧会做。