首页 > 代码库 > bzoj 3505: [Cqoi2014]数三角形

bzoj 3505: [Cqoi2014]数三角形

2024-11-28 04:21:02   204人阅读

Description

给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。

注意三角形的三点不能共线。

Input

输入一行，包含两个空格分隔的正整数m和n。

Output

输出一个正整数，为所求三角形数量。

solution

给的 n，m 是格子数，实际上点数是n+1，m+1，所以我们先++n，++m  下面说的n，m是点数

我一开始是想着总方案数是 C(n*m，3)，然后减去 竖列，横行，对角线 长度len的 C(len，3) 

但是我只考虑斜率为 1/-1 的对角线，在wa了多次后看题解，发现竟然还有其他的对角线...

其实考虑到那种情况，我也做不出来，因为用 组合数 计算 三点共线的三角形 无法去重...

 

 

补集思想我想出来了

但是正解计算不合法三角形是：

枚举不合法三角形中 最左边和最右边的两个端点，计算中间端点的个数，即为当前端点为这样时的不合法三角形个数

计算中间端点有个定(gui)理(lv)：

(x1,y1)和(x2,y2)之间的点数(不包括端点)为 gcd( abs(x1-x2),abs(y1-y2) )-1 个

暴力枚举两个端点是O(n^2*m^2*logn)肯定超时

优化是固定左端点为(1,1) (我习惯最上角是(1,1)) 枚举右端点，得到一条线段，然后将这条线段挪动

得到 (n-i+1)*(m-j+1) 个相同的线段 (这个不是定理，可以自己画画找规律)

O(n*m*logn)

最后 ans=C(n*m,3)-sum(不合法三角形个数)

 

技术分享 
 1 #include<cstring>
 2 #include<cstdio>
 3 #include<iostream>
 4 #define ll long long
 5 #define mem(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 const int N=1066;
 8 const int LEN=303;
 9 ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
10 
11 ll n,m;
12 
13 int main(){
14     
15     scanf("%lld%lld",&n,&m);
16     if(n<m)swap(n,m);
17     ++n;++m;
18     
19     ll ans=(ll)(n*m-1)*(ll)(n*m-2)*n*m/6;
20     ll temp;
21     for(int i=1;i<=n;++i)
22       for(int j=1;j<=m;++j)
23       {
24             if(i==1&&j==1)
25               temp=0;
26             else
27               if(i==1)
28                 temp=j-2;
29             else
30               if(j==1)
31                 temp=i-2;
32             else
33                 temp=gcd(i-1,j-1)-1;
34             
35             if(i!=1&&j!=1)
36                 ans-=(temp*(n-i+1)*(m-j+1)*2);
37             else
38               ans-=(temp*(n-i+1)*(m-j+1));
39         }
40     cout<<ans;
41     //while(1);
42     return 0;
43 } 
44
code

 

bzoj 3505: [Cqoi2014]数三角形


联系
我们