CF GYM 101196 G That’s One Hanoi-ed Teacher

That’s One Hanoi-ed Teacher

链接

题意：

　　询问一个汉诺塔的状态是否是最优的状态，如果是，询问还有多少步到最终状态。

分析：

　　考虑汉诺塔是怎么操作的，首先是考虑F(i)是有i个盘子，从一根柱子完全移到另一根柱子的花费。如果存在x个盘子，那么答案是F(x - 1)+1+F(x-1)，为前x-1盘子先从1移动到2，然后第x个盘子移动到3，然后x-1个盘子从2移到3。

　　所以对于一个状态，可以先找到最大的盘子x，如果在中间的话，无解。否则使用F(x-1)+1次操作，将它移动到应该在的位置，然后当前的状态又是一样的。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

LL ans = ;

bool dfs(int now,vector<int>& A, vector<int> &B, vector<int> &C) {

    if (!now) return ;

    if (A.size() && A[] == now) {

        ans += 1ll << (now - );

        A.erase(A.begin());

        return dfs(now - , A, C, B);

    }

    if (C.size() && C[] == now) {

        C.erase(C.begin());

        return dfs(now - , B, A, C);

    }

    return ;

}

vector<int> A, B, C;

int main() {

    int a = read();

    for (int i = ; i <= a; ++i) A.push_back(read());

    int b = read();

    for (int i = ; i <= b; ++i) B.push_back(read());

    int c = read();

    for (int i = ; i <= c; ++i) C.push_back(read());

    if (!dfs(a + b + c, A, B, C)) puts("No");

    else printf("%I64d\n", ans);

    return ;

}