4.10日2017年普及组比赛 总结

$4.10$4.10日$2017$2017年普及组比赛 总结

这次比赛我考了$320$320分，还可以，但是还是要强化一下一些其他算法，如单调队列。

第一题：成绩

解题思路

直接利用公式，简单数学题。
公式：

得分情况

比赛时满分。

程序

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	printf("%d",a/10*2+b/10*3+c/10*5);
}

第二题：图书管理员

解题思路

直接模拟，注意要先把编码按从小到大排序。

得分情况

比赛时满分。

程序

#include<bits/stdc++.h>
using namespace std;
int n,q,a[1001],b[1001],l[1001],c[1001][11],k[1001],d[1001];
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&l[i],&b[i]);
	}
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(a[i]>a[j]) 
				swap(a[i],a[j]);
	for(int i=1;i<=n;i++)
	{
		int x=a[i];
		while(x!=0)
		{
			k[i]++;
			x/=10;
		}
		d[i]=1;
		for(int j=1;j<=k[i];j++) d[i]*=10;
	}
	for(int i=1;i<=q;i++)
	{
		int ck=0;
		for(int j=1;j<=n;j++)
		{
			for(int k=10;k<=d[j];k*=10)
			{
				if(a[j]%k==b[i])
				{
					printf("%d\n",a[j]);
					ck=1;
					break;
				}
			}	
			if(ck==1) break;		
		}
		if(ck==0) putchar('-'),putchar('1'),putchar('\n');
	}
}

第三题：棋盘

解题思路

有很多种方法。
可以用深搜+剪枝，广搜+队列优化，动态规划，最短路等等来做。

得分情况

比赛时$70$70分。
改题后满分。

程序

#include<bits/stdc++.h>
using namespace std;
int m,n,a[101][101],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},f[101][101];
void dfs(int x,int y,int s,int b)
{	
	if(s>=f[x][y]) return;
	f[x][y]=s;
	for(int i=0;i<4;i++)
	{
		int u,v;
		u=x+dx[i];
		v=y+dy[i];
		if(u>=1&&u<=m&&v>=1&&v<=m)
		{
			if(a[u][v]!=0)
			{
				if(a[x][y]==a[u][v]) dfs(u,v,s,0);
				else dfs(u,v,s+1,0);
			}
			else
			{
				if(b==0)
				{
					a[u][v]=a[x][y];
					dfs(u,v,s+2,1);
					a[u][v]=0;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			f[i][j]=INT_MAX;
	for(int i=1;i<=n;i++)
	{
		int u,v,p;
		scanf("%d%d%d",&u,&v,&p);
		if(p==1) a[u][v]=1;//yellow
		if(p==0) a[u][v]=2;//red
	}
	dfs(1,1,0,0);
	if(f[m][m]==INT_MAX) printf("-1");
	else printf("%d",f[m][m]);
}

第四题：跳房子

解题思路

对于$50$50分的方法，直接二分$g$g，然后用动态规划判断。

满分做法，把上面的动态规划利用单调队列优化，可惜我不懂 。

得分情况

比赛时$50$50分。
不知道怎么改题。

程序（$50$50分）

#include<bits/stdc++.h>
#define sm -1000000000000
#define ll long long
using namespace std;
ll n,d,k,x[500001],s[500001],f[500001],ans=INT_MAX;
ll ck(ll g)
{
	for(ll i=1;i<=n;i++) f[i]=sm;
	ll sum=sm;
	if(g<d)
	{
		for(ll i=1;i<=n;i++)
		{
			for(ll j=0;j<i;j++)
			{
				ll y=x[i]-x[j];
				if(d-g<=y&&y<=d+g) f[i]=max(f[i],f[j]+s[i]);
			}
			sum=max(sum,f[i]);
		}
	}
	else
	{
		for(ll i=1;i<=n;i++)
		{
			for(ll j=0;j<i;j++)
			{
				ll y=x[i]-x[j];
				if(1<=y&&y<=d+g) f[i]=max(f[i],f[j]+s[i]);
			}
			sum=max(sum,f[i]);
		}
	}
	if(sum>=k) return 1;
	else return 0;
}
int main()
{
	scanf("%lld%lld%lld",&n,&d,&k);
	for(ll i=1;i<=n;i++) scanf("%lld%lld",&x[i],&s[i]);
	if(ck(0)==1)
	{
		putchar('0');
		return 0;	
	}
	ll l=1,r=1000000000;
	while(l<=r)
	{
		ll mid=(l+r)/2;
		if(ck(mid)==0)
		{
			l=mid+1;
		}
		else
		{
			ans=min(ans,mid);
			r=mid-1;
		}
	}
	if(ans==INT_MAX) printf("-1");
	else printf("%lld",ans);
}

总结：

我们还是要自学一些算法，比赛才能高分！