递推、meset()、memcpy() 的使用

(数组名，值，数组大小)

meset(backup，0，sizeof backup)；

作用：把 backup 的每一个字节都变成 0

C++中memset()用法_awenwenwem的博客-CSDN博客_c++ memset

(第一个数组，第二个数组，长度)

memcpy(backup，st，sizeof st)；

作用：把从 st 开始的，长度是 sizeof st 的一段复制给第一个数组 backup（就是把 st 的内容复制到 backup）

C++之memcpy的用法_浩海烟云的博客-CSDN博客_c++ memcpy

递归就是把某个问题分解成若干个同种子问题，递推就是反过过来，先求子问题，然后用子问题把原问题直接计算出来

递归：

先想 f( n ) 怎么做？

f( n ) = f( n - 1 ) + f( n - 2 )，如果定义一个函数 f( n )，可以返回斐波那契数列第 n 项的话，只需要调用一下两个子问题就可以了

递推：

先算 f( n - 1)、f( n -  2 )，再算 f( n )，从 1 ~ n 开始一项一项计算就可以了

用数组来存储，数组的第 n 项就是 f( n )，然后从前往后递推一遍就可以了

#include 
#include 
#include 

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    //定义一个数组 最多 46 项
    int f[46];
    //第一项 第二项
    f[1] = 0,f[2] = 1;
    //从第 3 项开始,每一项都是前两项的和
    for(int i = 3;i <= n;i++ ) f[i] = f[i - 1] + f[i - 2];
    //最后把每一项输出
    for(int i = 1;i <= n;i++) cout << f[i] << ' ';
    return 0;
}

优化：由于每一项只与前两项有关，可以节省空间，不开数组，开变量就可以了，每次只记录前两项是多少

滚动数组的雏形：动态规划DP_小雪菜本菜的博客-CSDN博客

#include 
#include 
#include 

using namespace std;

int main()
{
    int n;
    cin >> n;
    //a是第一项 b是第二项
    int a = 0,b = 1;

    for(int i = 1;i <= n;i++ )
    {
       cout << a << ' ';
       int fn = a + b;
       a = b,b = fn;
    }
    return 0;
}

有一个 5 × 5 的开关阵列，25 盏灯组成一个正方形，每一个灯有一个开关，开关按一下就会改变状态，如果是关的，摁一下就变成开；’如果是开的，摁一下就变成关，开关具有连锁反应，每次都是十字形的变化

看一下样例 2

给出一个初始状态，问最少需要多少步可以把它变成全亮？

如果超出 6 步，就输出 -1

第一行的所有状态通过枚举的方式来选，第一行的所有状态只有 2 种选择，每一个开关有按和不按两种情况，第一行总共的方案数量是 2^n，也就是 2^5 种不同的摁法，一共有 32 种不同的状态（一共有 5 个数，每个数有摁和不摁两种情况）

假设我们已经枚举完第一行的状态了，而且已经把第一行操作完了，接下来再操作的时候，不能再操作第一行的格子了

①每一个格子最多只能摁一次，如果摁两次，相当于没有摁，还因此多了两步

②顺序可以任意，摁法和顺序没有关系，每个灯的状态取决于十字形的格子一共被摁了几次，摁奇数次就变化，摁偶数次就不变，只与次数有关

第一行所有格子的操作固定之后，接下来在操作的时候，不能再操作第一行的格子，只能从第二行开始操作，如果第一行还有暗的格子，由于不能再按第一行的格子，所以能够改变第一行暗的格子的开关只有第二行与之对应的格子，如果第一行的格子是暗着的，第二行这个格子必须得摁下；同理，如果第一行的格子是亮着的，那么下面这个格子就必须不能按

第二行的摁法是唯一确定的，只需要看上面一行当前的状态是什么就可以了

最后一行开关的操作，会被前一行灯的状态决定，此时就意味着所有开关的操作都已经被确定了

只要第一行的操作固定之后，第二行的操作一定是被第一行当前灯的亮灭状态所唯一确定，此时前两行已经操作完成，前两行不能再操作了，对于第二行的每个状态来说，如果上面是暗的，第三行对应位置就必须摁下；如果上面是亮的，下面就不能摁（因此第三行必须得全部摁下，由于第二行全部是暗的），对于第三行的开关是否摁下，也是完全取决于第二行

每操作完一行，其实只能保证前面所有行都变成亮的，操作完最后一行后，只能保证前 n - 1 行都变成亮的，此时最后一行的状态不一定全亮，最后判断最后一行的灯此时有没有灭的，如果有灭就说明方案不合法，如果没有灭着的，就说明方案 ok，更新最小步数即可

