【马三模拟赛】Day1题解
我是有良心的出题人，出了三道傻逼题，不像毛主力，他出的题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);
}
2015年7月14日 08:22
md你很大？我要来骂你
2015年7月14日 14:50
被主力骂了QAQ
2022年9月16日 22:02
All Andhra Pradesh State Class 10th (SSC) Students can download AP SSC Science model paper 2023 with Answer solutions in Chapter by Chapter for Physical Science, Chemistry, Biological Science and Environmental science for AP SSC Science Model Paper 2023 examination test for Unit Test-1, Unit Test-2, AP SSC General Science Question Paper Unit Test-3, Unit Test-4, and Quarterly, Half Yearly, Pre-Final with Annual final examination tests 2023. The Andhra Pradesh State Board of Secondary Education has published the General Science model paper with study material with practice paper with mock test question bank as AP 10th Biology, PS, Chemistry Model Paper 2023 for all examination tests conducted by BSEAP.