[luogu4285 SHOI2008] 汉诺塔 (暴力，数学)

Solution

强行猜测公式形如\(f_i=k\times f_{i-1}+b\)，暴力求\(f_1,f_2,f_3\)，剩下的递推就行

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

inline int read() {

	int x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

const int N=40;

int n;

long long f[N],top[4],t[4][N];

char ch[3];

struct M{int fr,to;}mv[10];

int get(int x) {

	F(i,1,x) t[1][i]=x-i+1;

	top[1]=x;top[2]=top[3]=0;

	int res=0,las=0;

	while(1) {

		if(top[2]==x||top[3]==x) return res;

		F(i,1,6) {

			int u=mv[i].fr,v=mv[i].to;

			if(u==las||!top[u]||(t[u][top[u]]>t[v][top[v]]&&top[v])) continue;

			t[v][++top[v]]=t[u][top[u]];

			t[u][top[u]--]=0;las=v;

			res++;break;

		}

	}

}

int main() {

	n=read();

	F(i,1,6) scanf("%s",ch+1),mv[i].fr=ch[1]-'A'+1,mv[i].to=ch[2]-'A'+1;

	f[1]=get(1);f[2]=get(2);f[3]=get(3);

	int k=(f[3]-f[2])/(f[2]-f[1]),b=f[3]-f[2]*k;

	F(i,4,n) f[i]=k*f[i-1]+b;

	printf("%lld",f[n]);

	return 0;

}

巴特西

[luogu4285 SHOI2008] 汉诺塔 (暴力，数学)

Solution

Code

最新文章

热门文章