36 条题解
-
4zone LV 10 @ 2016-07-29 14:33:37
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int n,step=0; int a[50]; bool ok=1; void mov(int n,int from,int to,int temp) { if(!ok || n<=0) return; if(a[n]==from) { mov(n-1,from,temp,to); } else if(a[n]==to) { step+=pow(2,n-1); mov(n-1,temp,to,from); } else if(a[n]==temp) { ok=0; return; } //cout<<n<<" "<<from<<" "<<to<<endl; } int main() { ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; mov(n,1,2,3); if(ok) cout<<step; else cout<<"-1"; return 0; }
-
12009-04-06 21:42:14@
首先地球人都知道n个盘子问题的移动数是2的n次方-1。
先来看3个盘的时候(题目上面有)。
我们发现第3个盘只移动了一次(从1到2),因此如果发现它在3号柱上直接输出-1。
方案是:
1-2盘开始在1号柱上,把1-2盘移到3号柱上。
把3盘移到2号柱。
1-2盘开始在3号柱上,把1-2盘移到2号柱上。
我们发现,3盘的位置决定了1-2盘开始在什么地方,和要去哪里!!
如果3盘在1,那么解数不变,而1-2盘开始在1号柱,要去3号柱(子问题)
如果3盘在2,那么说明1-2已经到3号柱上去了(ans相应增加),而现在1-2盘需要从3号柱到2号柱(又是一个子问题)
至此,我们已经成功的转化出了子问题。
Dfs(n,st,ed)表示前n个盘,需要从st号柱到ed柱去,然后根据盘n的状态可以转化出子问题。procedure dfs(k,a,b:longint);
begin
if k=0 then exit;
if s[k]=b then
begin
m:=m+two[k-1];
dfs(k-1,6-a-b,b);
end else
if s[k]=a then dfs(k-1,a,6-a-b)
else
begin
writeln(-1);
halt;
end;
end; -
02018-07-28 16:25:29@
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long #define pos(x,y) (x+(y)*n) const int N=100000+10; const int inf=0x3f3f3f3f; const ll mod=7777777; const double eps=1e-8; int n; int f[35]; int a[40]; ll hanoi(int n) { if (n<=0) return 0; if (f[n]) return f[n]; ll res=0; res+=hanoi(n-1); ++res; res+=hanoi(n-1); f[n]=res; return res; } ll work(int n,int from,int to,int temp) { if (n<=0) return 0; if (a[n]==temp) { cout<<-1<<endl; exit(0); } if (a[n]==from) { return work(n-1,from,temp,to); } ll res=0; res+=f[n-1]+1; if (a[n]==to) { bool flag=1; FOR(i,n-1) if (a[i]!=temp) { flag=0; break; } if (flag) { return res; } } return res+work(n-1,temp,to,from); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n; FOR(i,n) cin>>a[i]; hanoi(n); cout<<work(n,1,2,3)<<endl; return 0; }
-
02015-04-19 11:58:59@
var n,x,y,z,i:longint; //x起点柱 y终点柱 z中转柱
a:array[1..31] of longint;
ans:int64;
begin
readln(n);
for i:=1 to n do read(a[i]);
readln;
ans:=0;
x:=1;
y:=2;
z:=3;
for i:=n downto 1 do begin
if a[i]=z then begin
writeln(-1);
exit;
end;
if a[i]=x then begin
y:=z;
z:=6-x-y;
end else begin
ans:=ans+1 shl(i-1);
x:=z;
z:=6-x-y;
end;
end;
writeln(ans);
end. -
02009-02-20 12:59:24@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msvar
n,i:integer;
p:array[1..31]of integer;
f:array[1..31]of qword;
ans:qword;
procedure work(k,a,b,c:integer);
begin
if p[k]=c then
begin writeln(-1);halt;end;
if k=1 then
begin if p[k]=b then inc(ans);end
else
if p[k]=a then work(k-1,a,c,b)
else begin
inc(ans,f[k-1]+1);
work(k-1,c,b,a);
end;
end;begin
readln(n);
for i:=1 to n do read(p[i]);
f[1]:=2;
for i:=2 to n do
begin
f[i]:=f*2;
dec(f);
end; //f[i]=2^i-1
work(n,1,2,3);
writeln(ans);
end.12:58 2009-2-20
-
02008-10-25 12:11:27@
推..
-
02008-10-20 13:04:55@
lx两人均正解...
-
02008-10-06 22:41:28@
多谢fammiebright牛写的题解,
让我2次AC,
第一次O(2^n)
第二次O(n)(或者大些?O(n^2)?)
天壤之别啊!
对于每一个a[n],
等于to_就加上2^(n-1),
执行后半步;
等于from就直接执行前半步;
等于temp直接输-1;
题目中的代码今天才弄懂,不易啊~ -
02008-09-12 13:11:47@
正如题目所给的那个hanoi代码,递归每一次都分“前半步” (hanoi(n-1,from,temp,to_));和“后半步” (hanoi(n-1,temp,to_,from))。这样有了一个状态,就可以判断它处在“前半步”还是“后半步”,再作出相应的递归。
(供大牛们BS)http://dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!343.entry
-
02008-09-11 23:48:59@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms没发现还有个-1的问题,害我找了n次错。。。
-
02007-11-11 11:10:48@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
看错了
以为要把所有的盘移到3号柱子
结果是2号
wa了N次 -
02007-11-08 19:28:35@
没看见-1,Wa了N次..
-
02007-07-31 22:35:01@
O(3 * n)......
找规律......
开始没用int64,结果90分.....
WA了一个点...... -
02007-07-24 14:37:02@
终于通过一百人以下的题了!
gf-sky,gf-fly,gf-star,gbf,ttt -
02007-06-28 13:59:09@
递归.
时间复杂度为O(n) -
02007-03-27 17:40:41@
超级郁闷,一开始只开到31,结果WA掉2个点....
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02006-10-28 19:20:59@
跟1084比较类似,只是不需要高精度。。。
-
02006-05-24 20:44:27@
我的方法。。。
O(n)。。。N=31。。。。
所以,结果是。。。常数时间。。 -
02006-03-13 23:03:09@
用了一个极其猥琐的枚举判断无解的方法过了
总体思想是二分 -
02006-03-24 20:17:16@
规定要求不能贴出任何有关于此题的程序代码
ft还是删了吧