167. 木棒
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
注意: 数据中可能包含长度大于50的木棒，请在处理时忽略这些木棒。
输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。
输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
输入样例：
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例：
6
5
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 64;
int n, sum, length; //木棒个数 木棒总和 当前枚举的长度
int sticks[N];
bool st[N];//当前木棍有没有被使用过
bool dfs(int u, int cur, int start)//木根数 当前多长 木棍起始下标
{
if(u * length == sum) return true;
if(cur == length) return dfs(u + 1, 0, 0);
for(int i = start; i < n; i++)
{
if(st[i]) continue;//当前木棍已经用掉 继续
int l = sticks[i];
if(cur + l > length) continue;
st[i] = true;
if(dfs(u, cur + l, i + 1)) return true;
st[i] = false; //恢复现场
//剪枝2 放第一根木棒失败 放最后一根失败
if(!cur) return false;
if(cur + l == length) return false;
//剪枝1 跳过所有相等的木棍
int j = i;
while(j < n && sticks[j] == l) j ++;
i = j - 1;
}
return false;
}
int main()
{
while(cin >> n, n)
{
sum = 0, length = 0;
for(int i = 0; i < n; i++)
{
int l = 0;
cin >> l;
sticks[i] = l;
if(l > 50) continue;
sum += l;
length = max(length, l);
}
sort(sticks, sticks + n);
reverse(sticks, sticks + n);//从小到大排序
memset(st, false, sizeof st);
for(int i = 0; i < n; i ++)
if(sticks[i] > 50)
st[i] = true;
while(length)//从小到大枚举length
{
if(sum % length == 0 && dfs(0, 0, 0))
{
cout << length << endl;
break;
}
length ++;
}
}
return 0;
}
168. 生日蛋糕
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i层蛋糕是半径为Ri, 高度为Hi的圆柱。
当i < M时，要求Ri> Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ，请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
除Q外，以上所有数据皆为正整数 。
输入格式
输入包含两行，第一行为整数N（N <= 10000），表示待制作的蛋糕的体积为Nπ。
第二行为整数M(M <= 20)，表示蛋糕的层数为M。
输出格式
输出仅一行，是一个正整数S（若无解则S = 0）。
数据范围
1≤N≤10000,
1≤M≤20
输入样例：
100
2
输出样例：
68
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 25, INF = 1e9;
int n, m;
int R[N], H[N];
int minv[N], mins[N]; //前i层体积最小 前i层最小侧面积
int ans = INF;
void dfs(int u, int v, int s)//u层数
{
//剪枝
if(v + minv[u] > n) return;
if(s + mins[u] >= ans) return;
if(s + 2 * (n - v) / R[u + 1] >= ans) return;
if(!u) //处理到了第一层
{
if(n == v) ans = s;
return;
}
for(int r = min((int)sqrt(n - v), R[u + 1] - 1); r >= u; r--)
for(int h = min((n - v) / r / r, H[u + 1] - 1); h >= u; h --)
{
int t = 0;
if(u == m) t = r * r;//最后一层面积
R[u] = r, H[u] = h;
dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
minv[i] = minv[i - 1] + i * i * i;// v = π * r * r * h
mins[i] = mins[i - 1] + 2 * i * i;// s = π * 2 * r * h
}
R[m + 1] = H[m + 1] = INF; //哨兵
dfs(m, 0, 0);
cout << ans << endl;
return 0;
}
169. 数独2
请你将一个16×16的数独填写完整，使得每行、每列、每个4×4十六宫格内字母A~P均恰好出现一次。
保证每个输入只有唯一解决方案。
输入格式
输入包含多组测试用例。
每组测试用例包括16行，每行一组字符串，共16个字符串。
第i个字符串表示数独的第i行。
字符串包含字符可能为字母A~P或”-“（表示等待填充）。
测试用例之间用单个空行分隔，输入至文件结尾处终止。
输出格式
对于每个测试用例，均要求保持与输入相同的格式，将填充完成后的数独输出。
每个测试用例输出结束后，输出一个空行。
输入样例：
–A—-C—–O-I
-J–A-B-P-CGF-H-
–D–F-I-E—-P-
-G-EL-H—-M-J–
—-E—-C–G—
-I–K-GA-B—E-J
D-GP–J-F—-A–
-E—C-B–DP–O-
E–F-M–D–L-K-A
-C——–O-I-L-
H-P-C–F-A–B—
—G-OD—J—-H
K—J—-H-A-P-L
–B–P–E–K–A-
-H–B–K–FI-C–
–F—C–D–H-N-
输出样例：
FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK
/*
dance links : 1.精确覆盖 2.重复覆盖
搜索顺序，每次找到一个空格，枚举空格选择哪个字母，然后往下递归。
边界：所有空格都填满
状态的存储：state[x][y]，表示x行y列这个格子可以填哪些数(0 - 15) 用15位二进制表示 0 ~ 2 ^ 15 - 1
优化：
1.对于每个空格，如果不能填任何一个字母，无解；如果只能填一个字母，那么直接填上；
2.对于每一行，如果某个字母不能出现在任何一个位置，无解；如果某个字母只有一个位置可以填，则直接填上；
3.对于每一列，与行类似；
4.对于每个16宫格，与行类似；
5.每次选择空格时，选择备选方案最少的格子来填（先选备选方案少，分支少）
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 16, M = N * N + 1;
int ones[1 << N]; //存储每一个二进制里面有多少个1 ones[5] = 2 5的二进制里面有两个1
int log[1 << N];
int state[N][N]; //每个空格的所有备选数字
char str[N][N + 1]; //整个状态
int bstate[M][N][N], bstate2[M][N][N]; //备份
char bstr[M][N][N + 1];
inline int lowbit(int x) //返回x的二进制表示里面最后一个1 lowbit(6) = 2
{
return x & - x;
}
void draw(int x, int y, int c)
{
str[x][y] = c + 'A';
for(int i = 0; i < N; i++)
{
state[x][i] &= ~(1 << c); //其他位不变，如果当前位是1的话变成0
state[i][y] &= ~(1 << c);
}
//xy所在的九宫格做同样操作，即当前位选了，其他为不能选
int sx = x / 4 * 4, sy = y / 4 * 4;
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
state[sx + i][sy + j] &= ~(1 << c);
state[x][y] = 1 << c;
}
bool dfs(int cnt)
{
if(!cnt) return true;
// 枚举过程
int kcnt = cnt;
memcpy(bstate[kcnt], state, sizeof state);//备份，方便恢复现场
memcpy(bstr[kcnt], str, sizeof str);
//剪枝1 对于每个空格，如果不能填任何一个字母，无解；如果只能填一个字母，那么直接填上；
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(str[i][j] == '-')
{
int s = str[i][j];
if(!s)
{
memcpy(state, bstate[kcnt], sizeof state);//恢复现场
memcpy(str, bstr[kcnt], sizeof str);
return false;
}
if(ones[s] == 1)
{
draw(i, j, log[s]);
cnt --;
}
}
//剪枝2 对于每一行，如果某个字母不能出现在任何一个位置，无解；如果某个字母只有一个位置可以填，则直接填上；
for(int i = 0; i < N; i ++)
{
int sor = 0, sand = (1 << N) - 1;//存储所有数字或和与的结果
int drawn = 0; //当前行格子已经填上的
for(int j = 0; j < N; j ++)
{
int s = state[i][j];
sand &= ~(s & sor); //sand为1表示这一个字母只有一个位置可以填
sor |= s;
if(str[i][j] != '-') drawn |= state[i][j];
}
if(sor != (1 << N) - 1) //这一行并集没有16个1 false
{
memcpy(state, bstate[kcnt], sizeof state);//恢复现场
memcpy(str, bstr[kcnt], sizeof str);
return false;
}
for(int j = sand; j; j -= lowbit(j))
{
int t = lowbit(j);
if(!(drawn & t))
{
for(int k = 0; k < N; k++)
if(state[i][k] & t)
{
draw(i, k, log[t]);
cnt --;
}
}
}
}
//剪枝3 对于每一列，如果某个字母不能出现在任何一个位置，无解；如果某个字母只有一个位置可以填，则直接填上；
for(int i = 0; i < N; i ++)
{
int sor = 0, sand = (1 << N) - 1;//存储所有数字或和与的结果
int drawn = 0; //当前行格子已经填上的
for(int j = 0; j < N; j ++)
{
int s = state[j][i];
sand &= ~(s & sor); //sand为1表示这一个字母只有一个位置可以填
sor |= s;
if(str[j][i] != '-') drawn |= state[j][i];
}
if(sor != (1 << N) - 1) //这一行并集没有16个1 false
{
memcpy(state, bstate[kcnt], sizeof state);//恢复现场
memcpy(str, bstr[kcnt], sizeof str);
return false;
}
for(int j = sand; j; j -= lowbit(j))
{
int t = lowbit(j);
if(!(drawn & t))
{
for(int k = 0; k < N; k++)
if(state[k][i] & t)
{
draw(k, i, log[t]);
cnt --;
}
}
}
}
//剪枝4 对于每个16宫格，如果某个字母不能出现在任何一个位置，无解；如果某个字母只有一个位置可以填，则直接填上；
for(int i = 0; i < N; i ++)
{
int sor = 0, sand = (1 << N) - 1;//存储所有数字或和与的结果
int drawn = 0; //当前行格子已经填上的
for(int j = 0; j < N; j ++)
{
int sx = i / 4 * 4, sy = i % 4 * 4;
int dx = j / 4, dy = j % 4;
int s = state[sx + dx][sy + dy];
sand &= ~(s & sor); //sand为1表示这一个字母只有一个位置可以填
sor |= s;
if(str[sx + dx][sy + dy] != '-') drawn |= state[sx + dx][sy + dy];
}
if(sor != (1 << N) - 1) //这一行并集没有16个1 false
{
memcpy(state, bstate[kcnt], sizeof state);//恢复现场
memcpy(str, bstr[kcnt], sizeof str);
return false;
}
for(int j = sand; j; j -= lowbit(j))
{
int t = lowbit(j);
if(!(drawn & t))
{
for(int k = 0; k < N; k++)
{
int sx = i / 4 * 4, sy = i % 4 * 4;
int dx = k / 4, dy = k % 4;
if(state[sx + dx][sy + dy] & t)
{
draw(sx + dx, sy + dy, log[t]);
cnt --;
}
}
}
}
}
if(!cnt) return true;
//剪枝5 每次选择空格时，选择备选方案最少的格子来填（先选备选方案少，分支少）
int x, y, s = 100;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(str[i][j] == '-' && ones[state[i][j]] < s)
{
s = ones[state[i][j]];
x = i, y = j;
}
memcpy(bstate2[kcnt], state, sizeof state);
for(int i = state[x][y]; i; i -= lowbit(i))
{
memcpy(state, bstate2[kcnt], sizeof state);
draw(x, y, log[lowbit(i)]);
if(dfs(cnt - 1)) return true;
}
memcpy(state, bstate[kcnt], sizeof state);//恢复现场
memcpy(str, bstr[kcnt], sizeof str);
return false;
}
int main()
{
for(int i = 0; i < N; i ++) log[1 << i] = i;//初始化
for(int i = 0; i < 1 << N; i ++)
{
for(int j = i; j; j -= lowbit(j)) ones[i] ++; //~i 等价于i >=0 i 等价于 i > 0
}
while(cin >> str[0])
{
for(int i = 1; i < N; i ++) cin >> str[i];
for(int i = 0; i < N; i++) //初始化state
for(int j = 0; j < N; j ++)
state[i][j] = (1 << N) - 1;
int cnt = 0; //存储空格个数
for(int i = 0; i < N; i ++) //遍历已经填的格子
for(int j = 0; j < N; j++)
if(str[i][j] != '-')
{
draw(i, j, str[i][j] - 'A'); //更新格子
}
else cnt ++;
dfs(cnt);
for(int i = 0; i < N; i ++) cout << str[i] << endl;
cout << endl;
}
return 0;
}