[ARC177B] Puzzle of Lamps

思路

首先可以发现这题并没有限制最少操作步骤，于是逆序遍历序列，若要将位置 $i$ 的数字变成 $1$ (下标从 $0$ 开始)，则先执行 $i+1$ 次操作 $A$，再执行 $i$ 次操作 $B$，这样可以保证只将位置 $i$ 的数字变成 $1$。由于是逆序遍历，所以不会影响后面的数字。

代码

#include <bits/stdc++.h>
using namespace std;
int cnt,n;
string s,res;
signed main() {
	cin>>n>>s;
	for(int i=s.length()-1;i>=0;i--)
		if(s[i]=='1'){
			cnt+=2*i+1;
			for(int j=1;j<=i+1;j++) res=res+"A";
			for(int j=1;j<=i;j++) res=res+"B";
		}
	cout<<cnt<<endl<<res;
	return 0; 
}