【題目】

B. Lost Array

【描述】

Bajtek有一個(gè)數(shù)組x[0],x[1],...,x[k-1]但被搞丟了，但他知道另一個(gè)n+1長(zhǎng)的數(shù)組a，有a[0]=0，對(duì)i=1,2,...,n。由此可以找到數(shù)組x[0],x[1],...,x[k-1]的一些可能情況，即滿足這個(gè)關(guān)系的數(shù)組x[0],x[1],...,x[k-1]。問一共有多少種可能的數(shù)組x[0],x[1],...,x[k-1]的長(zhǎng)度k，輸出可能的數(shù)量以及所有可能的長(zhǎng)度k。

數(shù)據(jù)范圍：1<=n<=1000，1<=a[i]<=10^6（這里不包括a[0]，默認(rèn)a[0]=0）

【思路】

?先不考慮數(shù)組x是循環(huán)的，即不考慮數(shù)組x是有限長(zhǎng)的，那么由數(shù)組a可以反解出與數(shù)組a等長(zhǎng)的一個(gè)數(shù)組“x”，我們要找的真正的數(shù)組x實(shí)際上是這個(gè)反解出來(lái)的“x”的一個(gè)周期，我們要找的就是這個(gè)“x”有多少種周期長(zhǎng)度。

要驗(yàn)證i是不是“x”的一個(gè)周期長(zhǎng)度，則將“x”的元素分為i組，即下標(biāo)模i相同的分到一組，檢查每一組從前往后數(shù)第某個(gè)元素是不是都是相同的。這里復(fù)雜度是O(n)的。

對(duì)i進(jìn)行枚舉，即可找到所有可能的周期長(zhǎng)度。至此復(fù)雜度為O(n^2)。

【我的實(shí)現(xiàn)】

?復(fù)雜度：O(n^2)

1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 6 using namespace std; 7 #define MaxN 1020 8 int x[MaxN]; 9 int Ans[MaxN]; 10 11 int main() 12 { 13 int n; 14 int a, pre_a = 0; 15 int i, j, k; 16 //int cur; 17 bool flag; 18 scanf("%d", &n); 19 for(i = 1; i <= n; i++) 20 { 21 scanf("%d", &a); 22 x[i-1] = a - pre_a; 23 pre_a = a; 24 } 25 for(i = 1; i <= n; i++) //step = i 26 { 27 flag = false; 28 for(j = 0; j < i; j++) //start at j for each zhouqi 29 { 30 for(k = j; k < n; k += i) 31 { 32 if(k > j && x[k] != x[k-i]) 33 { 34 flag = true; 35 break; 36 } 37 } 38 if(flag) 39 break; 40 } 41 if(!flag) 42 Ans[++Ans[0]] = i; 43 } 44 printf("%d\n", Ans[0]); 45 for(i = 1; i <= Ans[0]; i++) 46 printf("%d ", Ans[i]); 47 return 0; 48 } View Code

【評(píng)測(cè)結(jié)果】

?

轉(zhuǎn)載于:https://www.cnblogs.com/CQBZOIer-zyy/p/9873846.html

總結(jié)

以上是生活随笔為你收集整理的[题解]Codeforces Round #519 - B. Lost Array的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。