AcWing 4401. 找回数组
原题链接
中等
作者:
绿水
,
2022-04-26 23:34:14
,
所有人可见
,
阅读 197
分析
题意很复杂,抽丝剥茧
得出一个构造数组的模型,
给定长度为n(小于1000,可以用n^2的时间复杂度)的数组a, 通过这种方式能构造 x
x[0 % k] == a[1]
x[1 % k] == a[2] - a[1]
x[2 % k] == a[3] - a[2]
...
x[(n - 1) % k] == a[n] - a[n - 1]
要使k符合要求 即需所有有相同下标的x数组值相同
我们可以从k + 1 开始往前看, 枚举到 n, 因为第一次出现重复的值就是k + 1
相同的值为 a[i] - a[i - 1] == a[i - k] - a[i - k - 1]
剩下枚举即可,主要题意难理解
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
vector<int> res;
for (int k = 1; k <= n; k ++ )
{
bool flag = true;
for (int i = k + 1; i <= n; i ++ )
if (a[i] - a[i - 1] != a[i - k] - a[i - k - 1])
flag = false;
if (flag) res.push_back(k);
}
cout << res.size() << endl;
for (auto& v: res)
cout << v << ' ';
return 0;
}