数学基础题

Bertha 。 2021-12-12 04:41 273阅读 0赞

### uva[11538 - Chess Queen][] ###

///*UVa11538
    ///*两皇后放在同一行A（n,m）=n*m*(m-1)  即先选出白后，先从n行中选1行n种，然后在每行中放二后有m*(m-1)种
    ///*放在同一列同样方法B（n,m）=m*n*(n-1) 种
    ///*放在对角线上时，假设n<=m,D=（2n(n-1)*(3m-n-1)/3）种，
    ///则从左到右长度依次为1,2,3,4...(n-1),(m-n+1)个n,(n-1)...3,2,1   两条对角线乘以2求和就是上面的值
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        unsigned long long n,m;
        while(cin>>n>>m)
        {
            if(!n&&!m) break;
            if(n>m) swap(n,m);
            cout<<n*m*(m+n-2)+2*n*(n-1)*(3*m-n-1)/3<<endl;
        }
        return 0;
    }

### [uva11401 - Triangle Counting][] 计算从1-n中任取三个数组成三角形的个数 ###

///最大边长为x的三角形有f[x]个，另外两条边为Y，z，有y+z>x,则x-y<z<x
    ///从y=2开始有解为0+1+2++++（n-3）+（n-2）=（n-1）*（n-2）/ 2。
    ///但是包含y=z的情况，而且每个三角形算了两遍统计y=z的情况有x-1-x/2=(x-1)/2.
    ///则f[i]=f[i-1] + ((i-1)*(i-2)/2 - (i-1)/2)/2;
    #include <iostream>
    using namespace std;
    
    long long f[1000010];
    int main()
    {
        f[3]=0;
        for(long long i=4;i<=1000000;i++)
            f[i]=f[i-1] + ((i-1)*(i-2)/2 - (i-1)/2)/2;
    
        int n;
        while(cin>>n)
        {
            if(n<3) break;
            cout<<f[n]<<endl;
        }
        return 0;
    }

### [UVa11806 - Cheerleaders][] ###

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    const int Mod = 1000007;
    const int Max = 500;
    
    int v[Max+10][Max+10];
    int main()
    {
        memset(v,0,sizeof(v));
        v[0][0]=1;
        for(int i=0;i<=Max;i++)
        {
            v[i][0]=v[i][i]=1;
            for(int j=1;j<i;j++)
                v[i][j]=(v[i-1][j] + v[i-1][j-1])%Mod;
        }
    
        int T;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            int n,m,k,sum=0;
            scanf("%d%d%d",&n,&m,&k);
            for(int i=0;i<16;i++)
            {
                int b=0,r=n,c=m;
                if(i&1) { r--;b++; }
                if(i&2) { r--;b++; }
                if(i&4) { c--;b++; }
                if(i&8) { c--;b++; }
                if(b&1)
                    sum=(sum+Mod - v[r*c][k]) %Mod;
                else sum=(sum + v[r*c][k])%Mod;
            }
            printf("Case %d: %d\n",cas,sum);
        }
        return 0;
    }

[11538 - Chess Queen]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2533
[uva11401 - Triangle Counting]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2396
[UVa11806 - Cheerleaders]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2906