题解 P2181 【对角线】

· · 题解

嗯...

各位大佬都用了O（1）的代码

蒟蒻推不出公式瑟瑟发抖

这里我打了一个表

n 交点

2 = 0

3 = 0

4 = 1

5 = 5

6 = 15

7 = 35

8 = 70

... ...

对数列每相邻两项作差

得到

  1. a[3]-a[2] = 0

  2. a[4]-a[3] = 1

  3. a[5]-a[4] = 4

  4. a[6]-a[5] = 10

  5. a[7]-a[6] = 20

  6. a[8]-a[7] = 35

真相就要浮出水面了！

再做差得到

1

3

6

10

15

有没有很熟悉了？得到结论：再做差

1

2

3

4

5

...

所以，类似的这种题都可以坚持不懈做差找规律

虽然是道入门难度...

那附上代码，这里十分简洁明了

#include<cstdio>
long long a1[100000];
long long a2[100000];
long long a3[100000];
int main()
{
    long long n;
    scanf("%lld",&n);
    int t=0;
    for(int i=1;i<=n;i++)
    {
        a1[i]=a1[i-1]+i;//这里生成1,3,6,10序列
    }
    for(int i=1;i<=n;i++)
    {
        a2[i]=a2[i-1]+a1[i];//这里生成1,4,10,20序列
    }
    for(int i=1;i<=n;i++)
    {
        a3[i]=a3[i-1]+a2[i];//这里生成答案序列：1,5,15,35
    }
    printf("%lld",a3[n-3]);
    return 0;
}

注意开longlong，显然数列连着加到100000项会很大

希望对大家有帮助

来自蒟蒻的第一篇可能过审的题解