[关闭]
@wwwqeqeqeqe 2019-05-12T09:13:00.000000Z 字数 7473 阅读 696

搜索问题讨论（2019.5.14）

搜索

A Sticks （POJ 1011）

题目大意：

给出n个木棍，将这些木棍进行组合，使得所有组合后的木棍长度相同。问，我们能得到的最小的长度是多少？将这个长度输出。

解题思路：

一个很裸的DFS，但是在搜索的过程中，我们需要注意以下几个问题：
1、我们最后得到的长度很显然，最短为我们输入的所有数字中最大的那个，最长为所有木棍的长度总和。
2、在搜索的过程中，当我们发现和某一长度的木棍拼接失败后，就不要再继续和相同长度的木棍进行结合了。
3、在拼木棍是，我们应该先拼长的，后拼短的，因为相对而言，长的木棍更不容易被其他木棍选择进行拼接。
所以，我们可以对得到的木棍进行一个排序，然后在选择木棍时，对我们选择的木棍进行一个标记，如果这个木棍不适合我们这次的拼接，那么，后面相同长度的所有木棍都直接跳过。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. int s[70],vis[70];
  9. int n,len,num;
  11. bool cmp(int x, int y)
  12. {
  13.     return x>y;
  14. }
  16. int dfs(int c,int k,int cnt)
  17. {
  18.     if(cnt == num)
  19.         return 1;
  20.     if(c == len)
  21.         return dfs(0,0,cnt+1);
  22.     int i,pre=0;
  23.     for(i=k;i<n;i++)
  24.     {
  25.         if(vis[i] == 0 && s[i]+c<=len && s[i]!=pre)
  26.         {
  27.             pre=s[i];
  28.             vis[i]=1;
  29.             if(dfs(s[i]+c,i+1,cnt))
  30.                 break;
  31.             vis[i]=0;
  32.             if(k == 0)
  33.                 return 0;
  34.         }
  35.     }
  36.     if(i == n)
  37.         return 0;
  38.     return 1;
  39. }
  41. int main()
  42. {
  43.     while(cin >> n && n)
  44.     {
  45.         memset(s,0,sizeof(s));
  46.         memset(vis,0,sizeof(vis));
  47.         int sum=0;
  48.         for(int i=0;i<n;i++)
  49.         {
  50.             cin >> s[i];
  51.             sum+=s[i];
  52.         }
  53.         sort(s,s+n,cmp);
  54.         len=s[0];
  55.         for(len;len<=sum/2;len++)
  56.         {
  57.             if(sum%len == 0)
  58.             {
  59.                 num=sum/len;
  60.                 if(dfs(0,0,0))
  61.                     break;
  62.             }
  63.         }
  64.         if(len>sum/2)
  65.             cout << sum << endl;
  66.         else
  67.             cout << len << endl;
  68.     }
  69.     return 0;
  70. }

B Best Sequence （POJ 1699）

题目大意：

题目给出n个只包含‘A’，‘C’，‘G’，‘T’的字符串，若某个字符串结尾的几个字符和另一个字符串开头的几个字符相同，他们就可以共用这些字符。问将这些字符串全部结合在一起后的字符串最短的长度。

解题思路：

通过DFS枚举所有的情况，将已经搜索过的字符串做一个标记，我们将已经搜过的串所组成的那个字符串开个数组存起来，每次从这个字符串的结尾和我们搜索的字符串进行比较，如果满足题目条件就往这个字符串里面继续加，直到最后加完所有的字符串为止。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. char str[12][22] ;
  9. char s[300], s1[300] ;
  10. int vis[12], min1, n, l[12];
  12. void dfs(int cnt,int k)//cnt表示组合后的串的长度，k表示组合了这么多个串
  13. {
  14.     if( cnt >= min1 ) 
  15.         return ;
  16.     if(k == n)
  17.     {
  18.         min1 = min(min1,cnt) ;
  19.         return ;
  20.     }
  21.     int num ;
  22.     for(int i = 0 ; i < n ; i++)
  23.     {
  24.         if( vis[i] ) 
  25.             continue ;
  26.         vis[i] = 1 ;
  27.         for(int p = max(0,cnt-l[i]) ; p <= cnt ; p++)
  28.         {
  29.             for(int q = p ; q < cnt ; q++)
  30.                 if( str[i][q-p] != s[q] ) 
  31.                     break ;
  32.             if( q == cnt )
  33.             {
  34.                 num = cnt ;
  35.                 for(int q = q-p ; q < l[i] ; q++)
  36.                     s[num++] = str[i][q] ;
  37.                 break ;
  38.             }
  39.         }
  40.         dfs(num,k+1) ;
  41.         vis[i] = 0 ;
  42.     }
  43.     return ;
  44. }
  45. int main()
  46. {
  47.     int t ;
  48.     scanf("%d", &t) ;
  49.     while( t-- )
  50.     {
  51.         scanf("%d", &n) ;
  52.         for(int i = 0 ; i < n ; i++)
  53.         {
  54.             scanf("%s", str[i]) ;
  55.             l[i] = strlen(str[i]) ;
  56.         }
  57.         min1 = 1000 ;
  58.         memset(s,0,sizeof(s)) ;
  59.         memset(vis,0,sizeof(vis)) ;
  60.         dfs(0,0) ;
  61.         printf("%d\n", min1) ;
  62.     }
  63.     return 0 ;
  64. }