最后一行的状态不能改变，所有行的操作唯一确定，最后一行如果有灭的灯也没有办法

第一行的操作固定之后就直接决定了整个棋盘的操作

数据范围：5 × 5

如何枚举第一行的操作？指数类型枚举：递推和递归_小雪菜本菜的博客-CSDN博客

第一行的操作有 5 位 0 或者 1

位运算的技巧：1 表示操作，0表示不操作

每一个操作都可以看成一个二进制的数，把这个二进制的数转换成十进制的数是多少呢？

每一次操作都可以对应一个十进制的数，反过来任何一个从 0 ~ 2^5  - 1 之间的一个十进制的数都可以对应一个操作( 对应 5 位的 0、1 串 )，0 ~ 31 就可以分别代表这 32 种方案中的每一个

接下来看某一位是不是应该操作，就看一下 i 的二进制的某一位是不是 1 就可以了

怎么看 i 的二进制表示从低位往高位数的第 k 位是不是 1？

双指针算法、位运算、离散化、区间合并_小雪菜本菜的博客-CSDN博客

看 11010 的第 1 位是不是 1？

>> 一位相当于把这个数移到个位，& 1 相当于取出个位数字

想看第 k 位是不是 1，就先把第 k 位移到个位，然后把最低位取出来

如何进行操作？

把第 x 行第 y 列的开关按一下

可以定义偏移量，只需要存储上、下、左、右、中 5 个位置的偏移量，最后枚举偏移量，再加上偏移量就可以得到这 5 个格子

时间复杂度：第一行的状态有 32 种情况（第一行的状态确定之后，第一行会推出后面每一个开关的状态） ×  后面每一个开关的情况：除了第一行之外大概 25 个格子 × 每个开关最多有 5 个格子摁或者不摁 × 500个测试数据 = 200w

改变状态的技巧：

把字符类型的 ' 0 '  变成字符类型的 ' 1 '，然后把字符类型的 ' 1 ' 变成字符类型的 ' 0 '，也可以写一个判断：如果是 1 就改成 0，如果是 0 就改成 1

也可以用位运算来简化操作：

字符类型的 ' 0 ' 和字符类型的 ' 1 ' 的二进制表示只有最后一位是不一样的，让它改变状态的话，异或一个 1 即可

#include 
#include 
#include 
#include 

using namespace std;
//需要多开一个位置 由于要用字符串来读入 字符串最后需要有一个'' 一个长度是5的字符串其实需要6位
const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};

//在g里面改变5个位置的值
void turn(int x, int y)
{
    //用偏移量来做
    //枚举5个位置
    for (int i = 0; i < 5; i ++ )
    {
        //a、b表示偏移后的位置
        int a = x + dx[i], b = y + dy[i];
        //判断有没有出界
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;   // 在边界外,直接忽略即可
        //改变状态
        g[a][b] ^= 1;
    }
}

int main()
{
    int T;
    //输入测试数据的数量
    cin >> T;
    while (T -- )
    {
        //读入棋盘:字符串读入
        for (int i = 0; i < 5; i ++ ) cin >> g[i];
        //最多需要多少步:超过6步就是无解
        int res = 10;
        //枚举第一行所有的选择
        for (int op = 0; op < 32; op ++ )
        {
            //memcpy 可以用来复制数组,这里是先把原数组备份一下,然后对本数组操作
            //本次操作结束后,要用备份数组还原回来,再进行下一次操作
            memcpy(backup, g, sizeof g);
            //表示操作的步数
            int step = 0;
            //从第一行开始
            for (int i = 0; i < 5; i ++ )
                //如果是 1 就操作
                if (op >> i & 1)
                {
                    step ++ ;
                    turn(0, i);
                }
            //枚举前4行,每一行决定了后面一行的操作,一直倒数第2行
            for (int i = 0; i < 4; i ++ )
                //依次判断每一列
                for (int j = 0; j < 5; j ++ )
                    //如果当前的灯的状态是灭的
                    if (g[i][j] == '0')
                    {
                        step ++ ;
                        //下一行的对应位置一定要按一下开关
                        turn(i + 1, j);
                    }
            //最后一行灯的状态已经不能再操作 如果最后一行不是全亮就是无解
            bool dark = false;
            for (int i = 0; i < 5; i ++ )
                if (g[4][i] == '0')
                {
                    //有灭的灯
                    dark = true;
                    break;
                }
            //如果全亮 更新状态
            if (!dark) res = min(res, step);
            //把原数组从备份中拿回来
            memcpy(g, backup, sizeof g);
        }
        //无解返回-1
        if (res > 6) res = -1;

        cout << res << endl;
    }

    return 0;
}