http://acm.hdu.edu.cn/showproblem.php?pid=1525
1 //題意: 給定n,m兩個數，兩個人輪流操作:
2 //選m,n小的數，每次都是大的減去小的數的k倍,k<=max(n,m)/min(n,m);
3 //知道其中一個為0時，執行該操作的為勝者
4
5 //Analyse:for example: if n>m,then n=m*k+c(k<=n/m,c=n%m)
6 //if k>1,then the first player can decide who'll win.if current statue is lost,he can decrease (k-1)*m,
7 //the statue is changed to (m+c,m),the second player only operate m,so the statue is changed to (m,c) which
8 //is the winning statue. if current is the winning statue,he can decrease k*m,the statue is changed to (m,c)
9 //which is the lost statue.So if k>1,the one who operate it is the winner,he is active.but if k==1,he can only
10 //operate the small one.the one who first meet k>1 is the winner.specially,if no one meet k>1,the player operate
11 //it in turn,the first makes the n or m to zero is the winner.
12 #include <iostream>
13
14 using namespace std;
15 int main()
16 {
17 int n,m;
18 while(cin>>n>>m,n+m){
19 int cnt=0;
20 int ans=0;
21 while(1){
22 if(n<m)swap(n,m);
23 ans=n/m;
24 if(ans>=2){
25 break;
26 }
27 cnt++;
28 n%=m;
29 if(n==0){
30 cnt++;
31 break;
32 }
33 }
34 if(cnt&1){
35 cout<<"Ollie wins\n";
36 }
37 else cout<<"Stan wins\n";
38 }
39 return 0;
40 }
posted @
2008-07-23 18:55 小果子 閱讀(263) |
評論 (0) |
編輯 收藏
摘要: 下面的代碼（比較垃圾）在vs2008下有運行錯誤...我找了很久，終于找到錯誤...不過不知道什么地方有問題...
1 #include <iostream> 2 #include <queue> 3 4 using&nb...
閱讀全文
posted @
2008-07-22 19:18 小果子 閱讀(131) |
評論 (0) |
編輯 收藏
RT...
posted @
2008-07-21 21:51 小果子 閱讀(96) |
評論 (0) |
編輯 收藏 http://acm.hdu.edu.cn/showproblem.php?pid=1010
1 //////////////////////////////////////////////////////////////////////////////////
2 //以前寫的1010是參考別人的,今天把它寫了下(省賽題）,
3 //過程相當艱難，忘了road=0,以至于少了一個剪枝,TLE,調試了
4 //N久，沒發現，以至于去優化dfs過程，最后發現，把第一次交
5 //的改了后就過了，不過比未優化時慢了100ms左右不過還是
6 //比較開心的，雖然囧
7 /////////////////////////////////////////////////////////////////////////////////
8 #include <iostream>
9
10 using namespace std;
11 const int N=8;
12 const int M=8;
13 char mp[N][M];
14 int dir[4][2]={1,0,-1,0,0,-1,0,1};
15 int n,m,t,road;
16 struct Node
17 {
18 int xi,yi;
19 int time;
20 Node(int x=0,int y=0,int t=0):xi(x),yi(y),time(t){};
21 }start,end;
22 int gf;
23 inline void Input()
24 {
25 road=0;
26 gf=0;
27 for(int i=0;i<n;i++){
28 for(int j=0;j<m;j++){
29 cin>>mp[i][j];
30 if(mp[i][j]=='S'){
31 start.xi=i;
32 start.yi=j;
33 mp[i][j]='X';
34 }
35 if(mp[i][j]=='D'){
36 end.xi=i;
37 end.yi=j;
38 }
39 if(mp[i][j]=='.')
40 ++road;
41 }
42 }
43 }
44 inline bool optimize(const Node& a,const Node& b,const int ti)
45 {
46 if(((a.xi+a.yi+b.xi+b.yi)&1) != (ti&1) )return false;
47 if(abs(a.xi-b.xi)+abs(a.yi-b.yi)>ti)
48 return false;
49 return true;
50 }
51 int dfs(Node const& c,int ti)
52 {
53 if(gf)return 1;
54 Node ans;
55 --ti;
56 for(int i=0;i<4;i++){
57 ans.xi=c.xi+dir[i][0];
58 ans.yi=c.yi+dir[i][1];
59 ans.time=c.time+1;
60 if(ans.time>t)continue;
61 if(ans.xi==end.xi && ans.yi==end.yi && ans.time == t){
62 gf=1;
63 return 1;
64 }
65 if(mp[ans.xi][ans.yi]=='D')continue;
66 if(ans.xi<0||ans.yi<0||ans.xi>=n||ans.yi>=m)
67 continue;
68 if(mp[ans.xi][ans.yi]=='X')
69 continue;
70 mp[ans.xi][ans.yi]='X';
71 if(optimize(ans,end,ti))
72 dfs(ans,ti);
73 if(gf)return 1;
74 mp[ans.xi][ans.yi]='.';
75 }
76 return 0;
77 }
78 int main()
79 {
80 while(cin>>n>>m>>t,n+m+t){
81 Input();
82 if(road+1<t){
83 cout<<"NO\n";
84 }
85 else if(optimize(start,end,t)){
86 if(dfs(start,t))
87 cout<<"YES\n";
88 else cout<<"NO\n";
89 }
90 else cout<<"NO\n";
91 }
92 return 0;
93 }
posted @
2008-07-21 15:59 小果子 閱讀(1148) |
評論 (0) |
編輯 收藏 1 //重新寫了下hdu1253,以前沒剪枝的全部TLE掉了，加了幾個小剪枝就過了.
2 //所以還是有點啟發的http://acm.hdu.edu.cn/showproblem.php?pid=1253
3 #include <iostream>
4 #include <queue>
5
6 using namespace std;
7 const int N=51;
8 const int M=51;
9 const int R=51;
10 int mp[N][M][R];
11 bool mark[N][M][R];
12 int A,B,C,T,Road;
13 int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
14 struct Node
15 {
16 int xi,yi,zi;
17 int time;
18 Node(int x=0,int y=0,int z=0,int t=0):xi(x),yi(y),zi(z),time(t){
19 };
20 bool operator==(const Node& c)const{
21 if(xi == c.xi && yi == c.yi && zi == c.zi)return true;
22 return false;
23 };
24 };
25 inline void Input()
26 {
27 //cin>>A>>B>>C>>T;
28 Road=0;
29 scanf("%d%d%d%d",&A,&B,&C,&T);
30 for(int i=0;i<A;i++)
31 for(int j=0;j<B;j++)
32 for(int r=0;r<C;r++){
33 scanf("%d",&mp[i][j][r]);
34 if(mp[i][j][r]==0)
35 ++Road;
36 }
37 }
38 inline int BFS()
39 {
40 queue<Node> que;
41 Node start(0,0,0),end(A-1,B-1,C-1);
42 que.push(start);
43 memset(mark,0,sizeof(mark));
44 mark[0][0][0]=true;
45 Node ans;
46 while(!que.empty()){
47 Node tmp=que.front();
48 que.pop();
49 for(int i=0;i<6;i++){
50 ans.xi=tmp.xi+dir[i][0];
51 ans.yi=tmp.yi+dir[i][1];
52 ans.zi=tmp.zi+dir[i][2];
53 ans.time=tmp.time+1;
54 if(ans==end){
55 return ans.time>T?-1:ans.time;
56 }
57 if(ans.time>=T+1)return -1;
58 if(ans.xi<0||ans.yi<0||ans.zi<0||ans.xi>=A||ans.yi>=B||ans.zi>=C)continue;
59 if(mp[ans.xi][ans.yi][ans.zi]==1)continue;
60 if(mark[ans.xi][ans.yi][ans.zi])continue;
61 que.push(ans);
62 mark[ans.xi][ans.yi][ans.zi]=true;
63 }
64 }
65 return -1;
66 }
67 int main()
68 {
69 int c;
70 scanf("%d",&c);
71 while(c--){
72 Input();
73 if(mp[A-1][B-1][C-1] == 1 || A+B+C > T || A+B+C>Road )printf("-1\n");//剪枝
74 else printf("%d\n",BFS());
75 }
76 return 0;
77 }
posted @
2008-07-21 13:31 小果子 閱讀(372) |
評論 (0) |
編輯 收藏