ShineEternal 的小站

如有任何问题请联系QQ：3197301325

2020年男人八题赛后订正与总结

发布于 2020-09-13 | 分类于 ezoj 、 题解 | 12分钟 | 2073字数 | 浏览量：

A. 【2020男人八题】礼物

考场代码：（100pts）

#include<cstdio>
using namespace std;
long long Mod=1000000007;
int main()
{
	long long n,m;
	scanf("%lld%lld",&n,&m);
	long long NN=n*(n-1)/2;
	long long MM=m*(m-1)/2;
	printf("%lld\n",((NN%Mod)*(MM%Mod)%Mod));
	return 0;
}

这道题目考察 long long 的相关问题，注意随时取模就好了，考场上找规律大概 15min15min 才写好。算是挺签到的题目。

B. 【2020男人八题】序列

考场代码：（40pts）

#include<cstdio>
using namespace std;
long long a[100005],b[100005],c[100005];
long long Abs(long long x)
{
	if(x<0)return -x;
	return x;
}
int main()
{
	long long n,S;
	long long sum=0;
	long long dif=0;
	scanf("%lld%lld",&n,&S);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
	}
	if(sum<S)
	{
		printf("-1\n");
		return 0;
	}
	long long cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(b[i]<=a[i])
		{
			c[i]=b[i];
		}
		else
		{
			c[i]=a[i];
			dif+=Abs(c[i]-b[i]);
		}
		cnt+=c[i];
	}
	if(cnt==S)
	{
		printf("%lld\n",dif);
		for(int i=1;i<=n;i++)
		{
			printf("%lld ",c[i]);
		}
		printf("\n");
		return 0;
	}
	dif=0;
	if(cnt<S)
	for(int i=1;i<=n;i++)
	{
		long long tmp=a[i]-c[i];
		if(c[i]<a[i])
		{
			if(S-cnt>tmp)
			{
				c[i]=a[i];
				dif+=Abs(c[i]-b[i]);
				cnt+=tmp;
			}
			else
			{
				c[i]+=S-cnt;
				dif+=Abs(c[i]-b[i]);
				cnt=S;
			}
		}
		if(cnt==S)
		{
			printf("%lld\n",dif);
			for(int i=1;i<=n;i++)
			{
				printf("%lld ",c[i]);
			}
			printf("\n");
			return 0;
		}
		
	}
	dif=0;
	for(int i=1;i<=n;i++)
	{
		int tmp=c[i];
		if(c[i]<a[i])
		{
			if(cnt-S>tmp)
			{
				c[i]=0;
				dif+=Abs(c[i]-b[i]);
				cnt-=tmp;
			}
			else
			{
				c[i]-=cnt-S;
				dif+=Abs(c[i]-b[i]);
				cnt=S;
			}
		}
		if(cnt==S)
		{
			printf("%lld\n",dif);
			for(int i=1;i<=n;i++)
			{
				printf("%lld ",c[i]);
			}
			printf("\n");
			return 0;
		}
		
	}
	printf("-1\n");
	return 0;
}

赛后订正：（100pts）

#include<cstdio>
using namespace std;
long long a[100005],b[100005],c[100005];
long long abs(long long x)
{
	if(x<0)return -x;
	return x; 
}
int main()
{
	long long n,S;
	scanf("%lld%lld",&n,&S);
	long long sum=0;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	long long cnt=0;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
		if(b[i]>a[i])
		{
			c[i]=a[i];
		}
		else
		c[i]=b[i];
		cnt+=c[i];
	}
	if(sum<S)
	{
		printf("-1\n");
		return 0;
	}
	long long flag=0; 
	for(long long i=1;i<=n;i++)
	{
		
		long long del;
		if(cnt>S)
		{
			del=cnt-S;
			if(del<c[i])
			{
				c[i]=c[i]-del;
				flag=1;
				break;
			}
			else
			{
				cnt-=c[i];
				c[i]=0;
			}
		}
		if(cnt<S)
		{
			del=S-cnt;
			if(del<a[i]-c[i])
			{
				c[i]+=del;
				flag=1;
				break;
			}
			else
			{
				cnt+=a[i]-c[i];
				c[i]=a[i];
			}
		}
		if(cnt==S)
		{
			flag=1;
			break;
		}
	}
	if(flag==0)
	{
		printf("-1\n");
		return 0;
	}
	long long res=0;
	for(long long i=1;i<=n;i++)
	{
		res+=abs(c[i]-b[i]);
	}
	printf("%lld\n",res);
	for(long long i=1;i<=n;i++)
	{
		printf("%lld ",c[i]);
	}
	printf("\n");
	return 0;
}

