汉诺塔问题 X

怼烎@ 2023-07-05 13:18 16阅读 0赞

## 题目链接：[汉诺塔 问题 X][_ X]. ##

### 题目： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

### 分析： ###

与之前两题类似

#### [汉诺塔 问题 XIII][_ XIII]. ####

我们只需要找到当前步数下的状态，

还有当前步数前一步的状态，

检查一下两种状态的区别，就能知道结果了

### AC代码： ###

package Two;
    
    import java.util.*;
    
    public class 汉诺塔X {
    	public static ArrayList<Integer> arr1[]=new ArrayList[3];
    	public static ArrayList<Integer> arr2[]=new ArrayList[3];
    	public static int ans=-1;
    	public static void dfs(int n,long m,int from,int mid,int to,ArrayList<Integer> arr[]){
    		if(n<=0)return ;
    		if(m>=(long)(Math.pow(2, n-1)+0.000001)){
    			m-=(long)(Math.pow(2, n-1)+0.000001);
    			arr[to].add(n);
    			dfs(n-1,m,mid,from,to,arr);
    		}else{
    			arr[from].add(n);
    			dfs(n-1,m,from,to,mid,arr);
    		}
    	}
    	public static void main(String[] args) {
    		Scanner sc=new Scanner(System.in);
    		int t=sc.nextInt();
    		while(t-->0){
    			int n=sc.nextInt();
    			long m=sc.nextLong();
    			for(int i=0;i<3;i++){
    				arr1[i]=new ArrayList<Integer>();
    				arr2[i]=new ArrayList<Integer>();
    			}
    			dfs(n,m,0,1,2,arr2);
    			dfs(n,m-1,0,1,2,arr1);
    			int x=-1,y=-1,z=-1;
    			for(int i=0;i<3;i++){
    				if(arr1[i].size()>arr2[i].size()){
    					y=i;
    					y++;
    				}
    				else if(arr1[i].size()<arr2[i].size()){
    					z=i;
    					z++;
    					x=arr2[i].get(arr2[i].size()-1);
    				}
    			}
    			System.out.println(x+" "+y+" "+z);
    		}
    	}
    }

[_ X]: http://acm.hdu.edu.cn/showproblem.php?pid=2511
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200215114836213.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[_ XIII]: https://blog.csdn.net/qq_43652327/article/details/104324277