首页 > 代码库 > 有一种恐怖，叫大爆搜

有一种恐怖，叫大爆搜

2024-11-22 01:50:01   203人阅读

到目前这个阶段，大爆搜做了好几个，有必要做一下小的总结了。

玛雅游戏：出门左转 http://www.cnblogs.com/Loser-of-Life/p/7247413.html的A

斗地主：出门右转http://www.cnblogs.com/Loser-of-Life/p/7259858.html的B

天鹅会面：出门直行http://www.cnblogs.com/Loser-of-Life/p/7295770.html的A

引水入城：链接：http://cogs.pro/cogs/problem/problem.php?pid=521

先正向$bfs$判断一下是否存在解，然后反向$bfs$，运用贪心策略选择最长线段进行覆盖。

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=505;
 8 int a[maxn][maxn],mp[maxn][maxn],l[maxn][maxn],r[maxn][maxn],n,m;
 9 int px[4]={1,-1,0,0},py[4]={0,0,1,-1};
10 typedef pair<int,int> pii;
11 void bfs(int b[maxn][maxn],int x,int y,int v,int f)
12 {
13     queue<pii>q;q.push(make_pair(x,y));b[x][y]=v;
14     while(!q.empty())
15     {
16         pii p=q.front();q.pop();
17         x=p.first,y=p.second;
18         for(int i=0;i<4;i++)
19         {
20             int nowx=x+px[i],nowy=y+py[i];
21             if(nowx<1||nowx>n||nowy<1||nowy>m||b[nowx][nowy])continue;
22             if(!f&&a[nowx][nowy]>=a[x][y])continue;
23             if(f&&a[nowx][nowy]<=a[x][y])continue;
24             b[nowx][nowy]=b[x][y];
25             q.push(make_pair(nowx,nowy));
26         }
27     }
28 }
29 struct data
30 {
31     int l,r;
32 }c[maxn];
33 inline bool cmp(data a,data b)
34 {
35     if(a.l!=b.l)return a.l<b.l;
36     return a.r<b.r;
37 }
38 int haha()
39 {
40     freopen("flow.in","r",stdin);
41     freopen("flow.out","w",stdout);
42     scanf("%d%d",&n,&m);
43     for(int i=1;i<=n;i++)
44         for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
45     for(int i=1;i<=m;i++)bfs(mp,1,i,1,0);
46     int tot=0;
47     for(int i=1;i<=m;i++)
48         if(!mp[n][i])tot++;
49     if(tot)
50     {
51         printf("0\n%d\n",tot);
52         return 0;
53     }
54     for(int i=1;i<=m;i++)
55         if(!l[n][i])bfs(l,n,i,i,1);
56     for(int i=m;i;i--)
57         if(!r[n][i])bfs(r,n,i,i,1);
58     for(int i=1;i<=m;i++)
59     {
60         if(!l[1][i])l[1][i]=r[1][i];
61         if(!r[1][i])r[1][i]=l[1][i];
62         c[i].l=l[1][i],c[i].r=r[1][i];
63     }
64     sort(c+1,c+m+1,cmp);
65     int now=0,to=0;
66     for(int i=1;i<=m;i++)
67         if(now+1>=c[i].l)to=max(to,c[i].r);
68         else
69         {
70             now=to;
71             to=max(to,c[i].r);
72             tot++;
73         }
74     if(now!=m)tot++;
75     printf("1\n%d\n",tot);
76 }
77 int sb=haha();
78 int main(){;}
cogs521

 靶形数独：链接：http://cogs.pro/cogs/problem/problem.php?pid=407

说好的状压启发式搜索呢？怎么是裸的$dfs$？虽然我很喜欢……港真，我今天下午颓了半下午这道题样例……和$wcx$比赛数独结果对面最后还剩两步发现他全错……欢声笑语中打出$GG$……

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int x,y;
 9 }V[101];
