题解：AT_abc290_e [ABC290E] Make it Palindrome

· · 题解

题意

在题目给定的一个序列中遍历所有子序列，对于每个子序列要求求出当前子序列修改变成回文数列所修改的元素个数的最小值，并输出所有子序列所需的元素次数总和的最小值。

思路

分析

要求出当前子序列修改变成回文数列所修改的元素个数的最小值就是求在这个子序列中对称位置元素不相等的对数。因为直接求子序列中对称位置元素不相等的对数有点难，所以我们可以“正难则反”，求子序列中对称位置元素相等的对数再用总对数减子序列中对称位置元素相等的对数就是答案。

1. 求总对数

对于第 i 个元素，我们可以计算他能成为多少个子序列的“左对称点”。子序列的左边界可以选择 [1,i]（i 种选择），右边界可以选择 [i,n]（n-i+1 种选择）， 整理可得 ans_i=(n-i+1)\times(i\div2)。

2. 求子序列中对称位置元素相等的对数

一个个配对的时间复杂度是 O(N^2) 会超时，所以这里我们采用双指针优化。对于每个相同数字的 [L,R]，令 x 为数字 v 的第 L 个下标位置，y 为数字 v 的第 R 个下标位置。则 [x,y] 的相等对数为 \min(x,n-y+1) 且共有 (r-l) 个与位置与之相匹配。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],ans;
vector<long long>pos[200005];
signed main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
    {
        ans+=(n-i+1)*(i/2);
        scanf("%lld",&a[i]);
        pos[a[i]].push_back(i);
    }
    for(long long i=1;i<=n;i++)
    {
        long long l=0,r=pos[i].size()-1;
        while(l<r)
        {
            long long x=pos[i][l],y=pos[i][r];
            ans-=(r-l)*min(x,n-y+1);
            if(x<n-y+1)l++;
            else r--;
        }
    }
    printf("%lld",ans);
    return 0;
}