三道一眼题，原来应该AK的，结果爆炸了

T1：

①统计有多少个数是负数，若有偶数个不管负数，奇数个尽量把最大的负数的变为0；不行的话尽量把最小的负数变得尽量大，然后转⑦

②尽量把0变为1，否则输出0退出

③尽量把1变为2，否则转⑦

④尽量把2变为3，否则转⑦

⑤增加m/3个3，然后m=m%3

⑥如果m=1,给最小的正数＋1；如果m=2，增加一个2

⑦统计每种数有多少个，直接快速幂

统计数的个数有多少个时直接计数即可

复杂度O(T*20000*logM)

考试时候错的代码。。。一个小小的错误。。

统计负数时for(i=0;i<=9999;i++)if(ws[i])fs+=ws[i]写成for(i=0;i<=9999;i++)if(ws[i])fs++;

结果就0分了，~~~~(>_<)~~~~

#include<cstdio>
#include<cstring>
#define MOD 1000000007
long long m,x,T,u,n,w,fs,i,now,ws[22222];
bool ff;
void get(){
	long long ans=1,now;
	for(long long i=0;i<=20000;i++){
		now=i-10000;
		for(w=ws[i];w;w>>=1){
			if(w&1)ans=(ans*now)%MOD;
			now=(now*now)%MOD;
		}
	}
	printf("Case %lld: %lld\n",u,ans);
}
int main(){
	freopen("maximum.in","r",stdin);
	freopen("maximum.out","w",stdout);
	scanf("%lld",&T);
	for(u=1;u<=T;u++){
		scanf("%lld%lld",&n,&m);
		memset(ws,0,sizeof(ws));
		for(i=1;i<=n;i++){
			scanf("%lld",&x);
			ws[x+10000]++;
		}
		ff=fs=0;
		for(i=0;i<=9999;i++)if(ws[i])fs++;
		if(fs&1){
			for(i=9999;i;i--)if(ws[i])break;
			now=i-10000;
			if(m<=-now){
				ws[now+10000]--;
				now+=m;
				ws[now+10000]++;
				ff=1;
			}else{
				ws[now+10000]--;
				m+=now;
				now=0;
				ws[now+10000]++;
			}
		}
		if(ff){get();continue;}
		now=ws[10000];
		if(m<now){
			ws[10000]-=m;
			ws[10001]+=m;
			get();
			continue;
		}else{
			ws[10001]+=ws[10000];
			m-=ws[10000];
			ws[10000]=0;
		}
		now=ws[10001];
		if(m<now){
			ws[10001]-=m;
			ws[10002]+=m;
			get();
			continue;
		}else{
			ws[10002]+=ws[10001];
			m-=ws[10001];
			ws[10001]=0;
		}
		now=ws[10002];
		if(m<now){
			ws[10002]-=m;
			ws[10003]+=m;
			get();
			continue;
		}else{
			ws[10003]+=ws[10002];
			m-=ws[10002];
			ws[10002]=0;
		}
		ws[10003]+=(m/3);
		m%=3;
		if(m==2)ws[10002]++;else
		if(m==1){
			for(i=10000;i<=20000;i++)if(ws[i]){
				ws[i]--;
				ws[i+1]++;
				break;
			}
		}
		get();
	}
	fclose(stdin);fclose(stdout);
	return 0;
}

正确的代码：

