【AcWing】递推（就是那种很棘手的题）

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
char start[N], aim[N];
void turn(int i)
{
    if (start[i] == '*') start[i] = 'o';
    else start[i] = '*';
}
int main()
{
    cin >> start >> aim;
    n = strlen(start);
    int res = 0;
    for (int i = 0; i < n - 1; i ++ )
        if (start[i] != aim[i])
        {
            turn(i);//反转
            turn(i + 1);
            res ++ ;
        }
    cout << res << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n;
string str;
void update(char& c)//引用
{
    if (c == 'W') c = 'B';//更换颜色
    else c = 'W';
}
bool check(char c)
{
    vector<int> res;
    string s = str;
    for (int i = 0; i + 1 < n; i ++ )
    {
        if (s[i] != c)
        {
            update(s[i]);
            update(s[i + 1]);
            res.push_back(i);//存下这个操作，因为下面要输出
        }
    }
    if (s.back() != c) return false;//就是没有全部变为一个颜色
    cout << res.size() << endl;
    for (int x: res) cout << x + 1 << ' ';//因为题目中的下标从1开始
    if (res.size()) cout << endl;
    return true;
}
int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n >> str;
        if (!check('B') && !check('W')) puts("-1");
        //判断能不能全部变为一个颜色
        //注意，check的返回类型为bool类型
    }
    return 0;
}

#include<iostream>
using namespace std;
const int maxn=101;
bool a[maxn];//a数组负责存储硬币的状态
int n;//n枚硬币
int main()
{
    cin>>n;
    cout<<n<<endl;//因为相当于只翻一枚，所以翻n次即可
    for(int i=1;i<=n;i++){//i表示这是第几次翻
        for(int j=1;j<=n;j++){//表示当前翻得是第几枚硬币
            if(j!=i){//如果不为第i枚（因为翻的是n-1枚）
                if(a[j])a[j]=0;//1变成0
                else a[j]=1;//0变成1
            }
            cout<<a[j];//输出当前状态
        }
        cout<<endl;//别忘了换行
    }
    return 0;
}