P8452 「SWTR-8」15B03

题目背景

15B03 获得了 ION2064 的承办权。

题目描述

15B03 的座位非常拥挤，可以看成一张 $n\times m$ 的网格，每个小正方形 $(i,j)$ 代表一张桌子。

根据规定，考场上任何两张桌子不得相邻。这里相邻指含有 公共点。严格定义两张桌子 $(i,j)$ 和 $(i^{\prime },j^{\prime })$ 相邻当且仅当 $|i-i^{\prime }|\le 1$ 且 $|j-j^{\prime }|\le 1$。

布置考场的任务落在小 A 头上，他希望撤去最少的桌子满足上述要求。

小 A 认为这样太简单了，因此他添加了限制：在保证撤去桌子最少的前提下，最大化剩余每张桌子到距离它最远的桌子的距离之和。这里距离指 欧几里得 距离：桌子 $(a,b)$ 和 $(c,d)$ 的距离为 $\sqrt{(a-c{)}^2+(b-d{)}^2}$。

平行时空中 15B03 的规模不尽相同：多组测试数据。

请选手认真阅读本题的评分方式。

输入格式

第一行一个整数 $S$，表示该测试点的编号。

第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：

• 一行两个整数 $n,m$。

输出格式

对于每组测试数据：

• 输出一个整数和一个实数，由空格隔开。分别表示最少撤去的桌子数量以及每张桌子到距离它最远的桌子的距离之和的最大值。

实数比较按绝对误差或相对误差不超过 $10^{-9}$：令你输出的答案为 $a$，标准答案为 $b$，你的答案被判为正确当且仅当 $\frac{|a-b|}{\max (1,|b|)}\le 10^{-9}$。

输入输出样例 #1

输入 #1

0
4
3 3
2 4
15 57
1064 822

输出 #1

5 11.313708499
6 6.324555320
623 10206.135788972
655956 222400384.677931725

说明/提示

「样例解释」

对于第一组询问，选择 $(1,1),(1,3),(3,1)$ 和 $(3,3)$ 最优。撤去了 $3\times 3-4=5$ 张桌子，且每张桌子到距离它最远的桌子的距离均为 $\sqrt{2^2+2^2}=2\sqrt{2}$，因此第二问答案为 $8\sqrt{2}$。如下图所示：

对于第二组询问，选择 $(1,1)$ 和 $(2,4)$ 最优。撤去了 $2\times 4-2=6$ 张桌子，且每张桌子到距离它最远的桌子的距离均为 $\sqrt{1^2+3^2}=\sqrt{10}$，因此第二问答案为 $2\sqrt{10}$。

如果选择 $(1,1)$ 和 $(2,3)$，则第二问答案为 $2\sqrt{5}$，不优。

「评分方式」

对于每组测试数据：

• 若你第一问的答案错误，得 0 分。
• 否则，若你第二问的答案错误，得 0.8 分。
• 否则，得 1 分。

每个测试点的得分为测试点内所有测试数据的得分的最小值乘以该测试点的分值。

注意，若你输出的格式错误，得 0 分。因此，如果你只希望获得第一问的分数，请在第二问输出任意合理范围内的实数。

「数据范围与约定」

• 测试点 #1（15 points）：$n,m$ 均为奇数。
• 测试点 #2（20 points）：$n=1$。
• 测试点 #3（25 points）：$n=2$。
• 测试点 #4（30 points）：$n$ 为奇数。
• 测试点 #5（10 points）：无特殊限制。

对于 $100\%$ 的数据：

• $1\le T\le 57$。
• $1\le n,m\le 1064$。

「帮助与提示」

• 你可以使用 cmath 中的 sqrt(x) 函数计算 $x$ 的平方根。它返回 double 类型的值。sqrtl(x) 精度更高，它返回 long double 类型的值。

「题目来源」

• Sweet Round 8 A
• Idea & Solution：Alex_Wei。
• Tester：chenxia25。

C++实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll s,t,n,m,r;
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>s>>t;
	for(int i=1;i<=t;i++)	{
		bool p=1,q=1;
		cin>>n>>m;
		r=n*m;
		if(n%2==0) n--,p=0;
		if(m%2==0) m--,q=0;
		r-=(n/2+1)*(m/2+1);
		cout<<r<<" ";		
		if(p==0) n++;
		if(q==0) m++;
		if(n*m-r==1) {cout<<"0.000000000"<<endl; continue;}
		long double ans=0.0;
		long long k=1,j=1;
		p=1,q=1;
		for(k=1;k<=n;k+=2)		{
			q=1;
			for(j=1;j<=m;j+=2)			{
				if(m%2==0&&j>(m/2)&&(q)) j++,q=0;
				long long x,y;
				if(k<=(n+1)/2) x=k;
				else x=n-k+1;
				if(j<=(m+1)/2) y=j;
				else y=m-j+1;
				ans+=sqrtl(((long double)((n-x)*(n-x))+((long double)((m-y)*(m-y)))));
			}
			if(n%2==0&&k+2>=(n/2)&&(p)) k++,p=0;
		}
		cout<<fixed<<setprecision(9)<<ans<<endl; 
	}
	return (0-0);  
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容