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\n", 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;
}
View Code
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;
}
View Code
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\n");
return;
}
printf("%d\n", manacher(str, lenstr));
}
I
A题待补，还有一题好像是防ak还没看，其他都是简单题，不过还是挺有意思
，
标签：Arabella,return,Contest,int,题解,maxn,str,include,id From： https://blog.51cto.com/u_15833059/5779570