题解 UVA11401 【Triangle Counting】

Mutsumi_0114 · 2018-12-19 20:19:54 · 题解

本题根据数据范围可看出大概是O(N)或O(Nlog(N))复杂度算法。

考虑打表找规律：

#include <cstdio>
using namespace std;
int main()
{
    int ans=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            for(int k=j+1;k<=n;k++)
                if(i+j>k)
                    ans++;
    printf("%d",ans);
    return 0;
}

得出如下数列：

N   : 3 4 5 6 7  8  9  10 11 12 13  14
ans : 0 1 3 7 13 22 34 50 70 95 125 161

观察ans相邻两项差值得到如下数列：

x : 1 2 4 6 9 12 16 20 25 30 36

不难发现数列x中奇数项为平方数，偶数项为相邻两整数乘积的平方根。

我们根据找到的规律先打出初步代码：

#include <cstdio>
using namespace std;
int n;
long long ans;
int main()
{
    scanf("%d",&n);
    while(n>=3)
    {
        ans=0;
        long long k=n/2-1;
        for(long long i=1;i<=k;i++)
            ans+=i*i;
        for(long long i=1;i<k;i++)
            ans+=i*(i+1);
        if(n%2)
            ans+=k*(k+1);//若n为偶，则x数列末项为平方数，反之则为相邻整数乘积
        printf("%lld\n",ans);
        scanf("%d",&n);
    }
    return 0;
}

有了这个程序之后，为了保险，将它与暴力程序对拍。因为刚才暴力的复杂度为O(N^3)，所以可以尝试数据N=1000，N=999（为了保险可以再稍微大一些），发现答案无误，可以确定规律无误。

做完之后了解到正解递推为：