#include<cstdio>
#include<cstring>
#define MOD 1000000007
long long m,x,T,u,n,w,fs,i,now,ws[22222];
bool ff;
void get(){
	long long ans=1,now;
	for(long long i=0;i<=20000;i++){
		now=i-10000;
		for(w=ws[i];w;w>>=1){
			if(w&1)ans=(ans*now)%MOD;
			now=(now*now)%MOD;
		}
	}
	printf("Case %lld: %lld\n",++u,ans);
}
int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		memset(ws,0,sizeof(ws));
		for(i=1;i<=n;i++){
			scanf("%lld",&x);
			ws[x+10000]++;
		}
		ff=fs=0;
		for(i=0;i<=9999;i++)if(ws[i])fs+=ws[i];//考试时候写成for(i=0;i<=9999;i++)if(ws[i])fs++;，结果全错了QAQ

		if(fs&1){
			for(i=9999;i;i--)if(ws[i])break;
			now=i-10000;
			if(m<=(-now)){
				ws[now+10000]--;
				now+=m;
				ws[now+10000]++;
				ff=1;
			}else{
				ws[now+10000]--;
				m+=now;
				now=0;
				ws[now+10000]++;
			}
		}
		if(ff){get();continue;}
		ff=0;
		for(i=10000;i<=20000;i++)if(ws[i]){ff=1;break;}
		now=ws[10000];
		if(m<now){
			ws[10000]-=m;
			ws[10001]+=m;
			get();
			continue;
		}else{
			ws[10001]+=ws[10000];
			m-=ws[10000];
			ws[10000]=0;
		}
		now=ws[10001];
		if(m<now){
			ws[10001]-=m;
			ws[10002]+=m;
			get();
			continue;
		}else{
			ws[10002]+=ws[10001];
			m-=ws[10001];
			ws[10001]=0;
		}
		now=ws[10002];
		if(m<now){
			ws[10002]-=m;
			ws[10003]+=m;
			get();
			continue;
		}else{
			ws[10003]+=ws[10002];
			m-=ws[10002];
			ws[10002]=0;
		}
		if(m>=3)ff=1;
		ws[10003]+=(m/3);
		m%=3;
		if(m==2)ws[10002]++;else
		if(m==1&ff){
			for(i=10000;i<=20000;i++)if(ws[i]){
				ws[i]--;
				ws[i+1]++;
				break;
			}
		}
		get();
	}
}

T2：

很容易写出dp方程：dp[i][j]=min(dp[i-1][k]+abs(k-j))+val[i][j]

然后发现这是单调的，如果从左边转移到右边，只需顺序维护dp[i-1][j]+n-j+1的最小值即可，则dp[i][j]=min(dp[i][j],now-(n-j+1)+val[i][j])

             如果从右边转移到左边，只需逆序维护dp[i-1][j]+j的最小值即可，dp[i][j]=min(dp[i][j],now-j+val[i][j])

时间复杂度从O(Tmn^2)降为O(Tmn)

