P8030 [COCI2021-2022#3] Ekoeko 题解

P8030 [COCI2021-2022#3] Ekoeko 题解

原题链接

题目描述

给定一个正整数 和一个由 个小写字母组成的字符串。

交换字符串的相邻两个字母视为一次操作。求使得原串的前 个小字母和后 个完全相同所需的最少操作次数。

对于这道题目，我们从部分分入手。（以下下标从 开始）

• Subtask 1（10 pts）：字符串前 个字母均为 ，后 个均为 。

明显就是找规律的，我们不看这个。

• Subtask 2（20 pts）：每个字母在字符串中至多出现两次。

说明每个字母在前半部分和后半部分应该要各有一个，暂时没有帮助，先跳过。

• Subtask 3（20 pts）：前 个字母和后 个字母的组成完全相同，但顺序可能不同。

看到 Subtack3 后，我们开始考虑，当前半部分和后半部分的组成一定时，显然可得，我们每次交换应当在前半部分和后半部分中独立进行，肯定不会有交换跨越两个部分。

进一步我们可知，这里面的顺序是相对的，我们只是要顺序相同，所以我们只需要在前半部分或后半部分选择其一，将其中的顺序交换为同另一部分相同，当前最优。

至于实现比较简单。设前半部分为 ，后半部分为 ，只在前半部分交换，每次找到在 中找到第一个 ,设下标为 ，将它调换到下标为 ，代价为 ,然后我们直接将其删去。

for(register int i=0;i<n;++i)
{
    int k=a.find(b[i],0);
    ans+=k,a.erase(k,1);
}

• Subtask 4（20 pts）：。
• Subtask 5（40 pts）：无特殊限制。

相当于没有特殊性质了，我们回过来看 Subtack2

• Subtask 2（20 pts）：每个字母在字符串中至多出现两次。

先前的操作，是在前半部分和后半部分的组成相同之后，所需要的代价，我们现在要解决的问题是如何将一整个字符串分成前半部分和后半部分，使其组成相同。

对于 Subtack2 来说，我们可以得到很简单的思路，每个字母第一次出现，放到前半部分，第二次出现，放到后半部分。

推而广之，如果一个字母出现了 次，我们使前 次在前半部分，使后 次在后半部分，当前最优。

实现即记录每个字母出现的次数，对于一个应处于后半部分的字母，将它移到后面，如果这是当前后半部分的第 个字母，我们便应将其移动到 ，当前下标为 ，代价为 ，同时分离前半部分和后半部分。

for(register int i=0;i<(n<<1);++i) t[s[i]-'a']++;
for(register int i=0;i<(n<<1);++i)
{
    if(cnt[s[i]-'a']==t[s[i]-'a']/2) b+=s[i],tot++,ans+=n+tot-1-i;
    else cnt[s[i]-'a']++,a+=s[i];
}

说的比较多，但总结就是先分离前半部分和后半部分，然后将前半部分变为后半部分，根据特殊性质比较容易想出思路，贪心正确性也可以不严谨的证明，完整代码不想放了，记得开 long long。（话说没开 long long调了半天）