10 int v[9][9]={
11     {1,1,1,2,2,2,3,3,3},
12     {1,1,1,2,2,2,3,3,3},
13     {1,1,1,2,2,2,3,3,3},
14     {4,4,4,5,5,5,6,6,6},
15     {4,4,4,5,5,5,6,6,6},
16     {4,4,4,5,5,5,6,6,6},
17     {7,7,7,8,8,8,9,9,9},
18     {7,7,7,8,8,8,9,9,9},
19     {7,7,7,8,8,8,9,9,9}
20 },x,ans=-1,tim=0;
21 int w[9][9]={
22     {6,6,6,6,6,6,6,6,6},
23     {6,7,7,7,7,7,7,7,6},
24     {6,7,8,8,8,8,8,7,6},
25     {6,7,8,9,9,9,8,7,6},
26     {6,7,8,9,10,9,8,7,6},
27     {6,7,8,9,9,9,8,7,6},
28     {6,7,8,8,8,8,8,7,6},
29     {6,7,7,7,7,7,7,7,6},
30     {6,6,6,6,6,6,6,6,6}
31 },tot=0;
32 int vis[10][10],lx[10][10],ly[10][10];
33 void dfs(int rem,int now)
34 {
35     if(!rem)
36     {
37         ans=max(ans,now);
38         return;
39     }
40     for(int i=1;i<=9;i++)
41         if(!vis[v[V[rem].x][V[rem].y]][i]&&!lx[V[rem].x][i]&&!ly[V[rem].y][i])
42         {
43             vis[v[V[rem].x][V[rem].y]][i]=1;
44             lx[V[rem].x][i]=1;
45             ly[V[rem].y][i]=1;
46             dfs(rem-1,now+w[V[rem].x][V[rem].y]*i);
47             vis[v[V[rem].x][V[rem].y]][i]=0;
48             lx[V[rem].x][i]=0;
49             ly[V[rem].y][i]=0;
50         }
51 }
52 int haha()
53 {
54     freopen("sudoku.in","r",stdin);
55     freopen("sudoku.out","w",stdout);
56     int stat=0;
57     for(int i=0;i<9;i++)
58         for(int j=0;j<9;j++)
59         {
60             int x;scanf("%d",&x);
61             if(!x)V[++tot]=(node){i,j};
62             else 
63             {
64                 stat+=x*w[i][j];
65                 vis[v[i][j]][x]=lx[i][x]=ly[j][x]=1;
66             }
67         }
68     dfs(tot,stat);
69     printf("%d\n",ans);
70 }
71 int sb=haha();
72 int main(){;}
cogs407

传染病控制：链接：http://cogs.pro/cogs/problem/problem.php?pid=107

果然$CCF$老爷机啊……正常情况下每一次都是要剪枝的，但是在评测机上直接裸$dfs$，每一层暴力判断，改都不改就过了……

技术分享 
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=310;
 7 struct node
 8 {
 9     int from,to,next;
10 }edge[maxn<<1];
11 int head[maxn],tot;
12 void addedge(int u,int v)
13 {
14     edge[++tot]=(node){u,v,head[u]};head[u]=tot;
15 }
16 int fa[maxn],n,m,deep[maxn][maxn];
17 bool cutt[maxn];
18 void cut(int root)
19 {
20     cutt[root]=1;
21     for(int i=head[root];i;i=edge[i].next)
22     {
23         int v=edge[i].to;
24         if(v!=fa[root])cut(v);
25     }
26 }
27 void rebuild(int root)
28 {
29     cutt[root]=0;
30     for(int i=head[root];i;i=edge[i].next)
31     {
32         int v=edge[i].to;
33         if(v!=fa[root])rebuild(v);
34     }
35 }
36 int siz[maxn];
37 void dfs(int root,int dep)
38 {
39     siz[root]=1;deep[dep][++deep[dep][0]]=root;
40     for(int i=head[root];i;i=edge[i].next)
41     {
42         int v=edge[i].to;
43         if(v!=fa[root])
44         {
45             fa[v]=root;
46             dfs(v,dep+1);
47             siz[root]+=siz[v];
48         }
49     }
50 }
51 int maxl=-1;
52 void dfss(int dep,int num)
53 {
54     maxl=max(maxl,num);
55     for(int i=1;i<=deep[dep][0];i++)
56         if(!cutt[deep[dep][i]])
57         {
58             cut(deep[dep][i]);
59             dfss(dep+1,num+siz[deep[dep][i]]);
60             rebuild(deep[dep][i]);
61         }
62 }
63 int haha()
64 {
65     freopen("epidemic.in","r",stdin);
66     freopen("epidemic.out","w",stdout);
67     scanf("%d%d",&n,&m);
68     for(int i=1;i<=m;i++)
69     {
70         int u,v;scanf("%d%d",&u,&v);
71         addedge(u,v);addedge(v,u);
72     }
73     dfs(1,1);
74     dfss(2,0);
75     printf("%d\n",n-maxl);
76     //for(int i=1;i<=n;i++)cout<<siz[i]<<" ";
77     //puts("");
78 }
79 int sb=haha();
80 int main(){;}
cogs107

