前言
上午就写完这题了,但是因为还有很多别的麻烦事导致现在才有空写题解。
好多看起来暴力的代码,实际上复杂度都是完全正确的,自己也想到过这种暴力代码,但是就是觉得复杂度不对,所以就不敢写。
比如某场校赛的那个质数的暴力题,赛时一直想不出怎么写,也不敢交暴力代码,没想到正解就是暴力。。。
还有就是这题,这题敢于交上代码了,然后看着绿油油的AC我也很意外。细细分析完复杂度,却又发现是正确的了。。还是太笨了捏
题意
给定数组a[],求数组中有多少等差子数组。
做法
考虑f[i][d]表示以第i个数字结尾,公差的d的方案数。
然后转移很简单,f[i][d] += f[j][d],其中a[j] + d == a[i]。做到这里 ,可能就会发现,不止a[j] + d,还有a[j] - d。那就再加一个g[i][d]表示第i个数字结尾,公差为d的方案数好了。
至于a[i] ± d的位置怎么找,很简单,放进vector就好了。
int a[N], f[N][20005], g[N][20005];
vector<int> v[20005];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
v[a[i]].emplace_back(i);
}
int ma = *max_element(a + 1, a + 1 + n);
// f[i][d]表示第i个路灯结尾?
// f[j][d] 其中 a[i] -或+ d == a[j]
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int d = 0; d <= ma; d++)
{
// 枚举公差,看看前面有几个符合条件的
int pos;
pos = a[i] - d;
if (pos >= 0) for (auto j : v[pos]) {
if (j < i) f[i][d] = (f[i][d] + f[j][d] + 1) % mod;
else break;
}
ans = (ans + f[i][d]) % mod;
if (d != 0)
{
pos = a[i] + d;
if (pos <= ma) for (auto j : v[pos]) {
if (j < i) g[i][d] = (g[i][d] + g[j][d] + 1) % mod;
else break;
}
ans = (ans + g[i][d]) % mod;
}
}
}
cout << (ans + n) % mod;
}