搜索考后总结
\(T_1\) 午餐费
题目描述
现要对某班学生进行N天培训，该班所有学生都订了N天的午餐，所以我们知道他们每天要花多少钱。现在该班班主任需要决定如何使用班费。由于钱有限，他们不可能每天都吃免费午餐。因此，每天班主任可以选择自己支付或使用班费支付当天午餐费。当然，班主任比较小气，希望尽可能多地花掉班费，但是他太忙了，请你帮他计算他最多能够花多少班费。
输入格式
输入包含多个测试数据（不超过 \(50\) 个）。
每个测试数据有两行。第一行有两个整数，\(N\) 为培训天数，\(M\) 为班费总数。
第二行包含 \(N\) 个正整数，其中第i个整数表示该班当天需要支付第午餐的钱。所有这些整数都不超过\(10000000\) ，整数之间用空格分隔。
输出格式
对于每个测试数据，输出一行整数，表示班主任能够花班费的最大金额
样例
样例输入
3 10
8 4 5
样例输入
9
数据范围与提示
\(1 <= N <= 30\)
\(0 <= M <= 10000000\)
思路
我们来说说本题的剪枝：
第一个剪枝： 我们选钱的时候尽量从最大的开始选，这样会更快地搜索到最优解，所以进行从大到小的排序。
第二个剪枝： 如果搜索到的班费和已经大于了最大可使用的班费，就没必要再搜索下去了。
第三个剪枝： 如果搜索到的班费加上所有没有搜到的班费和还要小于最优解，也没必要继续搜索下去。为了更快的求到没搜到的班费和，我们可以用一个数组求一下后缀和。
注意开 long long
\(code\)
#include
#include
#include
using namespace std;
long long n, m;
long long a[105];
long long b[105];
long long Max = -1e15;
void dfs(long long t, long long sum) {
//printf("%d\n", sum);
if (Max == m) return;
if (sum > m || sum + b[t] < Max) return;
if (t == n + 1) {
Max = max(Max, sum);
return;
}
dfs(t + 1, sum + a[t]);
dfs(t + 1, sum);
}
bool cmp(long long x, long long y) { return x > y; }
int main() {
freopen("lunch.in", "r", stdin);
freopen("lunch.out", "w", stdout);
while (scanf("%lld %lld", &n, &m) != EOF) {
Max = -1e15;
memset(b, 0, sizeof(b));
for (long long i = 1; i <= n; i++) {
scanf("%d", &a[i]);
//a[i] = ((i - 1) * 123456789 + 2147483647) % 1234567891;
}
sort(a + 1, a + n + 1, cmp);
for (long long i = n; i >= 1; i--) {
b[i] = b[i + 1] + a[i];
}
dfs(0, 0);
printf("%lld\n", Max);
}
return 0;
}
本人做此题时，最开始瞎搞半天，忘把后缀和这个剪枝加上，用随机数连出 \(3\) 组 \(n = 30\) 的数据，都是秒出，正当我准备去干 \(T_2\) 时，终于给我出了一个让我炸的数据。不然就有可能就爆 \(40\)
\(T_2\) 生日快乐
题目描述
windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 \(X\) 和 \(Y\) 的矩形蛋糕。现在包括 windy，一共有 \(N\) 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。windy主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成 \(N\) 块蛋糕，windy必须切 \(N - 1\) 次。为了使得每块蛋糕看起来漂亮，我们要求 \(N\) 块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？
输入格式
包含三个整数，\(X\ Y\ N。1 <= X,Y <= 10000 ； 1 <= N <= 10\)
输出格式
包含一个浮点数，保留 \(6\) 位小数。
样例
样例输入
5 5 5
样例输入
1.800000
思路
\(code\)
#include
#include
using namespace std;
double dfs(double x, double y, int n) {
if (n == 1) return max(x, y) / min(x, y);
double ans = 1e5;
for (int i = 1; i <= n / 2; i++) {
ans = min(ans, max(dfs(x, y / n * i, i), dfs(x, y - y / n * i, n - i)));
ans = min(ans, max(dfs(x / n * i, y, i), dfs(x - x / n * i, y, n - i)));
}
return ans;
}
int main() {
freopen("birthday.in", "r", stdin);
freopen("birthday.out", "w", stdout);
double x, y;
int n;
scanf("%lf %lf %d", &x, &y, &n);
printf("%.6lf", dfs(x, y, n));
return 0;
}
第一眼看到这题时，就没有思路。然后写了一大堆代码去骗分，然后一分都没有骗到。。。
\(T_3\) 碎纸机
题目描述
你现在负责设计一种新式的碎纸机。一般的碎纸机会把纸切成小片，变得难以阅读。而你设计的新式的碎纸机有以下的特点：
\(1.\) 每次切割之前，先要给定碎纸机一个目标数，而且在每张被送入碎纸机的纸片上也需要包含一个数。
\(2.\) 碎纸机切出的每个纸片上都包括一个数。
\(3.\) 要求切出的每个纸片上的数的和要不大于目标数而且与目标数最接近。
举一个例子，如下图，假设目标数是 \(50\) ，输入纸片上的数是 \(12346\) 。碎纸机会把纸片切成 \(4\) 块，分别包含 \(1，2，34\) 和 \(6\) 。这样这些数的和是 \(43 (= 1 + 2 + 34 + 6)\) ，这是所有的分割方式中，不超过 \(50\) ，而又最接近 \(50\) 的分割方式。又比如，分割成 \(1，23，4\) 和 \(6\) 是不正确的，因为这样的总和是 \(34 (= 1 + 23 + 4 + 6)\) ，比刚才得到的结果 \(43\) 小。分割成 \(12，34\) 和 \(6\) 也是不正确的，因为这时的总和是 \(52 (= 12 + 34 + 6)\) ，超过了 \(50\) 。
还有三个特别的规则：
\(1.\) 如果目标数和输入纸片上的数相同，那么纸片不进行切割。
\(2.\) 如果不论怎样切割，分割得到的纸片上数的和都大于目标数，那么打印机显示错误信息。
\(3.\) 如果有多种不同的切割方式可以得到相同的最优结果。那么打印机显示拒绝服务信息。比如，如果目标数是 \(15\) ，输入纸片上的数是 \(111\) ，那么有两种不同的方式可以得到最优解，分别是切割成 \(1\) 和 \(11\) 或者切割成 \(11\) 和 \(1\) ，在这种情况下，打印机会显示拒绝服务信息。
为了设计这样的一个碎纸机，你需要先写一个简单的程序模拟这个打印机的工作。给定两个数，第一个是目标数，第二个是输入纸片上的数，你需要给出碎纸机对纸片的分割方式。
输入格式
输入包括多组数据，每一组包括一行。每行上包括两个正整数，分别表示目标数和输入纸片上的数。已知输入保证：两个数都不会以 \(0\) 开头，而且两个数至多都只包含 \(6\) 个数字。
输入的最后一行包括两个 \(0\) ，这行表示输入的结束。
输出格式
对每一组输入数据，输出相应的输出。有三种不同的输出结果：
sum part1 part2 ...
rejected
error
第一种结果表示：
\(1.\) 每一个 \(partj\) 是切割得到的纸片上的一个数。 \(partj\) 的顺序和输入纸片上原始数中数字出现的次序一致。
\(2.\) \(sum\) 是切割得到的纸片上的数的和，也就是说： \(sum = part1 + part2 +...\)
第一种结果中相邻的两个数之间用一个空格隔开。
如果不论怎样切割，分割得到的纸片上数的和都大于目标数，那么打印 \(“error”\) 。
如果有多种不同的切割方式可以得到相同的最优结果，那么打印 \(“rejected”\) 。
样例
样例输入
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
样例输入
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
思路
\(code\)
#include
#include
using namespace std;
int n, len, ans, d[1000005], num, a[15], b[15];
char s[15];
void dfs(int k, int sum, int tot) {
if (k >= len) {
d[sum]++;
if (sum > ans) {
ans = sum;
num = tot;
for (int i = 0; i < tot; i++) a[i] = b[i];
}
return;
}
int t = 0;
for (int i = k; i < len; i++) {
t = t * 10 + s[i] - '0';
if (sum + t > n) return;
b[tot] = t;
dfs(i + 1, sum + t, tot + 1);
}
}
int main() {
freopen("paper.in", "r", stdin);
freopen("paper.out", "w", stdout);
int sum;
while (scanf("%d %s", &n, s) != EOF) {
len = strlen(s);
if (n == 0 && s[0] == '0' && len == 1) break;
sum = 0;
for (int i = 0; i < len; i++) sum += s[i] - '0';
if (sum > n) {
printf("error\n");
continue;
}
memset(d, 0, sizeof(d));
num = 0, ans = 0;
dfs(0, 0, 0);
if (d[ans] > 1)
printf("rejected\n");
else {
printf("%d", ans);
for (int i = 0; i < num; i++) printf(" %d", a[i]);
printf("\n");
}
}
return 0;
}
\(T_5\) 炸僵尸
题目描述
妈妈得知小星星成功地解决了买玩具难题，奖励他去看电影《生化危机 6》，小星星看着看着就替女主角担心起来了，因为她要对付那么多的僵尸怪物，小星星恨不得扔颗炸弹消除可恶的僵尸们，他脑袋里开始构思出这样的场景：
在一个 N 行 M 列单元格构成的地图中，去放置一个炸弹，这种炸弹威力巨大，以放置点为中心进行行列延伸炸到同行同列的僵尸，但不能穿墙。上图中可以把炸弹放置在第 3 行第 4 列，最多可以炸到 4 个僵尸，如果对地图稍加改动（如下图），在第 5 行第 4 列处加入一个墙体，又如何呢？答案还是最多炸到 4 个僵尸，只不过最佳炸弹放置点发生了变化，应该放到第 6 行第 6 列的位置。
当然炸弹要靠勇敢的小星星去放，他只能在地图中朝上下左右四个方向行进（不能斜对 角移动） ，他不能穿墙，也不能穿越僵尸，要保证他的安全，如下图，告诉你小星星起始位 置是第 2 行第 2 列，那么他的最佳放置炸弹位置应该是第 3 行第 2 列，最多炸到 2 个僵尸。
现在请聪明的你也一起加入到消除僵尸的队伍来。
输入格式
输入格式
第一行四个用空格隔开的正整数表示 N,M,X,Y，分别表示 N 行 M 列的地图，小星星起 始位置第 X 行，第 Y 列。
接下来 N 行 M 列用来描述地图上每个单元格，‘ G’表示僵尸，‘#’表示墙体，只有‘.’ 表示的单元格才是小星星能够正常行走，能够放置炸弹的单元格。（数据保证四面都是墙体， 也就是第 1 行、第 N 行、第 1 列、第 M 列肯定都是墙体）。
输出格式
一个整数，最多能炸掉的僵尸数量。
样例
样例输入
13 13 4 2
#############
###..GG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############
样例输入
10
数据范围与提示
\(1 <= N <= 30\)
\(0 <= M <= 10000000\)
思路
\(code\)
#include
#include
#include
using namespace std;
struct node {
int x, y;
} k1, k2;
int n, m, x, y;
char a[2005][2005];
bool flag[2005][2005];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
queue q;
int Max = -1e9, xm, ym;
void bfs(int x, int y) {
flag[x][y] = true;
k1.x = x, k1.y = y;
q.push(k1);
while (!q.empty()) {
k2 = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int gx = k2.x + dx[i];
int gy = k2.y + dy[i];
if (gx >= 1 && gx <= n && gy >= 1 && gy <= m && !flag[gx][gy] && a[gx][gy] == '.') {
flag[gx][gy] = true;
k1.x = gx, k1.y = gy;
q.push(k1);
}
}
}
}
int main() {
freopen("zombie.in", "r", stdin);
freopen("zombie.out", "w", stdout);
cin >> n >> m >> x >> y;
for (int i = 1; i <= n; i++) {
getchar();
for (int j = 1; j <= m; j++) {
a[i][j] = getchar();
}
}
bfs(x, y);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int sum = 0;
if (a[i][j] == '.' && flag[i][j]) {
int x = i, y = j;
while (a[x][j] != '#') {
if (a[x][j] == 'G')
sum++;
x--;
}
x = i;
while (a[x][j] != '#') {
if (a[x][j] == 'G')
sum++;
x++;
}
while (a[i][y] != '#') {
if (a[i][y] == 'G')
sum++;
y++;
}
y = j;
while (a[i][y] != '#') {
if (a[i][y] == 'G')
sum++;
y--;
}
}
if (sum > Max) {
xm = i;
ym = j;
Max = sum;
}
}
}
printf("%d", Max);
return 0;
}
\(T_6\) A计划
题目描述
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
输入格式
输入格式
输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小 \(N × M\) 。T如上所意。接下去的前 \(N × M\) 表示迷宫的第一层的布置情况，后 \(N × M\) 表示迷宫第二层的布置情况。
输出格式
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。
样例
样例输入
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
样例输入
YES
数据范围与提示
1 <= N,M <=10
思路
\(code\)
#include
#include
#include
#include
using namespace std;
struct node {
int x, y, z, tot;
} k1, k2, k3;
char a[15][15][5];
int n, m, t;
bool flag[15][15][5];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
queue q;
int sx, sy, sz;
int mx, my, mz;
bool bfs(int x, int y, int z) {
flag[x][y][z] = true;
k1.x = x, k1.y = y, k1.z = z, k1.tot = 0;
q.push(k1);
while (!q.empty()) {
k2 = q.front();
q.pop();
// printf("%d %d %d\n", k2.x, k2.y, k2.z);
if (k2.tot > t)
return false;
for (int i = 0; i < 4; i++) {
int gx = k2.x + dx[i];
int gy = k2.y + dy[i];
int gz = k2.z;
if (gx >= 1 && gx <= n && gy >= 1 && gy <= m && gz >= 1 && gz <= 2 && !flag[gx][gy][gz] &&
a[gx][gy][gz] != '*') {
flag[gx][gy][gz] = true;
bool f = false;
if (a[gx][gy][gz] == '#' && a[gx][gy][gz + 1] != '*' && gz == 1) {
k1.x = gx, k1.y = gy, k1.z = gz + 1, k1.tot = k2.tot + 1, f = true;
} else if (a[gx][gy][gz] == '#' && a[gx][gy][gz - 1] != '*' && gz == 2) {
k1.x = gx, k1.y = gy, k1.z = gz - 1, k1.tot = k2.tot + 1, f = true;
} else if (a[gx][gy][gz] != '#')
k1.x = gx, k1.y = gy, k1.z = gz, k1.tot = k2.tot + 1, f = true;
if (k1.x == sx && k1.y == sy && k1.z == sz && k1.tot <= t) {
// cout << k3.tot << ' ' << k1.tot << endl;
return true;
}
if (gz == 1) {
if (f && !(a[gx][gy][gz + 1] == '#' && a[gx][gy][gz] == '#'))
q.push(k1);
} else {
if (f && !(a[gx][gy][gz - 1] == '#' && a[gx][gy][gz] == '#'))
q.push(k1);
}
}
}
}
return false;
}
int main() {
freopen("plan.in", "r", stdin);
freopen("plan.out", "w", stdout);
int c;
cin >> c;
while (c--) {
memset(flag, false, sizeof(flag));
while (!q.empty()) q.pop();
cin >> n >> m >> t;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j][1];
if (a[i][j][1] == 'P') {
sx = i, sy = j, sz = 1;
}
if (a[i][j][1] == 'S') {
mx = i, my = j, mz = 1;
}
}
}
// char st[1005];
// cin >> st;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j][2];
if (a[i][j][2] == 'P') {
sx = i, sy = j, sz = 2;
}
if (a[i][j][1] == 'S') {
mx = i, my = j, mz = 1;
}
}
}
// printf("%d %d %d\n", sx, sy, sz);
if (bfs(mx, my, mz))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}