字串变换：链接：http://cogs.pro/cogs/problem/problem.php?pid=65

这果然是那个没有$STL$的时代啊……原来可是要$Hash$加$Treap$判重的，现在$std::queue$、$std::queue$、$std::map$、$std::string$直接碾压……除去这些，就是一个双向广搜。

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 #include<string>
 7 #include<queue>
 8 using namespace std;
 9 struct node
10 {
11     string s;int num;
12 };
13 queue<node>q1,q2;
14 map<string,int>m1,m2;
15 string changings[6][2];
16 int cnt,ans;
17 string become(string now,int pos,int n,string tmp)
18 {
19     return now.replace(pos,n,tmp);
20 }
21 bool dbfs()
22 {
23     while(!q1.empty()&&!q2.empty())
24     {
25         node s1=q1.front(),s2;q1.pop();
26         int len=s1.s.size();
27         for(int i=0;i<len;i++)
28             for(int j=0;j<cnt;j++)
29             {
30                 int siz=changings[j][0].size();
31                 if(i+siz-1<len&&!s1.s.compare(i,siz,changings[j][0])&&!m1.count(become(s1.s,i,siz,changings[j][1])))
32                 {
33                     s2.s=become(s1.s,i,siz,changings[j][1]);
34                     s2.num=s1.num+1;
35                     if(s2.num>10)return 0;
36                     m1[s2.s]=s2.num;q1.push(s2);
37                     if(m2.count(s2.s))
38                     {
39                         ans=s2.num+m2[s2.s];
40                         return 1;
41                     }
42                 }
43             }
44         s1=q2.front(),s2;q2.pop();
45         len=s1.s.size();
46         for(int i=0;i<len;i++)
47             for(int j=0;j<cnt;j++)
48             {
49                 int siz=changings[j][1].size();
50                 if(i+siz-1<len&&!s1.s.compare(i,siz,changings[j][1])&&!m2.count(become(s1.s,i,siz,changings[j][0])))
51                 {
52                     s2.s=become(s1.s,i,siz,changings[j][0]);
53                     s2.num=s1.num+1;
54                     if(s2.num>10)return 0;
55                     m2[s2.s]=s2.num;q2.push(s2);
56                     if(m1.count(s2.s))
57                     {
58                         ans=s2.num+m1[s2.s];
59                         return 1;
60                     }
61                 }
62             }
63     }
64     return 0;
65 }
66 int haha()
67 {
68     freopen("string.in","r",stdin);
69     freopen("string.out","w",stdout);
70     node a,b;cin>>a.s>>b.s;
71     if(a.s==b.s)
72     {
73         cout<<0;
74         return 0;
75     }
76     a.num=b.num=0;
77     q1.push(a);q2.push(b);
78     while(cin>>changings[cnt][0]>>changings[cnt][1])cnt++;
79     m1[a.s]=0;m2[b.s]=0;
80     if(dbfs())cout<<ans;
81     else puts("NO ANSWER!");
82 }
83 int sb=haha();
84 int main(){;}
cogs65

我回来一定要总结$std::string$来骗一波访问量（有生之年系列）

持续填坑中……

有一种恐怖，叫大爆搜


联系
我们