【训练】算法竞赛进阶指南-2搜索13题

本处难度分档以个人实力为参照系
难度1:半小时内想出,半小时内ac
难度2:半小时想不出,看题解,服气
难度3:半小时想不出,看题解,ac后依然觉得难度很大

0x20 搜索

题目

1 2101 可达性统计

7.9 难度2

请先思考后再展开

一开始以为是统计 siz 的sb题
原来是我sb了,因为会有重复,那么只能把每个点能到达的统计下来了
而且因为是有向的,必须要按照拓扑序(建反边)来统计
用bitset统计,查询1的个数即可

复杂度的话,时间是$O(n^2/32)$,空间是128MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=31000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
struct Nod
{
int hou;
int ru;
Nod()
{
hou=ru=0;
}
}p[MAXN];
struct Edge
{
int y,g;
}e[MAXN];
int ln=0;
void ins(int x,int y)
{
ln++;
e[ln].y=y;e[ln].g=p[x].hou;
p[x].hou=ln;
p[y].ru++;
}
int lst[MAXN],top=0;
bitset<MAXN> f[MAXN];
int main()
{
int n,m;scanf("%d%d",&n,&m);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
ins(y,x);
}
for(int i=1;i<=n;i++)
{
f[i][i]=1;
if(p[i].ru==0) lst[++top]=i;
}
while(top>0)
{
int x=lst[top--];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
f[y]=f[y]|f[x];
p[y].ru--;
if(p[y].ru==0) lst[++top]=y;
}
}
for(int i=1;i<=n;i++) printf("%d\n",f[i].count());
}

2 2201 小猫爬山

7.10 难度2

请先思考后再展开

这道题引发了我对暴搜方式的思考:
如果用车来找猫,就有次序性;
而反过来,新车选择就会减少,次序也固定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=20;
int n,w;
int ans=MAXN;
int use[MAXN];
int c[MAXN];
void dfs(int now,int cnt)
{
if(cnt>=ans) return;//最优化剪枝
if(now>n) {ans=cnt;return;}
for(int i=1;i<=cnt;i++)
if(use[i]+c[now]<=w)
{
use[i]+=c[now];
dfs(now+1,cnt);
use[i]-=c[now];
}
use[cnt+1]=c[now];
dfs(now+1,cnt+1);
}
bool cmp(int x,int y) {return x>y;}
int main()
{
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
sort(c+1,c+n+1,cmp);//减少选择
dfs(1,0);
printf("%d",ans);
}

3 poj2676 poj3074 Sudoku

7.10 难度2

请先思考后再展开

poj2676 0ms
poj3074 tle,精A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
int mp[MAXN][MAXN];
bitset<10> hang[MAXN],lie[MAXN],block[MAXN];
int getid(int x,int y) { return ((x-1)/3)*3+(y-1)/3+1; }
int tot;
int fx,fy;
void getnxt()
{
int ans=INF;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(mp[i][j]==0)
{
int t=(hang[i]&lie[j]&block[getid(i,j)]).count();
if(ans>t) ans=t,fx=i,fy=j;
}
}
bool bk;
void dfs(int now)
{
if(bk) return;
if(now>tot)
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
printf("%d",mp[i][j]);
putchar('\n');
}
//putchar('\n');
bk=1;
return;
}
getnxt();//debug 原本直接用fx、fy,后果严重,查错很久!
int x=fx,y=fy,id=getid(x,y);
for(int t=1;t<=9;t++)
if(hang[x][t] and lie[y][t] and block[id][t])
{
hang[x][t]=lie[y][t]=block[id][t]=0;
mp[x][y]=t;
dfs(now+1);
mp[x][y]=0;
hang[x][t]=lie[y][t]=block[id][t]=1;
}
}
char str[MAXN*MAXN];
int main()
{
int T;scanf("%d",&T);
while(T--)
//while(1)
{
tot=0;
for(int i=1;i<=9;i++) hang[i].set(),lie[i].set(),block[i].set();
//scanf("%s",str+1);
if(str[1]=='e') break;
for(int i=1;i<=9;i++)
{
scanf("%s",str+1);
for(int j=1;j<=9;j++)
{
int now=str[j]-'0';
//int now=(str[(i-1)*9+j]=='.')?0:str[(i-1)*9+j]-'0';
mp[i][j]=now;
if(now>0) hang[i][now]=lie[j][now]=block[getid(i,j)][now]=0;
else tot++;
}
}
bk=0;dfs(1);
}
}

