题目描述

汉诺塔。给出初始第 i 小的圆盘在哪根柱子上，回答将所有圆盘放到第三根柱子上的最少操作次数。

输入格式

第一行一个正整数 n ，表示圆盘的个数。

接下来一行 n 个正整数 a1,a2,…,an ，表示所有圆盘初始在哪根柱子上。初始每根柱子上的所有圆盘都是按照小的在大的上面的顺序排列的。

输出格式

一行一个二进制整数，表示最小的操作次数。

看到了神仙写的代码如下，但是完全不懂用异或切换目标柱子那里与这样的答案为什么正确QAQ，有没有人能解释一下。

bdfs无果，全是递归写法。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n,a[maxn];
int main(){
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
	}
	int l = 3,fl = 0;
	for(int i = n;i;i--){
		int x = a[i]!=l;
		fl|=x;
		if(fl)cout<<x;//为什么是这个答案
		if(x)l^=a[i];//不懂为什么这样切换
	}if(!fl)cout<<0;
}