一维

翻硬币 AcWing 1208

思路 ： 每次只能翻相邻的两个硬币，给定目标状态，那么第一枚硬币翻或不翻是确定的。第一枚确定后，第二枚也确定了，最后与目标状态比较一下最后一位是否一样即可。

#include<iostream>
using namespace std;
string a, b;
int res;
void turn(int i)
{
    if(a[i] == '*')a[i] = 'o';
    else a[i] = '*';
}
int main()
{
    cin >> a >> b;
    for(int i = 0 ; i < a.size() - 1 ; i ++ )
        if(a[i] != b[i])
        {
            turn(i);
            turn(i + 1);
            res ++;
        }
    cout << res << endl;
}

二维

费解的开关 Acwing 95

思路：确定一个行灯泡的按法，通过下一行的按或不按将上一行的灯泡全部变成亮着，最后判断最后一行是否是全亮即可。
用二进制来枚举第一行灯泡的按法，这里假定第x位为1时，按下开关。为0时，保持原先状态不动。

#include<iostream>
#include<cstring>
using namespace std;
char g[5][5],bd[5][5];
int dx[5] = {1,0,-1,0,0}, dy[5] = {0,1,0,-1,0};
int T;
void turn(int a, int b)
{
    for(int i = 0 ; i < 5 ; i ++ )
    {
        int x = a + dx[i] , y = b + dy[i];
        if(x >= 0 && x < 5 && y >= 0 && y < 5)
            bd[x][y] ^= 1;
    }
}
int main()
{
    cin >> T;
    while(T --)
    {
        for(int i = 0 ; i< 5 ; i ++ )
            for(int j = 0 ; j < 5 ; j ++ )
                cin >> g[i][j];
        int res = 10;
        for(int i = 0 ; i <32 ; i ++)
        {
            memcpy(bd, g, sizeof bd);
            int cnt = 0;
            for(int j = 0; j < 5 ; j ++)
                if(i >> j & 1)
                {
                    cnt ++;
                    turn(0, j);
                }
            for(int i = 1 ; i < 5 ; i ++)
                for(int j = 0 ; j < 5 ; j ++)
                    if(bd[i - 1][j] == '0')
                    {
                        turn(i, j);
                        cnt ++;
                    }
            for(int j = 0 ; j < 5 ; j ++ )
                if(bd[4][j] == '0')
                    cnt = 10;

            res = min(res , cnt);
        }
        if(res <= 6)
            cout << res << endl;
        else cout << -1 << endl;
    }
    return 0;
}

打表、分类讨论

派对的灯 AcWing 1367
思路：每种开关按两次相当于没按，有四种开关，所以无论按了几次都可以等价于4次之内的操作。又有按12等价于3，13等价于2，23等价于1.所以无论按了几次都可以等价于2次及2次之内的操作。通过模拟把按0，1，2次的方案都写出来，按3，4次，则可以全按出来。3=5=7…,4=6=8…所以分类讨论即可。另外，所有的灯都是6个一循环，即第i个和第i+6k个灯的状态是一样的。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<int> on, off;
int n, c;
int state[8][6] = {
    {1,1,1,1,1,1},
    {0,0,0,0,0,0},
    {0,1,0,1,0,1},
    {1,0,1,0,1,0},
    {0,1,1,0,1,1},
    {1,0,0,1,0,0},
    {1,1,0,0,0,1},
    {0,0,1,1,1,0}
};

bool check(int s[6])
{
    for(auto item : on)
        if(!s[item % 6])
            return false;
    for(auto item : off)
        if(s[item % 6])
            return false;
    return true;
}
bool cmp(int a, int b)
{
    for(int i = 0 ; i < 6 ; i ++)
        if(state[a][i] != state[b][i])
            return state[a][i] < state[b][i];
}
void work(vector<int> ids)
{
    sort(ids.begin(),ids.end(),cmp);
    bool flag = true;
    for(auto item : ids)
    {
        if(check(state[item]))
        {
            flag = false;
            for(int i = 0 ; i < n ; i ++ )
                cout << state[item][i % 6];
            cout << endl;
        }
    }
    if(flag)cout << "IMPOSSIBLE" << endl;
}
int main()
{
    cin >> n >> c;
    int id;
    while(cin >> id, ~id)on.push_back(id - 1);
    while(cin >> id, ~id)off.push_back(id - 1);
    if(!c)work({0});
    else if(c == 1)work({1,2,3,4});
    else if(c == 2)work({0,1,2,3,5,6,7});
    else work({0,1,2,3,4,5,6,7});
}