4 poj1011 luogu1120 Sticks

7.11 难度3

请先思考后再展开

去掉次序性的套路:强行限制大小关系,例如我选择了递减

由于值的数量比个数少,可以把值映射一下,方便查找,
至于可用性可以直接更改数量
然后这个方法包含了一个剪枝——同值不再考虑

书上的一个剪枝一直没有理解,就是当空的时候,检验前面决策
具体而言是尝试每一个木棒,任何一个失败都意味着前面决策错误
然后我的策略是毫不犹豫地选择最大的
本来是一直坚信其优越性的,直到惊觉我的做法,
发现决策的错误要在以后的层,多出了很多无用枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=100;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int sum,mx,k;
int n;
int c[MAXN];//映射
bool okay;
void dfs(int done,int now,int lst)//强制递减
{
if(done==sum/k) okay=1;
if(okay) return;
int t=mymin(lst,k-now);//debug 原本 k-lst
if(lst==INF) t=mx;
for(;t>0;t--)
{
if(c[t]==0) continue;
c[t]--;
if(now+t==k) dfs(done+1,0,INF);
else dfs(done,now+t,t);
c[t]++;
if(!okay and (now==0 or now+t==k)) return;//现在失败,前面有问题
//大剪枝,因为耗时大部分都是失败的结果,否则已经结束了
//now==0:空的,塞东西后失败,迟早会用到
//now+t==k:大的块一定不会比【小的拼起来一样长】的更有用,因为不能拆开
}
}
int main()
{
while(1)
{
scanf("%d",&n);
if(n==0) break;
memset(c,0,sizeof c);
mx=sum=0;
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
if(t<=50)
{
sum+=t;
mx=mymax(mx,t);
c[t]++;
}
}
int ans=INF;
for(int t=1;t<=sqrt(sum);t++)
if(sum%t==0)
{
k=t;
if(k>=mx)
{
okay=0;dfs(0,0,INF);
if(okay) ans=mymin(ans,k);
}
k=sum/t;
if(k!=t and k>=mx)
{
okay=0;dfs(0,0,INF);
if(okay) ans=mymin(ans,k);
}
}
printf("%d\n",ans);
}
}

5 poj1190 生日蛋糕

7.12 难度2

请先思考后再展开

剪枝

  1. 最优化剪枝
    nows>=ans
  2. 可行性剪枝
    Ri>=1+2(m-i)
    Hi>=1+2
    (m-i)
  3. 最小化可行性剪枝
    nown+getmin()>n
  4. 最大化可行性剪枝
    nown+getmax()<n

最后一个剪枝特tm难想到
首先,如果要剪枝,肯定要把上面部分的东西表示出来
N表示去掉$\pi$的体积,S表示去掉$\pi$的表面积

$$
N_后=\sum_{i=now}^m R_i^2 H_i
$$

$$
S_后=2 \times \sum_{i=now}^m R_i H_i
$$

所谓剪枝,可以考虑不等式
【据说接下来的是高中数学灰常恶心的东西:不等式的缩放】

加入元$R_{now-1}$(很难想)
$$
S_后=
\frac{2}{R_{now-1}}
\times
\sum_{i=now}^m R_i H_i R_{now-1}
$$

把右边部分缩放一下
由于$R_{now-1} > R_i$

$$
S_后

\frac{2}{R_{now-1}}
\times
\sum_{i=now}^m R_i^2 H_i
$$

联系一下体积
$$
S_后> \frac{2}{R_{now-1}} \times N_剩
$$

因为前面几个剪枝,只有一个是关于【有关答案的表面积】的
那么可以说$S_后$一定比某个值大
可以最优化剪枝一波,条件:
$$
S_现+\frac{2}{R_{now-1}} \times N_剩>=ans
$$