C Paid Roads (POJ 3411)
题目大意：

这里有n座城市和m条路，现在要从城市1走到城市n，其中，通过这些路是需要收费的，从城市a到城市b之前如果到过城市c，那么收取过路费p元，否则收取q元。问从城市1到城市n最少需要花费多少钱？

解题思路：

这个题和其他最短路的最大区别在于，这个题并不一定是每条路都走当前最优解进行通行，可能重复通过某些对象能得到更优的解，即可能会走一遍环什么的。但我们又不能始终重复这个操作，这样会死循环下去，于是，我们对所有的点进行一个标记，因为我们的m最大只有10，那么，我们可以设置一个阈值k，当一个人到达这个城市大于k次后，我们则认为他进入了死循环，然后dfs即可。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int INF=0x3f3f3f3f;
  9. int n,m;
  10. int vis[11];
  11. int ans;
  13. struct node
  14. {
  15.     int a,b,c,p,r;
  16. } r[11];
  19. void dfs(int x,int cost)
  20. {
  21.     if(x==n)
  22.     {
  23.         if(cost < ans)
  24.             ans=cost;
  25.         return;
  26.     }
  27.     for(int i=1; i<=m; i++)
  28.         if(r[i].a==x&&vis[r[i].b]<=3)
  29.         {
  30.             vis[r[i].b]++;
  31.             if(vis[r[i].c]>0)
  32.                 dfs(r[i].b,cost+r[i].p);
  33.             else
  34.                 dfs(r[i].b,cost+r[i].r);
  35.             vis[r[i].b]--;
  37.         }
  38.     return;
  39. }
  41. int main()
  42. {
  43.     cin>>n>>m;
  44.     for(int i=1; i<=m; i++)
  45.         cin>>r[i].a>>r[i].b>>r[i].c>>r[i].p>>r[i].r;
  46.     vis[1]=1;
  47.     ans=INF;
  48.     dfs(1,0);
  49.     if(ans==INF)
  50.         cout<<"impossible"<<endl;
  51.     else
  52.         cout<<ans<<endl;
  55. }

D Changing Digits (POJ 3373)

题目大意：

题目给出两个数字n和k，要求出满足一下条件的数字m。
1、m的位数和n相同。
2、m能被k整除。
3、在满足前两个条件的基础下，m和n在相同位置的地方，数字不同的个数最少。
4、在满足前三个条件的情况下，m尽量小。

解题思路：

