专栏文章

题解：P13938 [EC Final 2019] City

LLotleTos
P13938题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio13dly
此快照首次捕获于
2025/12/02 11:38
3 个月前
此快照最后确认于
2025/12/02 11:38
3 个月前
查看原文
分别计算与已有线条重叠的（就是横的和竖的）和斜的线段的个数，并相加。

对于与已有线条重叠的线段

要使中点在已有线的交点上，就要让边长是偶数，就是让两个端点坐标的的奇偶性相同。
  • 对于横的，只要预处理出所有横坐标中奇数和偶数的数量，然后套上组合数公式求出一行的数量，然后乘以行数。
  • 对于竖的，更横的差不多。预处理出所有纵坐标中奇数和偶数的数量，然后套上组合数公式求出一列的数量，然后乘以列数。

对于斜的线段

可以枚举线段的中点，对于这个点，求出合法的端点数量就行了。只要确定了一个端点，另一个端点就确定了，因为它们对于中点的偏移量是一样的。
如果再去枚举端点的话，时间复杂度 O(n4)O(n^4)，会超时。
所以要直接算出端点数量，分别计算在上下方向能延伸的最大长度的最小值，和左右方向能延伸的最大长度的最小值。把这两个值相乘。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	n++;
	m++;
	int n1=n/2,m1=m/2;
	int n2=n-n1,m2=m-m1;
	long long sum=n1*(n1-1)/2*m+n2*(n2-1)/2*m+m1*(m1-1)/2*n+m2*(m2-1)/2*n;//横竖的数量
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sum+=min((n-i)*(m-j),(i-1)*(j-1))*2;
		}
	}
	cout<<sum;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...