最后就是碰到搜索要无脑倒序循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n,m;
int r[MAXN],h[MAXN];
int mi[MAXN];
ll getmx(int x)
{
ll sum=0,rr=r[x-1],hh=h[x-1];
for(int i=x;i<=m;i++) sum+=(rr+i)*(rr+i)*(hh+i);
return sum;
}
int ans=INF;
void dfs(int nows,int nown,int x)
{
if(nows+r[1]*r[1]>=ans) return;
if(x==m+1)
{
if(nown==n) ans=nows+r[1]*r[1];
return;
}
//if(nown+mi[m-x+1]>n) return;
//if(getmx(x)+nown<n) return; 会拖慢
if(r[1]*r[1]+nows+2*(n-nown)/r[x-1]>=ans) return;
for(int ri=mymin(sqrt(n-mi[m-x]-nown),r[x-1]-1);ri>=1+(m-x);ri--)//debug,sqrt部分没想到
{
int hmx=(n-mi[m-x]-nown)/(ri*ri);//最小化可行性剪枝的变形
if(x==m)
{
r[x]=ri;h[x]=hmx;
if(hmx<=h[x-1]-1) dfs(nows+2*ri*hmx,nown+ri*ri*hmx,x+1);
continue;
}
for(int hi=mymin(hmx,h[x-1]-1);hi>=1+(m-x);hi--)
{
r[x]=ri;h[x]=hi;
dfs(nows+2*ri*hi,nown+ri*ri*hi,x+1);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) mi[i]=i*i*i;
r[0]=100+1;h[0]=20000+1;
dfs(0,0,1);
if(ans==INF) ans=0;
printf("%d",ans);
}

6 poj2248 Addition Chains

7.12 难度1

请先思考后再展开

迭代加深这个东西第一次看到
感觉它虽然比bfs慢一些,但其优势在于便于还原状态、不用大量空间来存储状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int ed;
int ln;
int a[MAXN];
bool v[MAXN];
bool dfs(int now)
{
if(a[now-1]==ed)
{
for(int i=1;i<=now-1;i++) printf("%d ",a[i]);
return 1;
}
if(now>ln) return 0;
memset(v,0,sizeof v);
for(int i=now-1;i>=1;i--)
for(int j=now-1;j>=i;j--)
{
a[now]=a[i]+a[j];
if(v[a[now]] or a[now]>ed or a[now]<=a[now-1]) continue;
v[a[now]]=1;
if(dfs(now+1)) return 1;
}
return 0;
}
int main()
{
a[1]=1;
while(1)
{
scanf("%d",&ed);
if(ed==0) break;
for(ln=1;ln<=100;ln++) if(dfs(2)) break;
printf("\n");
}
}

7 2401 送礼物

7.13 难度2

请先思考后再展开

其实通常面对一个决策与顺序无关,而且不卡log的题目,排序一下都不亏
其实看不出这个正解和折半搜索有什么关系
但是灰常鬼畜啊hh
主要思路来自【指数级爆搜】
把问题分成两边(已排序),搜索左右两边,然后通过枚举左边的结果,二分查找右边的
这样子复杂度就被硬生生变成了$O(2^{n/2} log_2 2^{n/2})$

折半搜索还有道体现得更明显的题目:
然后我们通过折半,把取值的数量从2^45变成最坏2^22,其实还不少,所以要剪枝

可恶啊卡我的set……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=50;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int w,n;
int a[MAXN];
int ans=0;
//set<int> f;//left
int f[1<<25],cnt=0;//left
void dfs(int x,int now,bool right)
{
if(!right and x>n/2) f[++cnt]=now;//f.insert(now);
else if(right and x>n)
{
//int t=*( --upper_bound(f.begin(),f.end(),w-now) );//<=w-now
int t=f[upper_bound(f+1,f+cnt+1,w-now)-f-1];
ans=mymax(ans,t+now);
}
else
{
dfs(x+1,now,right);
if(ll(now)+a[x]<=w) dfs(x+1,now+a[x],right);
}
}
int main()
{
scanf("%d%d",&w,&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);reverse(a+1,a+n+1);
dfs(1,0,0);
sort(f+1,f+cnt+1);
cnt=unique(f+1,f+cnt+1)-f-1;
dfs(n/2+1,0,1);
printf("%d",ans);
}

8 2601 电路维修

7.14 难度2

请先思考后再展开

最巧妙的地方:
把决策转化为边,边权为代价
于是就变成了最短路问题

spfa一直tle……
试一试书上的新做法,以为多特别所以没有打p[x].v=0,一直wa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=510;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n,m;
int calc(int x,int y) {return (x-1)*MAXN+y;}
struct Nod
{
int hou;
int dis;
bool v;
}p[MAXN*MAXN];
struct Edge
{
int y,c,g;
}e[MAXN*MAXN*2*2];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
ln++;
e[ln].y=x;e[ln].c=c;
e[ln].g=p[y].hou;p[y].hou=ln;
}
deque<int> q;
int bfs(int st,int ed)
{
p[st].v=1;q.push_back(st);p[st].dis=0;
while(!q.empty())
{
int x=q.front();q.pop_front();
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dis>p[x].dis+e[k].c)
{
p[y].dis=p[x].dis+e[k].c;
if(!p[y].v)
{
p[y].v=1;
if(e[k].c) q.push_back(y);
else q.push_front(y);
}
}
}
p[x].v=0;//debug
}
return p[ed].dis;
}
char s[MAXN];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ln=0;
for(int i=1;i<MAXN*MAXN;i++)
{
p[i].v=0;
p[i].hou=0;
p[i].dis=INF;
}
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
{
ins( calc(i,j),calc(i+1,j+1),(s[j]=='/') );
ins( calc(i+1,j),calc(i,j+1),(s[j]!='/') );
}
}
int ans=bfs(calc(1,1),calc(n+1,m+1));
if(ans==INF) puts("NO SOLUTION");
else printf("%d\n",ans);
}
}

