【马三模拟赛】Day1题解

orz hhw posted @ 2015年7月13日 14:48 in 做题记录 with tags 比赛 做题记录 , 506 阅读

我是有良心的出题人,出了三道傻逼题,不像毛主力,他出的题RANK1只拿了0分

T1 裸最短路 T2 裸树状数组 T3 裸树形DP

T1:简单的最短路 考虑起点终点各做一次最短路即可

T2:简单的树状数组 二维区间修改单点询问即可

T3:简单的树形DP

Dp[x]=Σmin(dp[y],w[<x,y>])(y子树有居民点且y不是居民点)

     w[<x,y>](y是居民点)

—如果X是污染点,把dp[x]加到答案中,然后直接把X点去除,在考虑X的父亲时不再考虑X,因为一个点有污染,在它上面是不可能治理的。
—时空复杂度O(n),得解。
注意三道都要开long long,我比较有良心,没要你写高精度。
 
下面给出三道题目的标程
#include<cstdio>
#include<cstring> 
#define inf 1e17
#define N 111111
#define M 888888
int n,m,x1,y1,x2,y2,k,i,j,u,x,y,head,tail,tot,s,t,first[N],cl[N],last[M],next[M],q[M<<4];
long long w,ans,h[N],dis1[N],dis2[N],value[M];
bool v[N];
long long abs(long long a){if(a<0)return -a;else return a;}
void insert(int x,int y,long long z){
	last[++tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot;
	last[++tot]=x;value[tot]=z;next[tot]=first[y];first[y]=tot;
}
int main(){
	scanf("%d%d%d%d%d%d%lld",&n,&m,&x1,&y1,&x2,&y2,&w);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			u=i*m-m+j;
			dis1[u]=dis2[u]=inf;
			scanf("%lld",&h[u]);
			if(j>1)insert(u,u-1,abs(h[u]-h[u-1])+w);
			if(i>1)insert(u,u-m,abs(h[u]-h[u-m])+w);
		}
	scanf("%d",&k);
	for(i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		u=x*m-m+y;
		cl[u]++;
	}
	s=x1*m-m+y1;t=x2*m-m+y2;
	head=0;tail=1;q[1]=s;v[s]=1;dis1[s]=0;
	while(head<tail){
		v[x=q[++head]]=0;
		if(!cl[x])for(i=first[x];i;i=next[i])
			if(dis1[x]+value[i]<dis1[y=last[i]]){
				dis1[y]=dis1[x]+value[i];
				if(!v[y])v[q[++tail]=y]=1;
			}
	}
	memset(v,0,sizeof(v));
	head=0;tail=1;q[1]=t;v[t]=1;dis2[t]=0;
	while(head<tail){
		v[x=q[++head]]=0;
		if(!cl[x])for(i=first[x];i;i=next[i])
			if(dis2[x]+value[i]<dis2[y=last[i]]){
				dis2[y]=dis2[x]+value[i];
				if(!v[y])v[q[++tail]=y]=1;
			}
	}
	ans=inf;
	for(i=1;i<=n*m;i++)if(dis1[i]+dis2[i]<ans&&cl[i]<=1)ans=dis1[i]+dis2[i];
	if(ans!=inf)printf("%lld",ans);else puts("Orz yizhou.");
}
#include<cstdio>
#include<map>
using namespace std;
int n,m,i,j,T,x1,y1,x2,y2,x,y,top;
long long p,now,ans,c[1111][1111];
bool f[1111][1111];
char s[99],ch;
map<long long,int> mp;
void read2(long long &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int lowbit(int x){return x&(-x);}
void add(int i,int j,long long z){
	int x,y;
	for(x=i;x<=n;x+=lowbit(x))
		for(y=j;y<=m;y+=lowbit(y))
			c[x][y]+=z;
}
long long query(int i,int j){
	long long sum=0;int x,y;
	for(x=i;x;x-=lowbit(x))
		for(y=j;y;y-=lowbit(y))
			sum+=c[x][y];
	return sum;
}
void cha(int x1,int y1,int x2,int y2,long long p){
	add(x1,y1,p);
	add(x2+1,y2+1,p);
	add(x1,y2+1,-p);
	add(x2+1,y1,-p);
}
int main(){
	read(n);read(m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			read2(p);
			cha(i,j,i,j,p);
		}
	scanf("%d",&T);
	while(T--){
		scanf("%s",s);
		if(s[0]=='A'){
			read(x1);read(y1);read(x2);read(y2);read2(p);
			cha(x1,y1,x2,y2,p);
		}else if(s[0]=='D'){
			read(x1);read(y1);read(x2);read(y2);read2(p);
			cha(x1,y1,x2,y2,-p);
		}else if(s[0]=='E'){
			read(x);read(y);
			if(f[x][y])continue;
			f[x][y]=1;
			now=query(x,y);
			cha(x,y,x,y,-now);
			if(mp.count(now))continue;else mp[now]=++top,ans+=now;
		}
	}
	printf("%lld",ans);
}
#include<cstdio>
#include<iostream>
#define N 1111111
using namespace std;
int n,m,k,s,i,x,y,tot,last[N<<1],next[N<<1],first[N];
long long z,ans,tmp,value[N<<1],dp[N],mn[N];
bool wu[N],jm[N],ww[N];
void ins(int x,int y,long long z){last[++tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot;}
void dfs(int x,int z){
	long long tmp=0;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=z){
			dfs(y,x);
			if(jm[y])jm[x]=1;
			if(ww[y])dp[x]+=value[i];else if(jm[y])dp[x]+=min(value[i],dp[y]);
		}
	}
	if(wu[x])ans+=dp[x],dp[x]=0,jm[x]=0,ww[x]=0;
}
int main(){
	scanf("%d%d",&n,&s);
	for(i=1;i<n;i++)scanf("%d%d%lld",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	scanf("%d",&m);for(i=1;i<=m;i++)scanf("%d",&x),wu[x]=1;
	scanf("%d",&k);for(i=1;i<=k;i++)scanf("%d",&x),jm[x]=1,ww[x]=1;
	dfs(s,0);
	printf("%lld\n",ans);
}
 
 
Avatar_small
hhw 说:
2015年7月14日 08:22

md你很大?我要来骂你


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter