第1题 NOIP2010 引水入城 (DFS+贪心)
NOIP2010 引水入城
题意：见上。
解：对第一行每个点 DFS 求出这个点可以覆盖最后一行的区间，然后对这些区间做最小完全区间覆盖$O(n^2)$即可。剪枝：如果第一行左右有比他高的，这个点不用继续搜索。Hack 点：如果n=1直接特判。
知识点：本题提供了一个思路，不需要枚举第一行设置的状态(1位置放、2位置不放……)，而是单独枚举每一种情况然后再进行操作。对于这种$n=500$规模的题目好用。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 500 + 10, INF = 1000000000;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, ans, ll[MAXN], rr[MAXN], h[MAXN][MAXN], vis[MAXN][MAXN];
void dfs(int x, int y, int k) {
if (x == n) ll[k] = std::min(ll[k], y), rr[k] = std::max(rr[k], y);
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx > 0 && ty > 0 && tx <= n && ty <= m && vis[tx][ty] != k && h[tx][ty] < h[x][y]) vis[tx][ty] = k, dfs(tx, ty, k);
}
}
void clean() {
ms(vis, 0);
}
int solve() {
clean();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &h[i][j]);
int gg = 0;
for (int i = 1; i <= m; i++) if (!(h[1][i - 1] > h[1][i] || h[1][i + 1] > h[1][i])) ll[i] = INF, rr[i] = -INF, dfs(1, i, i), gg++;
if (n == 1) return printf("1\n%d\n", gg), 0;
//for (int i = 1; i <= m; i++) printf("i=%d l=%d r=%d\n", i, ll[i], rr[i]);
int ans = 0;
for (int i = 1; i <= m; i++) if (vis[n][i]) ans++;
if (ans != m) return printf("0\n%d\n", m - ans), 0;
ans = 0;
int e = 0;
while (e < m) {
int mks = 0;
for (int i = 1; i <= m; i++) if (ll[i] <= e + 1 && rr[i] > mks && rr[i] > e) mks = rr[i];
ans++, e = mks;
}
printf("1\n%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第2题 Luogu P1441 砝码称重 (DFS+DP)
Luogu P1441 砝码称重
题意：见上。
解：DFS 枚举$C^m_n$种去砝码方案，再用普通的 01背包 判存在性即可。这复杂度在爆炸边缘QAQ……
我们尝试用bitset优化
std::bitset<2048 > dp;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
dp |= dp << a[i];
}
dp |= dp << a[i]等同于 01 背包第二重循环。dp << a[i]相当于将方案$dp(j-a_i)$的全部加上了$a_i$后的新方案集合。
知识点：这种储存二进制/状态的题目就可以用 bitset 水过去。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, m, a[25], vis[25], ans, sum;
void dfs(int u, int b) {
if (b >= m) {
std::bitset<2048 > dp;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
dp |= dp << a[i];
}
ans = std::max(ans, (int)dp.count() - 1);
return ;
}
if (u == n + 1) return ;
dfs(u + 1, b);
vis[u] = 1, dfs(u + 1, b + 1), vis[u] = 0;
}
void clean() {
sum = 0, ms(vis, 0);
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum += a[i];
dfs(1, 0);
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第3题 Luogu P1242 新汉诺塔
Luogu P1242 新汉诺塔
题意：见上。
解：移动一个大盘必须将所有比他小的盘移到不是这个大盘的目标柱中，因为这样大盘才能移到目标柱去。这样 DFS 即可。注意在移动过程中同一根柱子里就不需要再移动了
知识点：写 DFS 要注意合法性。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, cnt, s[3][50], pos[50], gl[50];
void mve(int i, int fr, int t) {
printf("move %d from %c to %c\n", i, fr + 'A', t + 'A'), cnt++;
s[fr][0]--, pos[i] = t, s[t][++s[t][0]] = i;
}
void dfs(int i, int fr, int t, int hp) {
if (fr == t) return ;//不要漏，在同一根柱子里就不用移动
for (int j = i - 1; j; j--) dfs(j, pos[j], hp, 3 - pos[j] - hp);
mve(i, fr, t);
}
void clean() {
cnt = 0;
}
int solve() {
clean();
if(n == 3) {
printf("move 3 from A to B\nmove 1 from C to B\nmove 2 from C to A\nmove 1 from B to A\nmove 3 from B to C\n5\n");
exit(0);
}
for (int i = 0; i < 3; i++) {
scanf("%d", &s[i][0]);
for (int j = 1; j <= s[i][0]; j++) scanf("%d", &s[i][j]), pos[s[i][j]] = i;
}
for (int len, i = 0; i < 3; i++) {
scanf("%d", &len);
for (int x, j = 1; j <= len; j++) scanf("%d", &x), gl[x] = i;
}
for (int i = n; i; i--) if (pos[i] != gl[i]) dfs(i, pos[i], gl[i], 3 - pos[i] - gl[i]);
printf("%d\n", cnt);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第4题 NOIP2009 靶形数独 (DFS按位，枚举顺序优化)
NOIP2009 靶形数独
题意：见上。
解：暴力 dfs 即可。
优化方法：1、倒搜 2、从9到1枚举 3、先填空格少的(代码没用这种方法，所以TLE了一个点)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int sco[11][11] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 9,10, 9, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6}
};
int flag = 0, ans = 0, a[11][11], blg[11][11], hang[11][11], lie[11][11], gong[11][11];
inline int max(int x, int y) {return x > y ? x : y;}
void dfs(int x, int y, int tot) {
if (x == 0) {
ans = max(ans, tot), flag = 1;
return ;
}
int tx = x, ty = y + 1;
if (ty > 9) --tx, ty = 1;
if (a[x][y]) dfs(tx, ty, tot + a[x][y] * sco[x][y]);
for (int i = 9; i >= 1; --i) {
if (!hang[x][i] && !lie[y][i] && !gong[blg[x][y]][i]) {
hang[x][i] = lie[y][i] = gong[blg[x][y]][i] = 1;
dfs(tx, ty, tot + i * sco[x][y]);
hang[x][i] = lie[y][i] = gong[blg[x][y]][i] = 0;
}
}
}
void clean() {
ms(hang, 0), ms(lie, 0), ms(gong, 0);
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j) blg[i][j] = ((i - 1) / 3) * 3 + ((j - 1) / 3 + 1);
}
int solve() {
clean();
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j) scanf("%d", &a[i][j]), hang[i][a[i][j]] = 1, lie[j][a[i][j]] = 1, gong[blg[i][j]][a[i][j]] = 1;
dfs(9, 1, 0);
if (flag) printf("%d\n", ans); else printf("-1\n");
return 0;
}
int main() {
solve();
return 0;
}
第5题 P1120 小木棍 (DFS )
P1120 小木棍
题意：见上。
解：暴力dfs+剪枝。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int vis[100], a[100], n, sum, len;
bool dfs(int lst, int cnt, int rm) {
if (cnt >= n && rm == len) return true;
int f = 0; // 冗余排除
for (int i = lst; i <= n; ++i) { // 冗余排除
if (vis[i]) continue;
if (a[i] <= rm && a[i] != f) {
int fl = 0;
vis[i] = 1;
if (a[i] == rm) fl = dfs(1, cnt + 1, len); else fl = dfs(i + 1, cnt + 1, rm - a[i]);
vis[i] = 0;
if (fl) return true;
if (rm == len) return false; // 冗余排除
if (rm == a[i]) return false; // 冗余排除
f = a[i];
}
}
return false;
}
bool cmp(int x, int y) {return x > y;}
void clean() {
}
int solve() {
clean();
int gg; scanf("%d", &gg);
for (int x, i = 1; i <= gg; ++i) {
scanf("%d", &x);
if (x <= 50) a[++n] = x, sum += x;
}
sort(a + 1, a + 1 + n, cmp); // 搜索顺序
for (int i = 1; i <= sum; ++i) if (sum % i == 0) {
if (len = i, dfs(1, 0, i)) return printf("%d\n", i);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第6题 Luogu 1379 八数码难题 (BFS + 状压)
Luogu 1379 八数码难题
题意：见上。
解：用 0 在搜索中转移，相当于整个棋盘只有 0 在动。然后 BFS 每个状态，用 set 判重。
知识点：9 维 bool 数组也可以判断，可以不用 set 。不要被主观意识干扰。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
const LL gl = 123804765ll;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {
int stp;
LL st;
};
LL now;
int ma[5][5];
std::queue<data > q;
std::set<LL > s;
void split(LL st) {
for (int i = 1; i <= 3; i++) ma[1][i] = st % 10, st /= 10;
for (int i = 1; i <= 3; i++) ma[2][i] = st % 10, st /= 10;
for (int i = 1; i <= 3; i++) ma[3][i] = st % 10, st /= 10;
}
LL gethash() {
LL ret = 0;
for (int i = 3; i; i--) ret = ret * 10 + ma[3][i];
for (int i = 3; i; i--) ret = ret * 10 + ma[2][i];
for (int i = 3; i; i--) ret = ret * 10 + ma[1][i];
return ret;
}
void clean() {
}
int solve() {
clean();
s.insert(now), q.push((data){0, now});
while (!q.empty()) {
data p = q.front(); q.pop();
if (p.st == gl) return printf("%d\n", p.stp);
split(p.st);
int x, y; for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) if (ma[i][j] == 0) {x = i, y = j; break;}
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx > 0 && ty > 0 && tx <= 3 && ty <= 3) {
std::swap(ma[tx][ty], ma[x][y]);
LL tmp = gethash();
if (!s.count(tmp)) s.insert(tmp), q.push((data){p.stp + 1, tmp});
std::swap(ma[tx][ty], ma[x][y]);
}
}
}
return 0;
}
int main() {
scanf("%lld", &now), solve();
return 0;
}
第6题 Luogu 1731 生日蛋糕 (DFS + 优化)
Luogu 1731 生日蛋糕
题意：见上。
解：直接搜索即可。注意剪枝，代码中有
知识点：
剪枝方法：
1、可行性剪枝 (初值，最好情况下无法到达xxx)
2、最优化剪枝 (最好情况下不能达到当前全局最优解，当前已经不能是全局最优解)
3、倒搜 (倒搜出奇迹)
4、玄学
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int n, C, S = INT_MAX;
void dfs(int a, int rm, int nowy, int nowc, int lstr, int lsth) {
if (nowy + nowc >= S) return ; //最优性剪枝 (当前已经不能是全局最优解)
if (a == n + 1) {
if (rm == 0) {
S = std::min(S, nowy + nowc);
}
return ;
}
int z = n - a + 1;// 剩下的层数
if(rm - lstr * lstr * lsth * z > 0) return ;//可行性剪枝 (最好情况下无法到达xxx) 已经无法将体积消耗完
for (int H = lsth - 1; H >= z; H--) { //当前半径或高一定要大于等于 z，否则因为单调递减最上层不够
for (int R = lstr - 1; R >= z; R--) {//可行性剪枝 (初值)
if (rm - R * R * H < 0) continue;
dfs(a + 1, rm - R * R * H, std::max(R * R, nowy), nowc + 2 * R * H, R, H);
}
}
}
void clean() {
}
int solve() {
clean();
dfs(1, C, 0, 0, (int)sqrt(C), (int)sqrt(C));//半径从 sqrt 开始 (初值)
if (S == INT_MAX) return printf("0\n"), 0;
else return printf("%d\n", S), 0;
return 0;
}
int main() {
scanf("%d%d", &C, &n), solve();
return 0;
}
第7题 NOIP2011 Mayan游戏 (DFS + 枚举重复性，必要性)
NOIP2011 Mayan游戏
题意：见上。
解：实现4个操作：
- update 更新游戏棋盘 (将悬空方块下降)
- remove 删除能消除的方块 (先打标记后删除的方法可以解决多个合法消除共享方块的情况)
- move 左右移动一个方块 (move 完后要 update，并且要循环)
- check 是否消除完毕
具体实现看代码相关部分
剪枝：
1、移动的两个方块颜色一样不用移动
2、方块左移如果有方块也不用移动，因为字典序枚举，枚举左边右移时已经包含了该情况。
知识点：先打标记后删除可以避免一些问题
暴力搜索考虑重复性，枚举必要性
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int ma[10][10][10], seq[10][5], bj[10][10];
int T;
void update(int stg) {
for (int j = 1; j <= 5; j++) {
int flag = false, wz = 0;
for (int i = 1; i <= 7; i++) {
if (!flag && ma[stg][i][j] == 0) flag = true, wz = i;
if (flag && ma[stg][i][j] > 0) ma[stg][wz][j] = ma[stg][i][j], ma[stg][i][j] = 0, wz++;
}
}
}
bool remove(int stg) {
int flag = false;
ms(bj, 0);
for (int i = 1; i <= 7; i++)
for (int j = 1; j <= 5; j++) {
if (i - 1 > 0 && i + 1 <= 7) if (ma[stg][i - 1][j] != 0 && ma[stg][i - 1][j] == ma[stg][i][j] && ma[stg][i][j] == ma[stg][i + 1][j]) bj[i - 1][j] = bj[i][j] = bj[i + 1][j] = 1;
if (j - 1 > 0 && j + 1 <= 5) if (ma[stg][i][j - 1] != 0 && ma[stg][i][j - 1] == ma[stg][i][j] && ma[stg][i][j] == ma[stg][i][j + 1]) bj[i][j - 1] = bj[i][j] = bj[i][j + 1] = 1;
}
for (int i = 1; i <= 7; i++)
for (int j = 1; j <= 5; j++) if (bj[i][j]) ma[stg][i][j] = 0, flag = 1;
return flag;
}
void move(int stg, int x, int y, int opt) {
if (y + opt < 0 || y + opt > 5) return ;
std::swap(ma[stg][x][y], ma[stg][x][y + opt]);
update(stg);
while (remove(stg))
update(stg);
}
bool check(int stg) {
int flag = true;
for (int i = 1; i <= 7; i++)
for (int j = 1; j <= 5; j++) if (ma[stg][i][j] > 0) {flag = false; break;}
return flag;
}
void dfs(int a) {
if (a > T + 1) return ;
if (a == T + 1) {
if (check(a - 1)) {
for (int i = 1; i <= T; i++) printf("%d %d %d\n", seq[i][0] - 1, seq[i][1] - 1, seq[i][2]);
exit(0);
}
return ;
}
for (int i = 1; i <= 7; i++) for (int j = 1; j <= 5; j++) ma[a][i][j] = ma[a - 1][i][j];
for (int j = 1; j <= 5; j++) {
for (int i = 1; i <= 7; i++) {
if (j + 1 <= 5) {
if (ma[a][i][j] != ma[a][i][j + 1] && ma[a][i][j] != 0) {
move(a, i, j, 1), seq[a][0] = j, seq[a][1] = i, seq[a][2] = 1, dfs(a + 1);
for (int i = 1; i <= 7; i++) for (int j = 1; j <= 5; j++) ma[a][i][j] = ma[a - 1][i][j];
}
}
if (j - 1 > 0) {
if (ma[a][i][j] != ma[a][i][j - 1] && ma[a][i][j] != 0 && ma[a][i][j - 1] == 0) {
move(a, i, j, -1), seq[a][0] = j, seq[a][1] = i, seq[a][2] = -1, dfs(a + 1);
for (int i = 1; i <= 7; i++) for (int j = 1; j <= 5; j++) ma[a][i][j] = ma[a - 1][i][j];
}
}
}
}
}
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= 5; i++) {
int x, j = 1; scanf("%d", &x);
while (x != 0) ma[0][j][i] = x, scanf("%d", &x), j++;
}
dfs(1);
printf("-1\n");
return 0;
}
int main() {
scanf("%d", &T), solve();
return 0;
}
第8题 NOIP2015 斗地主 (DFS + 枚举必要性)
NOIP2015 斗地主
题意：见上。
解：最朴素的方法是枚举每个题目所给的牌型，然后判断有没有空。只有30分，30分也可以乱搞。
其实我们发现炸弹、三张牌、对子、单牌都可以一次性走完，那么我们就直接将这4种情况都合并起来一下处理，然后就不会超时了。
知识点：暴力搜索考虑重复性和后程枚举必要性。
要把题目看全面才行
//代码后面提供了一些检验数据
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int n, tax[20], ans;
int check() {
for (int i = 1; i <= 15; i++) if (tax[i]) return false;
return true;
}
void dfs(int a) {
if (a - 1 >= ans) return ;
if (check()) {
ans = std::min(ans, a - 1);
return ;
}
//三顺子 2
for (int i = 3; i <= 12; i++) if (tax[i] >= 3) {
int j = i + 1; if (j > 13) j = 1;
while (1) {
if (j == 2) break;
if (tax[j] < 3) break;
j++; if (j > 13) j = 1;
}
j--;
if (j == 1) {
int tmp = 13 - i + 1 + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 3;
tax[1] -= 3;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 3;
tax[1] += 3;
} else if (j == 0) {
int tmp = 13 - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 3;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 3;
} else {
int tmp = j - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= j; k++) tax[k] -= 3;
dfs(a + 1);
for (int k = i; k <= j; k++) tax[k] += 3;
}
}
//双顺子 3
for (int i = 3; i <= 12; i++) if (tax[i] >= 2) {
int j = i + 1; if (j > 13) j = 1;
while (1) {
if (j == 2) break;
if (tax[j] < 2) break;
j++; if (j > 13) j = 1;
}
j--;
if (j == 1) {
int tmp = 13 - i + 1 + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 2;
tax[1] -= 2;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 2;
tax[1] += 2;
} else if (j == 0) {
int tmp = 13 - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 2;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 2;
} else {
int tmp = j - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= j; k++) tax[k] -= 2;
dfs(a + 1);
for (int k = i; k <= j; k++) tax[k] += 2;
}
}
//单顺子 4
for (int i = 3; i <= 12; i++) if (tax[i] >= 1) {
int j = i + 1; if (j > 13) j = 1;
while (1) {
if (j == 2) break;
if (tax[j] < 1) break;
j++; if (j > 13) j = 1;
}
j--;
if (j == 1) {
int tmp = 13 - i + 1 + 1;
if (tmp < 5) continue;
for (int k = i; k <= 13; k++) tax[k] -= 1;
tax[1] -= 1;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 1;
tax[1] += 1;
} else if (j == 0) {
int tmp = 13 - i + 1;
if (tmp < 5) continue;
for (int k = i; k <= 13; k++) tax[k] -= 1;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 1;
} else {
int tmp = j - i + 1;
if (tmp < 5) continue;
for (int k = i; k <= j; k++) tax[k] -= 1;
dfs(a + 1);
for (int k = i; k <= j; k++) tax[k] += 1;
}
}
//四带二 1
//对子
for (int i = 1; i <= 13; i++) if (tax[i] >= 4) {
tax[i] -= 4;
for (int j = 1; j <= 13; j++) if (tax[j] >= 2) {
tax[j] -= 2;
for (int k = 1; k <= 13; k++) if (tax[k] >= 2) {
tax[k] -= 2;
dfs(a + 1);
tax[k] += 2;
}
tax[j] += 2;
}
tax[i] += 4;
}
//单牌
for (int i = 1; i <= 13; i++) if (tax[i] >= 4) {
tax[i] -= 4;
for (int j = 1; j <= 15; j++) if (tax[j] >= 1) {
tax[j] -= 1;
for (int k = 1; k <= 15; k++) if (tax[k] >= 1) {
tax[k] -= 1;
dfs(a + 1);
tax[k] += 1;
}
tax[j] += 1;
}
tax[i] += 4;
}
//三带二 5
for (int i = 1; i <= 13; i++) if (tax[i] >= 3) {
tax[i] -= 3;
for (int j = 1; j <= 13; j++) if (tax[j] >= 2) {
tax[j] -= 2;
dfs(a + 1);
tax[j] += 2;
}
tax[i] += 3;
}
//三带一 6
for (int i = 1; i <= 13; i++) if (tax[i] >= 3) {
tax[i] -= 3;
for (int j = 1; j <= 15; j++) if (tax[j] >= 1) {
tax[j] -= 1;
dfs(a + 1);
tax[j] += 1;
}
tax[i] += 3;
}
//火箭 9
if (tax[14] && tax[15]) tax[14]--, tax[15]--, dfs(a + 1), tax[14]++, tax[15]++;
int hh = a - 1;
for (int i = 1; i <= 15; i++) if (tax[i]) hh++;
ans = std::min(ans, hh);
}
void clean() {
ms(tax, 0);
}
int solve() {
clean();
for (int a, b, i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
if (a == 0) tax[13 + b]++; else tax[a]++;
}
ans = n;
dfs(1);
printf("%d\n", ans);
return 0;
}
int main() {
int T; scanf("%d%d", &T, &n);
while (T--) solve();
return 0;
}
/*
//单，三顺子
1 10
4 1
4 2
4 3
5 1
5 2
5 3
6 1
6 2
6 3
13 1
//单，双顺子
1 7
4 1
4 2
5 1
5 2
6 1
6 2
5 3
//单，顺子
1 9
1 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
2 2
//单，双，火箭
1 6
0 1
0 2
1 3
1 2
2 1
13 5
//炸
1 4
3 1
3 2
3 3
3 4
//三张
1 3
3 1
3 2
3 3
//三带一
1 4
3 1
3 2
3 3
13 1
//三带二
1 5
3 1
3 2
3 3
13 1
13 2
//四带二
1 6
3 1
3 2
3 3
3 4
13 1
13 2
*/
第9题 NOIP2003 传染病控制 (DFS + 枚举必要性)
NOIP2003 传染病控制
题意：见上。
解：本题相当于每一层删掉一个子树，那么我们预处理每一层的点，用 DFS 按层删除子树即可。
1、如果一个子树被删除了就要打上标记，然后如果一个子树已经在一个打了标记的子树中，就不要删除这个子树。这里判断就暴力枚举祖先节点就行。
2、如果一层一个节点都没删除，那么就是已经处理完毕了，直接更新答案即可，类似斗地主思想，不要 DFS 一个个下去，很慢很慢很慢，直接处理即可
知识点：这种数据1000以内的都可能是搜索题，但是必要剪枝。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 300 + 5;
int n, p, fa[MAXN], dep[MAXN], siz[MAXN], ans = 0, maxd = 0, vis[MAXN];
std::vector<int > G[MAXN], whw[MAXN];
void dfs1(int u, int pa) {
dep[u] = dep[pa] + 1, siz[u] = 1, fa[u] = pa;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) dfs1(v, u), siz[u] += siz[v];
}
}
void dfs2(int a, int tmp) {
if (a == maxd + 1) {
ans = std::max(ans, tmp);
return ;
}
int gg = 0;
for (int i = 0; i < (int)whw[a].size(); i++) {
int u = whw[a][i], nmd = u, fl = 0;
while (nmd != 1) {
if (vis[nmd]) {fl = 1; break;}
nmd = fa[nmd];
}
if (fl) continue;
gg = 1, vis[u] = 1, dfs2(a + 1, tmp + siz[u]), vis[u] = 0;
}
if (!gg) ans = std::max(ans, tmp);
}
void clean() {
ms(vis, 0), ms(dep, 0), ms(siz, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= p; i++) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
dfs1(1, 0);
for (int i = 1; i <= n; i++) whw[dep[i]].push_back(i), maxd = std::max(maxd, dep[i]);
dfs2(2, 0);
printf("%d\n", n - ans);
return 0;
}
int main() {
scanf("%d%d", &n, &p), solve();
return 0;
}
第10题 NOIP2017 时间复杂度 (栈模拟)
NOIP2017 时间复杂度
题意：虽然这是个栈模拟题……
解：用栈维护模拟即可。
注意如果语法错误不能立刻退出，否则就会对后面的数据造成影响。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
struct data {
char ch;
int bj, gg;
};
int L, fzd, top, vis[30];
char s[500];
data st[105];
void clean() {
ms(vis, 0), fzd = top = 0;
}
int solve() {
clean();
scanf("%d%s", &L, s);
//复杂度
if (s[2] == '1') fzd = 0; else {
int tmp = 0, i = 4;
while ('0' <= s[i] && s[i] <= '9') tmp = tmp * 10 + s[i] - '0', ++i;
fzd = tmp;
//printf("%d\n", fzd);
}
int ans = 0, now = 0, cs = 0, fl = 0;
for (int i = 1; i <= L; ++i) {
scanf("%s", s);
if (s[0] == 'F') {
++cs;
scanf("%s", s);
char c = s[0];
if (vis[c - 'a']) fl = 1;
int hh = false, jj = false;
scanf("%s", s);
if (s[0] == 'n') {
scanf("%s", s);
if (s[0] != 'n') hh = true;//x 是 n，y 不是 n，显然不能进入循环
else jj = true, --cs;//x y 都是 n
} else {
int tmp1 = 0, tmp2 = 0, j = 0;
while ('0' <= s[j] && s[j] <= '9') tmp1 = tmp1 * 10 + s[j] - '0', ++j;
scanf("%s", s);
if (s[0] != 'n') {//x y 都是数字
int k = 0;
while ('0' <= s[k] && s[k] <= '9') tmp2 = tmp2 * 10 + s[k] - '0', ++k;
if (tmp1 > tmp2) hh = true;//x y 都是数字，x 比 y 大，显然不能进入循环
else jj = true, --cs; //x y 都是数字，x 比 y 小
}
//x 是数字, y 是 n
}
vis[c - 'a'] = 1, st[++top] = (data){c, now, jj};
now |= hh;
if (!now) ans = std::max(ans, cs);
} else if (s[0] == 'E') {
if (top == 0) {fl = 1;continue;}
data b = st[top]; --top;
vis[b.ch - 'a'] = 0, now = b.bj, cs -= !b.gg;
}
}
if (fl || top != 0) return printf("ERR\n"), 0;
if (ans == fzd) printf("Yes\n"); else printf("No\n");
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
第11题 NOIP2017 棋盘 (记忆化 DFS)
NOIP2017 棋盘
题意：见上。
解：
BFS解法：根据 BFS 转移费用为1第一次找到为最短路来优化复杂度。我们让同色之间转移费用设为1，然后异色之间转移费用拆成两步进行，相当于这个转移拆成两个费用为1的转移。对于魔法，我们拆成4步或者6步进行，具体类似上面的操作。这样 vis 数组就要加维。然而拆转移后状态不多，可以轻松AC。
记忆化搜索：直接搜索，然后最优化剪枝，每个坐标点记忆化一个最优解，最优化剪枝即可。
注意这题如果目标点没颜色如果能魔法就可以到达的！
知识点：
1、记忆化搜索-搜索-DP之间密切联系
2、不要忘记特殊情况的考虑
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
struct data {int x, y, rm, dis, tms;};
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int m, n, ma[105][105], vis[105][105][10];
queue<data > q;
void clean() {
ms(ma, -1), ms(vis, 0);
}
int solve() {
scanf("%d%d", &m, &n);
clean();
for (int x, y, c, i = 1; i <= n; ++i) scanf("%d%d%d", &x, &y, &c), ma[x][y] = c;
vis[1][1][0] = 1, q.push((data){1, 1, 0, 0, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
//printf("x=%d, y=%d, rm=%d, dis=%d, tms=%d\n", p.x, p.y, p.rm, p.dis, p.tms);
if (p.rm != 0) {
if (!vis[p.x][p.y][p.rm - 1]) q.push((data){p.x, p.y, p.rm - 1, p.dis + 1, p.tms}), vis[p.x][p.y][p.rm - 1] = 1;
continue;
}
if (p.x == m && p.y == m && p.rm == 0) return printf("%d\n", p.dis - p.tms), 0;
for (int i = 0; i < 4; i++) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx > 0 && ty > 0 && tx <= m && ty <= m) {
if (ma[p.x][p.y] == 0) {
if (ma[tx][ty] == 0 && !vis[tx][ty][0]) q.push((data){tx, ty, 0, p.dis + 1, p.tms + 1}), vis[tx][ty][0] = 1;
else if (ma[tx][ty] == 1 && !vis[tx][ty][1]) q.push((data){tx, ty, 1, p.dis + 1, p.tms + 1}), vis[tx][ty][1] = 1;
} else if (ma[p.x][p.y] == 1) {
if (ma[tx][ty] == 0 && !vis[tx][ty][1]) q.push((data){tx, ty, 1, p.dis + 1, p.tms + 1}), vis[tx][ty][1] = 1;
else if (ma[tx][ty] == 1 && !vis[tx][ty][0]) q.push((data){tx, ty, 0, p.dis + 1, p.tms + 1}), vis[tx][ty][0] = 1;
}
if (ma[tx][ty] < 0) {
if (tx == m && ty == m) return printf("%d\n", p.dis - p.tms + 2), 0;
for (int j = 0; j < 4; j++) {
int gx = tx + dx[j], gy = ty + dy[j];
if (gx == p.x && gy == p.y) continue;
if (gx > 0 && gy > 0 && gx <= m && gy <= m && (ma[gx][gy] == 0 || ma[gx][gy] == 1)) {
if (ma[p.x][p.y] == 0) {
if (ma[gx][gy] == 0 && !vis[gx][gy][3]) q.push((data){gx, gy, 3, p.dis + 1, p.tms + 2}), vis[gx][gy][3] = 1;
else if (ma[gx][gy] == 1 && !vis[gx][gy][4]) q.push((data){gx, gy, 4, p.dis + 1, p.tms + 2}), vis[gx][gy][4] = 1;
} else if (ma[p.x][p.y] == 1) {
if (ma[gx][gy] == 0 && !vis[gx][gy][4]) q.push((data){gx, gy, 4, p.dis + 1, p.tms + 2}), vis[gx][gy][4] = 1;
else if (ma[gx][gy] == 1 && !vis[gx][gy][3]) q.push((data){gx, gy, 3, p.dis + 1, p.tms + 2}), vis[gx][gy][3] = 1;
}
}
}
}
}
}
}
printf("-1\n");
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第12题 Poj 1691 Painting A Board (DFS + 最优化剪枝)
Poj 1691
题意：有这样一个面板（如下图），分成大大小小的矩形块。现在要对其上色，每个矩形块上一种颜色，颜色已经预先指定好。每次对一个矩形区域上色，要求必须在该矩形区域上方的所有矩形区域已经被上色后，才能对该矩形区域上色。如下图：如果要对F区域上色，则在它上面的区域A、B、C、D必须已经被上色。又每次上色，选择一种特定眼色的笔刷，例如选择蓝色，对A上色，此时可继续对C上色，无需更改颜色。之后，则只能对B区域上色了，则要选择红色笔刷，所以笔刷的使用次数加1。如果后续过程中，又要重新选择蓝色笔刷，则笔刷仍加1。问：所需的最少笔刷个数？
解：判断是否有矩形在上面用线段交。然后每个矩形预处理一个上面的矩形状态，每次DFS找到能刷的刷完再看换颜色刷的情况。
知识点：1、要记得加最优化剪枝
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 20;
struct rc {
int xl, yl, xr, yr;
int st, col;
} jx[MAXN];
int n, vis[MAXN], ans;
bool check(int i, int j) {
if (jx[i].xr >= jx[j].xl && jx[i].xr <= jx[j].xr) return 1;
return 0;
}
void dfs(int step, int st, int col) {
while (1) {
int fl = 0;
for (int i = 1; i <= n; ++i) if (!vis[i]) {
if (jx[i].col != col) continue ;
if ((jx[i].st & st) == jx[i].st) {
st += (1 << (i - 1)), vis[i] = step, fl = 1;
}
}
if (!fl) break;
}
int fl = 0;
for (int i = 1; i <= n; ++i) if (!vis[i]) fl = 1;
if (!fl) {
ans = min(ans, step);
for (int i = 1; i <= n; ++i) if (vis[i] == step) vis[i] = 0;
return ;
}
for (int i = 1; i <= n; ++i) if (!vis[i]) {
if ((jx[i].st & st) == jx[i].st) {
vis[i] = step + 1;
dfs(step + 1, st + (1 << (i - 1)), jx[i].col);
vis[i] = 0;
}
}
for (int i = 1; i <= n; ++i) if (vis[i] == step) vis[i] = 0;
}
void clean() {
ans = 1000000000, ms(vis, 0);
}
int solve() {
cin >> n;
clean();
for (int i = 1; i <= n; ++i) scanf("%d%d%d%d%d", &jx[i].yl, &jx[i].xl, &jx[i].yr, &jx[i].xr, &jx[i].col);
for (int i = 1; i <= n; ++i) {
jx[i].st = 0;
for (int j = 1; j <= n; ++j) if (i != j) {
if (jx[j].yr == jx[i].yl && (check(i, j) || check(j, i))) jx[i].st += (1 << (j - 1));
}
}
for (int i = 1; i <= n; ++i) if (jx[i].st == 0) vis[i] = 1, dfs(1, (1 << (i - 1)), jx[i].col), vis[i] = 0;
printf("%d\n", ans);
return 0;
}
}
int main() {
int T; scanf("%d", &T);
while (T--) flyinthesky::solve();
return 0;
}
第13题 Poj 2308 (DFS + 可行性剪枝)
Poj 2308
题意：连连看判是否有解。
解：DFS中途BFS。DFS看哪个点没消除用BFS找这个点能和哪个其他点消除，然后DFS递归消除即可。注意剪枝，如果出现
AB
BA
并且AB就各只有2个，则无解，直接退出本层DFS。
知识点：
1、无解早判省时间
2、DFS不要局限于下一步，下一个坐标，而是整体上的，适当情况下可以用BFS辅助。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, a[15][15]; // 原矩阵
int sz, whw[200][2]; // 可行消除方案
int vis[15][15];
int cnt, num[10], flag = 0; // 记录，答案
struct data {int x, y, fx, gj;};
bool check() {
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
if(!a[i][j] || !a[i][j + 1]) continue ;
if (a[i][j] == a[i + 1][j + 1] && a[i + 1][j] == a[i][j + 1] && num[a[i][j]] == 2 && num[a[i + 1][j]] == 2) return true;
}
}
return false;
}
void bfs(int x, int y, int col) {
queue<data > q;
ms(vis, 67), vis[x][y] = 0, q.push((data){x, y, -1, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
//if (col == 1) cerr << p.x << " " << p.y << " " << p.gj << endl;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i], tgj = p.gj;
if (tx <= 0 || ty <= 0 || tx > n || ty > m) continue ;
if (i != p.fx && p.fx != -1) ++tgj; // 拐角判断
if (tgj > 2) continue ;
if (vis[tx][ty] < tgj) continue ;
vis[tx][ty] = tgj; // 不如那么优
if (a[tx][ty] == col) { // 找到同一颜色
whw[++sz][0] = tx, whw[sz][1] = ty; // 记录位置
continue ;
}
if (a[tx][ty]) continue ; // 有方块挡着
q.push((data){tx, ty, i, tgj});
}
}
}
void dfs(int rm) {
if (rm == 0) {
flag = 1; return ;
}
if (check()) return ;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == 0) continue ;
sz = 0;
bfs(i, j, a[i][j]);
//for (int k = 1; k <= sz; ++k) cerr << "i=" << i << " j=" << j << "pos=" << whw[k][0] << " " << whw[k][1] << endl;
int col = a[i][j];
num[col] -= 2;
a[i][j] = 0;
for (int k = 1; k <= sz; ++k) {
a[whw[k][0]][whw[k][1]] = 0;
dfs(rm - 2);
a[whw[k][0]][whw[k][1]] = col;
}
num[col] += 2;
a[i][j] = col;
}
}
}
void clean() {
ms(num, 0), cnt = 0, ms(a, 0), ms(whw, 0), flag = 0;
}
int solve() {
clean();
char s[15];
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
int len = strlen(s + 1);
for (int j = 1; j <= len; ++j) {
if (s[j] != '*') ++cnt, ++num[s[j] - 'A' + 1], a[i][j] = s[j] - 'A' + 1;
}
}
dfs(cnt);
if (flag) printf("yes\n"); else printf("no\n");
return 0;
}
}
int main() {
while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && (flyinthesky::n && flyinthesky::m)) flyinthesky::solve();
return 0;
}
第14题 Poj 3322 (BFS)
Poj 3322
题意：题目中游戏最小步数。
解：如果方块是一个，那就是裸BFS。将移动转移写到增量数组中，然后每个方块状态以他两个坐标值最小的方格为主要格子。然后 BFS 即可。
知识点：
1、BFS / DFS 选用
2、多方格搜索要定义一个主格 (状压放$1 \times 2$方块也有类似方法)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int dx[3][4] = {{-2, 1, 0, 0}, {2, -1, 0, 0}, {0, 0, 1, -1}};
const int dy[3][4] = {{ 0, 0, -2, 1}, {0, 0, -1, 1}, {2, -1, 0, 0}};
const int dz[3][4] = {{ 1, 1, 2, 2}, {0, 0, 1, 1}, {0, 0, 2, 2}};
struct data {int x, y, z, stp;};
int n, m, endx, endy, stx, sty, stz, vis[505][505][5];
char s[505][505];
bool check(int x, int y, int z) {
if (x <= 0 || y <= 0 || x > n || y > m) return 0;
if (z == 0) {
if (s[x][y] != '#' && s[x][y] != 'E') return 1;
} else if (z == 1) {
if (s[x][y] != '#' && s[x + 1][y] != '#') return 1;
} else if (z == 2) {
if (s[x][y] != '#' && s[x][y + 1] != '#') return 1;
}
return 0;
}
void clean() {
stx = sty = stz = endx = endy = 0, ms(vis, 0);
}
int solve() {
for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
clean();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (s[i][j] == 'O') endx = i, endy = j;
if (!stx && s[i][j] == 'X' && s[i + 1][j] == 'X') stx = i, sty = j, stz = 1;
else if (!stx && s[i][j] == 'X' && s[i][j + 1] == 'X') stx = i, sty = j, stz = 2;
else if (!stx && s[i][j] == 'X') stx = i, sty = j, stz = 0;
}
// cerr << stx << " " << sty << " " << stz << " " << endl;
// cerr << endx << " " << endy << endl;
queue<data > q;
vis[stx][sty][stz] = 1, q.push((data){stx, sty, stz, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
// cerr << p.x << " " << p.y << " " << p.z << endl;
if (p.x == endx && p.y == endy && !p.z) return printf("%d\n", p.stp), 0;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[p.z][i], ty = p.y + dy[p.z][i], tz = dz[p.z][i];
if (vis[tx][ty][tz]) continue ; vis[tx][ty][tz] = 1;
if (!check(tx, ty, tz)) continue ;
q.push((data){tx, ty, tz, p.stp + 1});
}
}
printf("Impossible\n");
return 0;
}
}
int main() {
while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && flyinthesky::n && flyinthesky::m) flyinthesky::solve();
return 0;
}
/*
3 3
X..
...
..O
*/
第15题 Poj 1475 (BFS套BFS+状态简化)
Poj 1475
题意：推箱子游戏。
解：先 BFS 箱子的位移，然后再进行 BFS 人能不能到另一侧。状态记录人的位置，箱子的位置。由于箱子的位置和箱子上一次从哪里推来知道就能得出人的位置，所以 $vis$ 只用记录三维。
知识点：
1、搜索状态简化，类似差值DP
2、BFS 套 BFS
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<string>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
int kse = 0;
namespace flyinthesky {
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = { 0, 0, 1, -1};
const char upfx[4] = {'N', 'S', 'E', 'W'};
const char lwfx[4] = {'n', 's', 'e', 'w'};
struct data {int x, y, px, py; string s;};
struct data2 {int x, y; string s; };
int n, m, Tx, Ty, Sx, Sy, Bx, By, vis[25][25][4], v2[25][25];
char ma[25][25];
string ans, bs;
bool insd(int x, int y) {
if (x > 0 && y > 0 && x <= n && y <= m) return true;
return false;
}
bool bfsyou(int px, int py, int gx, int gy, int bx, int by) { // you position, goal position
queue<data2 > q;
ms(v2, 0), v2[px][py] = v2[bx][by] = 1, bs = "";
q.push((data2){px, py, ""});
while (!q.empty()) {
data2 p = q.front(); q.pop();
if (p.x == gx && p.y == gy) return bs = p.s, true;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (!insd(tx, ty)) continue ;
if (v2[tx][ty]) continue ;
if (ma[tx][ty] == '#') continue ;
if (tx == bx && ty == by) continue ;
v2[tx][ty] = 1;
q.push((data2){tx, ty, p.s + lwfx[i]});
}
}
return false;
}
bool bfsbox() {
queue<data > q;
ans = "", ++kse;
q.push((data){Bx, By, Sx, Sy, ""});
while (!q.empty()) {
data p = q.front(); q.pop();
// p.x, p.y 当前箱子所在
// px, py 目标玩家位置
// tx，ty 目标箱子位置
if (p.x == Tx && p.y == Ty) return ans = p.s, true;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i];
int px = p.x - dx[i], py = p.y - dy[i];
if (!insd(tx, ty)) continue ;
if (!insd(px, py)) continue ;
if (ma[tx][ty] == '#') continue ;
if (ma[px][py] == '#') continue ;
if (vis[tx][ty][i] == kse) continue ;
//cerr << "!!!" << p.px << " " << p.py << " " << px << " " << py << " " << tx << " " << ty << endl;
if (bfsyou(p.px, p.py, px, py, p.x, p.y)) {
// cerr << "???" << tx << " " << ty << " " << p.x << " " << p.y << endl;
q.push((data){tx, ty, p.x, p.y, p.s + bs + upfx[i]}), vis[tx][ty][i] = kse;
}
}
}
return false;
}
void clean() {
ms(vis, 0);
}
int solve() {
for (int i = 1; i <= n; ++i) scanf("%s", ma[i] + 1);
clean();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (ma[i][j] == 'S') Sx = i, Sy = j;
if (ma[i][j] == 'T') Tx = i, Ty = j;
if (ma[i][j] == 'B') Bx = i, By = j;
}
if (bfsbox()) {
printf("Maze #%d\n", kse);
cout << ans << endl << endl;
} else printf("Maze #%d\nImpossible.\n\n", kse);
return 0;
}
};
int main() {
while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && flyinthesky::n && flyinthesky::m) flyinthesky::solve();
return 0;
}
第16题 Poj 1324 (状压BFS+状态简化)
Poj 1324
题意：贪吃蛇。要求蛇头到$(1,1)$的最短路程。
解：BFS。然后状态状压判重。发现这里蛇身体都相邻，所以只用记录某个方块和哪个相邻即可。
知识点：BFS 开函数写不要写在 solve 里！！！
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int kse = 0;
namespace flyinthesky {
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {
int x, y, fx[10], bs;
};
int n, m, L, Hx, Hy, Bx[10], By[10], ma[22][22];
int vis[22][22][4][4][4][4][4][4][4];
void clean() {
ms(vis, 0), ms(Bx, 0), ms(By, 0), ms(ma, 0);
}
int solve() {
scanf("%d%d", &Hx, &Hy);
clean();
for (int i = 1; i < L; ++i) scanf("%d%d", &Bx[i], &By[i]);
int k; scanf("%d", &k); for (int x, y, i = 1; i <= k; ++i) scanf("%d%d", &x, &y), ma[x][y] = 1;
// printf("%.3f\n", (sizeof vis) / 1048576.0);
int fx[10];
ms(fx, 0);
for (int i = 0; i < 4; ++i) if ((Bx[1] == Hx + dx[i]) && (By[1] == Hy + dy[i])) {fx[1] = i; break ;}
for (int o = 1; o < L - 1; ++o) {
if (Bx[o] == 0 && By[o] == 0) break ;
for (int i = 0; i < 4; ++i) if ((Bx[o + 1] == Bx[o] + dx[i]) && (By[o + 1] == By[o] + dy[i])) {fx[o + 1] = i; break ;}
}
// for (int i = 1; i <= 7; ++i) cerr << fx[i] << endl;
vis[Hx][Hy][fx[1]][fx[2]][fx[3]][fx[4]][fx[5]][fx[6]][fx[7]] = 1;
data gg; gg.x = Hx, gg.y = Hy, gg.bs = 0; for (int i = 1; i <= 7; ++i) gg.fx[i] = fx[i];
queue<data > q; q.push(gg);
while (!q.empty()) {
data p = q.front(); q.pop();
// cerr << "***" << p.x << " " << p.y << endl;
// for (int i = 1; i <= 7; ++i) cerr << p.fx[i] << " ";
// cerr << endl;
if (p.x == 1 && p.y == 1) return printf("Case %d: %d\n", ++kse, p.bs), 0;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx <= 0 || ty <= 0 || tx > n || ty > m) continue ;
if (ma[tx][ty] == 1) continue ;
// check 1
int nx = p.x, ny = p.y, fl = 0;
// cerr << "!!!" << tx << " " << ty << endl;
for (int j = 1; j < L; ++j) {
nx += dx[p.fx[j]], ny += dy[p.fx[j]];
// cerr << "???" << nx << " " << ny << endl;
if (tx == nx && ty == ny) {fl = 1; break ;}
}
if (fl) continue ;
// check 2
data gg; gg.x = tx, gg.y = ty, gg.bs = p.bs + 1, ms(gg.fx, 0); for (int j = 2; j < L; ++j) gg.fx[j] = p.fx[j - 1];
for (int j = 0; j < 4; ++j) if (tx + dx[j] == p.x && ty + dy[j] == p.y) {gg.fx[1] = j; break ;}
/* if(tx == 5 && ty == 1) {
cerr << "Fuck";
for (int i = 1; i <= 7; ++i) cerr << gg.fx[i] << " ";
cerr << endl;
}*/
if (vis[tx][ty][gg.fx[1]][gg.fx[2]][gg.fx[3]][gg.fx[4]][gg.fx[5]][gg.fx[6]][gg.fx[7]] == 1) continue ;
// in queue
vis[tx][ty][gg.fx[1]][gg.fx[2]][gg.fx[3]][gg.fx[4]][gg.fx[5]][gg.fx[6]][gg.fx[7]] = 1;
// cerr << vis[5][1][2][1][1][2][2][0][0] << endl;
q.push(gg);
}
}
printf("Case %d: %d\n", ++kse, -1);
return 0;
}
}
int main() {
while (scanf("%d%d%d", &flyinthesky::n, &flyinthesky::m, &flyinthesky::L) == 3 &&
flyinthesky::n && flyinthesky::m && flyinthesky::L)
flyinthesky::solve();
return 0;
}
第17题 Poj 2248 Addition Chains (迭代加深 DFS)
考虑对于每个位置 $k$ 枚举 $i,j$ 成为 $k$ 位置的值。
观察样例，层数不会太大，即 $m$ 不会太大，所以迭代加深搜索即可。
剪枝：
1、可行性剪枝
A：a[i] + a[j] > n 则剪枝
2、搜索顺序
A：从大到小枚举$i,j$以尽快逼近$n$
3、冗余排除
A：a[i] + a[j] 相等的不要二次进行分支
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 200;
int fl, len, n, a[MAXN];
void dfs(int ith) {
bool vis[101];
if (fl) return ;
if (ith > len) {
if (a[ith - 1] == n) fl = 1;
return ;
}
ms(vis, 0);
for (int i = ith - 1; i >= 0; --i)
for (int j = ith - 1; j >= 0; --j) {
if (fl) return ;
if (a[i] + a[j] > n) continue ;
if (a[i] + a[j] <= a[ith - 1]) continue ;
if (vis[a[i] + a[j]]) continue ;
vis[a[i] + a[j]] = 1;
a[ith] = a[i] + a[j];
dfs(ith + 1);
}
}
void clean() {
fl = 0;
len = 1;
a[0] = 1;
}
int solve() {
clean();
if(n == 1) {printf("1\n"); return 0;}
while (1) {
for (int i = 1; i <= len; ++i) a[i] = 0;
a[len] = n;
dfs(1);
if (fl) {
for (int i = 0; i <= len; ++i) printf("%d ", a[i]);
printf("\n");
break ;
}
++len;
}
return 0;
}
}
int main() {
while (scanf("%d", &flyinthesky::n) == 1 && flyinthesky::n) flyinthesky::solve();
return 0;
}
第18题 CH 2401 (折半搜索+DFS)
CH 2401
题意：值域为$2^{31}-1$的01背包。
解：暴力即可。折半搜索减半复杂度。
将物品分成两半，前一半的答案存进桶/set/map/平衡树里，后一半答案边 DFS 边查询更新合并。
剪枝：
A: 降序排序
B: 适当增加前面一半的物品数量 (只在后半段用二分的话)
这里代码用set被卡两个点。
知识点：这种搜索爆炸又是搜索的题目就要像到折半搜索。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 45 + 5;
LL w, n, g[MAXN], m, ans = 0;
set<LL > s;
void dfs1(LL a, LL v) {
if (v > w) return ;
s.insert(-v);
if (a > m) return ;
dfs1(a + 1, v), dfs1(a + 1, v + g[a]);
}
void dfs2(LL a, LL v) {
if (v > w) return ;
set<LL >::iterator it = s.lower_bound(-(w - v));
ans = max(ans, v);
if (it != s.end()) if (v + -*it <= w) ans = max(ans, v + -*it);
if (a > n) return ;
dfs2(a + 1, v), dfs2(a + 1, v + g[a]);
}
bool cmp(int a, int b) {return a > b;}
void clean() {
}
int solve() {
clean();
scanf("%lld%lld", &w, &n);
for (LL i = 1; i <= n; ++i) scanf("%lld", &g[i]);
sort(g + 1, g + 1 + n, cmp);
m = n / 2 + 2;
dfs1(1, 0);
dfs2(m + 1, 0);
printf("%lld\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
