简单斐波那契数列
https://www.acwing.com/problem/content/solution/719/1/
开关问题共同点
1.每个开关 只按 一次(最优解)
2.按的顺序无关紧要
每个灯泡的最终状态 只有 能影响到他的 开关的 按得次数有关
费解的开关 https://www.acwing.com/problem/content/97/
开关问题 性质
1.按开关的顺序是不重要的 决定 它 开 与 关 是由 周边几个决定的
2.每个格子最多按一次 如果按两次的话 相当于没按
这道题 的核心是 每一行开关的操作 完全被前一行的灯的亮灭状态 所决定
因此 我们可以通过枚举第一行的开关的亮灭状态 来决定 后 n-1 行的状态
枚举 第一行的开关的亮灭状态 （设定 1 按一下 0 不按）
因为 有 5个格子 每个格子都有2 种选择 所以说 有 2的5次 种 方案
1.可以用 递归 指数型枚举 dfs
还没写，记得写
2.可以用位运算
可以将0 ---2的5次 -1 转化为 5位 2进制数
eg：
//假如第一行是00111, op从0到31进行枚举，如果op = 00001，
//那么代表g矩阵中第一行的第一个灯要点击一下，
//第一行变为11111。
//k不断变大(0变到31)
//假如第一行是00111, op从0到31进行枚举，如果op = 10001，
//那么代表g矩阵中第一行的第一个灯和最后一个灯要点击一下，
//第一行变为11100。
对于if(op >> i & 1)的解释
可以看 https://www.acwing.com/solution/content/22367/
turn()函数
我们 可以 通过 偏移量的方法
对于 0 变 1 1 变 0 的操作
可以 通过 if语句
也可以 通过 ^ 异或操作
字符1的ASCII码为49 11001,
0的ASCII码为48 11000 转化为二进制最后一位分别是1,0
^表示异或运算 0^1=1,1^1=0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char g[6][6],temp[6][6];
int n;
int dx[] = {-1,0,1,0,0},dy[]={0,1,0,-1,0};
void turn(int x,int y)
{
for(int i = 0;i < 5;i++)
{
int a = x + dx[i],b = y + dy[i];
if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
//g[a][b] ^= 1;
if(g[a][b] == '1') g[a][b] = '0';
else g[a][b] = '1';
}
}
int main()
{
scanf("%d",&n);
while(n--)
{
for(int i = 0;i<5;i++) cin>>g[i];
int res = 10;//用来记录 最后的结果 只要该数 比 6大就行
for(int op = 0;op < 32;op++)
//枚举第一行 1 表示 按一下 0 表示不按
//每个位置 都有 2种选择 所以 说 有 2的五次方种选择
//00000 ---11111
// 这里我们枚举了第一行的32种按法，不用管是亮是灭，把第一行所有情况都按一遍
//下一行的操作 就只能跟着第一行的操作走
{ //因为要多次 所以说 备份一下 数组 防止上次的操作影响
memcpy(temp,g,sizeof g);
int step = 0;//操作数
for(int i = 0;i<5;i++)//对第一行进行操作
{
if(op >> i & 1)// 求 op的第i个位置上的数 是几
{
step++;
turn(0,i);
}
}
//根据第一行结果 看2 3 4 行咋变
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 used = false;
for(int i = 0;i<5;i++)
{
if(g[4][i] == '0')
{
used = true;
break;
}
}
if(!used) res = min(res,step);
memcpy(g, temp, sizeof g);
}
if(res > 6) res = -1;
cout<<res<<endl;
}
return 0;
}
飞行员兄弟 https://www.acwing.com/problem/content/118/
目标 全部 变成 -
1.每个开关 只按 一次
2.按的顺序无关紧要
翻硬币 https://www.acwing.com/problem/content/1210/
给一个初始状态 再给一些操作，问经过几步 可以将 初始状态 变成目标状态
1.宽搜 bfs https://www.acwing.com/problem/content/847/ 八数码问题
状态数 不多 才能用bfs
2.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
char start[N],last[N];
void turn(int x,int y)
{
if(start[x] == '*') start[x] = 'o';
else start[x] = '*';
if(start[y] == '*') start[y] = 'o';
else start[y] = '*';
}
int main()
{
cin>>start>>last;
int len = strlen(start);
int step = 0;
for(int i = 0;i < len;i++)
{
if(start[i] != last[i])
{
step++;
turn(i,i+1);
}
}
cout<<step;
}