我们可以通过DFS对这些条件进行一步一步的运算，首先要满足m最高位非0（除去m=0）且和n位数相同，m能被k整除，在满足m和n在对应位置上不相等数量尽量少，再满足m尽量小。由于n这个数字很大，我们可以需要通过数组对数据进行存储，因为在最后， 我们是计算对k取模的值，那么我们可以开一个数组mod[i][j]用来预处理（10^i）*j模k的值。这样，在改变某一位后，m%k的值也能较快的计算出来。为了使得到的m最小，我们先从m<n开始搜索，再从m>n搜索，其中，当m<n时，res=（m_modk-(mod[i][n[i]]-mod[i][j]+k）%k,当m>n时，res=(m_modk+(mod[i][j]-mod[i][n[i]+k)%k,并对修改过的位打上标记。令引入flag数组进行剪枝，当搜索区间为[0,pos]且此时m%k=m_modk时，如果最多修改restnum位不能成功，那么，修改小于这个位数的位也是不能成功的，就不用继续搜索了。

AC代码:

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=1e2+5;
  9. const int maxk=1e4+5;
  11. int len, k, n[maxn], mod[maxn][10];
  12. int m[maxn], flag[maxn][maxk];
  13. char num[maxn];
  15. void init_mod()//mod[i][j]表示(10^i)*j模k的值
  16. {
  17.     for (int i = 0; i <= 9; i++)
  18.         mod[0][i] = i % k;
  19.     for (int i = 1; i < len; i++)
  20.         for (int j = 0; j <= 9; j++)
  21.             mod[i][j] = (mod[i-1][j] * 10) % k;
  22. }
  24. int dfs(int pos,int restnum,int m_modk)
  25. {
  26.     if (!m_modk)
  27.         return 1;
  28.     if (!restnum || pos < 0)
  29.         return 0;
  30.     if (restnum <= flag[pos][m_modk])
  31.         return 0;
  32.     for (int i = pos; i > -1; i--)//搜索比n小的数，要尽可能小，则从高位开始
  33.         for (int j = 0; j < n[i]; j++)
  34.         {
  35.             if (i == len - 1 && !j)
  36.                 continue;
  37.             int res = (m_modk - (mod[i][n[i]] - mod[i][j]) + k) % k;
  38.             m[i] = j;
  39.             if (dfs(i - 1, restnum - 1, res))
  40.                 return 1;
  41.             m[i] = n[i];
  42.         }
  43.     for (int i = 0; i <= pos; i++)//搜索比n大的数，要尽可能小，则从低位开始
  44.         for (int j = n[i] + 1; j < 10; j++)
  45.         {
  46.             int res = (m_modk + (mod[i][j] - mod[i][n[i]]) + k) % k;
  47.             m[i] = j;
  48.             if (dfs(i - 1, restnum - 1, res))
  49.                 return 1;
  50.             m[i] = n[i];
  51.         }
  52.     flag[pos][m_modk] = restnum;//能运行到这里说明搜索失败，更新剪枝数值
  53.     return 0;
  54. }
  56. int main()
  57. {
  58.     while (~scanf("%s%d", num, &k))
  59.     {
  60.         int n_modk = 0;
  61.         len = strlen(num);
  62.         init_mod();
  63.         for (int i = 0; i < len; i++)//将num反序存入整型数组
  64.         {
  65.             n[i] = num[len-1-i] - '0';
  66.             m[i] = n[i];
  67.             n_modk = (n_modk + mod[i][ n[i] ]) % k;//计算n % k
  68.         }
  69.         memset(flag, 0, sizeof(flag));
  70.         int ok = 0;
  71.         for (int i = 1; i <= len; i++)//从小到大枚举可以修改的位数
  72.             if (dfs(len - 1, i, n_modk))
  73.                 break;
  74.         for (int i = len - 1; i > -1; i--)
  75.             printf("%d", m[i]);
  76.         printf("\n");
  77.     }
  78.     return 0;
  79. }

E The Treasure （POJ 1924）

题目大意：

题目给出一张地图，地图中有六种字符，‘#’表示墙，‘p’表示人最初始的位置，‘t’表示终点，‘.’表示可以走的路，‘a’表示有攻击欲望的怪，可以攻击他周围的九个格子，‘n’表示没有攻击欲望的怪，只会攻击自己所处的格子。人每次可以像自己的周围八个方向移动一或两格，或不动。怪兽会在固定的循环内移动自己的位置，题目给出所有怪物的移动轨迹。人每次移动不能穿墙，也不能从会被怪兽攻击的格子中穿过。且每次移动是怪兽先移动，即人站在怪兽下一秒的攻击范围内也会死。问人最少需要多少时间到达终点。题目保证最少时间不会超过100S，如果100S内不能到达终点，则输出impossible。

解题思路：

因为我们的怪物是会动的，而且最多只会有100S，那么我们可以建一个地图来预处理我们的地图，在预处理地图时，要注意每次是怪物先走，要考虑到怪物走了一秒后在人还没动的时候就把人吃掉这一种情况。接下来就是BFS跑图就可以了。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<queue>
  7. using namespace std;
  9. const int maxn=1e2+5;
  11. int n,m,ans,cnt;
  12. int sx,sy,ex,ey;
  13. char s[maxn];
  15. int walkx[9]= {-1,1,0,0,-1,-1,1,1,0};  // walk stay
  16. int walky[9]= {0,0,-1,1,-1,1,-1,1,0};
  17. int runx[8]= {-2,2,0,0,-2,-2,2,2};     // run
  18. int runy[8]= {0,0,-2,2,-2,2,-2,2};
  20. bool mp[maxn][maxn][maxn];             // time x y
  21. bool tmp[maxn][maxn];
  22. bool vis[maxn][maxn][maxn];            // time x y    三维数组判重
  23. bool type[maxn];
  24. struct node
  25. {
  26.     int step;
  27.     int xx,yy;
  28. } cur,now;
  29. queue<node>q;
  31. bool isok(int x1,int y1,int tst,int dir,int flag)       // 判断是否能走
  32. {
  33.     int i,j,xx,yy,temp,xx1,yy1;
  34.     if(x1<1||x1>n||y1<1||y1>m||vis[tst][x1][y1]||tst>100) return false ;
  35.     if(flag)                          // 如果是跑的话  还要注意不能穿过墙和怪物级攻击范围
  36.     {
  37.         x1-=walkx[dir];
  38.         y1-=walky[dir];
  39.         if(mp[tst][x1][y1]) return false ;
  40.         x1+=walkx[dir];
  41.         y1+=walky[dir];
  42.         if(mp[tst][x1][y1]||mp[tst][x1-runx[dir]][y1-runy[dir]])
  43.             return false ;
  44.     }
  45.     else if(mp[tst][x1][y1]||mp[tst][x1-walkx[dir]][y1-walky[dir]])
  46.         return false ;
  47.     return true ;
  48. }
  50. bool bfs()
  51. {
  52.     int i,j;
  53.     int nx,ny,nstep,tx,ty,tstep;
  54.     while(!q.empty())
  55.         q.pop();
  56.     memset(vis,0,sizeof(vis));
  57.     cur.xx=sx;
  58.     cur.yy=sy;
  59.     cur.step=0;
  60.     q.push(cur);
  61.     vis[0][sx][sy]=1;
  62.     while(!q.empty())
  63.     {
  64.         now=q.front();
  65.         nx=now.xx;
  66.         ny=now.yy;
  67.         nstep=now.step;
  68.         if(nx==ex&&ny==ey)
  69.         {
  70.             ans=nstep;
  71.             return true ;
  72.         }
  73.         for(i=0; i<9; i++)           // 走的8个方向及站着不动
  74.         {
  75.             tx=nx+walkx[i];
  76.             ty=ny+walky[i];
  77.             tstep=nstep+1;
  78.             if(isok(tx,ty,tstep,i,0))
  79.             {
  80.                 vis[tstep][tx][ty]=1;
  81.                 cur.xx=tx;
  82.                 cur.yy=ty;
  83.                 cur.step=tstep;
  84.                 q.push(cur);
  86.             }
  87.             if(i<8)                  // 跑的8个方向
  88.             {
  89.                 tx=nx+runx[i];
  90.                 ty=ny+runy[i];
  91.                 tstep=nstep+1;
  92.                 if(isok(tx,ty,tstep,i,1))
  93.                 {
  94.                     vis[tstep][tx][ty]=1;
  95.                     cur.xx=tx;
  96.                     cur.yy=ty;
  97.                     cur.step=tstep;
  98.                     q.push(cur);
  99.                 }
  100.             }
  101.         }
  102.         q.pop();
  103.     }
  104.     return false ;
  105. }
  106. int main()
  107. {
  108.     int i,ii,j,jj,p,ss,k=0,monx,mony;
  109.     while(scanf("%d%d",&n,&m),n||m)
  110.     {
  111.         memset(tmp,1,sizeof(tmp));       // 存原始地图
  112.         cnt=0;
  113.         for(int i=1; i<=n; i++)
  114.         {
  115.             scanf("%s",s);
  116.             for(int j=1; j<=m; j++)
  117.             {
  118.                 if(s[j-1]=='.')
  119.                 {
  120.                     tmp[i][j]=0;
  121.                 }
  122.                 else if(s[j-1]=='p')
  123.                 {
  124.                     tmp[i][j]=0;
  125.                     sx=i;
  126.                     sy=j;
  127.                 }
  128.                 else if(s[j-1]=='t')
  129.                 {
  130.                     tmp[i][j]=0;
  131.                     ex=i;
  132.                     ey=j;
  133.                 }
  134.                 else if(s[j-1]=='a')
  135.                 {
  136.                     tmp[i][j]=0;
  137.                     cnt++;
  138.                     type[cnt]=1;
  139.                 }
  140.                 else if(s[j-1]=='n')
  141.                 {
  142.                     tmp[i][j]=0;
  143.                     cnt++;
  144.                     type[cnt]=0;
  145.                 }
  146.             }
  147.         }
  148.         for(int i=1; i<=100; i++)
  149.         {
  150.             memcpy(mp[i],tmp,sizeof(tmp));
  151.         }
  152.         scanf("%d",&p);
  153.         for(int i=1; i<=p; i++)          // 将每一个时间地图的情况都预处理出来   则可将怪物看做墙
  154.         {
  155.             scanf("%d",&ss);
  156.             for(int j=0; j<ss; j++)
  157.             {
  158.                 scanf("%d%d",&monx,&mony);
  159.                 if(type[i])
  160.                 {
  161.                     for(int jj=j; jj<=102; jj+=ss)
  162.                     {
  163.                         for(int ii=0; ii<9; ii++)
  164.                         {
  165.                             mp[jj][monx+walkx[ii]][mony+walky[ii]]=1;
  166.                         }
  167.                     }
  168.                 }
  169.                 else
  170.                 {
  171.                     for(int jj=j; jj<=102; jj+=ss)
  172.                     {
  173.                         mp[jj][monx][mony]=1;
  174.                     }
  175.                 }
  176.             }
  177.         }
  178.         k++;
  179.         if(k!=1)
  180.             printf("\n");
  181.         if(bfs())
  182.             printf("%d\n",ans);
  183.         else
  184.             printf("impossible\n");
  185.     }
  186.     return 0;
  187. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注