9 poj3635 Full Tank?

7.17 难度1

请先思考后再展开

本来以为可以dfs去记忆化
然鹅这样是错的,因为不能保证第一次就是最优解……
话说bfs的复杂度其实灰常悬,可能数据水?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=1100,MAXM=21000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int a[MAXN];
int hou[MAXN];
struct Edge
{
int y,c,g;
}e[MAXM];
int ln=0;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=hou[x];hou[x]=ln;
}
int full,st,ed;
struct Nod
{
int x,oil;
int cost;
Nod(int a=0,int b=0,int c=0) {x=a,oil=b,cost=c;}
friend bool operator > (Nod a,Nod b) {return a.cost>b.cost;}
};
bool v[MAXN][110];
priority_queue< Nod,vector<Nod>,greater<Nod> > q;
int bfs()
{
memset(v,0,sizeof v);
while(!q.empty()) q.pop();
q.push( Nod(st,0,0) );//题目中说是空箱
while(!q.empty())
{
Nod now=q.top();q.pop();
int x=now.x,oil=now.oil,cost=now.cost;
if(x==ed) return cost;
if(v[x][oil]) continue;
v[x][oil]=1;
if(oil<full) q.push( Nod(x,oil+1,cost+a[x]) );
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(oil>=e[k].c) q.push( Nod(y,oil-e[k].c,cost) );
}
}
return -1;
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
x++;y++;
ins(x,y,c);ins(y,x,c);
}
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&full,&st,&ed);
st++;ed++;
int ans=bfs();
if(ans<0) puts("impossible");
else printf("%d\n",ans);
}
}

10 poj2449 Remmarguts’ Date

7.17 难度2

请先思考后再展开

key:第k次出堆,得到第k小的解
akc眼中的模版题

不过最后奇奇怪怪mle
先放着吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=1100,MAXM=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int st,ed,K;
int hou[MAXN];
bool v[MAXN];
int f[MAXN];//估价函数
struct Edge
{
int y,c,g;
}e[MAXM];
int ln=0;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=hou[x];hou[x]=ln;
}
queue<int> lst;
void spfa()
{
memset(f,63,sizeof f);//debug 忘记了……
lst.push(ed);v[ed]=1;f[ed]=0;
while(!lst.empty())
{
int x=lst.front();lst.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(f[y]>f[x]+e[k].c)
{
f[y]=f[x]+e[k].c;
if(!v[y]) v[y]=1,lst.push(y);
}
}
v[x]=0;
}
}
int tot[MAXN];//次数
struct Nod
{
int x,dis;
Nod(int a=0,int b=0) {x=a,dis=b;}
friend bool operator > (Nod a,Nod b) {return a.dis+f[a.x]>b.dis+f[b.x];}
};
priority_queue< Nod,vector<Nod>,greater<Nod> > q;
int solve()
{
q.push( Nod(st,0) );
while(!q.empty())
{
Nod now=q.top();q.pop();
int x=now.x;
tot[x]++;
if(tot[x]>K) continue;
if(x==ed and tot[x]==K) return now.dis;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(tot[y]<K) q.push( Nod(y,now.dis+e[k].c) );
}
}
return -1;
}
int xx[MAXM],yy[MAXM],cc[MAXM];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&xx[i],&yy[i],&cc[i]);
ins(yy[i],xx[i],cc[i]);
}
scanf("%d%d%d",&st,&ed,&K);
if(st==ed) K++;//好像是必须要走???
spfa();
ln=0;memset(hou,0,sizeof hou);
for(int i=1;i<=m;i++) ins(xx[i],yy[i],cc[i]);
printf("%d",solve());
}

