Codeforces Round #519 B. Lost Array(思维)(1043B)

 

题目链接：http://codeforces.com/contest/1043/problem/B

       题意是给了n个数表示a数组，根据题目中的式子我们可以推出x0,x1,x2....，然后要我们求出x数组的长度有多少个并且输出x数组的长度，如果对于x0,x1,x2...对于题目中的式子不冲突时就表示这个长度的x数组是可行的，也就是对于在用a数组推x数组时，每一个x数组的位置仅只对应一个值，也就是说x0=1，后面出现的x0的值都是1。

       思路是我们先根据a数组，将所有的x数组求出来，然后去枚举长度是否可行就好了。

---

AC代码：

#include <bits/stdc++.h>
#define inf 1000005
using namespace std;
int n;
int pre[1005];
int b[1005],a[1005];

int main()
{
  scanf("%d",&n);
  int num = 0,num1 = 0;
  pre[0] = 0;
  for(int i=1;i<=n;i++){
    scanf("%d",&pre[i]);
  }
  for(int i=0;i<n;i++){
    a[i] = pre[i+1] - pre[i];
  }
  for(int i=1;i<=n;i++){
    int flag = 0;
    for(int j=i;j<=n;j++){
      if(pre[j] - pre[j-1] != a[(j-1)%i]){
        flag = 1;
        break;
      }
    }
    if(flag == 0){
      b[num++] = i;
    }
  }
  printf("%d\n",num);
  for(int i=0;i<num;i++){
    printf("%d ",b[i]);
  }
  puts("");
  return 0;
}