牛客小白月赛122 E

https://ac.nowcoder.com/acm/contest/119664

E

计算f（l，r）需要判断[l,r]是否为[1,l-1]+[r+1,n]的子序列（对此我们可以用双指针实现）；
如果每次枚举（l，r）时都去判断一次，得到时间复杂度为O(n³*logn)对于n=2000不够；
我们考虑如何预处理以达到快速判断的目的；

方法一

分析

显然对于一个确定的l，若r满足条件，那么显然r-1也满足条件。我们可以通过枚举l，然后从大到小枚举r，找到rmax，那么比r小的都不必进行双指针判断。

更进一步，对于符合条件的（l，r），l增加时，rmax不增；可以进一步减小枚举量 时间复杂度O（n²）

代码实现

#include <bits/stdc++.h>
using namespace std;
int n;
int P[10000];
bool check (int l, int r)//返回f（i，j）的值
{int x = l;for (int i = 1; i <= n; i++){if (i == l){i = r;continue;}if (x <= r && P[x] == P[i]){x++;}}return x == r + 1;
};
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> P[i];}int ans = 0;for (int i = 2; i < n; i++)//枚举l{int l = i - 1, r = n - 1;while (l < r)//二分查找最大的r{int mid = (l + r + 1) >> 1;if (check(i, mid)){l = mid;}else{r = mid - 1;}}ans += l - i + 1;}cout << ans << endl;return 0;
}

方法二

分析

考虑 ll[i] 和 rr[i] ：
ll[i] 是满足[i,i+x-1]是[1,i-1]的子序列的x的最大值
rr[i] 是满足[i-x+1,i]是[i+1,n]的子序列的x的最大值

那么f(i,j)==1等价于ll[l]+rr[r]>r-l;
时间复杂度O（n²）

代码实现

#include<bits/stdc++.h>
using namespace std;
int p[10000], ll[10000], rr[10000];
int n;
bool check1(int i, int x) //起点 长度
{int k = i;int t = 1;while (t <= i - 1 ){if (p[k] == p[t]){k++;if (k == i + x)return 1;}t++;}return 0;
}
bool check2(int i, int x) //终点 长度
{int k = i - x + 1;int t = i + 1;while (t <= n){if (p[k] == p[t]){k++;if (k == i + 1)return 1;}t++;}return 0;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> p[i];for (int i = 2; i < n; i++){int l = 0, r = n;int mid;while (r - l >= 0){if (r == l){ll[i] = l;break;}mid = (l + r + 1) / 2;if (check1(i, mid))l = mid;elser = mid-1;}}for (int i = 2; i < n; i++){int l = 0, r = n;int mid;while (r - l >= 0){if (r == l){rr[i] = l;break;}mid = (l + r + 1) / 2;if (check2(i, mid))l = mid;elser = mid-1;}}int sum = 0;for (int l = 2; l < n; l++)for (int r = l; r < n; r++)if (ll[l] + rr[r] >= r - l+1)sum++;cout << sum;return 0;
}