考场上对于两种分情况的讨论头脑有些混沌了，导致犯了一些本不该犯的错误。

以后还是应该一边写一边在旁边注释一下，理清思路。

原来的时候在初始化 c 数组之后，修正的过程中直接计算答案了，就会导致一些本可以避免的错误。

这种答案的统计因为时间复杂度不高，所以类似的题目处理时最好最后统一搞。

C. 【2020男人八题】洪水

赛时代码：(0pts)

#include<cstdio>
#include<algorithm>
using namespace std;
struct ben
{
	long long x,y;
}a[10005];
long long cmp(const ben &a,const ben &b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
long long Abs(long long qaq)
{
	if(qaq<0)return -qaq;
	return qaq;
}
long long Max(long long qwq,long long qvq)
{
	if(qwq>qvq)return qwq;
	return qvq;
}
long long Min(long long qwq,long long qvq)
{
	if(qwq<qvq)return qwq;
	return qvq;
}
long long x[10005],y[10005];
int main()
{
	long long W,H,n;
	scanf("%lld%lld%lld",&W,&H,&n);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld%lld",&a[i].x,&a[i].y);
	} 
	//sort(a+1,a+n+1,cmp);
	long long ans=0;
	for(long long i=1;i<=n;i++)
	{
		long long tmp=2147483640000000;
		for(long long j=1;j<=n;j++)
		{
			if(i==j)continue;
			long long midx=(a[i].x+a[j].x)/2;
			long long midy=(a[i].y+a[j].y)/2;
			tmp=Min(tmp,Abs(midx-Min(a[i].x,a[j].x))+Abs(midy-Min(a[i].y,a[j].y)));
			//prlong longf("tmp=%d\n",tmp);
			//tmp=Min(tmp,zc);
			//prlong longf("zc=%d\n",zc);
		}
		//prlong longf("tmp=%d\n",tmp);
		if(tmp==2147483640000000)continue;//差点这句话就把等于写成了赋值。。。。。 
		ans=Max(ans,tmp);  
	}
	printf("%lld\n",ans);
	return 0;
}

赛后订正：（10pts）

#include<cstdio>
#include<algorithm>
using namespace std;
struct ben
{
	int x,y;
}a[10005];
struct qwq
{
	int ls,g;
}d[10005];
int mp[10005];
int Abs(int x)
{
	if(x<0)return -x;
	return x; 
}
int ba[10005];
int main()
{
	int W,H,n;
	scanf("%d%d%d",&W,&H,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		d[i].g=0;
	}
	for(int i=1;i<=n;i++)
	{
		if(d[i].g!=0)continue;
		int tmp=2147483640,tag;
		for(int j=i+1;j<=n;j++)
		{
			if((Abs(a[j].x-a[i].x)+Abs(a[j].y-a[i].y))/2<tmp)
			{
				tmp=(Abs(a[j].x-a[i].x)+Abs(a[j].y-a[i].y))/2;
				tag=j;
			}	
		}
		d[i].ls=tmp;
		d[i].g=tag;
		d[tag].ls=tmp;
		d[tag].g=i;
	}
	ba[1]=1;
	int cnt=1;
	mp[1]=1;
	int ans=0;
	while(cnt<n)
	{
		int mina=2147483640;
		int taga;
		for(int i=1;i<=cnt;i++) 
		{
			
			if(d[ba[i]].ls<mina)
			{
				if(mp[d[ba[i]].g]==1)continue;
				mina=d[ba[i]].ls;
				taga=d[ba[i]].g;
			}
		}
		mp[taga]=1;
		ba[++cnt]=taga;
		if(mina!=2147483640)
		ans=max(ans,mina);
	}
	printf("%d\n",ans);
	return 0;
}

