首页 > 代码库 > BestCoder #20
BestCoder #20
A,B水
B的话可以花式做
线段树可以
优先队列可以
最好的方法就是离散后，对一个线段xi,yi
分成两个端点xi和yi+1
表示在xi点会加入一个线段，在yi+1会减少一个线段
用数组来存就是a[xi]++, a[yi+1]-- ，然后求a数组的最大前缀和就行了
C题是个DP
题意是，有n（1e3)个数对，a[i],b[i]
某个人有m(1e3)个能量，按顺序每次可以在a[i]或者b[i]中选择一个数 或者一个数都不选， 但是选择b[i]会花费1点能量，问他能选择出的最长上升子序列的长度是多少
dp[i][j][l]表示i在最长上升子序列中，已经损失j点能量,第i个人转换了ai和bi的最长上升子序列的数目，可以得到方程 dp[i][j][0]=max{dp[k][j][0](a[k]<a[i])+1,dp[k][j][1](b[k]<a[i])+1},dp[i][j][1]=max(dp[k][j-1][0](a[k]<b[i])+1,dp[k][j-1][1](b[k]<b[i])+1)。
这个的话看起来是个n^3的
我们可以优化成n^2 logn的
具体做法就是利用树状数组， 类似于求和的方法，也可以求最大值， 那么总共开m+1个树状数组。
开一个数组dp[i][j] 表示到第i个数，剩余j能量的最长上升子序列。
首先在第j个树状数组中找比a[i]小的数中最大的dp值，那么同时就可以更新该树状数组
然后在第j+1个树状数组中找比b[i]小的数中最大的dp值，那么同时就可以更新第j个树状数组，因为消耗了1个能量
看了bin神代码 ，学习了一下
D 题，
题意很简单，有个人，有Q（5e4)个操作，
每次操作有两种，一种是插入一个三维点，另外一个是问在 x1,y1,z1到x2,y2,z2这个区间内有多少三维点了（即x1<=x<=x2, y1<=y<=y2, z1<=z<=z2，满足要求的点(x,y,z)个数）
刚开始妄图使用三维树状数组来搞。 使用了花式hash，结果还是TLE了
赛中想到CDQ但没有细想。
赛后想了想还是很容易理解的。
具体是， 首先把求x1,y1,z1到x2,y2,z2这个区间内有多少三维点，转化为求一些点到原点这个区间内有多少点。
然后cdq分治，这样可以把时间这一维干掉， 干掉后按照x排序，再利用cdq，那么x这一维也就干掉了，再将y进行排序，那么剩下这一维z就可以用树状数组统计了。
这样也可以推广到多维区间求点个数。。
注意有个花式减少复杂度的方法。就是比如我们有个数组 a，如果我们用a只用了一小部分， 假设每次我们都对其进行memset初始化， 这样很浪费时间
于是再开一个数组vis表示时间戳， vis[i] = 2表示在第2个时间点我们用到了这个位置， 那么每次我们统计的时候， 把所有vis[i]=2的位置统计即可
每次更新某个位置的话，就把该位置的vis改成现在这个时间戳。
参考了chnlich的代码。
C 题code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#define MAXN 1111
#define MAXM 222222
#define INF 1000000001
using namespace std;
struct BIT {
int a[MAXN * 2];
int n;
void init(int _n) {
n = _n;
for(int i = 1; i <= n; i++) a[i] = 0;
}
int lowbit(int x) {
return x & -x;
}
int getsum(int x) {
int s = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
s = max(s, a[i]);
}
return s;
}
void add(int x, int v) {
for(int i = x; i <= n; i += lowbit(i)) {
a[i] = max(a[i], v);
}
}
}bit[MAXN];
int a[MAXN], b[MAXN], c[2 * MAXN];
int main() {
int T, n, m, cnt;
scanf("%d", &T);
while(T--) {
cnt = 0;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) {
scanf("%d%d", &a[i], &b[i]);
c[cnt++] = a[i];
c[cnt++] = b[i];
}
sort(c, c + cnt);
cnt = unique(c, c + cnt) - c;
for(int i = 0; i < n; i++) {
a[i] = lower_bound(c, c + cnt, a[i]) - c + 1;
b[i] = lower_bound(c, c + cnt, b[i]) - c + 1;
}
int ans = 0;
for(int i = 0; i <= m; i++) bit[i].init(cnt);
for(int i = 0; i < n; i++) {
for(int j = 0; j <= m; j++) {
int mx = bit[j].getsum(a[i] - 1) + 1;
bit[j].add(a[i], mx);
ans = max(ans, mx);
if(j < m) {
mx = bit[j + 1].getsum(b[i] - 1) + 1;
bit[j].add(b[i], mx);
ans = max(ans, mx);
}
}
}
printf("%d\n", ans);
}
return 0;
}D题code#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <algorithm> #include <map> #define MAXN 55555 #define MAXM 222222 #define INF 1000000001 using namespace std; int nx, ny, nz, n; int xa[MAXN], ya[MAXN], za[MAXN], xb[MAXN], yb[MAXN], zb[MAXN], op[MAXN]; int cx[MAXN * 2], cy[MAXN * 2], cz[MAXN * 2]; int lt[MAXN * 8], lx[MAXN * 8], ans[MAXN * 8], ct1, ct2, m; struct Q{ int op, x, y, z; Q() {} Q(int _op, int _x, int _y, int _z){op = _op; x = _x; y = _y; z = _z;} }q[MAXN * 8]; bool cmpx(int x, int y) { if(q[x].x == q[y].x) return q[x].op < q[y].op; return q[x].x < q[y].x; } bool cmpy(int x, int y) { if(q[x].y == q[y].y) return q[x].op < q[y].op; return q[x].y < q[y].y; } struct BIT { int a[MAXN * 2], vis[MAXN * 2], ind; void clr() { ind++; } int lowbit(int x) { return x & -x; } int getsum(int x) { int s = 0; for(int i = x; i > 0; i -= lowbit(i)) { if(vis[i] == ind) s += a[i]; } return s; } void add(int x, int v) { for(int i = x; i <= nz; i += lowbit(i)) { if(vis[i] == ind) a[i] += v; else vis[i] = ind, a[i] = v; } } }bit; void gao() { bit.clr(); sort(lx + 1, lx + ct2 + 1, cmpy); for(int i = 1; i <= ct2; i++) { if(q[lx[i]].op == 1) bit.add(q[lx[i]].z, 1); else ans[lx[i]] += bit.getsum(q[lx[i]].z); } } void cdq2(int l, int r) { if(l >= r) return; int mid = (l + r) >> 1; ct2 = 0; for(int i = l; i <= mid; i++) if(q[lt[i]].op == 1) lx[++ct2] = lt[i]; for(int i = mid + 1; i <= r; i++) if(q[lt[i]].op == 2) lx[++ct2] = lt[i]; gao(); cdq2(l, mid); cdq2(mid + 1, r); } void cdq(int l, int r) { if(l >= r) return; int mid = (l + r) >> 1; ct1 = 0; for(int i = l; i <= mid; i++) if(q[i].op == 1) lt[++ct1] = i; for(int i = mid + 1; i <= r; i++) if(q[i].op == 2) lt[++ct1] = i; sort(lt + 1, lt + ct1 + 1, cmpx); cdq2(1, ct1); cdq(l, mid); cdq(mid + 1, r); } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); nx = ny = nz = 0; m = 0; memset(ans, 0, sizeof(ans)); for(int i = 0; i < n; i++) { scanf("%d", &op[i]); scanf("%d%d%d", &xa[i], &ya[i], &za[i]); if(op[i] == 1) { cx[nx++] = xa[i]; cy[ny++] = ya[i]; cz[nz++] = za[i]; } else { scanf("%d%d%d", &xb[i], &yb[i], &zb[i]); cx[nx++] = (--xa[i]); cy[ny++] = (--ya[i]); cz[nz++] = (--za[i]); cx[nx++] = xb[i]; cy[ny++] = yb[i]; cz[nz++] = zb[i]; } } sort(cx, cx + nx); sort(cy, cy + ny); sort(cz, cz + nz); nx = unique(cx, cx + nx) - cx; ny = unique(cy, cy + ny) - cy; nz = unique(cz, cz + nz) - cz; for(int i = 0; i < n; i++) { xa[i] = lower_bound(cx, cx + nx, xa[i]) - cx + 1; ya[i] = lower_bound(cy, cy + ny, ya[i]) - cy + 1; za[i] = lower_bound(cz, cz + nz, za[i]) - cz + 1; if(op[i] == 1) { q[++m] = Q(1, xa[i], ya[i], za[i]); } else { xb[i] = lower_bound(cx, cx + nx, xb[i]) - cx + 1; yb[i] = lower_bound(cy, cy + ny, yb[i]) - cy + 1; zb[i] = lower_bound(cz, cz + nz, zb[i]) - cz + 1; q[++m] = Q(2, xb[i], yb[i], zb[i]); q[++m] = Q(2, xb[i], yb[i], za[i]); q[++m] = Q(2, xb[i], ya[i], zb[i]); q[++m] = Q(2, xa[i], yb[i], zb[i]); q[++m] = Q(2, xa[i], ya[i], zb[i]); q[++m] = Q(2, xa[i], yb[i], za[i]); q[++m] = Q(2, xb[i], ya[i], za[i]); q[++m] = Q(2, xa[i], ya[i], za[i]); } } cdq(1, m); for(int i = 1; i <= m; i++) { if(q[i].op == 2) { printf("%d\n", ans[i] - ans[i + 1] - ans[i + 2] - ans[i + 3] + ans[i + 4] + ans[i + 5] + ans[i + 6] - ans[i + 7]); i += 7; } } } return 0; }
BestCoder #20