11 poj3460 Booksort

7.17 难度3

请先思考后再展开

A=堆+bfs+估价
IDA
=迭代dfs+估价

最难的就是怎么估价了
目标是有序,但我们不能用【逆序对数量】,因为每次消除量是不确定的
观察题目性质,每次操作都是对连续的一段进行的
再有序的情况下,每个数都有一个正确的后继
而每次操作最多消除3个错误后继数
不过要向上取整

顺便再介绍一下折半搜索怎么做:
先考虑每次决策的分支量
如果选a本,有n-a+1种,可以插n-a处
同时对于前移,必定有一种后移方案与其等效,所以只后移
分支数$ \sum_{a=1}^{n-1} (n-a+1) \times (n-a) /2 = 560 $
普通dfs是4次方,折半一下,就变成了平方级别
可以用hash+map存储结果,第二次的时候对应找到,然后累计即可
总而言之复杂度$O(560^2 log_2 560^2)$

wa了一次,忘记判断完美情况了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n;
int mxdep;
bool bk;
void dfs(int now[MAXN],int step)
{
if(bk) return;
int f=0;
for(int i=1;i<n;i++) if(now[i+1]!=now[i]+1) f++;
f=int( ceil(double( f+(now[n]!=n) )/3.0) );
if(f==0) {bk=1;return;}
if(step+f>mxdep) return;
for(int a=1;a<=n-1;a++)
{
for(int st=1;st<=n-a+1;st++)
{
int ed=st+a-1;
for(int nw=ed+1;nw<=n;nw++)
{
//第一段 1~st-1
//第二段 ed+1~nw
//第三段 st~ed
//第四段 nw+1~n
int nx[MAXN],cnt=0;
for(int i=1;i<=st-1;i++) nx[++cnt]=now[i];
for(int i=ed+1;i<=nw;i++) nx[++cnt]=now[i];
for(int i=st;i<=ed;i++) nx[++cnt]=now[i];
for(int i=nw+1;i<=n;i++) nx[++cnt]=now[i];
dfs(nx,step+1);
}
}
}
}
int a[MAXN];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
bk=0;
for(mxdep=0;mxdep<=4;mxdep++)//debug 完美情况
{
dfs(a,0);
if(bk) break;
}
if(bk) printf("%d\n",mxdep);
else puts("5 or more");
}
}

0x29 搜索练习

题目

12 poj3700 Missile Defence System

7.18 难度2

请先思考后再展开

先给出一份比较显然的做法,一组组找
尽力加上了两个剪枝:

  1. 仅当没东西选的时候再结束
  2. 当前能被now到nx中间的覆盖时,延迟搜索
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<map>
    #include<set>
    #include<queue>
    #include<deque>
    #include<vector>
    #include<bitset>
    #include<algorithm>
    using namespace std;
    const int MAXN=60;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    typedef unsigned long long ull;
    int mymax(int x,int y) {return x>y?x:y;}
    int mymin(int x,int y) {return x<y?x:y;}
    int myabs(int x) {return x>0?x:-x;}
    int n;
    int a[MAXN];
    bool v[MAXN];
    bool bk;
    int mxdep;
    void dfs(int cnt,int tot,int now,int up)
    {
    if(bk) return;
    if(cnt>mxdep) return;
    if(tot==n) {bk=1;return;}
    bool b=0;
    int mi=INF,mx=0;
    for(int nx=now+1;nx<=n;nx++)
    {
    if(v[nx]) continue;
    if(up==0 and (a[now]<a[nx] or a[nx]<mx)) continue;
    if(up==1 and (a[now]>a[nx] or a[nx]>mi)) continue;
    b=1;mi=mymin(mi,a[nx]);mx=mymax(mx,a[nx]);
    v[nx]=1;
    if(up<0) dfs(cnt,tot+1,nx,0),dfs(cnt,tot+1,nx,1);
    else dfs(cnt,tot+1,nx,up);
    v[nx]=0;
    }
    if(!b)
    {
    for(int nx=1;nx<=n;nx++)
    if(!v[nx])
    {
    v[nx]=1;
    dfs(cnt+1,tot+1,nx,-1);
    v[nx]=0;
    break;
    }
    }
    }
    int main()
    {
    while(1)
    {
    scanf("%d",&n);if(n==0) break;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    bk=0;
    for(mxdep=1;mxdep<=n;mxdep++)
    {
    memset(v,0,sizeof v);
    v[1]=1;dfs(1,1,1,-1);
    if(bk) break;
    }
    printf("%d\n",mxdep);
    }
    }