考场上几乎把所有的错误想法都想过了一遍，最终摸索每一种错解之后走到了类似最小生成树的做法，但因打开方式不对，曼哈顿距离处理挂了

这道题目不能直接贪心，要用最小生成树的思想连边。赛时想到了类似的想法，但在曼哈顿距离上处理挂了。

D、 【2020男人八题】循环

赛时代码：（3pts）

#include<cstdio>
using namespace std;
int Mod=998244353;
long long a[21];
int main()
{
	long long p;
	scanf("%lld",&p);
	int n=10;
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
	}
	if(p==3)
	{
		long long tmp=a[3]+a[6];
		printf("%lld\n",tmp%Mod);
	}
	return 0;
}

赛后订正：(100pts)

#include<cstdio>
using namespace std;
int mod=998244353;
long long a[15]; 
bool tag[1000005];
long long xs[1000005];
int main()
{
	long long n,cnt=0,ans=0,x;
	scanf("%lld",&n);
	for(int i=0;i<=9;i++) 
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<n;i++)
	{
	    if(tag[i]==0)
	    {
			int tmp=0;
			cnt++;
	    	x=i;
		    xs[cnt]=1;
		    while(1) 
		    {
				tag[x]=1;
			    tmp++;
			    xs[cnt]=xs[cnt]*a[x*10/n]%mod;
			    x=x*10%n;
			    if(x==i) 
					break;
		    }
		    xs[cnt]=xs[cnt]*tmp%mod;
		    ans=(ans+xs[cnt])%mod;
	    }
	}
	printf("%lld\n",ans);
	return 0;
}

赛时只考虑了样例的情况，因为没有琢磨透循环节所以只草率的写了极少的部分分。其实即使是骗分的暴力也还是很可做，本应多骗些分。

E. 【2020男人八题】切割矩形

赛时代码：(30pts)

#include<cstdio>
#include<iostream>
using namespace std;
long long Max(long long qwq,long long qvq)
{
	if(qwq>qvq)return qwq;
	return qvq;
}
int main()
{
	int T;
	scanf("%d",&T);
	long long a,b;
	while(T--)
	{
		scanf("%lld%lld",&a,&b);
		long long x1=a,x2=b,y1=b,y2=b;
		long long ans=0;
		while(x1!=y1)
		{
			if(x1>y1)
			{
				long long tmp=x1-(x1/y1)*y1;
				if(tmp<1)
				{
					ans-=(1-tmp)/y1;
				}
			ans+=x1/y1;
			
			x1=Max(tmp,1);
			}
			else
			{
				long long z=x1;
				x1=y1;
				y1=z;
			}
			//printf("%lld %lld\n",x1,y1);
		}
		printf("%lld 114514\n",ans);
	}
	return 0;
}

赛后订正：(100pts)

#include<cstdio>
using namespace std;
int mod=1000000007;
long long res1,res2;
long long ksm(long long a,long long b)
{
	long long tmp=1;
	for(;b;b/=2,a=a*a%mod)
	{
		if(b%2==1)
		{
			tmp=tmp*a%mod;
		}
	}
	return tmp;
}
void gcd_ex(long long a,long long b)
{
	if(b==1)
	{
		res1=a-1;
		res2=0;
		return ;
	}
	gcd_ex(b,a%b);
	res2=(ksm(2,res1)-res2-1+mod)%mod;
	res1+=a/b;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		long long a,b;
		scanf("%lld%lld",&a,&b);
		gcd_ex(a,b);
		printf("%lld %lld\n",res1,(ksm(2,res1-1)-res2+mod)%mod);
	}
	return 0;
}

这道题在比赛时写了第一个空的解法，看出其和辗转相除法相似的本质，得到了30pts，对整场比赛的个人得分来说算是比较成功的暴力，但没有像初中探究题一样推下去找到第二问的规律比较可惜。

# ezoj # 题解
第一周校内OI模拟赛总结（day1&day2） 上一篇
CF1389A LCM Problem 题解 下一篇
Developed by vipblog
2020 , © ShineEternal
All rights reserved.
0%
召唤看板娘