昨天打比赛又遇到了子序列的题目,没写出来。
题目:https://ac.nowcoder.com/acm/contest/120061/E
题目大意:连续子数组是左右两边拼起来的数组的子序列,求这样的子数组数量。
最初想二分长度,发现不单调,题解是枚举每个左边界l,二分最大的右边界,此时对于每个左边界是单调的,因为大的可以小的一定可以。
代码:
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010;
int a[N],n;
bool check(int l,int mid)
{
int idx = l;
for(int i = 1;i<=n;i++)
{
if(i == l)
{
i = mid;
continue;
}
if(idx <= mid && a[idx] == a[i])
{
idx ++;
}
}
if(idx == mid + 1) return 1;
else return 0;
}
void solve()
{
cin >> n;
for(int i = 1;i<=n;i++) cin >> a[i];
ll ans = 0;
for(int i = 2;i<n;i++)
{
int l = i - 1,r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(i,mid)) l = mid;
else r = mid - 1;
}
ans += l - i + 1;
}
cout << ans << endl;
}
int main()
{
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}