题解：P13938 [EC Final 2019] City

LotleTos · 2025-09-02 21:45:56 · 题解

分别计算与已有线条重叠的（就是横的和竖的）和斜的线段的个数，并相加。

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

要使中点在已有线的交点上，就要让边长是偶数，就是让两个端点坐标的的奇偶性相同。

• 对于横的，只要预处理出所有横坐标中奇数和偶数的数量，然后套上组合数公式求出一行的数量，然后乘以行数。
• 对于竖的，更横的差不多。预处理出所有纵坐标中奇数和偶数的数量，然后套上组合数公式求出一列的数量，然后乘以列数。

  对于斜的线段

  可以枚举线段的中点，对于这个点，求出合法的端点数量就行了。只要确定了一个端点，另一个端点就确定了，因为它们对于中点的偏移量是一样的。

如果再去枚举端点的话，时间复杂度 O(n^4)，会超时。

所以要直接算出端点数量，分别计算在上下方向能延伸的最大长度的最小值，和左右方向能延伸的最大长度的最小值。把这两个值相乘。

代码

#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;
}