叉姐的魔法训练.docx

叉姐的魔法训练.docx叉姐的魔法训练（第一课）----初级魔法练****br/>一集合操作
POJ 2443 Set Operation
有1000个集合每个集合有10000个元素，给出每个集合所有的元素和Q组询问，问元素x 和y是否属于同一个集合。
手抽写了个集合类出来，效率低了。其实用元素开数组，压缩所属的集合效率更高。
[cpp] view plaincopyprint?
1.
#include <iostream>
2.
#include <cstdio>
3.
#include <algorithm>
4.
#include <cstring>
5.
using namespace std;
6.
const int maxn=llll;
7.
typedef unsigned int uint;
8.
const int Size=30;
9.
class SetOperation(
10.
private:
11.
uint st[400];
12.
int getldx(int num)(
13.
return num/Size;
14.
}
15.
int getLft(int num)(
16.
return num%Size;
17.
}
18.
public:
19.
SetOperation()(
20.
init();
21.
)
22.
void init()(
23.
rnemset(st,0, sizeof (st));
24.
)
25.
void addVal(int num)(
26.
st[getldx(num)]|=(l<<getLft(num));
27.
)
28.
void delVal(int num)(
29.
st[getldx(num)]&=~(l<<getLft(num))
30.
)
31.
void chgVal(int num)(
32.
st[getldx(num)]A=(l<<getLft(num));
33.
}
34.
bool inSet(int num){
35.
return st[getldx(num)]&(l<<getLft(num));
36.
}
37.
}a[maxn];
38.
int main()
39.
{
40.
int
41.
while (~scanf(”％d“,&n)){
42.
for (int i=l;i<=n;i++){
43.
a[i].init();
44.
scanf(”％d“,&m);
45.
while (m--)(
46.
int num;
47.
scanf("%d"j&num);
48.
a[i].addVal(num);
49.
}
50.
}
51.
scanf ("%d'\&m);
52.
while(m--)(
53.
int x,y;
54.
bool flag=false;
55.
scanf(”％d%d”，&x,&y);
56.
for (int i=l;i<=n;i++)(
57.
if (a[i].inSet(x)&&a[i].inSet(y)){
58.
flag=true;
59.
break;
60.
}
61.
}
62.
if (flag) printf("Yes\n");
63.
else printf("No\n");
64.
}
65.
}
66.
return 0;
67.
}
二公式推导
POJ 3244 Difference between Triplets
〃数学好题
〃定义两个三元组I(xi,yi,zi)和J(xj,yj,zj),(可以看做是空间中的点)
〃他们的距离为 D(I,J) = max{xi-xj,yi-yj,zi-zj}-min{xi-xj,yi-yj,zi-zj},
〃给定n个三元组(n< = 200000)，求任意两个三元组的差的和
〃抽化出来的模型是max(a,b,c)-min(a,b,c),这个东西吧他放在数轴上a,b,c
〃我们要求最大和最小的差就是这三个点构成的线段的距离，那么我们这里再变通下是不是端 点到中间那个点的距离
〃其实画出这个图的时候，就可以看到这个距离为(|a-b| + |b-c| + |c-a|)/2,这样我们并不需 要关心中间的那个
〃对应到题目中的原型,就是(I (xi-xj)-(yi-yj) | + |(yi-yj)-(zi-zj) | +