(ACM) 课第三次作业-搜索
(A. Sum It Up)
题意
给定 (t) 和 (n) 个整数 (x_{i})，从 (n) 个整数中挑任意个数，使得它们的和为 (t)
输入格式
多组数据，(nleq 12, tleq 1000, x_{i}leq 100)
输出格式
数字之间添 (+) 号，不考虑顺序（(2 + 2 + 1) 与 (2 + 1 + 2) 看作同一个），按照字典序列从大到小输出所有组合
题解
由于 (n) 很小，故考虑二进制枚举，然后 (check)
由于不考虑顺序，所以对于每一个枚举的情况都要用 (map) 记忆化一下，即 map<multiset<int>, int>
输出结果用字符串拼接，放到容器里面排序即可
(code)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 4e2 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
int t, n, cnt, a[20];
set<string, greater<string> > st;
map<multiset<int>, int> mp;
bool check(int x)
{
int res = 0;
for(int i = 0; i < n; ++i) {
if(x & (1 << i)) res += a[i];
}
return res == t;
}
int main()
{
while(scanf("%d %d", &t, &n) && t && n) {
mp.clear(), st.clear();
for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
printf("Sums of %d:
", t);
for(int i = 0; i < (1 << n); ++i) {
if(check(i)) {
string temp = "";
multiset<int> mlst;
for(int j = 0; j < n; ++j)
if(i & (1 << j)) temp += a[j] + '0', mlst.insert(a[j]);
if(!mp[mlst]) {
mp[mlst] = 1;
st.insert(temp);
}
}
}
int cnt = st.size();
if(!cnt) puts("NONE");
else {
for(auto i: st) {
int len = i.length();
for(int j = 0; j < len; ++j)
printf("%d%c", i[j] - '0', "+
"[j == len - 1]);
}
}
}
return 0;
}
/*
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
*/
时间复杂度
(O(2^{n}cdot n))，极限也就 (2^{12}cdot 12)
(B. Fling)
题意
给定一个 (7 imes 8) 的地图，上面分布着至多 (12) 个小球，每个小球可以向上下左右四个方向移动（'U', 'L', 'R', 'D'）
对于每一个小球，只有两种情况它无法移动
-
其当前移动方向上没有小球
-
其当前移动方向上紧挨着一个小球
小球会传递动能
- 对于每一个小球 (i)，若它在移动过程中撞到另一个小球 (j)，那么 (i) 会立刻停在 (j) 的前一个位置，而 (j) 继续按当前方向移动
- 若 (j) 与 另一个小球 (k) 紧邻，那么 (j) 不动，(k) 按当前方向移动，直到它掉落，以此类推
输入格式
多组数据
输出格式
输出 (i, j, k) ，分别代表小球的横坐标、纵坐标和移动方向
若有多个答案，按照字典序最小的输出
题解
这是一个游戏，玩一玩就能理解题意
对于计算机而言，最好的策略就是一步一步尝试
任取一个球，向四个方向搜索，若搜索成功，则更新图，继续搜索；若搜索失败，则回溯，把图复原，换方向继续搜索
(dfs) 实际上就是一个穷尽所有可能，搜索、回溯的过程
- 往下搜索更新状态
- 往上回溯复原状态
考虑可行性剪枝
用一个字符串维护答案，若当前得到的答案字符串已经比我们之前的答案大，那么没必要继续搜索，返回即可
注意开一个临时数组 (temp\_g) 存储地图，便于回溯的时候复原地图，但是 (temp\_g) 得设置成局部变量
(code)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 4e2 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
const int n = 7, m = 8;
const int D1[] = {-1, 0, 0, 1};
const int D2[] = {0, -1, 1, 0};
const char D[] = {'U', 'L', 'R', 'D'};
int vis[20][20], caseNum;
char g[20][20];
string ans;
struct node
{
int x, y;
char d;
node() {}
node(int _x, int _y, char _d) {x = _x, y = _y, d = _d;}
};
bool check(int s, int t) {return s >= 0 && s < n && t >= 0 && t < m;}
void dfs(int num, string &str)
{
if(num == 1) {
if(ans != "" && ans > str || ans == "") ans = str;
return;
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(g[i][j] == 'O') {
for(int k = 0; k < 4; ++k) {
if(check(i + D1[k], j + D2[k]) && g[i + D1[k]][j + D2[k]] == 'O') continue;
int f = 0;
for(int s = i + D1[k], t = j + D2[k]; check(s, t); s += D1[k], t += D2[k]) {
if(g[s][t] == 'O') {
f = 1;
break;
}
}
if(!f) continue;
else {//进入这个分支，就保证了从 i, j 往 k 方向移动球，一定可以移动
char temp_g[20][20] = {0}; //这个 temp 不能设为全局变量，否则会出错
memcpy(temp_g, g, sizeof(g));
g[i][j] = 'X';
for(int s = i + D1[k], t = j + D2[k]; check(s, t); s += D1[k], t += D2[k]) {
if(g[s][t] == 'O') {
g[s - D1[k]][t - D2[k]] = 'O';
g[s][t] = 'X';
}
}
str += i + '0', str += j + '0', str += D[k];
//cout<<str<<endl;
if(ans != "" && str > ans) { // 可行性剪枝，字典序小的答案不继续搜索
for(int it = 0; it < 3; ++it) str.erase(--str.end());
return;
}
dfs(num - 1, str);
for(int it = 0; it < 3; ++it) str.erase(--str.end()); //删除迭代器比赋值更快一点
memcpy(g, temp_g, sizeof(temp_g));
}
}
}
}
}
return;
}
int main()
{
while(~scanf("%s", g[0])) {
for(int i = 1; i < n; ++i)
scanf("%s", g[i]);
int cnt = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(g[i][j] == 'O') ++cnt;
string res = "";
dfs(cnt, res);
if(caseNum) puts(""); //诡异的输出格式
printf("CASE #%d:
", ++caseNum);
if(ans != "") {
int len = ans.length();
for(int i = 0; i < len; i += 3) {
putchar(ans[i]), putchar(' ');
putchar(ans[i + 1]), putchar(' ');
putchar(ans[i + 2]), puts("");
}
}
memset(g, 0, sizeof(g));
ans = "";
}
return 0;
}
后记
我一开始打算穷尽所有可能，把可行的答案字符串全部存起来，最后排序输出最小的
不幸得，代码 (T) 了
迫不得已考虑可行性剪枝，结果时间不仅减下来了，代码长度也缩减了很多
(C. N) 皇后
题意
在 (N imes N) 的棋盘上放置 (N) 个皇后，任意两个皇后需要满足
- 不在同一行
- 不在同一列
- 不处在与棋盘呈 (45^{circ}) 角的直线上
输入格式
多组数据，(Nleq 10)
输出格式
输出方案数
题解
经典题，考虑 (dfs)
枚举行，用 (col[i], d1[i], d2[i]) 维护列，两个对角线
对于处在斜率为 (-1) 的同一条直线上的两个皇后 (i_{1}, j_{1}, i_{2}, j_{2})，满足 (i_{1} - j_{1} = i_{2} - j_{2})
对于处在斜率为 (1) 的同一条直线上的两个皇后 (i_{1}, j_{1}, i_{2}, j_{2})，满足 (i_{1} + j_{1} = i_{2} + j_{2})
用上述条件进行可行性剪枝即可
对于此题，先预处理出答案，然后回答查询
(code)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 4e2 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
int n, col[20];
map<int, int> mp1, mp2;
void dfs(int x, int n, int &ans)
{
if(x == n + 1) {
ans++;
return;
}
for(int i = 1; i <= n; ++i) {
if(!col[i] && !mp1[i - x] && !mp2[i + x]) {
mp1[i - x] = mp2[i + x] = 1;
col[i] = 1;
dfs(x + 1, n, ans);
mp1[i - x] = mp2[i + x] = 0;
col[i] = 0;
}
}
}
int main()
{
int ans[20] = {0};
for(int i = 1; i <= 10; ++i) {
memset(col, 0, sizeof(col));
mp1.clear(), mp2.clear();
dfs(1, i, ans[i]);
}
while(scanf("%d", &n) && n) {
printf("%d
", ans[n]);
}
return 0;
}
/*
1
8
5
0
*/
后记
这题一开始没有预处理，狂 (T)
(D. Find a way)
题意
给定一个 (n imes m) 的地图，上面分布了多个 (KFC)，# 表示不可走，其他均表示可走，走一个单位耗时 (11) 分钟
两个小憨批 (Y, M) 约着在某个 (KFC) 相遇，假设他们同时出发，求他们的最短相遇时间
输入格式
多组数据，(2leq n, mleq 200)
输出格式
输出最短相遇时间
题解
以 (Y, M) 为起点分别作 (1) 次 (bfs)，对每个 (KFC) 维护一个俩人相遇所耗费的时间，最后取最小值即可
(code)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%f%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 4e2 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
int n, m, dis[207][207], vis[207][207];
char g[207][207];
struct node
{
int x, y, step;
node() {}
node(int _x, int _y, int _step) {x = _x, y = _y, step = _step;}
};
void bfs(int s, int t)
{
queue<node> q;
q.push(node(s, t, 0));
vis[s][t] = 1;
while(!q.empty()) {
node temp = q.front(); q.pop();
if(g[temp.x][temp.y] == '@') dis[temp.x][temp.y] += temp.step;
for(int i = 1; i <= 4; ++i) {
int sx = temp.x + DX[i], sy = temp.y + DY[i];
if(sx >= 1 && sx <= n && sx >= 1 && sy <= m && g[sx][sy] != '#' && !vis[sx][sy]) {
q.push(node(sx, sy, temp.step + 1));
vis[sx][sy] = 1;
}
}
}
}
int main()
{
while(~scanf("%d %d", &n, &m)) {
memset(dis, 0, sizeof(dis));
for(int i = 1; i <= n; ++i)
scanf("%s", g[i] + 1);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(g[i][j] == 'Y' || g[i][j] == 'M') memset(vis, 0, sizeof(vis)), bfs(i, j);
}
}
int ans = inf;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(g[i][j] == '@') ans = min(ans, dis[i][j]);
printf("%d
", ans * 11);
}
return 0;
}