09-09 HDU_Steps5.3 树状数组,LCA HDU1166 HDU2492 HDU3584 HDU2586 HDU2874 HDU3486 HDU2688

2016-12-14 09:53:18来源:http://blog.csdn.net/swm8023/article/details/6770841作者:swm8023人点击

5.3.1 HDU1166 敌兵布阵


裸的树状数组


query[i..j]=sum(j)-sum(i-1)


#include 
#include using namespace std;
const int MAXN=50010;
int n,cas,x,y;char op[6];
//树状数组操作int c[MAXN*2];
void init(){memset(c,0,sizeof c);}
int lowbit(int x){return x&-x;}void modify(int i,int k){while(iint sum(int i){int s=0;while(i>0)s+=c[i],i-=lowbit(i);return s;}
//============
int main(){
scanf("%d",&cas);
for(int ca=1;ca<=cas;ca++){
init();
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&x);modify(i,x);}
printf("Case %d:/n",ca);
while(scanf("%s",op),strcmp(op,"End")){
scanf("%d%d",&x,&y);
if(strcmp(op,"Add")==0)modify(x,y);
else if(strcmp(op,"Sub")==0)modify(x,-y);
else printf("%d/n",sum(y)-sum(x-1));

}
}

}

5.3.2 HDU2492 Ping Pong
在数组中统计小中大数以及大中小数

将数组中的数从左至右到右扫描,记录右边比它大的数以及比它小的数..


再从右到左扫描,记录左边比它大的数以及比它小的数


每个裁判举办的比赛=左小*右大+左大*右小,加起来即可


上面的操作可以用树状数组实现


#include 
#include
#include
using namespace std;
const int MAXN=20010,MAXA=110010;
int cas,n,ai[MAXN];
int lmin[MAXN],rmin[MAXN],lmax[MAXN],rmax[MAXN];//每个裁判左右边大/小于他的数的个数//树状数组
int c[MAXA*2];
void init(){memset(c,0,sizeof c);}
int lowbit(int x){return x&-x;}
void modify(int x){while(xint sum(int x){int s=0;while(x>0)s+=c[x],x-=lowbit(x);return s;}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&ai[i]);
//从左边开始扫描,扫描左边小于(大于)他的
init();
for(int i=1;i<=n;i++){
lmin[i]=sum(ai[i]-1);
lmax[i]=i-lmin[i]-1;
modify(ai[i]);
}
//从右边开始扫描,扫描右边小于(大于)他的
init();
for(int i=n;i>=1;i--){
rmin[i]=sum(ai[i]-1);
rmax[i]=n-i-rmin[i];
modify(ai[i]);
}
__int64 res=0;
for(int i=1;i<=n;i++){
res+=lmin[i]*rmax[i]+lmax[i]*rmin[i];
} printf("%I64d/n",res);
} return 0;
}

5.3.3
HDU3584 Cube

三维的树状数组


#include 
#include
using namespace std;
const int MAXN=105;
/*
三维树状数组
记录(0,0,0)->(x,y,z)这个点的修改次数
使用容斥原理得到(x1,y1,z1)->(x2,y2,z2); 在(x1,y1,z1)处+1,(x2,y2,z2)处-1 %2就能得到结果*/
int c[MAXN][MAXN][MAXN];
int lowbit(int x){return x&-x;}int modify(int x, int y, int z, int num){
int j, k;
while(x < MAXN){j = y;
while(j < MAXN){k = z;
while(k < MAXN){
c[x][j][k] += num;
k += lowbit(k);
}
j += lowbit(j);
}
x += lowbit(x);
}
}int sum(int x,int y,int z){
int s = 0;
int j,k;
while(x > 0){j = y;
while(j > 0){k = z;
while(k > 0){
s += c[x][j][k];
k -= lowbit(k);
}
j -= lowbit(j);
}
x -= lowbit(x);
} return s;
}int main(){
int n,m,op,x1,y1,z1,x2,y2,z2;
while(scanf("%d%d", &n, &m) != EOF){
memset(c, 0, sizeof c);
while(m--){
scanf("%d%d%d%d", &op, &x1, &y1, &z1);
if(op==1){
scanf("%d%d%d", &x2, &y2, &z2);
modify(x1, y1, z1, 1);
modify(x2+1, y1, z1, -1);
modify(x1, y2+1, z1, -1);
modify(x1, y1, z2+1, -1);
modify(x1, y2+1, z2+1, 1);
modify(x2+1, y1, z2+1, 1);
modify(x2+1, y2+1, z1, 1);
modify(x2+1, y2+1, z2+1, -1);
}else{
printf((sum(x1, y1, z1) & 1)?"1/n":"0/n");
}
}
}
return 0;
}

5.3.4 HDU2586How far away ?

5.3.5 HDU2874Connections between cities


两题都是LCA问题,用LCA_Targin算法就可以解决,两题的公式都是dis(u,v)=dis(u,root)+dis(v,root)-2*dis(lca(u,v),root)


其中lca(u,v)是u,v的最近公共祖先


2586比较裸,直接套算法就可以了


2874首先要判断两个点是否连通,这里可以用并查集实现,只有在一个区块中才去查询.


然后虚拟一个根节点,根节点向每个区块连一条线,对这个根节点进行LCA_Targin算法即可


