题解：P13938 [EC Final 2019] City

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

对于两个端点

(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：

CPP

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

题解：P13938 [EC Final 2019] City

文章操作

相关推荐

评论

题解：P13938 [EC Final 2019] City