codeforces #519B. Lost Array(数学思维)
程序员文章站
2022-05-09 16:24:23
...
【描述】
Bajtek有一个数组x[0],x[1],…,x[k-1]但被搞丢了,但他知道另一个n+1长的数组a,有a[0]=0,对i=1,2,…,n。由此可以找到数组x[0],x[1],…,x[k-1]的一些可能情况,即满足这个关系的数组x[0],x[1],…,x[k-1]。问一共有多少种可能的数组x[0],x[1],…,x[k-1]的长度k,输出可能的数量以及所有可能的长度k。
数据范围:1<=n<=1000,1<=a[i]<=10^6(这里不包括a[0],默认a[0]=0)
【思路】
先不考虑数组x是循环的,即不考虑数组x是有限长的,那么由数组a可以反解出与数组a等长的一个数组“x”,我们要找的真正的数组x实际上是这个反解出来的“x”的一个周期,我们要找的就是这个“x”有多少种周期长度。
要验证i是不是“x”的一个周期长度,则将“x”的元素分为i组,即下标模i相同的分到一组,检查每一组从前往后数第某个元素是不是都是相同的。这里复杂度是O(n)的。
对i进行枚举,即可找到所有可能的周期长度。至此复杂度为O(n^2)。
这题看题就知道公式x[i-1]=a[i]+a[i-1],然后让你求哪些k可以一直满足b[j]==bj-i这个k就可以行
#include<bits/stdc++.h>
using namespace std;
int n,k,fl,a[1005],b[1005],c[1005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",a+i),b[i]=a[i]-a[i-1];
for(int i=1;i<=n;++i){
fl=1;
for(int j=i+1;j<=n;++j) if(b[j]!=b[j-i]) {fl=0;break;}
if(fl) c[++k]=i;
}
printf("%d\n",k);
for(int i=1;i<=k;++i) printf("%d ",c[i]);
return 0;
}
上一篇: 自己的手撸一个hashMap
推荐阅读
-
Divide Candies CodeForces - 1056B(思维+数学)
-
Codeforces Round #657 (Div. 2) B. Dubious Cyrpto(思维,数学)
-
C.Good Array (思维) Codeforces Round #521 (Div. 3)
-
codeforces #519B. Lost Array(数学思维)
-
Codeforces 1204B. Mislove Has Lost an Array 贪心
-
【 Codeforces Round #519 by Botan Investments B】Lost Array
-
Codeforces - Ayoub and Lost Array
-
(CodeForces) C.Ayoub and Lost Array (线性dp)
-
Codeforces Round #519 B. Lost Array(思维)(1043B)
-
【 Codeforces Round #519 by Botan Investments B】Lost Array