{"id":342,"date":"2010-08-11T22:32:00","date_gmt":"2010-08-11T14:32:00","guid":{"rendered":"http:\/\/localhost\/?p=342"},"modified":"2010-08-11T22:32:00","modified_gmt":"2010-08-11T14:32:00","slug":"shoi2008_tower_of_hanoi","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=342","title":{"rendered":"[SHOI2008]\u6c49\u8bfa\u5854"},"content":{"rendered":"\n

[SHOI2008]\u6c49\u8bfa\u5854<\/p>\n

Time Limit:1000MS  Memory Limit:165536K
Total Submit:21 Accepted:15<\/p>\n

Description <\/strong><\/p>\n

\u6c49\u8bfa\u5854\u7531\u4e09\u6839\u67f1\u5b50\uff08\u5206\u522b\u7528A B C\u8868\u793a\uff09\u548cn\u4e2a\u5927\u5c0f\u4e92\u4e0d\u76f8\u540c\u7684\u7a7a\u5fc3\u76d8\u5b50\u7ec4\u6210\u3002\u4e00\u5f00\u59cbn\u4e2a\u76d8\u5b50\u90fd\u645e\u5728\u67f1\u5b50A\u4e0a\uff0c\u5927\u7684\u5728\u4e0b\u9762\uff0c\u5c0f\u7684\u5728\u4e0a\u9762\uff0c\u5f62\u6210\u4e86\u4e00\u4e2a\u5854\u72b6\u7684\u9525\u5f62\u4f53\u3002 <\/p>\n


\u5bf9\u6c49\u8bfa\u5854\u7684\u4e00\u6b21\u5408\u6cd5\u7684\u64cd\u4f5c\u662f\u6307\uff1a\u4ece\u4e00\u6839\u67f1\u5b50\u7684\u6700\u4e0a\u5c42\u62ff\u4e00\u4e2a\u76d8\u5b50\u653e\u5230\u53e6\u4e00\u6839\u67f1\u5b50\u7684\u6700\u4e0a\u5c42\uff0c\u540c\u65f6\u8981\u4fdd\u8bc1\u88ab\u79fb\u52a8\u7684\u76d8\u5b50\u4e00\u5b9a\u653e\u5728\u6bd4\u5b83\u66f4\u5927\u7684\u76d8\u5b50\u4e0a\u9762\uff08\u5982\u679c \u79fb\u52a8\u5230\u7a7a\u67f1\u5b50\u4e0a\u5c31\u4e0d\u9700\u8981\u6ee1\u8db3\u8fd9\u4e2a\u8981\u6c42\uff09\u3002\u6211\u4eec\u53ef\u4ee5\u7528\u4e24\u4e2a\u5b57\u6bcd\u6765\u63cf\u8ff0\u4e00\u6b21\u64cd\u4f5c\uff1a\u7b2c\u4e00\u4e2a\u5b57\u6bcd\u4ee3\u8868\u8d77\u59cb\u67f1\u5b50\uff0c\u7b2c\u4e8c\u4e2a\u5b57\u6bcd\u4ee3\u8868\u76ee\u6807\u67f1\u5b50\u3002\u4f8b\u5982\uff0cAB\u5c31\u662f\u628a\u67f1\u5b50A\u6700 \u4e0a\u9762\u7684\u90a3\u4e2a\u76d8\u5b50\u79fb\u5230\u67f1\u5b50B\u3002\u6c49\u8bfa\u5854\u7684\u6e38\u620f\u76ee\u6807\u662f\u5c06\u6240\u6709\u7684\u76d8\u5b50\u4ece\u67f1\u5b50A\u79fb\u52a8\u5230\u67f1\u5b50B\u6216\u67f1\u5b50C\u4e0a\u9762\u3002
\u6709\u4e00\u79cd\u975e\u5e38\u7b80\u6d01\u800c\u7ecf\u5178\u7684\u7b56\u7565\u53ef\u4ee5\u5e2e\u52a9\u6211\u4eec\u5b8c\u6210\u8fd9\u4e2a\u6e38\u620f\u3002\u9996\u5148\uff0c\u5728\u4efb\u4f55\u64cd\u4f5c\u6267\u884c\u4e4b\u524d\uff0c\u6211\u4eec\u4ee5\u4efb\u610f\u7684\u6b21\u5e8f\u4e3a\u516d\u79cd\u64cd\u4f5c\uff08AB\u3001AC\u3001BA\u3001BC\u3001CA\u548c CB\uff09\u8d4b\u4e88\u4e0d\u540c\u7684\u4f18\u5148\u7ea7\uff0c\u7136\u540e\uff0c\u6211\u4eec\u603b\u662f\u9009\u62e9\u7b26\u5408\u4ee5\u4e0b\u4e24\u4e2a\u6761\u4ef6\u7684\u64cd\u4f5c\u6765\u79fb\u52a8\u76d8\u5b50\uff0c\u76f4\u5230\u6240\u6709\u7684\u76d8\u5b50\u90fd\u4ece\u67f1\u5b50A\u79fb\u52a8\u5230\u53e6\u4e00\u6839\u67f1\u5b50\uff1a
\uff081\uff09\u8fd9\u79cd\u64cd\u4f5c\u662f\u6240\u6709\u5408\u6cd5\u64cd\u4f5c\u4e2d\u4f18\u5148\u7ea7\u6700\u9ad8\u7684\uff1b
\uff082\uff09\u8fd9\u79cd\u64cd\u4f5c\u6240\u8981\u79fb\u52a8\u7684\u76d8\u5b50\u4e0d\u662f\u4e0a\u4e00\u6b21\u64cd\u4f5c\u6240\u79fb\u52a8\u7684\u90a3\u4e2a\u76d8\u5b50\u3002
\u53ef\u4ee5\u8bc1\u660e\uff0c\u4e0a\u8ff0\u7b56\u7565\u4e00\u5b9a\u80fd\u5b8c\u6210\u6c49\u8bfa\u5854\u6e38\u620f\u3002\u73b0\u5728\u4f60\u7684\u4efb\u52a1\u5c31\u662f\u5047\u8bbe\u7ed9\u5b9a\u4e86\u6bcf\u79cd\u64cd\u4f5c\u7684\u4f18\u5148\u7ea7\uff0c\u8ba1\u7b97\u6309\u7167\u4e0a\u8ff0\u7b56\u7565\u64cd\u4f5c\u6c49\u8bfa\u5854\u79fb\u52a8\u6240\u9700\u8981\u7684\u6b65\u9aa4\u6570\u3002 <\/p>\n

Input <\/strong><\/p>\n

\u8f93\u5165\u6709\u4e24\u884c\u3002\u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6574\u6570n\uff081\u2264n\u226430\uff09\uff0c\u4ee3\u8868\u76d8\u5b50\u7684\u4e2a\u6570\u3002\u7b2c\u4e8c\u884c\u662f\u4e00\u4e32\u5927\u5199\u7684ABC\u5b57\u7b26\uff0c\u4ee3\u8868\u516d\u79cd\u64cd\u4f5c\u7684\u4f18\u5148\u7ea7\uff0c\u9760\u524d\u7684\u64cd\u4f5c\u5177\u6709\u8f83\u9ad8\u7684\u4f18\u5148\u7ea7\u3002 \u6bcf\u79cd\u64cd\u4f5c\u90fd\u7531\u4e00\u4e2a\u7a7a\u683c\u9694\u5f00\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u53ea\u9700\u8f93\u51fa\u4e00\u4e2a\u6570\uff0c\u8fd9\u4e2a\u6570\u8868\u793a\u79fb\u52a8\u7684\u6b21\u6570\u3002\u6211\u4eec\u4fdd\u8bc1\u7b54\u6848\u4e0d\u4f1a\u8d85\u8fc710\u768418\u6b21\u65b9\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n

3
AB BC CA BA CB AC<\/p>\n

Sample Output <\/strong><\/p>\n

7<\/p>\n

Source
\u8fd9\u9898\u5f88\u6709\u610f\u601d\u3002\u3002
\u9996\u5148\u5982\u679cn<=3\u7684\u8bdd\u53ef\u4ee5\u66b4\u529b\u6a21\u62df\u3002\u3002
\u7136\u540e\u53ef\u4ee5\u8bc1\u660e\u8fd9\u4e2a\u4e00\u5b9a\u6ee1\u8db3Fn=Fn-1*a+b
\u6240\u4ee5\u53ef\u4ee5\u7b97\u51faa\u548cb\u4e4b\u540e\u3002\u3002\u63a8\u51faFn\u3002
<\/strong><\/p>\n

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1;
using namespace std;
typedef long long ll;
int Moves[6][2],n;
void init()
{
cin>>n;
char a;
rep(i,6)
{
scanf(" ");
rep(j,2)cin>>a,Moves[i][j]=a-‘A’;
}
}
int Stupid_Cal(int n)
{
vector<int> Stack[3];
for(int i=n;i>=1;i–)Stack[0].pb(i);
int last=0;
for(int num=0;;)
{
if(Stack[1].size()==n||Stack[2].size()==n)
return num;
rep(i,6)
{
int from=Moves[i][0],to=Moves[i][1];
if(Stack[from].size()&&Stack[from].back()!=last)
if(Stack[to].size()==0||Stack[from].back()<Stack[to].back())
{
last=Stack[from].back();
Stack[from].pop_back();
Stack[to].pb(last);
num++;
break;
}
}
}
}
void Solve()
{
if(n<=3){cout<<Stupid_Cal(n)<<endl;return;}
int a2=Stupid_Cal(2),a3=Stupid_Cal(3);
int a=a3\/a2,b=a3-a*a2;
ll ans=a3;
for(int i=4;i<=n;i++)
ans=ans*a+b;
cout<<ans<<endl;
}
int main()
{
\/\/freopen("in","r",stdin);
init();
Solve();
}<\/p>\n","protected":false},"excerpt":{"rendered":"

[SHOI2008]\u6c49\u8bfa\u5854 Time Limit:1000MS  Memory Limit:165536KTotal Submit:21 Accepted:15 Description \u6c49\u8bfa\u5854\u7531\u4e09\u6839\u67f1\u5b50\uff08\u5206\u522b\u7528A B C\u8868\u793a\uff09\u548cn\u4e2a\u5927\u5c0f\u4e92\u4e0d\u76f8\u540c\u7684\u7a7a\u5fc3\u76d8\u5b50\u7ec4\u6210\u3002\u4e00\u5f00\u59cbn\u4e2a\u76d8\u5b50\u90fd\u645e\u5728\u67f1\u5b50A\u4e0a\uff0c\u5927\u7684\u5728\u4e0b\u9762\uff0c\u5c0f\u7684\u5728\u4e0a\u9762\uff0c\u5f62\u6210\u4e86\u4e00\u4e2a\u5854\u72b6\u7684\u9525\u5f62\u4f53\u3002 \u5bf9\u6c49\u8bfa\u5854\u7684\u4e00\u6b21\u5408\u6cd5\u7684\u64cd\u4f5c\u662f\u6307\uff1a\u4ece\u4e00\u6839\u67f1\u5b50\u7684\u6700\u4e0a\u5c42\u62ff\u4e00\u4e2a\u76d8\u5b50\u653e\u5230\u53e6\u4e00\u6839\u67f1\u5b50\u7684\u6700\u4e0a\u5c42\uff0c\u540c\u65f6\u8981\u4fdd\u8bc1\u88ab\u79fb\u52a8\u7684\u76d8\u5b50\u4e00\u5b9a\u653e\u5728\u6bd4\u5b83\u66f4\u5927\u7684\u76d8\u5b50\u4e0a\u9762\uff08\u5982\u679c \u79fb\u52a8\u5230\u7a7a\u67f1\u5b50\u4e0a\u5c31\u4e0d\u9700\u8981\u6ee1\u8db3\u8fd9\u4e2a\u8981\u6c42\uff09\u3002\u6211\u4eec\u53ef\u4ee5\u7528\u4e24\u4e2a\u5b57\u6bcd\u6765\u63cf\u8ff0\u4e00\u6b21\u64cd\u4f5c\uff1a\u7b2c\u4e00\u4e2a\u5b57\u6bcd\u4ee3\u8868\u8d77\u59cb\u67f1\u5b50\uff0c\u7b2c\u4e8c\u4e2a\u5b57\u6bcd\u4ee3\u8868\u76ee\u6807\u67f1\u5b50\u3002\u4f8b\u5982\uff0cAB\u5c31\u662f\u628a\u67f1\u5b50A\u6700 \u4e0a\u9762\u7684\u90a3\u4e2a\u76d8\u5b50\u79fb\u5230\u67f1\u5b50B\u3002\u6c49\u8bfa\u5854\u7684\u6e38\u620f\u76ee\u6807\u662f\u5c06\u6240\u6709\u7684\u76d8\u5b50\u4ece\u67f1\u5b50A\u79fb\u52a8\u5230\u67f1\u5b50B\u6216\u67f1\u5b50C\u4e0a\u9762\u3002 \u6709\u4e00\u79cd\u975e\u5e38\u7b80\u6d01\u800c\u7ecf\u5178\u7684\u7b56\u7565\u53ef\u4ee5\u5e2e\u52a9\u6211\u4eec\u5b8c\u6210\u8fd9\u4e2a\u6e38\u620f\u3002\u9996\u5148\uff0c\u5728\u4efb\u4f55\u64cd\u4f5c\u6267\u884c\u4e4b\u524d\uff0c\u6211\u4eec\u4ee5\u4efb\u610f\u7684\u6b21\u5e8f\u4e3a\u516d\u79cd\u64cd\u4f5c\uff08AB\u3001AC\u3001BA\u3001BC\u3001CA\u548c CB\uff09\u8d4b\u4e88\u4e0d\u540c\u7684\u4f18\u5148\u7ea7\uff0c\u7136\u540e\uff0c\u6211\u4eec\u603b\u662f\u9009\u62e9\u7b26\u5408\u4ee5\u4e0b\u4e24\u4e2a\u6761\u4ef6\u7684\u64cd\u4f5c\u6765\u79fb\u52a8\u76d8\u5b50\uff0c\u76f4\u5230\u6240\u6709\u7684\u76d8\u5b50\u90fd\u4ece\u67f1\u5b50A\u79fb\u52a8\u5230\u53e6\u4e00\u6839\u67f1\u5b50\uff1a \uff081\uff09\u8fd9\u79cd\u64cd\u4f5c\u662f\u6240\u6709\u5408\u6cd5\u64cd\u4f5c\u4e2d\u4f18\u5148\u7ea7\u6700\u9ad8\u7684\uff1b \uff082\uff09\u8fd9\u79cd\u64cd\u4f5c\u6240\u8981\u79fb\u52a8\u7684\u76d8\u5b50\u4e0d\u662f\u4e0a\u4e00\u6b21\u64cd\u4f5c\u6240\u79fb\u52a8\u7684\u90a3\u4e2a\u76d8\u5b50\u3002 \u53ef\u4ee5\u8bc1\u660e\uff0c\u4e0a\u8ff0\u7b56\u7565\u4e00\u5b9a\u80fd\u5b8c\u6210\u6c49\u8bfa\u5854\u6e38\u620f\u3002\u73b0\u5728\u4f60\u7684\u4efb\u52a1\u5c31\u662f\u5047\u8bbe\u7ed9\u5b9a\u4e86\u6bcf\u79cd\u64cd\u4f5c\u7684\u4f18\u5148\u7ea7\uff0c\u8ba1\u7b97\u6309\u7167\u4e0a\u8ff0\u7b56\u7565\u64cd\u4f5c\u6c49\u8bfa\u5854\u79fb\u52a8\u6240\u9700\u8981\u7684\u6b65\u9aa4\u6570\u3002 Input \u8f93\u5165\u6709\u4e24\u884c\u3002\u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6574\u6570n\uff081\u2264n\u226430\uff09\uff0c\u4ee3\u8868\u76d8\u5b50\u7684\u4e2a\u6570\u3002\u7b2c\u4e8c\u884c\u662f\u4e00\u4e32\u5927\u5199\u7684ABC\u5b57\u7b26\uff0c\u4ee3\u8868\u516d\u79cd\u64cd\u4f5c\u7684\u4f18\u5148\u7ea7\uff0c\u9760\u524d\u7684\u64cd\u4f5c\u5177\u6709\u8f83\u9ad8\u7684\u4f18\u5148\u7ea7\u3002 \u6bcf\u79cd\u64cd\u4f5c\u90fd\u7531\u4e00\u4e2a\u7a7a\u683c\u9694\u5f00\u3002 Output \u53ea\u9700\u8f93\u51fa\u4e00\u4e2a\u6570\uff0c\u8fd9\u4e2a\u6570\u8868\u793a\u79fb\u52a8\u7684\u6b21\u6570\u3002\u6211\u4eec\u4fdd\u8bc1\u7b54\u6848\u4e0d\u4f1a\u8d85\u8fc710\u768418\u6b21\u65b9\u3002 Sample Input 3AB BC CA BA CB AC Sample Output 7 Source\u8fd9\u9898\u5f88\u6709\u610f\u601d\u3002\u3002\u9996\u5148\u5982\u679cn<=3\u7684\u8bdd\u53ef\u4ee5\u66b4\u529b\u6a21\u62df\u3002\u3002\u7136\u540e\u53ef\u4ee5\u8bc1\u660e\u8fd9\u4e2a\u4e00\u5b9a\u6ee1\u8db3Fn=Fn-1*a+b\u6240\u4ee5\u53ef\u4ee5\u7b97\u51faa\u548cb\u4e4b\u540e\u3002\u3002\u63a8\u51faFn\u3002 #include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <set>#include <map>#include <cstring>#include <time.h>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define Debug(x) cout<<#x<<"="<<x<<endl;#define […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/342"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=342"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/342\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}