APIO 2018 Practice Session T3 / CF 936C Lock Puzzle

传送门

题目大意

给你一个字符串 origin，一个字符串 target，长度均为 n n $n$。要求在 3n$3n$$3n$（ 52n 5 2 n $\frac {5} {2}n$）次操作以内将 origin 变成 target。操作是：对于字符串 S S $S$，我们将它表示成 αβ$\alpha \beta$$\alpha \beta$ 的形式，操作之后这个字符串将会变成 βRα β R α $\beta^R \alpha$，其中 R R $^R$ 表示将字符串反转。 α α $\alpha$ 和 β β $\beta$ 可以为空串。

思路

唉，我太弱了，什么都不会，一开始还以为求最少操作次数，后来发现是给出方案即可，但是完全没思路。唉，我太弱啦！

一般这种变换式的构造题都可以一步一步构造，即在不改变已经构造好了的部分的前提下扩大构造的范围。但是我太弱了，看到了这个思路，我也只想到了 4n 4 n $4n$ 的解法。

我们逐步构造 target 的后缀，把它放到 origin 的最前面去。设字符串 v1w2 v 1 w 2 $v1w2$ 表示 origin，其中 v v $v$ 表示已经构造好了的后缀，w$w$$w$ 表示后缀前面要接的一个字符（显然长度为 1 1 $1$），1$1$$1$ 和 2 2 $2$ 表示夹在它们之间的其它串。我们这样变化：

$$v1 \!\!\mid\!\! w2 \\\downarrow\\ 2^R \!\!\mid\!\! wv1 \\\downarrow\\ 1^R v^R w \!\!\mid\!\! 2^R \\\downarrow\\ 21^R \!\!\mid\!\! v^Rw \\\downarrow\\ wv21^R$$

显然 wv w v $wv$ 是我们想要的，因此我们得到了一个 4n 4 n $4n$ 的做法，在练习赛中获得了很弱的 78 78 $78$ 分，唉，我太弱啦！

---

我们还是用这个思路：

$$\mid v1w2 \\\downarrow\\ 2^R w \!\!\mid\!\! 1^R v^R \\\downarrow\\ v 1 2^R \!\!\mid\!\! w \\\downarrow\\ w v 1 2^R$$

这样我们得到了一个 3n 3 n $3n$ 的做法，通过了 CF 936C，并在练习赛中得到了很弱的 89 89 $89$ 分，看来要拿铁牌了，唉，我太弱啦！

参考代码

（两道题输入不一样，下面这个是 CF 936C）

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = 2005;
int n, m;
char origin[maxn];
char target[maxn];
int bound;
int disc[maxn];
int disc2[maxn];

#define RunInstance(x) delete new x
struct cheat1
{
    std::vector<int> ans;
    void handle(int x)
    {
        if (!x) return;
        ans.push_back(x);
        static char temp[maxn];
        int t = 0;
        for (int i = n; i > n - x; i--)
            temp[++t] = origin[i];
        for (int i = 1; i <= n - x; i++)
            temp[++t] = origin[i];
        memcpy(origin + 1, temp + 1, sizeof(char) * t);
    }
    cheat1()
    {
        for (int i = 1; i <= n; i++)
        {
            char wanted = target[n - i + 1];
            int pos = i;
            while (origin[pos] != wanted)
                pos++;
            handle(n - pos + 1);
            handle(pos);
            handle(n - pos);
            handle(i);
        }
        printOut(ans.size());
        putchar('\n');
        for (int i = 0; i < ans.size(); i++)
        {
            printOut(ans[i]);
            putchar(' ');
        }
    }
};
struct cheat2
{
    std::vector<int> ans;
    void handle(int x)
    {
        if (!x) return;
        ans.push_back(x);
        static char temp[maxn];
        int t = 0;
        for (int i = n; i > n - x; i--)
            temp[++t] = origin[i];
        for (int i = 1; i <= n - x; i++)
            temp[++t] = origin[i];
        memcpy(origin + 1, temp + 1, sizeof(char) * t);
    }
    cheat2()
    {
        for (int i = 1; i <= n; i++)
        {
            char wanted = target[n - i + 1];
            int pos = i;
            while (origin[pos] != wanted)
                pos++;
            handle(n);
            handle(pos - 1);
            handle(1);
        }
        printOut(ans.size());
        putchar('\n');
        for (int i = 0; i < ans.size(); i++)
        {
            printOut(ans[i]);
            putchar(' ');
        }
    }
};

void run()
{
    n = readIn();
    scanf("%s%s", origin + 1, target + 1);
    for (int i = 1; i <= n; i++)
    {
        disc[++bound] = origin[i];
        disc2[bound] = target[i];
    }
    std::sort(disc + 1, disc + 1 + bound);
    std::sort(disc2 + 1, disc2 + 1 + bound);
    for (int i = 1; i <= bound; i++)
        if (disc[i] != disc2[i])
        {
            printOut(-1);
            return;
        }

    RunInstance(cheat2);
}

int main()
{
#ifdef LOCAL
    freopen("E.in", "r", stdin);
#endif
    run();
    return 0;
}

总结

1. 认真读题，逐字逐句翻译读题（说翻译好像没什么不对的），仔细理解题目的意思！
2. 构造题考虑从小到大逐步扩展，有点解决子问题的味道。