网上关于FFT的介绍很多,算导也有相关算法描述,但是原来读的时候很清楚,可是读完也不知道怎么实现.这次在机房膜拜了大神的代码后自己琢磨了一个初等数学描述的证明,并得到了一个比较简洁的实现方法.主要是For OIer,所以给出的证明是简洁而不失于严谨性的(融合了算导, 维基百科的证明和自己的理解).
TJOI2012Day2解题报告
2014年4月22日 13:56
这一年的天津省选出的题还是比较复杂的，而Day2的题或许还好吧。
这第一题还算好做，只要想出了关于时间建立树状数组即可，当然运用可持久化线段树也未尝不可。具体细节看代码吧，只要想清楚了三十分钟应该能调对。需要注意的是打爆了防御的那次攻击，伤害值并不会翻倍，哪怕在这一次开始前攻击力已经大于防御力了也不会使伤害值翻倍。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 200005
#define base 1000000009
#define lowbit(x) ((x)&(-(x)))
vector<pair<int,int> > q;
vector<pair<pair<int,int>,int> > a;
int p[maxn],n,nq,s[maxn],ans;
void insert(int w,int x){
while(w < maxn){
s[w] += x;
w += lowbit(w);
}
}
int sum(int w){
int ret = 0;
while(w){
ret += s[w];
w -= lowbit(w);
}
return ret;
}
int main(){
freopen("defense.in","r",stdin);
freopen("defense.out","w",stdout);
scanf("%d%d",&n,&nq);
for(int i = 1;i<=n;i++) scanf("%d",&p[i]);
scanf("\n");
for(int i = 1;i<=nq;i++){
char c;
scanf("%c",&c);
if(c == 'A'){
int l,r,x;
scanf("%d%d%d\n",&l,&r,&x);
a.push_back(make_pair(make_pair(l,i),x));
a.push_back(make_pair(make_pair(r+1,i),-x));
}
else{
int x;
scanf("%d\n",&x);
q.push_back(make_pair(x,i));
}
}
sort(a.begin(),a.end());
sort(q.begin(),q.end());
vector<pair<pair<int,int>,int> >::iterator aw = a.begin();
for(int i = 0;i<q.size();i++){
while(aw < a.end() && (*aw).first.first <= q[i].first){
insert((*aw).first.second,(*aw).second);
aw++;
}
int l = 0,r = q[i].second;
while(l < r){
int m = (l + r) >> 1;
if(sum(m) >= p[q[i].first]) r = m;
else l = m + 1;
}
int ret = (2*sum(q[i].second) - sum(l))%base;
ans = (ans + ret) % base;
}
printf("%d\n",ans);
return 0;
}
第三题需要稍微动一下脑筋，第一个发现的是如果对于一个点，满足题设的点们应该分布在以之为中心的一个倾斜[tex]\frac{\pi}{4}[/tex]角度的一个正方形内部，由此想到将其转过来，变成我们通常看到的正方形那样。即对点(x,y)→(x+y,x-y),继续思考发现，我们只需将这些新点按照x坐标排序，然后扫一遍，找到在其上方和下方刚刚扫过的点中离它最近的两个点。判断这两个点的纵坐标与之相差是否小于等于R即可，如果小于等于R就把他俩所在的集合合并，最后求集合个数即可。用并查集维护。实现时注意，每两个点判断是否符合条件时需要验证x坐标和y坐标，具体实现可以把一个点拆分成两个点，碰到第一个点就把它加入平衡树中，以y坐标作为关键字，碰到第二个点就删除之即可。当然平衡树自然可以使用树状数组+二分+离散化代替。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define maxn 300005
#define connect(x,y) father[getfather((x))] = getfather((y))
int ans,n,r,father[maxn];
vector<pair<pair<int,int>,pair<int,int> > > point;
map<int,int> past;
map<int,int>::iterator t1,t2;
int getfather(int x){
if(father[x] == x) return x;
father[x] = getfather(father[x]);
return father[x];
}
int main(){
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
scanf("%d%d",&n,&r);
memset(father,-1,sizeof(father));
for(int i = 0;i<n;i++) father[i] = i;
for(int i = 0;i<n;i++){
int x0,y0;
scanf("%d%d",&x0,&y0);
point.push_back(make_pair(make_pair(x0+y0,1),make_pair(i,x0-y0)));
point.push_back(make_pair(make_pair(x0+y0+r+1,-1),make_pair(i,x0-y0)));//for erasing points first
}
sort(point.begin(),point.end());
for(int i = 0;i<point.size();i++){
int x = point[i].first.first,p = point[i].first.second,w = point[i].second.first,y = point[i].second.second;
t1 = past.find(y);
if(p == -1){
if((*t1).second == w) past.erase(t1);
}
else{
if(t1 != past.end()){connect(w,(*t1).second);past.erase(t1);}
else{
t1 = past.upper_bound(y),t2 = past.lower_bound(y);
if(t1 != past.end() && ((*t1).first)-y <= r) connect(w,(*t1).second);
if(t2 != past.begin() && y - (*(--t2)).first <= r) connect(w,(*t2).second);
}
past.insert(make_pair(y,w));
}
}
for(int i = 0;i<n;i++) ans += getfather(i) == i;
printf("%d\n",ans);
return 0;
}