题目这里
A.map裸题
#include <bits/stdc++.h>using namespace std;map <string, int> p;string s[] = {"Tetrahedron","Cube","Octahedron" ,"Dodecahedron","Icosahedron" };int ss[] = {4, 6, 8, 12, 20};int main() {ios::sync_with_stdio(false);for(int i = 0;i < 5;i ++) p[s[i]] = ss[i];int n, m = 0;string str;cin >> n;while(n --) cin >> str, m += p[str];cout << m; return 0; }
B.贪心，先上的课尽早下课，后上的课尽量晚点上课
#include <bits/stdc++.h>using namespace std;int n, l, r, l1, l2, r1, r2, ans;int main() {ios::sync_with_stdio(false);r1 = r2 = 1e9;cin >> n;while(n --) {cin >> l >> r;l1 = max(l1, l);r1 = min(r1, r);}cin >> n;while(n --) {cin >> l >> r;l2 = max(l2, l);r2 = min(r2, r);}ans = max(max(0, l2 - r1), max(0, l1 - r2));cout << ans;return 0; }
C.先讨论一下
如果n <= m ，那么前 n - 1 天都是当天补满，然后第 n 天被吃光
当 n > m ， 前 m 天肯定吃不完的
然后第 m + 1 天鸟走之后(没吃完)下一天再补上，就只有 n - 1 了
第 m + 2 天鸟走之后(没吃完)再补上，就只有 n - 1 - 2 了
......
第 ans 天鸟走之后仓库已经被吃光了
那么就有 n - (ans - m) * (ans - m - 1) / 2 - ans <= 0
令 t = ans - m ， 化简以后就有 t * t + t >= 2 * (n - m)
这时候可以选择二分，右边界肯定是sqrt(2 * 1e18)啦，再大会爆long long
当然可以直接开根，然后左右小小调整一下就能出来结果
#include <bits/stdc++.h>using namespace std;int main() {unsigned long long n, m, ans;cin >> n >> m;if(n <= m) cout << n;else {n = (n - m) * 2, ans = sqrt(n);while(ans * ans + ans >= n) ans --;ans ++;while(ans * ans + ans < n) ans ++;cout << ans + m;}return 0; }
D.为了避免重复，我们选择这样一个策略:
每当遇到一个左括号，我们计算包含这个左括号的合法序列数量加入ans
显然如果当前左括号左边有 L 个左括号(不含这个)
右边有 R 个右括号，那么对ans贡献为
sigma（C(L，i ) * C(R，i + 1) ），0 <= i < R
然后我们用一个范德蒙恒等式就变成了求 C(L + R ，R - 1)
剩下求组合数就O(nlogn)预处理，O(1)计算即可
#include <cstdio> #include <iostream>const int Mod = 1e9 + 7;char s[200010];long long ans, fac[200010], v[200010];int calc(long long x, int k = Mod - 2) {long long ret = 1;for(;k;k >>= 1, x = x * x % Mod)if(k & 1) ret = ret * x % Mod;return ret; }long long C(int n, int m) {return fac[n] * v[m] % Mod * v[n - m] % Mod; }int main() {fac[0] = v[0] = 1;for(int i = 1;i <= 200000;i ++)fac[i] = fac[i - 1] * i % Mod, v[i] = calc(fac[i]);int l = 0, r = 0;scanf("%s", s);for(int i = 0;s[i];i ++) r += (s[i] == ')');for(int i = 0;s[i];i ++) {if(s[i] == ')') r --;else ans += C(l + r, r - 1), ans %= Mod, l ++;}printf("%lld", ans);return 0; }
E.原序列为 1 - n 的排列，每次操作交换两数位置，并操作后求出逆序对个数
转化为二维模型就能很熟悉的联系到cdq上，于是 cdq + 树状数组 解决即可
当然树套树也可做，不再分析思路
用cdq来做呢，我们每次计算这次操作对逆序对数的改变量即为
( l, a[r] )左上和右下矩阵中点的个数 + ( r, a[l] ) 左上和右下矩阵中点的个数
- ( l, a[l] ) 左上和右下矩阵中点的个数 - ( r, a[r] ) 左上和右下矩阵中点的个数
当然我们需要注意避免逆序对的重复计算
另外需要注意我们计算的是改变量，所以答案是需要累加的
#include <bits/stdc++.h>#define lb(x) (x & (-x)) #define rep(i, j, k) for(int i = j;i <= k;i ++)using namespace std;const int maxn = 200010, maxm = maxn * 5;struct node {int x, y, op, bel, id;bool operator < (const node &a) const {if(x != a.x) return x < a.x;if(y != a.y) return y < a.y;return id < a.id;} }q[maxm], q0[maxm];int n, m, k, a[maxn], c[maxn]; long long ans[maxn];void add(int i, int x) {while(i <= n) c[i] += x, i += lb(i); }int ask(int i) {int ret = 0;while(i > 0) ret += c[i], i -= lb(i);return ret; }void solve(int l, int r) {if(l == r) return;int mid = (l + r) >> 1, cnt = 0;solve(l, mid), solve(mid + 1, r);rep(i, l, mid) if(q[i].op == 3 || q[i].op == -3) q0[++ cnt] = q[i];rep(i, 1 + mid, r) if(q[i].op != 3 && q[i].op != -3) q0[++ cnt] = q[i];sort(q0 + 1, q0 + cnt + 1);rep(i, 1, cnt) {if(q0[i].op == 3 || q0[i].op == -3) add(q0[i].y, q0[i].op / 3);else ans[q0[i].bel] += ask(q0[i].y) * q0[i].op;}rep(i, 1, cnt) if(q0[i].op == 3 || q0[i].op == -3) add(q0[i].y, q0[i].op / -3); }int main() {ios::sync_with_stdio(false);int l, r;cin >> n >> m;rep(i, 1, n) a[i] = i, q[++ k] = (node){i, i, 3, 0, k};rep(i, 1, m) {cin >> l >> r;if(l != r) {q[++ k] = (node){l - 1, n, -1, i, k};q[++ k] = (node){n, a[l] - 1, -1, i, k};q[++ k] = (node){l - 1, a[l] - 1, 2, i, k};q[++ k] = (node){l, a[l], -3, 0, k};q[++ k] = (node){r - 1, n, -1, i, k};q[++ k] = (node){n, a[r] - 1, -1, i, k};q[++ k] = (node){r - 1, a[r] - 1, 2, i, k};q[++ k] = (node){r, a[r], -3, 0, k};q[++ k] = (node){l - 1, n, 1, i, k};q[++ k] = (node){n, a[r] - 1, 1, i, k};q[++ k] = (node){l - 1, a[r] - 1, -2, i, k};q[++ k] = (node){l, a[r], 3, 0, k};q[++ k] = (node){r - 1, n, 1, i, k};q[++ k] = (node){n, a[l] - 1, 1, i, k};q[++ k] = (node){r - 1, a[l] - 1, -2, i, k};q[++ k] = (node){r, a[l], 3, 0, k};swap(a[l], a[r]);}}solve(1, k);rep(i, 1, m) {ans[i] += ans[i - 1];cout << ans[i] << endl;}return 0; }
代码写的很丑很暴力，仅供参考
