三元组加强版

Problem

题目描述

给定两个整数 \(n,m\) 问有多少三元组 \((x,y,z)\) 满足:

  • \(0\le x,y,z\le n\)
  • \(x+y+z=m\)

输入格式

一行给出两个整数 \(n,m\) 。

输出格式

一个整数,代表答案。

Example&Prompt

输入输出样例

样例\(1\):
输入:$2\ 2\ \ \ $ 输出:\(6\)
样例\(2\):
输入:$3\ 15\ $ 输出:\(1\)

数据范围

对于\(20\%\)的数据,满足\(1\le n\le 100\)。
对于\(50\%\)的数据,满足\(1\le n\le 10^4\)。
对于\(100\%\)的数据,满足\(1\le n\le 10^7,0\le m\le3n\)。

Solution1(20pts)

暴力枚举\(x,y,z\),再判断合不合法,时间复杂度为\(O(n^3)\)。

Solution2(50pts)

暴力枚举\(x,y\),根据条件\(2\)算出\(z\),再判断合不合法,时间复杂度为\(O(n^2)\)。

Solution3(100pts)

暴力枚举\(x\),再求出\(y,z\)的所有可能性。

那如何求\(y,z\)的所有可能性呢?不妨先令\(k=m-x\),因为条件\(1\),所以当\(k< 0\)时没有合法的解,只要讨论\(k\ge 0\)的情况。

首先先看一种简单的情况:\(n\ge k\)

根据条件\(2\),我们有\(y+z=k\),因为\(n\ge k\),所以不存在不合法的结果。

因此,我们就是要求两个自然数之和为\(k\)的数量,这个很明显是\(k+1\)种,举个例子:

\[4=0+4=1+3=2+2=3+1=4+0 \]

其实也就是\(k=i+(k-i)(0\le i\le k)\),共\(k+1\)种可能。

然后再看\(n<k\)的情况,我们依旧有\(y+z=k\),但此时可能有不合法结果,甚至没有合法结果。

我们先设\(y=n\),此时\(z=k-n=m-2n\)为最小值,如果\(z>n\),那么代表没有合法结果,因为最小的可能也不符合要求,也就没有符合要求的结果了。

然后考虑有不合法结果也有合法结果,根据上面的例子\(4\)我们可以看出,分解的两端(即\(y,z\)分别取较大值时)最可能不符合要求,因此我们只要找出有多少不符合要求的值,再用总情况减去,就知道了有多少合法值。

很明显,从\(k=i+(k-i)(0\le i\le k)\)可以看出\(i>n\)不符合情况的数量是\(k-n\),\(k-i\)不符合情况的数量也是\(k-n\)(正好与\(i\)不符合情况相反)。

总情况仍是\(k+1\),因此,这时候符合情况的数量就是\(k+1-(k-n)* 2=2n-k+1\)。

我们把所有情况加起来就是答案了,时间复杂度为\(O(n)\)。

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
    {
        int k=m-i,j=0;
        if(k>=0)
        {
            if(k>n)
            {
                if(k-n>n)
                j=0;
                else
                j=2*n-k+1;
            }
            else
            j=k+1;
        }
        ans+=j;
    }
    printf("%d",ans);
    return 0;
}
上一篇:排序 pat1080 Graduate Admission (30 分) (未AC,一个节点超时)


下一篇:类欧几里得算法