F. Monkeying Around 维护点在多少个线段上
http://codeforces.com/gym/101350/problem/F
题意：有m个笑话，每个笑话的区间是[L, R]，笑话种类有1e5，一开始所有猴子都在凳子上，听到一个笑话，就倒下，但是如果是听过的笑话，就重新回到凳子上。问最终有多少个猴子在凳子上。
相当于有1e5个线段，如果我们能知道第i个猴子，被多少个线段覆盖了，那么可以找出那些线段中的最后那一条，就是最后覆盖上去的那一条，那条线段是哪一个笑话，设为k，如果这个笑话覆盖这个猴子的次数 > 1，那么这个猴子将会回到凳子上。也就是只和最后一步有关
那么，假如有线段:
按左端点排序：[1, 100], [2, 2] ，一个扫描变量p1 = 1开始
按右端点排序：[2, 2], [1, 100]， 一个扫描变量p2 = 1开始
就能很快判断到第i个猴子被那些线段覆盖了。
按顺序枚举每一个猴子i，比如i = 2
那么，把i >= segment1[p1].L的都表明这条线段能覆盖i
吧i > segment2[p2].R的都表明这条线段已经离开了i
然后统计即可。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 2e5 + 20; struct Node { int L, R, id; }one[maxn], two[maxn]; bool cmp1(struct Node a, struct Node b) { return a.L < b.L; } bool cmp2(struct Node a, struct Node b) { return a.R < b.R; } int idForJoke[maxn]; int has[maxn]; set<int>ss; void work() { ss.clear(); memset(has, 0, sizeof has); int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { int pos, joke, dis; scanf("%d%d%d", &pos, &joke, &dis); one[i].L = max(1, pos - dis), one[i].R = min(n, pos + dis), one[i].id = i; two[i] = one[i]; idForJoke[i] = joke; } sort(one + 1, one + 1 + m, cmp1); sort(two + 1, two + 1 + m, cmp2); int ans = 0, p1 = 1, p2 = 1; for (int i = 1; i <= n; ++i) { while (p1 <= m && i >= one[p1].L) { ss.insert(one[p1].id); has[idForJoke[one[p1].id]]++; ++p1; } while (p2 <= m && i > two[p2].R) { ss.erase(two[p2].id); has[idForJoke[two[p2].id]]--; ++p2; } if (ss.size()) { ans += has[idForJoke[*ss.rbegin()]] > 1; } else ans++; } printf("%d ", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
G. Snake Rana 容斥原理 + 数学
题意是给定一个n * m（n, m <= 1e4）的地图，有k <= 20个污点，问有多少个子矩形，不包含任何一个污点
首先要知道n * m的矩形里面，一共有多少个子矩形。
对于列来说，可以选择边长是1， 2， ... m，分别有m种、m - 1种、m - 2 ... 1种选法。
对于行来说，可以选择边长是1， 2， ....n， 分别有n种、n - 1种，....1种选法。
所以一共(1 + .... + n) * (1 + .... + m) = (n + 1) * n / 2 * (m + 1) * m / 2种
1 << k暴力枚举哪一个点在里面，容斥原理奇减偶加
若包含x个点，那这x个点肯定围成一个矩形，那么有多少个矩形包含这个矩形呢？
如法炮制，算出在y方向，左右扩展能有多少个矩形，x方向，上下扩展能有多少种可能，然后相乘即可。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> LL n, m; int k; const int maxn = 20 + 2; int x[maxn], y[maxn]; LL ans; void dfs(int cur, int sel, int x1, int y1, int x2, int y2) { if (cur == k + 1) { if (!sel) return; LL res = (x1) * (n - x2 + 1) * (y1) * (m - y2 + 1); if (sel & 1) ans -= res; else ans += res; return; } dfs(cur + 1, sel + 1, min(x1, x[cur]), min(y1, y[cur]), max(x2, x[cur]), max(y2, y[cur])); dfs(cur + 1, sel, x1, y1, x2, y2); } void work() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= k; ++i) { scanf("%d%d", &x[i], &y[i]); } ans = (n + 1) * n / 2 * (m + 1) * m / 2; dfs(1, 0, inf, inf, -inf, -inf); cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
I. Mirrored String II 简单manacher变种不写题解了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> #include <time.h> const int maxn = 5e3 + 20; char str[maxn]; bool book[maxn]; int p[maxn]; int manacher(char str[], int lenstr) { str[0] = '*'; for (int i = lenstr; i >= 0; --i) { str[i + i + 2] = str[i + 1]; str[i + i + 1] = '#'; } int id = 0, maxLen = 0; for (int i = 2; i <= 2 * lenstr + 1; ++i) { if (!book[str[i]]) { p[i] = 0; continue; } if (p[id] + id > i) { p[i] = min(p[id] + id - i, p[2 * id - i]); } else p[i] = 1; while (str[i + p[i]] == str[i - p[i]] && (book[str[i - p[i]]] || str[i - p[i]] == '#')) ++p[i]; if (p[id] + id < p[i] + i) id = i; maxLen = max(maxLen, p[i]); } return maxLen - 1; } void work() { scanf("%s", str + 1); int lenstr = strlen(str + 1); bool flag = false; for (int i = 1; i <= lenstr; ++i) { if (book[str[i]]) { flag = true; break; } } if (!flag) { printf("0 "); return; } printf("%d ", manacher(str, lenstr)); }
A题待补，还有一题好像是防ak还没看，其他都是简单题，不过还是挺有意思
，