【HDU】 1121 Complete the Sequence

2024-03-09 06:48

文章标签 hdu sequence complete 1121

本文主要是介绍【HDU】 1121 Complete the Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Complete the Sequence

题目链接

Complete the Sequence

题目大意

这题题意挺好懂的，就是给你一列数，现在然你找规律找到后面S位是什么。

题解

    首先这题是用差分求解。
    关于这题为什么要差分，我不知道….看了好多东西还是不懂…我这里就直接写解法吧。
    我们对前面n个数，求其差分，从1阶差分一直求到n-1阶差分，可以想到如果在第k阶差分全部相同的话，P的阶就是k（因为后面更高阶的差分全部为零了，即使求和也不会改变阶数），因为我们求出n-1阶差分后就只剩下一个数了，于是我们在后面构造S个跟该数相同的数然后倒推回去，就得到了解。
    我的问题主要在于，如果我们求出n-1阶差分后最后一个数仍然不等于0的话，即使这列数满足某个多项式它也应该是n阶的，我们应该求不出来或者是求出它的某一个n-1阶近似才对，可是我们这样写却AC了….

代码

#include <iostream>
#include <cstring>
#include <cstring>
#include <cstdlib>
#include <cstdio>using namespace std;int n,s,d[110][110],T;int main()
{scanf("%d",&T);while(T--){memset(d,0,sizeof(d));scanf("%d%d",&n,&s);for (int i=0;i<n;i++) scanf("%d",&d[0][i]);for (int i=1;i<=n-1;i++)for (int j=i;j<n;j++) d[i][j]=d[i-1][j]-d[i-1][j-1];for (int j=n;j<n+s;j++) d[n-1][j]=d[n-1][n-1];for (int i=n-2;i>=0;i--)for (int j=n;j<n+s;j++) d[i][j]=d[i][j-1]+d[i+1][j];for (int j=n;j<n+s-1;j++) printf("%d ",d[0][j]);printf("%d\n",d[0][n+s-1]);}return 0;
}