当前位置:编程学习 > C/C++ >>

zoj3647Gao the Grid

题目意思:在一个n*m个方格中(顶点有(n+1)*(m+1)个),求所有三角形数,即三点不共线的所有情况。
题解:令所有点的个数为t,用c[t,3]来枚举所有情况,用总数扣去所有三点共线数就是所求的三角形数。那么在求三点共线的情况时,水平和垂直的情况读者自己考虑。对于倾斜的情况,先枚举两端的端点,如图,在一个6*10的方格中选4*4的两个端点,其中可构成三点花线的另一点的个数为最大公约数gcd(4,4) -1.如图中的三个点,然后用乘于剩下的倍数(6-4+1)*(10-4+1),再乘于2(倾斜时有右上,右下两种情况).然后依次枚举所有的矩形,求出所有三点共线的情况。于是所有情况减三点共线情况就是答案了。
 
 
 
 
代码如下:
[cpp] 
/*  
 * File:   main.cpp 
 * Author: ssslpk 
 * 
 * Created on September 29, 2012, 12:20 PM 
 */  
  
#include <cstdlib>  
#include<math.h>  
#include<stdio.h>  
#define int64 long long int  
using namespace std;  
#define N 1002  
int64 f[N][N];  
int gcd(int a,int b){return b? gcd(b,a%b): a;}  
void init()  
{  
    for(int i=1;i<=1000;i++)  
    {  
        for(int j=i;j<=1000;j++)  
        {  
            int d=gcd(i,j);  
            f[i][j]=f[j][i]=(int64)(d-1);  
        }  
    }  
}  
int main() {  
    int64 n,m;  
    init();  
    while(scanf("%lld%lld",&n,&m)!=EOF)  
    {  
        int64 sum=0;  
        for(int64 i=1;i<=n;i++)  
        {  www.zzzyk.com
            for(int64 j=1;j<=m;j++)  
            {  
                sum+=f[j][i]*2*(n-i+1)*(m-j+1);  
            }  
        }  
        if(n>=2)sum+=(n+1)*(n)*(n-1)/6*(m+1);  
        if(m>=2)sum+=(m+1)*(m)*(m-1)/6*(n+1);  
        int64 t=(n+1)*(m+1);  
        int64 num;  
        if(t%3==0)  
        {  
            if((t-1)%2==0)num=t/3*(t-1)/2*(t-2);  
            else num=t/3*(t-2)/2*(t-1);  
        }  
        else if((t-1)%3==0)  
        {  
            if(t%2==0)  
                num=t/2*(t-1)/3*(t-2);  
            else num=(t-1)/6*(t-2)*t;  
        }  
        else  
        {  
            if((t-1)%2==0)  
                num=(t-1)/2*(t-2)/3*t;  
            else  num=(t)/2*(t-2)/3*(t-1);  
        }  
     //   printf("sum: %lld\n",sum);  
        printf("%lld\n",num-sum);  
    }  
  
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,