CF1316B 题解

Andrewzdm · 2020-03-06 10:46:25 · 题解

CF1316B String Modification

这道题我在参加比赛的时候AC的方法是强行找规律。 然后我按自己找到的规律写代码，就过了…… 先把代码给出，读者可通过阅读代码体会我发现的规律。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct res
{
    string str;
    int k;
};
res ans[5005];

bool cmp(res x, res y)
{
    if(x.str < y.str)
        return true;
    if(x.str > y.str)
        return false;
    return x.k < y.k;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        for(int i = 1; i <= n; i++)
        {
            ans[i].k = i;
            string tmp = s;
            string st = tmp.substr(0, i - 1);
            if(i % 2 == n % 2)
                reverse(st.begin(), st.end());
            tmp += st;
            tmp.erase(0, i - 1);
            ans[i].str = tmp;
        }
        sort(ans + 1, ans + n + 1, cmp);
        cout << ans[1].str << endl << ans[1].k << endl;
    }
    return 0;
}

时间复杂度 O(n^2)

相信大家已经通过阅读程序明白了我发现的规律。 接下来我们来简略地证明一下：

首先我们有一个字符串 s ， 我们可以把它表示为 s_1s_2s_3\dots s_n。

然后我们选择一个 k ：

• 经过第一次反转： s_ks_{k-1}s_{k-2}\dots s_1s_{k+1}s_{k+2}\dots s_n 观察到之后 s_k 的位置就不会发生变化了。
• 经过第二次反转： s_ks_{k+1}s_1\dots s_{k-2}s_{k-1}s_{k+2}\dots s_n 观察到之后 s_ks_{k+1} 的位置都不会发生变化。
• 经过第三次反转： s_ks_{k+1}s_{k+2}\dots s_2s_1s_{k+3}\dots s_n 观察到之后 s_ks_{k+1}s_{k+2} 的位置不会再发生变化。

……

以此类推，最后反转变换过后的字符串 s' 前 n-k+1 个字符一定是 s_ks_{k+1}s_{k+2}\dots s_n 。

通过观察还可发现， s 中的前 k-1 个字符 s_1s_2s_3\dots s_{k-1} 一定会被搬到 s' 的后半部分，但是方向不确定。

实际上，不难得到，若反转次数为奇数，则最后 s' 的后半部分为s_{k-1}s_{k-2}s_{k-3}\dots s_1 ；反之，若反转次数为偶数，则最后 s' 的后半部分为s_1s_2s_3\dots s_{k-1} 。

我们的反转次数是 n-k+1 ，所以当且仅当 n 与 k 奇偶性相同时反转次数为奇数。

于是代码就不难理解了。