课上实例1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
// n最大为25
// 数组多开一些防止越界
const int N = 30;
int n, m;
// way表示方案
int way[N]; // 记录每个位置
// 三个参数
// 位置way是全局变量,不需要传
// u表示当前枚举到第几个位置
// start表示当前可以从哪个数开始枚举
void dfs(int u, int start)
{
// 边界
// 边界二(剪枝优化)
// dfs可以用剪枝优化,即发现分支无解可以提前退出
// u表示正在选第u个数,即已经选了u-1个数
// 可以从start选到n
// 如果从start到n全部选上也不够m个数,此时无解,可以提前退出
// start到n一共n-start+1个数
// 总共为u-1+n-start+1个数
if (u + n - start < m) return; // 剪枝
// 边界一
// u == m + 1说明已经选了m个数
if (u == m + 1)
{
// 将方案输出
for (int i = 1; i <= m; i ++ ) printf("%d ", way[i]);
puts("");
return;
}
// 每个位置从start到n枚举
for (int i = start; i <= n; i ++ )
{
// 将当前的数放到位置
way[u] = i;
// dfs到下一层
// 当前的数填i,因此下个数要从i+1开始枚举
dfs(u + 1, i + 1);
// 本题恢复现场可以省略
way[u] = 0; // 恢复现场
}
}
int main()
{
// 本题输出较多,建议使用scanf和printf
scanf("%d%d", &n, &m);
// 从第一个位置开始枚举
// 第一个位置可以从1开始枚举
dfs(1, 1);
return 0;
}
课上实例2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
// 判重数组st
// 备份的判重数组backup
bool st[N], backup[N];
int ans; // 记录方案数
// 判断a和c是否满足要求
bool check(int a, int c)
{
// 需先将b算出来
// c可能有7位数,那么和n乘起来以后就会溢出int
// 那么b就可能变成负数
// 从而它的个位数字的余数也可能是负数
// 那么backup[x]的下标就可能是负数,所以下标就越界了
// 会发生未知错误
long long b = n * (long long)c - a * c;
// 代码修正:int b = n * c - a * c;
// a,b,c都不能是0
if (!a || !b || !c) return false;
// 因为要对判重数组做修改,因此做一个备份
// st要保持原样,因为需恢复现场
// memset(); memcpy();
memcpy(backup, st, sizeof st);
// 判断条件一
// 取出b中每一位的数字,检查与a和c有无重复
// 常用技巧:取出某数的每一位
// while(该数);%10取个位;/10删个位
while (b)
{
// 从前往后取出b的每一位
int x = b % 10; // 取个位%10
b /= 10; // 个位删掉/10
// 判断x是否出现过
// 如果x出现过,或者x为0,不合法
if (!x || backup[x]) return false;
// 否则将x标记,代表x已经被用过
backup[x] = true;
}
// 判断条件二
// 遍历看1到9是否都出现过
for (int i = 1; i <= 9; i ++ )
if (!backup[i])
return false;
// 否则返回ture
return true;
}
// dfs_c枚举c的全排列
void dfs_c(int u, int a, int c)
{
// 如果已经用完9个数字,则return
if (u > 9) return;
// 判断a和c是否满足题目要求
// 满足的话,答案数++
if (check(a, c)) ans ++ ;
// 否则从1到9枚举每个数
for (int i = 1; i <= 9; i ++ )
// 如果当前这个数没有被用过
if (!st[i])
{
// 则将该数标记被用过
st[i] = true;
// 并将该数接到c的后面
// dfs到下一层,a不变,c后面加上一位i
dfs_c(u + 1, a, c * 10 + i);
// 恢复现场
st[i] = false;
}
}
// u表示当前已经用了几个数字
// a表示a的当前值
void dfs_a(int u, int a)
{
// 如果a≥n,此时无解
// 因为三个数至少要有1位数字
if (a >= n) return;
// 只要a小于n,对于每种方案都可以dfs下c
// 从u开始枚举,将当前的a传给它,c为0
// a可以提前判断,只有a大于0的情况往下做(剪枝)
if (a) dfs_c(u, a, 0);
// 枚举当前位置可以用哪个数字
// 从1到9循环
for (int i = 1; i <= 9; i ++ )
// 如果当前数字没被用过
if (!st[i])
{
// 则将该数标记被用过
st[i] = true;
// dfs到下一层
// 同时更新a
// 常用技巧在某一个数后面加上一位
// 将原数字乘10,再加上要添加的数字即可
dfs_a(u + 1, a * 10 + i);
// 恢复现场
st[i] = false;
}
}
int main()
{
// 输入输出数据量都很小,用cin读入
// nc = ac + b
cin >> n;
// 首先dfs_a(枚举a的所有全排列)
// 第一个参数为当前已经用了几个数字,最开始时0,一个数字都没用
// 第二个参数是a当前是多少,最开始是0
dfs_a(0, 0);
// 输出方案数
cout << ans << endl;
return 0;
}
课上实例3
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int f[46];
f[1] = 0, f[2] = 1;
// 从第三项开始每项是前两项的和
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] << ' ';
// 评测时最后一个回车可以省略
cout << endl;
return 0;
}
课上实例4
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int a = 0, b = 1;
// 从第一项i=1开始
for (int i = 1; i <= n; i ++ )
{
cout << a << ' ';
int fn = a + b;
a = b, b = fn;
}
cout << endl;
return 0;
}
课上实例5
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
// 多开一个位置
// 因为本例用字符串存放
// 字符串最后有一个'\0'
// 长度为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};
// 改变五个位置的值
void turn(int x, int y)
{
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; // 在边界外,直接忽略即可
// 如果没有出界,改变状态
// 希望将字符类型的0变成1
// 将字符类型的1变成0
// 位运算小技巧,异或一个1即可
g[a][b] ^= 1;
}
}
int main()
{
// 多组测试数据
int T;
cin >> T;
while (T -- )
{
// 读入棋盘
// 字符串读入,因此只有一维
for (int i = 0; i < 5; i ++ ) cin >> g[i];
// 最大步数
// 因为本题超过6步无解
// 因此先赋值一个较大数10
int res = 10;
// 枚举所有方案
// 首先枚举第一行所有操作
// 可以用递归实现指数型枚举
// 本例用位运算技巧
// 每个操作可以看做一个二进制数
// 1代表操作,0代表不操作
// 第一行的操作用op表示
for (int op = 0; op < 32; op ++ )
{
// 每次操作会改变原棋盘
// 因此做一个备份
// 每次在备份上操作
memcpy(backup, g, sizeof g);
// 记录操作的步数
int step = 0;
// 操作第一行
for (int i = 0; i < 5; i ++ )
// 判断当前这一位要不要操作
// 判断对应二进制的对应第i位是不是1
// 如果是1就操作
// 整数op的从低位往高位数第i位(下标从0开始)是否为1
// 只需将op右移i位与上1
if (op >> i & 1)
{
// 步数++
step ++ ;
turn(0, i);
}
// 枚举接下来每一行,一直到倒数第二行
for (int i = 0; i < 4; i ++ )
for (int j = 0; j < 5; j ++ )
// 如果当前位置是灭
// 说明下一行对应的位置要按开关
if (g[i][j] == '0')
{
// 步数++
step ++ ;
// turn下一行对应位置
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);
}
// 如果最大步数大于6,说明无解
if (res > 6) res = -1;
cout << res << endl;
}
return 0;
}
