2015-07-07解题报告、2015-07-09解题报告

orz hhw posted @ 2015年7月07日 19:44 in 做题记录 with tags 做题记录 , 2966 阅读

三道一眼题,原来应该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]),然后就是斜率优化裸题啦

dp[j]+sum[j]-x[i]*sump[j]<dp[k]+sum[k]-x[i]*sump[k]
dp[j]+sum[j]-dp[k]-sum[k]<x[i](sump[j]-sump[k])
然后这就单调啦,但我只是会写斜率优化,并不懂原理哈
#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]);
}
  • 无匹配
Avatar_small
nbdhhzh 说:
2015年7月08日 15:02

每天贪心写写很自豪么。

Avatar_small
hhw 说:
2015年7月08日 20:58

每天贪心写写很自豪么。

Avatar_small
jcvb 说:
2015年7月09日 10:26

每天贪心写写很自豪么。

Avatar_small
jiry_2 说:
2015年7月09日 10:45

每天贪心写写很自豪么。

Avatar_small
wangyisong1996 说:
2015年7月09日 10:51

每天贪心写写很自豪么。

Avatar_small
xyz111 说:
2015年7月09日 10:51

每天贪心写写很自豪么。

Avatar_small
hzwer 说:
2015年7月09日 10:52

每天贪心写写很自豪么。

Avatar_small
across_the_sky 说:
2015年7月09日 10:52

每天贪心写写很自豪么。

Avatar_small
WJMZBMR 说:
2015年7月09日 10:54

每天贪心写写很自豪么。

Avatar_small
_叫我猪猪侠 说:
2015年7月09日 11:00

每天贪心写写很自豪么。

Avatar_small
Claris 说:
2015年7月09日 11:01

每天贪心写写很自豪么。

Avatar_small
zhonghaoxi 说:
2015年7月09日 11:01

每天贪心写写很自豪么。

Avatar_small
dzy493941464 说:
2015年7月09日 11:02

每天贪心写写很自豪么。

Avatar_small
WCMG 说:
2015年7月09日 11:02

每天贪心写写很自豪么。

Avatar_small
Memphis 说:
2015年7月09日 11:02

每天贪心写写很自豪么。

Avatar_small
xllend3 说:
2015年7月09日 22:26

每天贪心写写很自豪么。

Avatar_small
matthew99 说:
2015年7月09日 22:27

每天贪心写写很自豪么。

Avatar_small
vfleaking 说:
2015年7月09日 22:27

每天贪心写写很自豪么。

Avatar_small
Stillwell 说:
2015年7月09日 22:28

每天贪心写写很自豪么。

Avatar_small
Sone2 说:
2015年7月09日 22:28

每天贪心写写很自豪么。

Avatar_small
fotile96 说:
2015年7月09日 22:28

每天贪心写写很自豪么。

Avatar_small
Seter 说:
2015年7月09日 22:29

每天贪心写写很自豪么。

Avatar_small
AHdoc 说:
2015年7月09日 22:29

每天贪心写写很自豪么。

Avatar_small
PoPoQQQ 说:
2015年7月09日 22:29

每天贪心写写很自豪么。

Avatar_small
qwer_zcc 说:
2015年7月09日 22:30

每天贪心写写很自豪么。

Avatar_small
xudyh 说:
2015年7月09日 22:30

每天贪心写写很自豪么。

Avatar_small
Ruchiose 说:
2015年7月09日 22:30

每天贪心写写很自豪么。

Avatar_small
Starzxy 说:
2015年7月09日 22:31

每天贪心写写很自豪么。

Avatar_small
hrzhrz_hrzhrz 说:
2015年7月09日 22:31

每天贪心写写很自豪么。

Avatar_small
ljcc 说:
2015年7月09日 22:31

每天贪心写写很自豪么。

Avatar_small
Delayyy 说:
2015年7月09日 22:32

每天贪心写写很自豪么。

Avatar_small
ACMonster 说:
2015年7月09日 22:32

每天贪心写写很自豪么。

Avatar_small
Sevenkplus 说:
2015年7月09日 22:32

每天贪心写写很自豪么。

Avatar_small
saffah 说:
2015年7月09日 22:33

每天贪心写写很自豪么。

Avatar_small
taorunz 说:
2015年7月09日 22:33

每天贪心写写很自豪么。

Avatar_small
ydcydc 说:
2015年7月09日 22:33

每天贪心写写很自豪么。

Avatar_small
Gromah 说:
2015年7月09日 22:33

每天贪心写写很自豪么。

Avatar_small
fanhq666 说:
2015年7月09日 22:34

每天贪心写写很自豪么。

Avatar_small
yangff 说:
2015年7月09日 22:35

每天贪心写写很自豪么。

Avatar_small
tangjz 说:
2015年7月09日 22:37

每天贪心写写很自豪么。

Avatar_small
SkyDec 说:
2015年7月09日 22:37

每天贪心写写很自豪么。

Avatar_small
cenbo 说:
2015年7月09日 22:37

每天贪心写写很自豪么。

Avatar_small
fullpower 说:
2015年7月09日 22:38

每天贪心写写很自豪么。

Avatar_small
iwtwiioi 说:
2015年7月09日 22:38

每天贪心写写很自豪么。

Avatar_small
picks 说:
2015年7月09日 22:39

每天贪心写写很自豪么。

Avatar_small
dwjshift 说:
2015年7月09日 22:40

每天贪心写写很自豪么。

Avatar_small
yu990601 说:
2015年7月09日 22:40

每天贪心写写很自豪么。

Avatar_small
Mato_No1 说:
2015年7月09日 22:41

每天贪心写写很自豪么。

Avatar_small
SillyCross 说:
2015年7月09日 22:41

每天贪心写写很自豪么。

Avatar_small
lijian3256 说:
2015年7月09日 22:42

每天贪心写写很自豪么。

Avatar_small
Ginger88895 说:
2015年7月15日 09:35

每天贪心写写很自豪么。


登录 *


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