E - Make it Palindrome

原题链接

题目大意

对于数列 $X$ ，记 $f(X)$ 为修改其为回文串的最少次数。现在给定数列 $A$ ，求出 $A$ 的所有连续子序列进行 $f$ 操作的和。

思路

注意到数据范围 $N <= 2e5$ ， $O(n^2)$ 肯定是过不了的，我们要想更优的算法。但是复杂度更低的算法不是一下子就能想到的，所以我们可以考虑先想出 $n^2$ 的做法，再对其进行优化。

$O(n^2)$ 解法

既然要在 $n^2$ 内解决问题，意味着对于任意一个连续子列，我们只能枚举它的头和尾，而我们就要通过所有子列的头和尾来得出答案。我们不妨来看一个例子：

5 2 1 2 2

对于如上的数列，如果我们枚举到了第一和第四个元素，即 $(5\ 2\ 1\ 2)\ 2$ 的话，显然是需要进行一次操作的，但是这个连续子列中间的 $2\ 1$ 我们怎么处理呢？事实上，由于我们能够枚举到所有的数对，所以在之后的循环中 $2\ 1$ 是肯定能被枚举到的，我们只需要在那个时候让操作次数再加一即可。至此，我们就得到了 $O(n^2)$ 做法的思路：枚举所有点对，如果不相等，就判断最多能向外延展多少，让操作次数 = 1 + 延展数量，最后就能得到总操作次数。

int num[maxn]; //存放题目给出的数列
int cnt = 0; //记录操作次数
for(int i = 1; i <= n; i++)
    for(int j = i; j <= n; j++)
        if(num[i] != num[j])
            cnt += 1 + min(i - 1, n - j);

$O(n)$ 解法

现在让我们考虑优化。不难发现，对于任意一个点对，它延展的范围是有限的，同时点对的数量也是有限的，所以我们最多的操作次数是有限的。知道这个对我们来说有什么用呢？这意味着对于一个序列，我们可以用它的总可操作次数减去不用操作的次数，剩下的就是需要操作的次数。那为什么这样做更优呢？还是对于上述序列，我们考虑五号位的 $2$ ，由于五号位的 $2$ 不能再向外延展，所以所有 $(2,2)$ 的包含五号位的点对就是它的贡献。这样之后，我们就不用再考虑五号位的 $2$ 了。我们可以用同样的思路来处理二号位和四号位的 $2$ 。

如果我们这样做的话，在枚举所有元素的时候，当我们第一次枚举到 $2$ ，就处理完了所有 $2$ 的贡献，之后就不需要枚举 $2$ 了；而对于 $2$ 的处理，每一个位置的 $2$ 我们只利用了一次。所以从整体上来说，相当于我们仅遍历了序列所有元素一次，时间复杂度为 $O(n)$

int a[maxn]; //原数列
vector<int> pos[maxn]; //存放元素的位置信息
set<int> num; //存放数列中的元素
int sum = 0; //总的可操作次数
int ans = 0; //不需要操作的次数

int l = 1, r = n;
while(l < r)
{
    if(l < n + 1 - r) 
    {
        sum += (r - 1) * l;
        l++;
    }
    else 
    {
        sum += (r - l) * (n + 1 - r);
        r--;
    }
} //对于任意一个数，计算它能构成的所有点对的贡献，注意以延展范围最小的数为准，从左右两边枚举

for(auto i : num)
{
    int l = 0, r = pos[i].size() - 1;
    while(l < r)
    {
        if(pos[i][l] < n + 1 - pos[i][r])
        {
            ans += (r - l) * pos[i][l];
            l++
        }
        else
        {
            ans += (r - l) * (n + 1 - pos[i][r]);
            r--;
        }
    }
}

E - Make it Palindrome

题目大意

思路

O(n2)O(n^2)O(n2) 解法

O(n)O(n)O(n)解法

$O(n^2)$ 解法

$O(n)$ 解法