保研機試整理-搜尋
-模擬窮舉
-Bfs 廣度優先搜尋
-Dfs 深度優先搜尋
-Meet in the middle 雙向搜尋
1、Safecracker
北京大學2017計算機學科夏令營上機考試&Mid-Central USA 2002
Poj1248
http：//
poj。org/problem？
id=1248
給出一個target和一個字符集，其中’A’代表數字1，’B’-2。。。’Z’-26。
在其中選擇五個各不相同的字元vwxyz，使得其滿足方程v - w^2 + x^3 - y^4 + z^5 = target
若存在多種方案，則取字典序最大者輸出
列舉
每個字元取值共26種，直接列舉26^5個方案判是否滿足方程。
剪枝：倒序列舉，找到解時即為字典序最大的解，直接退出搜尋並輸出該解。
//shjj-poj1248
#include
#include
#include
#include
#include
#include
using
namespace
std
；
char
s
［
30
］；
int
g
［
30
］，
ans
［
6
］，
ls
，
m
；
bool
checkEnd
（）
{
if
（
m
||
strlen
（
s
+
1
）
！=
3
）
return
0
；
return
s
［
1
］
==
‘E’
&&
s
［
2
］
==
‘N’
&&
s
［
3
］
==
‘D’
；
}
int
pow
（
int
x
，
int
w
）
{
int
y
=
1
；
for
（
int
i
=
w
；
i
；
i
——
）
y
*=
x
；
return
y
；
}
bool
check
（）
{
for
（
int
i
=
1
；
i
<=
5
；
i
++
）
for
（
int
j
=
1
；
j
<
i
；
j
++
）
if
（
ans
［
i
］
==
ans
［
j
］）
return
0
；
int
x
=
0
，
y
=
1
；
for
（
int
i
=
1
；
i
<=
5
；
i
++
，
y
*=
-
1
）
{
x
+=
y
*
pow
（
ans
［
i
］，
i
）；
}
return
x
==
m
；
}
bool
search
（
int
w
）
{
if
（
w
>
5
）
{
return
check
（）；
}
for
（
int
i
=
ls
；
i
；
i
——
）
{
ans
［
w
］
=
g
［
i
］；
if
（
search
（
w
+
1
））
return
1
；
}
return
0
；
}
int
main
（）
{
for
（；
；
）
{
scanf
（
“%d%s”
，
&
m
，
s
+
1
）；
if
（
checkEnd
（））
break
；
int
len
=
strlen
（
s
+
1
）；
ls
=
0
；
for
（
int
i
=
1
；
i
<=
len
；
i
++
）
g
［
++
ls
］
=
s
［
i
］
-
‘A’
+
1
；
sort
（
g
+
1
，
g
+
ls
+
1
）；
if
（
search
（
1
））
{
for
（
int
i
=
1
；
i
<=
5
；
i
++
）
printf
（
“%c”
，
‘A’
+
ans
［
i
］
-
1
）；
puts
（
“”
）；
}
else
puts
（
“no solution”
）；
}
}
2、Dessert
USACO 2002 February
Poj1950
http：//
poj。org/problem？
id=1950
你要在數字1。。N 之間插入’+’，’-’或者’。’，使得最後的結果為0。
列舉
3^n列舉所有的情況判斷是否能算出0即可。
3、Meteor Shower
北京大學2017大資料研究中心夏令營上機考試&USACO 2008 February Silver
Poj3669
http：//
poj。org/problem？
id=3669
有m（50000）個隕石落到一個300*300的地圖上，（x，y，t），其在時刻t落到（x，y），摧毀該區域及四方向相鄰的區域。一個區域被摧毀後不能再進入。問從原點、0時刻開始最少需要多少時間能夠逃離到安全位置。
Bfs
預處理得到地圖上每個地點最早被摧毀的時間。由原點開始bfs，當一個點入隊時判斷當前時間是否在該點最早被摧毀時間之前。
//shjj-poj3669
#include
#include
#include
#include
#include
#include
using
namespace
std
；
const
int
N
=
303
；
int
f
［
N
］［
N
］，
time
［
N
］［
N
］；
int
Qx
［
100000
］，
Qy
［
100000
］，
m
；
const
int
tx
［
4
］
=
{
1
，
-
1
，
0
，
0
}；
const
int
ty
［
4
］
=
{
0
，
0
，
1
，
-
1
}；
void
Bfs
（）
{
f
［
0
］［
0
］
=
0
；
Qx
［
1
］
=
Qy
［
1
］
=
0
；
for
（
int
l
=
0
，
r
=
1
；
l
<
r
；
）
{
int
x
=
Qx
［
++
l
］，
y
=
Qy
［
l
］；
if
（
time
［
x
］［
y
］
==
2e9
）
//安全地點
{
printf
（
“%d”
，
f
［
x
］［
y
］）；
return
；
}
for
（
int
i
=
0
；
i
<
4
；
i
++
）
{
int
x3
=
x
+
tx
［
i
］，
y3
=
y
+
ty
［
i
］；
if
（
x3
<
0
||
x3
>=
N
||
y3
<
0
||
y3
>=
N
）
continue
；
//越界
if
（
f
［
x
］［
y
］
+
1
>=
time
［
x3
］［
y3
］）
continue
；
//危險區域
if
（
f
［
x3
］［
y3
］
<
2e9
）
continue
；
//該區域已被搜尋到
f
［
x3
］［
y3
］
=
f
［
x
］［
y
］
+
1
；
Qx
［
++
r
］
=
x3
，
Qy
［
r
］
=
y3
；
}
}
puts
（
“-1”
）；
}
int
main
（）
{
//每個點的危險時間初始化為無窮大
for
（
int
i
=
0
；
i
<
N
；
i
++
）
for
（
int
j
=
0
；
j
<
N
；
j
++
）
time
［
i
］［
j
］
=
2e9
；
scanf
（
“%d”
，
&
m
）；
for
（
int
i
=
1
；
i
<=
m
；
i
++
）
{
int
x
，
y
，
t
；
scanf
（
“%d%d%d”
，
&
x
，
&
y
，
&
t
）；
//strike
time
［
x
］［
y
］
=
min
（
time
［
x
］［
y
］，
t
）；
for
（
int
j
=
0
；
j
<
4
；
j
++
）
{
int
x3
=
x
+
tx
［
j
］；
int
y3
=
y
+
ty
［
j
］；
if
（
x3
<
0
||
x3
>=
N
||
y3
<
0
||
y3
>=
N
）
continue
；
time
［
x3
］［
y3
］
=
min
（
time
［
x3
］［
y3
］，
t
）；
}
}
//到達每個點的最短時間初始化為無窮大
for
（
int
i
=
0
；
i
<
N
；
i
++
）
for
（
int
j
=
0
；
j
<
N
；
j
++
）
f
［
i
］［
j
］
=
2e9
；
Bfs
（）；
}
4、Prime Path
北京大學2017研究生推免上機考試&Northwestern Europe 2006
Poj3126
http：//
poj。org/problem？
id=3126
給出兩個四位無前導0素數
定義一次變化為改變一個數位上的數字，且變化後的數仍為四位無前導0素數。
如1033-1733-3733-3739-3779-8779-8179，計6步。
問這兩個素數間需要經過幾次變化。
Bfs
先求出所有四位無前導0的素數。然後以st作起點bfs求至ed的變化次數。對每個數改變各數位上的值，若為素數則將其作為一個轉移方向。
//shjj-poj3126
#include
#include
#include
#include
using
namespace
std
；
const
int
N
=
10003
；
int
pre
［
N
］，
pri
［
N
］，
pn
；
int
q
［
N
］，
f
［
N
］；
int
g
［
50
］，
n
，
ls
，
st
，
ed
，
ans
；
void
Pre
（）
{
for
（
int
i
=
2
；
i
<
10000
；
i
++
）
if
（
！
pre
［
i
］）
{
if
（
i
>
999
）
pri
［
++
pn
］
=
i
；
for
（
int
j
=
i
+
i
；
j
<
10000
；
j
+=
i
）
pre
［
j
］
=
i
；
}
}
//變化各數位存至g陣列，共ls個數
void
search
（
int
x
）
{
for
（
int
i
=
1
；
i
<
10
；
i
++
）
{
int
y
=
x
-
x
/
1000
*
1000
；
g
［
++
ls
］
=
y
+
i
*
1000
；
}
for
（
int
i
=
0
；
i
<
10
；
i
++
）
{
int
y
=
x
-
x
/
100
%
10
*
100
；
g
［
++
ls
］
=
y
+
i
*
100
；
}
for
（
int
i
=
0
；
i
<
10
；
i
++
）
{
int
y
=
x
-
x
/
10
%
10
*
10
；
g
［
++
ls
］
=
y
+
i
*
10
；
}
for
（
int
i
=
0
；
i
<
10
；
i
++
）
{
int
y
=
x
-
x
%
10
；
g
［
++
ls
］
=
y
+
i
；
}
}
void
Bfs
（
int
st
）
{
for
（
int
i
=
1
；
i
<=
pn
；
i
++
）
f
［
pri
［
i
］］
=
1e9
；
q
［
1
］
=
st
；
f
［
st
］
=
0
；
for
（
int
l
=
0
，
r
=
1
；
l
<
r
；
）
{
int
x
=
q
［
++
l
］；
ls
=
0
；
search
（
x
）；
for
（
int
i
=
1
；
i
<=
ls
；
i
++
）
{
if
（
f
［
g
［
i
］］
<
1e9
）
continue
；
//非素數或已入隊素數不考慮
f
［
g
［
i
］］
=
f
［
x
］
+
1
；
q
［
++
r
］
=
g
［
i
］；
}
}
}
int
main
（）
{
int
T
；
scanf
（
“%d”
，
&
T
）；
Pre
（）；
for
（；
T
——
；
）
{
scanf
（
“%d%d”
，
&
st
，
&
ed
）；
Bfs
（
st
）；
if
（
f
［
ed
］
==
2e9
）
puts
（
“Impossible”
）；
else
printf
（
“%d
\n
”
，
f
［
ed
］）；
}
}
5、Lake Counting
USACO 2004 November
Poj2386
http：//
poj。org/problem？
id=2386
N*M（100*100）的地圖中，有’。’和’W’兩種地圖元素，問其中有多少個’W’八連通塊
Dfs / Bfs
八方向搜尋，對於遍歷到的’W’將其’。’避免再次訪問
//shjj - poj2386
#include
#include
#include
#include
using
namespace
std
；
char
s
［
100
+
3
］［
100
+
3
］；
int
n
，
m
，
ans
；
const
int
tx
［
8
］
=
{
-
1
，
-
1
，
-
1
，
0
，
0
，
1
，
1
，
1
}；
const
int
ty
［
8
］
=
{
-
1
，
0
，
1
，
-
1
，
1
，
-
1
，
0
，
1
}；
void
find
（
int
x
，
int
y
）
{
if
（
x
<
1
||
x
>
n
||
y
<
1
||
y
>
m
）
return
；
//越界
if
（
s
［
x
］［
y
］
！=
‘W’
）
return
；
//不屬於連通塊內
s
［
x
］［
y
］
=
‘。’
；
//已訪問，改為背景
for
（
int
i
=
0
；
i
<
8
；
i
++
）
find
（
x
+
tx
［
i
］，
y
+
ty
［
i
］）；
//八連通dfs
}
int
main
（）
{
scanf
（
“%d%d”
，
&
n
，
&
m
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
scanf
（
“%s”
，
s
［
i
］
+
1
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
for
（
int
j
=
1
；
j
<=
m
；
j
++
）
if
（
s
［
i
］［
j
］
==
‘W’
）
//未訪問的連通塊
{
find
（
i
，
j
）；
ans
++
；
}
printf
（
“%d”
，
ans
）；
}
6、生日快樂
SCOI2009
Bzoj1024
https：//www。
lydsy。com/JudgeOnline/p
roblem。php？id=1024
一塊大小為X * Y的矩形蛋糕，現要將其切成n塊面積相同的蛋糕，且每次切的時候只能將。每一切只能平行於一塊蛋糕的一邊，並且必須切成兩塊。這樣要切成n塊需要切n-1刀。要求 N 塊蛋糕的長邊與短邊的比值的最大值最小。求這個比值
Dfs
分析題意有以下特徵：
1、n塊蛋糕面積均為X * Y / n
2、每次一刀切下分成的兩塊都是 X * Y / n 的整數倍
故以（x， y， n）表示一個搜尋狀態，其意義為這一塊x * y 的蛋糕要分給n個人。在其上切的一刀，一塊給i個人和一塊給n-i個人。
若在x上切，則切成 （x / n * i ， y ， i） 和 （x - x / n * i， y， n - i）
若在y上切，則切成 （x， y / n * i ， i） 和 （x， y - y / n * i， n - i）
//shjj-bzoj1024
#include
#include
#include
#include
using
namespace
std
；
int
X
，
Y
，
n
；
double
ans
；
double
search
（
double
x
，
double
y
，
int
n
）
{
if
（
n
==
1
）
return
max
（
x
，
y
）
/
min
（
x
，
y
）；
double
ss
=
2e9
，
dx
=
x
/
n
，
dy
=
y
/
n
；
for
（
int
i
=
1
；
i
<=
（
n
>>
1
）；
i
++
）
{
ss
=
min
（
ss
，
max
（
search
（
dx
*
i
，
y
，
i
），
search
（
x
-
dx
*
i
，
y
，
n
-
i
）））；
ss
=
min
（
ss
，
max
（
search
（
x
，
dy
*
i
，
i
），
search
（
x
，
y
-
dy
*
i
，
n
-
i
）））；
}
return
ss
；
}
int
main
（）
{
scanf
（
“%d%d%d”
，
&
X
，
&
Y
，
&
n
）；
ans
=
search
（
X
，
Y
，
n
）；
printf
（
“%。6lf”
，
ans
）；
}
7、Eqs
北京大學2017研究生推免上機考試&Romania OI 2002
Poj1840
http：//
poj。org/problem？
id=1840
對於方程a1X1^3 + a2X2^3 + a3X3^3 + a4X4^3 + a5X5^3
其中Ai屬於［-50，50］
Xi屬於［-50，50］，且Xi ！= 0
問有多少個解
Meet in the middle
將方程分為兩部分，先列舉X1、X2求出前兩項和的所有可能的方案數。
F［x］儲存前兩項和為x的方案數。
列舉X3、X4、X5記和為y，則當前兩項和為-y時即構成方程的解，累加F［-y］即得方程的解的個數。
這樣搜尋的規模就成了50^2 + 50^3
用Map作hash超時，直接開50*50*50*50*2*2的short陣列，以下標直接hash。
//shjj-poj1840
#include
#include
#include
#include
using
namespace
std
；
const
int
M
=
12500000
；
short
f
［
M
*
2
+
1
］；
int
a
［
6
］；
long
long
ans
；
int
cubic
（
int
x
）
{
return
x
*
x
*
x
；
}
int
main
（）
{
for
（
int
i
=
1
；
i
<=
5
；
i
++
）
scanf
（
“%d”
，
&
a
［
i
］）；
for
（
int
i
=
-
50
；
i
<=
50
；
i
++
）
for
（
int
j
=
-
50
；
j
<=
50
&&
i
；
j
++
）
{
if
（
！
j
）
continue
；
f
［
M
+
a
［
1
］
*
cubic
（
i
）
+
a
［
2
］
*
cubic
（
j
）］
++
；
}
for
（
int
i
=
-
50
；
i
<=
50
；
i
++
）
for
（
int
j
=
-
50
；
j
<=
50
&&
i
；
j
++
）
for
（
int
k
=
-
50
；
k
<=
50
&&
j
；
k
++
）
{
if
（
！
k
）
continue
；
int
x
=
a
［
3
］
*
cubic
（
i
）
+
a
［
4
］
*
cubic
（
j
）
+
a
［
5
］
*
cubic
（
k
）；
if
（
x
>
M
||
x
<
-
M
）
continue
；
ans
+=
f
［
M
-
x
］；
}
printf
（
“%lld”
，
ans
）；
}
8、方程的解數
Noi2001
Poj1186
http：//
poj。org/problem？
id=1186
求解方程k1*x1^p1 + k2*x2^p2+。。。+kn*xn^pn=0
其中x1，x2。。。，xn是未知數，k1，k2。。。，kn是係數，p1，p2。。。，pn是指數，均為整數
假設未知數xi屬於［1，M］，求方程的整數解個數
1<=n<=6；1<=M<=150
|k1M^p1|+|k2M^p2|+。。。|knM^pn|<2^31
指數pi均為正整數
且保證方程的整數解個數小於2^31
Meet in the middle
直接列舉的規模是m^6，10^13的規模，顯然是不行的。
考慮將方程分成前後兩部分。先列舉前三項，計算得到的和及其方案數。
F［x］記錄前三項和為x共有f［x］種方案
再列舉後三項，記其和為y，則當前三項和為-y時即構成方程的解，累加F［-y］即得方程的解的個數。
這樣搜尋規模就成了m^3 * 2
用map作hash超時，手寫hash表實現hash
//shjj - 方程的解數
#include
#include
#include
#include
#include
using
namespace
std
；
int
K
［
7
］，
P
［
7
］，
n
，
m
，
lim
，
ans
；
int
value
［
3375003
］，
Next
［
3375003
］，
Last
［
3333331
］，
f
［
3375003
］，
nn
；
int
pow
（
int
x
，
int
w
）
{
int
y
=
1
；
for
（
int
i
=
1
；
i
<=
w
；
i
++
）
y
*=
x
；
return
y
；
}
//hash掛連結串列
void
Add
（
int
x
）
{
int
w
=
abs
（
x
）
%
3333331
；
for
（
int
i
=
Last
［
w
］；
i
；
i
=
Next
［
i
］）
if
（
value
［
i
］
==
x
）
{
f
［
i
］
++
；
//找到 x 的記錄，方案數+1
return
；
}
// x 無記錄，新建記錄
value
［
++
nn
］
=
x
；
Next
［
nn
］
=
Last
［
w
］；
Last
［
w
］
=
nn
；
f
［
nn
］
=
1
；
}
//訪問hash連結串列獲取 和為x的方案數
int
Get
（
int
x
）
{
int
w
=
abs
（
x
）
%
3333331
；
for
（
int
i
=
Last
［
w
］；
i
；
i
=
Next
［
i
］）
if
（
value
［
i
］
==
x
）
return
f
［
i
］；
// x 無記錄，方案數為0，返回
return
0
；
}
void
dfs1
（
int
w
，
int
sum
）
{
if
（
w
>
lim
）
{
Add
（
sum
）；
return
；
}
for
（
int
i
=
1
；
i
<=
m
；
i
++
）
dfs1
（
w
+
1
，
sum
+
K
［
w
］
*
pow
（
i
，
P
［
w
］））；
}
void
dfs2
（
int
w
，
int
sum
）
{
if
（
w
>
n
）
{
ans
+=
Get
（
-
sum
）；
return
；
}
for
（
int
i
=
1
；
i
<=
m
；
i
++
）
dfs2
（
w
+
1
，
sum
+
K
［
w
］
*
pow
（
i
，
P
［
w
］））；
}
int
main
（）
{
scanf
（
“%d%d”
，
&
n
，
&
m
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
scanf
（
“%d%d”
，
&
K
［
i
］，
&
P
［
i
］）；
lim
=
n
/
2
；
//前向
dfs1
（
1
，
0
）；
//後向
dfs2
（
lim
+
1
，
0
）；
printf
（
“%d
\n
”
，
ans
）；
}
