“统信杯” 第十七届黑龙江省大学生程序设计竞赛题解

---------更新中---------

比赛链接
A题

/* 
题意： 
书架高h 
n本高度为a的书和m本高度为b的书放在书架上
a的全部放左边，b的全部放右边 
原本所占用的书架宽度为n+m
现在可以拿出k本高度为b的书将其横着放在任意位置
问可以使得占用的书架宽度最少是多少 
*/
/*
题解：
先求长为n高为h-a的书架能横着放多少本高度为b的书
二分一下最多能拿走多少本高度为b的书 
*/ 
int a,b,n,m,h;
ll cnt,las;
bool check(int x)
{
	if(x<=cnt)return 1;
	if(1ll*(h-b)*((las+m-x)/b)>=x-cnt)return 1;
	return 0;
}
void solve()
{
	scanf("%d%d%d%d%d",&a,&b,&n,&m,&h);
	cnt=1ll*(h-a)*(n/b);//a上面的空间能放多少本 
	las=n%b;//a上面剩余的宽度 
	if(cnt>=m-1)
	{
		printf("%d\n",n+1);
		return;
	}
	int l=0,r=m-1,ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,ans=n+m-mid;
		else r=mid-1;
	}
	printf("%d\n",ans);
}

B题

/* 
题意： 
象能走7个位置
原本的两只象的位置为a1,a2
现在想让两个象的位置为b1,b2
问最少需要走多少步 
*/
/*
题解：
有2种情况
a1到b1,a2到b2
a1到b2,a2到b1
看哪种情况使用的步数最少 
*/ 
int a[8][8]={
0,0,0,0,0,0,0,0,
0,0,1,1,2,3,3,4,
0,1,0,2,1,2,2,3,
0,1,2,0,1,2,2,3,
0,2,1,1,0,1,1,2,
0,3,2,2,1,0,2,1,
0,3,2,2,1,2,0,1,
0,4,3,3,2,1,1,0
};
int a1,a2,b1,b2;
void solve()
{
	scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
	printf("%d\n",min(a[a1][b1]+a[a2][b2],a[a1][b2]+a[a2][b1]));
}

----这里有个小问题----
为什么下面代码就会出现段错误，通过率90%

int a[7][7]={
0,1,1,2,3,3,4,
1,0,2,1,2,2,3,
1,2,0,1,2,2,3,
2,1,1,0,1,1,2,
3,2,2,1,0,2,1,
3,2,2,1,2,0,1,
4,3,3,2,1,1,0
};
int a1,a2,b1,b2;
void solve()
{
    scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
    a1--;a2--;b1--;b2--;
    printf("%d\n",min(a[a1][b1]+a[a2][b2],a[a1][b2]+a[a2][b1]));
}