2874的内存比较紧张..注意节省空间..这里贴的是2874的代码


#include 
#include
#include
#include
using namespace std;
int n,m,c,ans[1000001],hash[10001];
//图操作
struct edge{
int v,w;
edge(int b,int c){v=b,w=c;}
};
struct edge2{
int v,ind;
edge2(int b,int c){v=b,ind=c;}
};
vector ed[10001];
vector qr[10001];
//并查集
int p[10010];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
void merge(int x,int y){p[find(y)]=find(x);}
//LCA
bool vis[10001];
int dis[10001];
void LCA_Targin(int u){
vis[u]=1;
for(size_t i=0;i int v=qr[u][i].v;
if(vis[v])ans[qr[u][i].ind]=dis[u]+dis[v]-2*dis[find(v)];
}
for(size_t i=0;i int v=ed[u][i].v;
if(!vis[v]){
dis[v]=dis[u]+ed[u][i].w;
LCA_Targin(v);
merge(u,v);
}
}
}
//初始化void init(){
memset(vis,0,sizeof vis);
memset(hash,0,sizeof hash);
for(int i=0;i<10001;i++){
p[i]=i;
ed[i].clear();qr[i].clear();
}
}
int main(){
while(scanf("%d%d%d",&n,&m,&c)!=EOF){
init();
int x,y,z;
for(int i=0;i scanf("%d%d%d",&x,&y,&z);
ed[x].push_back(edge(y,z));
ed[y].push_back(edge(x,z));
merge(x,y);
}

for(int i=0;i scanf("%d%d",&x,&y);
if(find(x)!=find(y)){//对于不连通的点 ans[i]=-1;continue;
}
qr[x].push_back(edge2(y,i));
qr[y].push_back(edge2(x,i));
}

//添加虚拟根节点,向每个块增加一条连线 for(int i=1;i<=n;i++){
int t=find(i);
if(hash[t]==0){
hash[t]=1;
ed[0].push_back(edge(t,0));
ed[t].push_back(edge(0,0));
}
}


for(int i=0;i<10010;i++)p[i]=i;
dis[0]=0;
LCA_Targin(0);

for(int i=0;i if(ans[i]==-1)printf("Not connected/n");
else printf("%d/n",ans[i]);
}
}
return 0;
}

5.3.6 HDU3486Interviewe
一开始写了个线段树..TLE了..后来想想其实这题线段树还没有朴素算法快...因为题中将n分为k个区间,查询这每个区间中的最大值,朴素算法的复杂度一定是O(N),线段树对于一次查询是O(LogN),总共就是O(k*LogN),比较可以发现,大多数情况下,线段树是不如朴素算法快的...以后要具体题目具体对待..不能盲目的敲代码..

#include 
using namespace std;
const int MAXN=200001;
int n,k,v[MAXN];
int mmax(int a,int b){return a>b?a:b;}
int r;
int getmax(int mid){
int rs=0,tk=n/mid;
for(int i=1;i<=mid;i++){
int maxn=-1;
for(int j=tk*(i-1)+1;j<=tk*i;j++)maxn=mmax(v[j],maxn);
rs+=maxn;
if(rs>k){r=mid;return 1;}
}
return 0;
}
int main(){
while(scanf("%d%d",&n,&k),n!=-1&&k!=-1){
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
sum+=v[i];
}
if(sum else{
int low=1,high=n;
//二分分成的组数 while(low<=high){
int mid=(low+high)/2;
//如果此时组数满足条件,减少组数,否则增加 if(getmax(mid))high=mid-1;
else low=mid+1;
}
printf("%d/n",r);
}
}
}

5.3.7 HDU2688 Rotate

一开始是一个类似于用树状数组求逆序对的操作,之后的修改算法用暴力算法就可以了,统计那一段中比第一个数大的数和小的数,修改res就可以了,res+=less-more;


#include 
#include
using namespace std;
typedef __int64 LL;
const int MAXN=3000010,MAXA=10010;
int n,m,f[MAXN],s,e,tmp,mor,les;
LL res;
char op,c;
LL a[MAXA];
int lowbit(int x){return x&-x;}
void modify(int x){while(xLL sum(int x){LL s=0;while(x>0)s+=a[x],x-=lowbit(x);return s;}inline void scan(int &x){
while(c=getchar(),c<'0'||c>'9');x=c-'0';
while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
}
int main(){
while(scanf("%d",&n)!=EOF){
res=0;
memset(a,0,sizeof a);

for(int i=1;i<=n;i++){
scan(f[i]);
modify(f[i]);
res+=sum(f[i]-1);
}
scan(m);
while(m--){
scanf(" %c",&op);
if(op=='Q'){
printf("%I64d/n",res);
}else if(op=='R'){
scan(s);scan(e);
s++,e++;
if(s>e)tmp=s,s=e,e=tmp;
tmp=f[s],mor=0,les=0;
for(int i=s+1;i<=e;i++){
if(f[i]>tmp)mor++;
else if(f[i] f[i-1]=f[i]; }
f[e]=tmp;
res+=les-mor;

}
}

}
return 0;
}

5.3.8 HDU3030 表示没看懂题..贴大牛代码的..罪过..


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台