题解：P13938 [EC Final 2019] City

L_T_L · 2025-09-04 19:33:54 · 题解

题目传送门

找到所有非零长度的线段，其端点和中点都是网格点。这样的线段必须满足对称性。因此，两个端点的坐标必须具有相同的奇偶性，这样它们的和才会是偶数，从而中点坐标为整数。

对于两个端点 (x1,y1) 和 (x2,y2)，其中点 \frac{x1+x2}{2}, \frac{y1+y2}{2} 必须是整数。这意味着 (x1+x2) 和 (y1+y2) 必须是偶数，即 x1 和 x2 的奇偶性相同，y1 和 y2 的奇偶性相同。

然后计算所有可能的有效线段
首先，网格点总数为 (n+2)\times(m+2)。但我们需要考虑线段的方向（包括斜向）。
将网格点按坐标的奇偶性分为四类：(奇,奇)、(奇,偶)、(偶,奇)、(偶,偶)。对于同一类中的任意两个点，它们形成的线段的中点必然是网格点。
对于每一类，如果有 k 个点，则这类点可以形成 C(k,2) 条线段。总的有效线段数是这四类中每类的点对数的总和。

CODE：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt1a,cnt1b,cnt2a,cnt2b;
int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            if(i%2==0&&j%2==0)
                cnt1a++;
            else if(i%2==0&&j%2==1)
                cnt1b++;
            else if(i%2==1&&j%2==0)
                cnt2a++;
            else
                cnt2b++;    
    cout<<
           cnt1a*(cnt1a-1)/2+
           cnt1b*(cnt1b-1)/2+
           cnt2a*(cnt2a-1)/2+
           cnt2b*(cnt2b-1)/2
    <<endl;
    return 0;
}