#include<cstdio>
#include<cstring>
#define inf 1e16
long long T,m,n,x,i,j,now,ans,dp[55][2222],wz[55][2222],val[55][2222],a[55][2222];
long long abs(long long x){if(x<0)return -x;return x;}
long long min(long long x,long long y){if(x<y)return x;return y;}
int main(){
	freopen("dragonball.in","r",stdin);
	freopen("dragonball.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		memset(val,0,sizeof(val));
		scanf("%lld%lld%lld",&m,&n,&x);
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
				scanf("%lld",&wz[i][j]);
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
				scanf("%lld",&a[i][j]);
		for(i=1;i<=m;i++)
			for(j=1;j<=2*n;j++)
				val[i][j]=dp[i][j]=inf;
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++){
				val[i][wz[i][j]]=min(val[i][wz[i][j]],a[i][j]);
				if(i==1)dp[i][wz[i][j]]=val[i][wz[i][j]]+abs(x-wz[i][j]);
			}
		for(i=2;i<=m;i++){
			now=inf;
			for(j=2*n;j;j--){
				if(dp[i-1][j]+j<=now)now=dp[i-1][j]+j;
				if(now-j+val[i][j]<dp[i][j])dp[i][j]=now-j+val[i][j];
			}
			now=inf;
			for(j=1;j<=2*n;j++){
				if(dp[i-1][j]+(n-j+1)<=now)now=dp[i-1][j]+(n-j+1);
				if(now-(n-j+1)+val[i][j]<dp[i][j])dp[i][j]=now-(n-j+1)+val[i][j];
			}
		}
		ans=inf;
		for(i=1;i<=2*n;i++)if(dp[m][i]<ans)ans=dp[m][i];
		printf("%lld\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}

T3：

枚举每条边，对所有点暴力宽搜一遍，时间复杂度O(nm^m)，考试时T了5个点。。

#include<cstdio>
#include<cstring>
#define N 111
#define M 6666
#define inf 1e9
int n,m,i,j,x,y,now,tot,head,tail,ans,last[M],next[M],first[N],dis[N],q[N];
bool v[N],ff;
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
int main(){
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	scanf("%d%d",&n,&m);tot=1;
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	for(now=1;now<=m;now++){
		ff=0;ans=0;
		for(j=1;j<=n;j++){
			memset(v,0,sizeof(v));
			for(i=1;i<=n;i++)dis[i]=inf;
			head=0;tail=1;q[1]=j;dis[j]=0;v[j]=1;
			while(head<tail)
				for(i=first[x=q[++head]];i;i=next[i])if(now!=(i>>1)){
					int y=last[i];
					if(!v[y]){
						v[y]=1;
						dis[y]=dis[x]+1;
						q[++tail]=y;
					}
				}
			for(i=1;i<=n;i++)if(dis[i]==inf){ff=1;break;}else ans+=dis[i];
			if(ff)break;
		}
		if(ff)puts("INF");else printf("%d\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}

然后用了小数据对拍会出错的贪心，结果A了、、

#include<cstdio>
#include<cstring>
#define N 111
#define M 6666
#define inf 1e9
int n,m,i,j,x,y,now,tot,head,tail,sum,ans1,ans2,S,T,uu,last[M],next[M],first[N],dis[N][N],dis2[N],q[N];
bool v[N],ff;
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
int main(){
	scanf("%d%d",&n,&m);tot=1;
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	for(j=1;j<=n;j++){
		memset(v,0,sizeof(v));
		for(i=1;i<=n;i++)dis[j][i]=inf;
		head=0;tail=1;q[1]=j;dis[j][j]=0;v[j]=1;
		while(head<tail)
			for(i=first[x=q[++head]];i;i=next[i]){
				int y=last[i];
				if(!v[y]){
					v[y]=1;
					dis[j][y]=dis[j][x]+1;
					q[++tail]=y;
				}
			}
		for(i=1;i<=n;i++)sum+=dis[j][i];
	}
	for(now=1;now<=m;now++){
		ff=0;ans1=ans2=0;
		S=last[now*2];
		T=last[now*2+1];
		memset(v,0,sizeof(v));
		for(i=1;i<=n;i++)dis2[i]=inf;
		head=0;tail=1;q[1]=S;dis2[S]=0;v[S]=1;
		while(head<tail)
			for(i=first[x=q[++head]];i;i=next[i])if(now!=(i>>1)){
				int y=last[i];
				if(!v[y]){
					v[y]=1;
					dis2[y]=dis2[x]+1;
					q[++tail]=y;
				}
			}
			for(i=1;i<=n;i++)if(dis2[i]==inf){ff=1;break;}else if(dis2[i]!=dis[S][i])ans1++;
		memset(v,0,sizeof(v));
		for(i=1;i<=n;i++)dis2[i]=inf;
		head=0;tail=1;q[1]=T;dis2[T]=0;v[T]=1;
		while(head<tail)
			for(i=first[x=q[++head]];i;i=next[i])if(now!=(i>>1)){
				int y=last[i];
				if(!v[y]){
					v[y]=1;
					dis2[y]=dis2[x]+1;
					q[++tail]=y;
				}
			}
			for(i=1;i<=n;i++)if(dis2[i]==inf){ff=1;break;}else if(dis2[i]!=dis[T][i])ans2++;
		if(dis2[S]!=1)ans1++,ans2++;
		uu=sum+ans1*ans2*(dis2[S]-dis[S][T])-(dis2[S]-dis[S][T])*2;
		if(uu&1)uu++;
		if(ff)puts("INF");else printf("%d\n",uu);
	}
}

2015-07-09

T1：似乎是基础题，但是从来没有做过，怎么弄应该都能过吧

#include<cstdio>
#include<algorithm>
#define N 3333
using namespace std;
int n,p,i,sz,a[N],pos[N];
struct EG{int v,id,h;}b[N];
bool cmp(EG a,EG b){return a.h<b.h||(a.h==b.h&&a.id<b.id);}
void find(int l1,int r1,int l2,int r2,int high){
	if(l1>r1||l2>r2)return;
	b[l2].id=++sz;b[l2].h=high;
	if(l1==r1||l2==r2){printf("%d ",b[l2].v);return;}
	find(l1,pos[b[l2].v]-1,l2+1,l2+pos[b[l2].v]-l1,high+1);
	find(pos[b[l2].v]+1,r1,l2+pos[b[l2].v]-l1+1,r2,high+1);
	printf("%d ",b[l2].v);
}
void find2(int l1,int r1,int l2,int r2,int high){
	if(l1>r1||l2>r2)return;
	b[r2].id=++sz;b[r2].h=high;
	if(l1==r1||l2==r2){printf("%d ",b[r2].v);return;}
	printf("%d ",b[r2].v);
	find2(l1,pos[b[r2].v]-1,l2,l2+pos[b[r2].v]-l1-1,high+1);
	find2(pos[b[r2].v]+1,r1,l2+pos[b[r2].v]-l1,r2-1,high+1);
}
int main(){
	scanf("%d%d",&n,&p);
	for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
	for(i=1;i<=n;i++)scanf("%d",&b[i].v);
	if(p==1)find(1,n,1,n,1);else find2(1,n,1,n,1);
	puts("");
	sort(b+1,b+n+1,cmp);
	for(i=1;i<=n;i++)printf("%d ",b[i].v);
}

T2：看到题目直接做了，以为就是傻逼拓扑排序，结果和HZH对拍的时候发现T了，原来n=50000

那么把度为0的点加入堆，每次选序号最小的就行了，变成O(nlgn+m)

#include<cstdio>
#include<iostream>
#define N 55555
#define M 1111111
using namespace std;
int n,m,x,y,i,ans,tot,root,last[M],next[M],first[N],du[N],stack[N],son[N][2];
bool f,v[N];char ch;
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void read(int &x){
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(x>y)swap(x,y);
	son[x][1]=merge(son[x][1],y);
	swap(son[x][0],son[x][1]);
	return x;
}
int main(){
	read(n);read(m);
	for(i=1;i<=m;i++){
		read(x);read(y);
		du[y]++;ins(x,y);
	}
	for(i=1;i<=n;i++)if(!du[i])root=merge(root,i);
	while(root){
		x=root;
		stack[++ans]=x;
		root=merge(son[root][0],son[root][1]);
		for(i=first[x];i;i=next[i]){
			du[last[i]]--;
			if(!du[last[i]])root=merge(root,last[i]);
		}
	}
	if(ans!=n)puts("No Answer!");else for(i=1;i<=n;i++)printf("%d ",stack[i]);
}

T3：8年前ZJOI的原题，当年ZJOI还是那么简单，还会考斜率优化这种最基础的东西，现在都的题已经没法做了

设sum[i]=Σp[i]*x[i]，sump[i]=Σp[i]

dp[i]=min(dp[j]+sum[j]-x[i]*sump[j]-(sum[i]-x[i]*sump[i])+c[i])，然后就是斜率优化裸题啦

#include<cstdio>
#define N 1000500
char ch;long long f[N],x[N],c[N],sum[N],sump[N],p[N],q[N],i,j,n,h,t; 
void read(long long &x){
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
long long getx(int i,int j){return f[i]+sum[i]-f[j]-sum[j];}
long long gety(int i,int j){return sump[i]-sump[j];}
int main(){
	freopen("storage.in","r",stdin);
	freopen("storage.out","w",stdout);
	read(n);
	for(i=1;i<=n;i++){
    		read(x[i]);read(p[i]);read(c[i]);
    		sum[i]=sum[i-1]+x[i]*p[i];
    		sump[i]=sump[i-1]+p[i];
	}
	t=1;
  	for(i=1;i<=n;i++){
    		while(h<t&&getx(q[h+1],q[h])<x[i]*gety(q[h+1],q[h]))h++; 
    		f[i]=f[q[h]]+sum[q[h]]-x[i]*sump[q[h]]+x[i]*sump[i]-sum[i]+c[i];
    		while(h<t&&getx(q[t],i)*gety(q[t-1],q[t])<=getx(q[t-1],q[t])*gety(q[t],i))t--; 
    		q[++t]=i;
  	}
	printf("%lld",f[n]);
}

• 相关文章推荐
• 全局相关文章