然鹅这样依然会tle
原因大概是叉太多了?
其实想到这么多剪枝,但方向大概都是错误的

正解是考虑元素,分配组(这大概也是一个套路)
这样的话只要贪心地找最不优秀但符合条件的即可
顺利变成二叉,然后迭代加深也没意义了,最优性剪枝即可
代码就不写了

13 poj1945 Power Hungry Cows

7.18 难度2

请先思考后再展开

网上到处都是打表和玄学(其实错误)剪枝
来一股IDA*清流吧
因为感性地感觉次数不会太多,迭代一下
重点是这个估价函数
不难猜出最优解一定先倍增上去再微调的
那么如果只考虑倍增,实现容易又能满足$f(s) \leq g(s)$的定义

不过有一个应该是正确的剪枝,不太会证明
如果P的约数中没有【x和y的最大公约数】,则返回
大概原因是,无论怎么操作,得到的数一定是包含这个【x和y的最大公约数】吧
想想,好像无论加减都是如此。
这个还是挺妙的

官方数据:
19997 18
15151 17
11111 17
10007 16
5123 14
5111 15
1234 13
1024 10
1023 11
1010 12
31 6
然后在这些数据中,没有卡掉一种错误做法:假设较小值不会超过50
反例:18673,答案应该是17
然后打表发现其实是6160?听别人说的

顺便吐槽一句lyd的代码是打特判过的,根本错误的做法

反正我是没卡过去
所有数据都是正确的

IDA*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=60;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int gcd(int x,int y)
{
return (y==0)?x:gcd(y,x%y);
}
int P;
int f(int x,int y)
{
if(y==P) return 0;
int ans=0;
while(x<P) x*=2,ans++;
return ans;
}
bool bk=0;
int mxdep;
void dfs(int x,int y,int step)
{
if(bk) return;
if(x<y) swap(x,y);
if(x>=2*P) return;
if(x==0) return;
if(P%gcd(x,y)!=0) return;
if(step+f(x,y)>mxdep) return;
if(x==P or y==P) {bk=1;return;}
//x+y
dfs(x+y,x,step+1);dfs(x+y,y,step+1);
//x-y
dfs(x-y,x,step+1),dfs(x-y,y,step+1);
//x+x
dfs(x+x,x,step+1);dfs(x+x,y,step+1);
//y+y
dfs(y+y,x,step+1);dfs(y+y,y,step+1);
}
int main()
{
scanf("%d",&P);
for(mxdep=0;mxdep<=P;mxdep++)
{
dfs(1,0,0);
if(bk) break;
}
printf("%d",mxdep);
}

A*,稍微快一点点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=60;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int gcd(int x,int y)
{
return (y==0)?x:gcd(y,x%y);
}
int P;
int f(int x,int y)
{
if(y==P) return 0;
int ans=0;
while(x<P) x*=2,ans++;
return ans;
}
set<ull> has;
ull gethas(ull x,ull y)
{
return x*13331+y;
}
struct Nod
{
int x,y;
int step,cost;
Nod(int a=0,int b=0,int c=0,int d=0) {x=a,y=b,step=c,cost=d;}
friend bool operator > (Nod a,Nod b) {return a.step+a.cost>b.step+b.cost;}
};
priority_queue< Nod,vector<Nod>,greater<Nod> > q;
void push(int x,int y,int step)
{
if(x<y) swap(x,y);
if(x>=2*P) return;
if(x==0) return;
if(P%gcd(x,y)!=0) return;
ull hs=gethas(x,y);
if(has.count(hs)) return;
has.insert(hs);
q.push( Nod(x,y,step,f(x,y)) );
}
int bfs()
{
q.push( Nod(1,0,0,f(1,0)) );
has.insert( gethas(1,0) );
while(!q.empty())
{
Nod now=q.top();q.pop();
int x=now.x,y=now.y,step=now.step;
if(x==P or y==P) return step;
push(x+y,x,step+1);push(x+y,y,step+1);//x+y
push(x-y,x,step+1),push(x-y,y,step+1);//x-y
push(x+x,x,step+1);push(x+x,y,step+1);//x+x
push(y+y,x,step+1);push(y+y,y,step+1);//y+y
}
return -1;
}
int main()
{
scanf("%d",&P);
printf("%d",bfs());
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/9d2f.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%