AcWing165. 小猫爬山
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤18,
1≤Ci≤W≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
题解
这道题目使用暴力搜索。
需要表示的状态是
- 现在装载哪一只猫咪
- 已经使用了多少个缆车
- 每一个缆车上装载了多少只猫咪
对于搜索的优化：
- 如果某一条分支所对应的cnt已经小于目前所发现的最小的缆车数目，那么就直接回溯。
- 由于总量大的小猫更加难以运送，所以先搜索总量大的小猫。
由于如果某一种情况上，小车所承载的小猫大于小车所能承载的范围，那么就不再搜索下面的了。如果把重的小猫放在开始，那么就会尽可能多地减去分支。
实现代码
#include <bits/stdc++.h>
using namespace std;
#define N 25
int n;
int a[N];
int cab[N];
int ans;
int vol;
void dfs(int now, int cnt)
{
//cout << "." << now;
if(cnt >= ans) return;//最优化剪枝
if(now == n+1)
{
ans = min(ans, cnt);
return;
}
for(int i = 1; i <= cnt; i++)
{
if(cab[i] + a[now] <= vol)//可行性剪枝
{
cab[i] += a[now];
dfs(now+1, cnt);
cab[i] -= a[now];
}
}
cab[cnt+1] += a[now];
dfs(now+1, cnt+1);
cab[cnt+1] -= a[now];
}
int main()
{
cin >> n >> vol;
for(int i = 1; i <= n; i++)
{
scanf("%d", a+i);
}
ans = n;
sort(a+1, a+1+n);//优化搜索的顺序
reverse(a+1, a+1+n);
dfs(1, 0);
cout << ans;
return 0;
}
AcWing166. 数独
数独 是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
要是完全暴力搜索的话：是\(9^{81} = 1.9662705047555291361807590852691e+77\)
这样显然是不可行的，所以考虑优化：
当全部搜索完后，得到答案；
- 可行性剪枝：
在考虑一个位置的时候，仅往下搜索可行的情况。
需要排除不可行的情况 - 搜索顺序优化：
先选择可供选择的方案较少的进行。
常数优化：采取位运算的方式。
这道题目的代码量多到令人发指
在我的代码中，把1-9映射成了0-8；
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define N 9
char a[100];
int mp[1<<N];
int ones[1<<N];
int row[N], col[N], cell[3][3];
inline int lowbit(int x)
{
return x & -x;
}
inline void init()
{
for(int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
cell[i][j] = (1 << N) - 1;
}
}
inline int get(int x, int y)
{
return row[x] & col[y] & cell[x/3][y/3];
}
bool dfs(int cnt)
{
if(!cnt) return true;
int minv = 10;
int x, y;
for(int i = 0, k = 0; i < N; i++)
{
for(int j = 0; j < N; j++, k++)
{
if(a[i*9+j] == '.')
{
if(ones[get(i, j)] < minv)
{
minv = ones[get(i, j)];
x = i, y = j;
}
}
}
}
for(int i = get(x, y); i; i -= lowbit(i))
{
int k = mp[lowbit(i)];
//BUG:注意lowbit运算之后仅仅是一个数字
row[x] -= 1 << k;
col[y] -= 1 << k;
cell[x/3][y/3] -= 1 << k;
a[x*9+y] = k+'1';
if(dfs(cnt-1)) return true;
row[x] += 1 << k;
col[y] += 1 << k;
cell[x/3][y/3] += 1 << k;
a[x*9+y] = '.';
}
return false;
}
int main()
{
for(int i = 0; i < N; i++) mp[1 << i] = i;
for(int i = 0; i < (1<<N); i++)
{
int t = 0;
for(int j = i; j; j -= lowbit(j)) t++;
ones[i] = t;
}
while(scanf("%s", a), a[0] != 'e')
{
init();
int cnt = 0;
for (int i = 0, k = 0; i < N; i++)
{
for (int j = 0; j < N; j++, k++)
{
if(a[k] != '.')
{
int t = a[k] - '1';//已经把1到9映射为了0到8
row[i] -= 1 << t;
col[j] -= 1 << t;
cell[i/3][j/3] -= 1 << t;
}
else cnt++;
}
}
dfs(cnt);
printf("%s\n", a);
}
return 0;
}
我写的BUG有点多，写代码要很长时间，调BUG也要很长时间！
标签：小猫,进阶,0x22,int,算法,.....,搜索,缆车,数独 From： https://www.cnblogs.com/xjsc01/p/16704876.html