BUPT-SUMMER-TRAINING-搜索

2024-08-24 12:18
文章标签 搜索 training summer bupt

本文主要是介绍BUPT-SUMMER-TRAINING-搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛地址


A - Sticks

剪枝：

1、  由于所有原始棒子等长，那么必有sumlen % Initlen==0；

2、  若能在[maxlen,sumlen-InitLen]找到最短的InitLen，该InitLen必也是[maxlen,sumlen]的最短；若不能在[maxlen,sumlen-InitLen]找到最短的InitLen，则必有InitLen=sumlen；（类似迭代加深）

3、  由于所有棒子已降序排序，在DFS时，若某根棒子不合适，则跳过其后面所有与它等长的棒子，并且如果某个棒子无法配对，则比它短的也无法配对；

4、  最重要的剪枝：对于某个目标InitLen，在每次构建新的长度为InitLen的原始棒时，检查新棒的第一根stick[i]，若在搜索完所有stick[]后都无法组合，则说明stick[i]无法在当前组合方式下组合（如上一点所说），不用往下搜索(往下搜索会令stick[i]被舍弃)，直接返回上一层


#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}int sticks[70],n,sum,num,l;
bool mark[70];bool cmp(int a,int b)
{return a>b;
}bool dfs(int s,int le,int pos)
{int i;bool sign=le?false:true;if(s==num)return true;for(int i=pos+1;i<n;i++){if(mark[i])continue;     if(le+sticks[i]==l){mark[i]=true;if(dfs(s+1,0,-1))return true;mark[i]=false;return false;}else if(le+sticks[i]<l){mark[i]=true;if(dfs(s,le+sticks[i],i))return true;mark[i]=false;if(sign)return false;while(sticks[i]==sticks[i+1])i++;}}return false;
}int main()
{while(read(n)&&n){sum=0;for(int i=0;i<n;i++){read(sticks[i]);sum += sticks[i];}sort(sticks,sticks+n,cmp);for(l=sticks[0];l<=sum;l++){if(sum%l==0){num=sum/l;memset(mark,false,sizeof(mark));if(dfs(1,0,-1)){printf("%d\n",l);break;}}}}return 0;
}

B -  滑雪

记忆化搜索

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
//--------------------------------------------------------------------------int mapp[110][110],n,m;
int step[110][110];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; bool in(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m; 
}int dfs(int x,int y)
{if(step[x][y])return step[x][y];int maxx=1;for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(mapp[x][y]>mapp[xx][yy]&&in(xx,yy)){if(step[x][y]){if(maxx<step[x][y]+1)maxx=step[x][y]+1;}else{int temp=dfs(xx,yy);if(maxx<temp+1)maxx=temp+1;}	}} return step[x][y]=maxx;
}int main()
{read(n);read(m);int maxx=1;for(int i=0;i<n;i++)for(int j=0;j<m;j++)read(mapp[i][j]);	for(int i=0;i<n;i++)for(int j=0;j<m;j++){int temp=dfs(i,j);if(maxx<temp)maxx=temp;	}printf("%d\n",maxx);return 0;
}

C -  Destroying the bus stations

迭代加深，枚举毁掉的站点数，满足条件则输出

深搜之前先bfs一趟，确定一条最短路，然后在最短路上删点回溯

当最短路的距离大于k值是则直接返回。

同时，注意dfs的剪枝，用ovl记录上面层次搜索点的次数，如果上一层次已经搜索过，则下一层次可以不必要搜索。

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}const int INF=0x3f3f3f3f;
const int MAXN=55;
const int MAXE=4010;
short n,m,k,ans,tot;
short head[MAXN];
bool vis[MAXN],de[MAXN];
char ovl[MAXN],prv[MAXN][MAXN];
char q[MAXN];struct Edge
{short to;short next;
}e[MAXE];void add(int u,int v)
{e[tot].to=v;e[tot].next=head[u];head[u]=tot++;
}int len(char *prv)
{//计算找出的路径的长度int	u=n;//临时变量，指向一个点int	cnt=0;//计数变量，记录路径长度while(u!=1){u=prv[u];cnt++;}return cnt;
}bool bfs(char *prv)
{memset(vis,false,sizeof(vis));vis[1]=1;int front=0,tail=1;q[0]=1;while(front<tail){int u=q[front++];for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(de[v]||vis[v])     //deletedcontinue ;vis[v]=true;prv[v]=u;if(v==n){if(len(prv)>k)return true;return false;}q[tail++]=v;}}return true;
}bool dfs(int num)
{if(num>ans)return false;if(bfs(prv[num]))return true;for(int u=prv[num][n];u!=1;u=prv[num][u]){if(!ovl[u]){de[u]=1;if(dfs(num+1))//回溯，删掉u点return true;de[u]=0;}ovl[u]++;}for(int u=prv[num][n];u!=1;u=prv[num][u])ovl[u]--;return false;
}int main()
{while(read(n)&&read(m)&&read(k)&&n&&m&&k){tot=1;memset(head,-1,sizeof(head));for(int i=0;i<m;i++){int u,v;read(u);read(v);add(u,v);}for(ans=0;ans<n-1;ans++){memset(de,0,sizeof(de));memset(ovl,0,sizeof(ovl));if(dfs(0)){printf("%d\n",ans);break;}}}return 0;
}
D -  Eight

八数码问题，裸的bfs就行了

用康托展开记录是否询问过，前驱结点以及前驱结点的移动到改节点的方式

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;
typedef long double ld;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
//-----------------------------------------typedef vector<int> vec;
typedef vector<vec> mat;struct Node
{int b[3][3];int x,y;int hash;
}s,t;bool vis[400010];
int pre[400010];
char ans[400010];
int HASH[10]={1,1,2,6,24,120,720,5040,40320,362880};
int dir[4][2]={1,0,0,1,-1,0,0,-1};
char move[5]="drul";inline bool in(int x,int y)
{return ((x>=0)&&(y>=0)&&(x<=2)&&(y<=2));
}int cantos(Node tmp)
{int a[10],k=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++)a[k++]=tmp.b[i][j];int res=0;for(int i=0;i<9;i++){int k=0;for(int j=0;j<i;j++)if(a[j]>a[i])k++;res+=HASH[i]*k;}return res;
}bool isok(Node tmp)
{int a[10],k=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++)a[k++]=tmp.b[i][j];int sum=0;for(int i=0;i<9;i++)for(int j=i+1;j<9;j++)if(a[j]!=9&&a[i]!=9&&a[i]>a[j])sum++;return !(sum&1);
}void bfs()
{queue<Node> q;Node temp=s;vis[temp.hash]=true;q.push(temp);while(!q.empty()){temp=q.front();q.pop();int hh=temp.hash;//原康托for(int i=0;i<4;i++){t=temp;t.x+=dir[i][0];t.y+=dir[i][1];if(!in(t.x,t.y))continue;t.b[temp.x][temp.y]=temp.b[t.x][t.y];t.b[t.x][t.y]=9;int th=t.hash=cantos(t);if(vis[th])continue;vis[th]=true;q.push(t);
/*            for(int ik=0;ik<3;ik++){for(int j=0;j<3;j++)cout<<t.b[ik][j]<<" ";cout<<endl;}cout<<endl;system("pause");*/pre[th]=hh;ans[th]=move[i];if(th==0)return;}}
}void print(int now)
{if(now!=s.hash)print(pre[now]);elsereturn;printf("%c",ans[now]);
}int main()
{char str[100];while(gets(str)){memset(vis,0,sizeof(vis));memset(pre,-1,sizeof(pre));for(int i=0,k=0;i<3;i++)for(int j=0;j<3;j++){if((str[k]<='9'&&str[k]>='0')||str[k]=='x'){if(str[k]=='x')s.b[i][j]=9,s.x=i,s.y=j;elses.b[i][j]=str[k]-'0';}elsej--;k++;}if(!isok(s)){printf("unsolvable\n");continue;}s.hash=cantos(s);if(s.hash==0){puts("");continue;}bfs();print(0);putchar('\n');}return 0;
}

Astar的算法

评估函数应用曼哈顿距离，其余和上面一样

#include <stdio.h>  
#include <string.h>  
#include <math.h>  
#include <queue>  
#include <stack>  
#include <algorithm>  
using namespace std;  struct node  
{  int f,h,g;  int x,y;  char map[5][5];  friend bool operator< (const node &a,const node &b)  {  if(a.f==b.f)  return a.g<b.g;  return a.f>b.f;  }  
};  char str[100];  
node start,next;  
int hash[15];  
int pos[][2]= {{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};  
bool vis[500000];  
char ans[500000];  
int pre[500000];  
int to[4][2] = {1,0,0,1,-1,0,0,-1};  
char to_c[10] = "drul";  int check()//判断不可能的状况  
{  int i,j,k;  int s[20];  int cnt = 0;  for(i = 0; i<3; i++)  {  for(j = 0; j<3; j++)  {  s[3*i+j] = start.map[i][j];  if(s[3*i+j] == 'x')  continue;  for(k = 3*i+j-1; k>=0; k--)  {  if(s[k] == 'x')  continue;  if(s[k]>s[3*i+j])  cnt++;  }  }  }  if(cnt%2)  return 0;  return 1;  
}  int solve(node a)//康托  
{  int i,j,k;  int s[20];  int ans = 0;  for(i = 0; i<3; i++)  {  for(j = 0; j<3; j++)  {  s[3*i+j] = a.map[i][j];  int cnt = 0;  for(k = 3*i+j-1; k>=0; k--)  {  if(s[k]>s[3*i+j])  cnt++;  }  ans = ans+hash[i*3+j]*cnt;  }  }  return ans;  
}  int get_h(node a)//得到H值  
{  int i,j;  int ans = 0;  for(i = 0; i<3; i++)  {  for(j = 0; j<3; j++)  {  if(a.map[i][j] == 'x')  continue;  int k = a.map[i][j]-'1';  ans+=abs(pos[k][0]-i)+abs(pos[k][1]-j);  }  }  return ans;  
}  void bfs()  
{  memset(vis,0,sizeof(vis));  priority_queue<node> Q;  start.g = 0;  start.h = get_h(start);  start.f = start.h;  Q.push(start);  while(!Q.empty())  {  node a = Q.top();  Q.pop();  int k_s = solve(a);  for(int i = 0; i<4; i++)  {  next = a;  next.x+=to[i][0];  next.y+=to[i][1];  if(next.x < 0 || next.y < 0 || next.x>2 || next.y > 2)  continue;  next.map[a.x][a.y] = a.map[next.x][next.y];  next.map[next.x][next.y] = 'x';  next.g+=1;  next.h = get_h(next);  next.f = next.g+next.h;  int k_n = solve(next);  if(vis[k_n])  continue;  vis[k_n] = true;  Q.push(next);  pre[k_n] = k_s;  ans[k_n] = to_c[i];  if(k_n == 0)  return ;  }  }  
}  int main()  
{  int i,j,len,x,y;  hash[0] = 1;  for(i = 1; i<=9; i++)  hash[i] = hash[i-1]*i;  while(gets(str))  {  x = y = 0;  len = strlen(str);  for(i = 0; i<len; i++)  {  if(str[i]>='0' && str[i]<='9' || str[i]=='x')  {  start.map[x][y] = str[i];  if(start.map[x][y] == 'x')  {  start.x = x;  start.y = y;  }  y++;  if(y==3)  {  y = 0;  x++;  }  }  }  if(!check())  {  printf("unsolvable\n");  continue;  }  int sa = solve(start);  bfs();  stack<int> s;  int now = 0;  while(sa!=now)  {  s.push(ans[now]);  now = pre[now];  }  while(!s.empty())  {  putchar(s.top());  s.pop();  }  printf("\n");  }  return 0;  
}


E - ROADS

我的这份代码是 slf 优化的 spfa ，然后在push进入队列的时候要注意到达每个节点的钱的最小值，优先队列排序以长度为第一关键字，钱为第二关键字，升序

可以裸的 spfa 但是要注意钱的更新，关于到达每个节点的钱的最小值有一些机智的处理，，可以单独用数组隔开，也可以如下地直接带入点中

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}const int MAXN=110;
const int MAXE=10010;
struct Edge
{int to,l,cost;int next;
}e[MAXE];struct Node
{int sp,len,fee;bool operator<(const Node a)const{if(a.len==len)return a.fee<fee;return a.len<len;}
}pp[MAXN];
priority_queue<Node> qq;int money,n,m,tot,head[MAXE],dis[MAXN];void add(int x,int y,int ll,int v)
{e[tot].to=y;e[tot].l=ll;e[tot].cost=v;e[tot].next=head[x];head[x]=tot++;
}void spfa()
{while(!qq.empty())qq.pop();Node p1;p1.fee=0;p1.len=0;p1.sp=1;qq.push(p1);while(!qq.empty()){Node p2=qq.top();qq.pop();int x=p2.sp;if(x==n){printf("%d\n",p2.len);return;}for(int i=head[x];i!=-1;i=e[i].next){int y=e[i].to;if(p2.fee+e[i].cost<=money){p1.fee=p2.fee+e[i].cost;p1.len=p2.len+e[i].l;p1.sp=y;qq.push(p1);}}}printf("-1\n");return ;
}
int main()
{//freopen("data.txt","r",stdin);while(read(money)){tot=0;memset(head,-1,sizeof(head));read(n);read(m);for(int i=1;i<=m;++i){int x,y,ll,v;read(x);read(y);read(ll);read(v);add(x,y,ll,v);}spfa();}return 0;
}

F -  Paint Me Less

IDA*，应该是属于比较裸的那种吧

<pre name="code" class="cpp">#include <iostream>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;#define DEBUG 0#define my_abs(x)   ((x)>0?(x):-(x))int dx[4] = {1, 0, 0, -1}; // d r l u
int dy[4] = {0, 1, -1, 0};typedef struct sdfkllsdjf
{int x[10000],y[10000],c[10000];int top;
}My_Path;My_Path path;typedef struct sdfl
{int d[5][5];int color[20];
}MAP;MAP maze;int ans_flag = 0,mi;
int r,c;
int color_flag[20],color[20];void My_Path_Push(int a,int b,int x)
{int t = path.top;path.x[t] = a;path.y[t] = b;path.c[t] = x;path.top++;
}void output()
{int t = path.top;printf("%d\n",path.top);for(int i = 0;i< t;i++){printf("%d %d %d\n",path.x[i]+1,path.y[i]+1,path.c[i]);}
}bool Judge(int x,int y)
{if(x>=0&&x<r&&y>=0&&y<c)return true;return false;
}bool neigbor(MAP m,int x,int y,int k) //判断x y位置的邻居是否有颜色K
{for(int i = 0;i<4;i++){int nx = x + dx[i];int ny = y + dy[i];if(!Judge(nx,ny))continue;if(m.d[nx][ny] == k)return true;}return false;
}void FillMap(MAP * m,int x,int y ,int color,int pre_color,int flag)
{int i;m->d[x][y] = color;for( i = 0;i<4;i++){int nx = x + dx[i];int ny = y + dy[i];if(!Judge(nx,ny))continue;if(m->d[nx][ny] != pre_color)continue;FillMap(m,nx,ny,color,pre_color,0);}if(!flag)return ;memset(m->color,0,sizeof(m->color));for( i = 0;i< r;i++){for (int j= 0;j<c;j++){if(m->d[i][j] != 0)m->color[m->d[i][j]] = 1;}}
}
//hash 从TLE 到 3200+msbitset<1000024> vst[25];
int hash(MAP m)
{unsigned __int64 sum = 0;for(int i = 0;i<r;i++){for (int j = 0;j<c;j++)sum = m.d[i][j] + sum*131;}return (sum % 1000007);
}int H(int color[])
{int sum = 0;for(int i = 0;i<20;i++){if(color[i])sum++;}return sum;
}void dfs(MAP m,int Ndp,int Maxdp)
{int h = H(m.color);if(mi>h)mi = h;if(Ndp + h >Maxdp || ans_flag == 1)return ;if(h == 0){output();ans_flag = 1;return ;}for(int i = 0;i< r;i++){for(int j= 0;j< c;j++){for(int k = 0;k< 20;k++){if( k!=0 && !m.color[k])continue;   //如果地图中不存在那种颜色，那么没必要涂if(k ==m.d[i][j])continue;   //如果将要涂的颜色个本来的颜色相同。那么没必要涂if(k!= 0 && !neigbor(m,i,j,k))continue; //重要剪枝 从3200+ms 减到 250+ms。x,y位置的颜色要么变成0，要么变成邻居的颜色，其他的都是没有意义的MAP tmp_map = m;FillMap(&tmp_map,i,j,k,tmp_map.d[i][j],1);int t = hash(tmp_map);if(vst[Ndp+1][t])continue;vst[Ndp+1][t] = 1;My_Path_Push(i,j,k);dfs(tmp_map,Ndp+1,Maxdp);if(ans_flag == 1)return ;path.top--;}}}
}void IDA()
{int maxdp = H(maze.color);ans_flag = 0;while(ans_flag ==0){for(int i = 0;i<= maxdp;i++)vst[i].reset();mi = 0x7fffffff;path.top = 0;dfs(maze,0,maxdp);mi = 1;maxdp += mi;}
}int main()
{while(scanf("%d %d",&r,&c) == 2){memset(maze.color,0,sizeof(maze.color));for(int i = 0;i<r;i++){for(int j= 0;j< c;j++){scanf("%d",&maze.d[i][j]);if(maze.d[i][j])maze.color[maze.d[i][j]] = 1;}}IDA();}return 0;
}


 
G -  
Remmarguts' Date 

 裸的第K短路，用Astar 

 

评估函数用从终点spfa预处理后到达每一个节点的最短距离
 

在Astar的时候，当终点第K次出队列的时候，则此时的实际代价（G）则为答案
 

 

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
const int MAXN =1005;
const int MAXM=500005;
const int INF=0x3f3f3f3f;
int n,m,k,tot=0,rtot=0,T,S;
int h[MAXN],rh[MAXN];
int d[MAXN];
bool vis[MAXN];struct Node
{int f,g,to;bool operator < (const Node b) const{return f>b.f;}	
};struct Edge
{int to,next,l;
}e[MAXM],re[MAXM];void add(int x,int y,int l)
{tot++;e[tot].to=y;e[tot].l=l;e[tot].next=h[x];h[x]=tot;
}void radd(int x,int y,int l)
{rtot++;re[rtot].to=y;re[rtot].l=l;re[rtot].next=rh[x];rh[x]=rtot;
}void spfa()
{memset(vis,0,sizeof(vis)); queue<int> q;for(int i=1;i<=n;i++)d[i]=INF;d[T]=0;vis[T]=1;q.push(T);while(!q.empty()){int x=q.front();q.pop();vis[x]=0;    //出栈可访问for(int i=rh[x];i!=-1;i=re[i].next){int y=re[i].to;if(d[y]>d[x]+re[i].l){d[y]=d[x]+re[i].l;if(!vis[y]){q.push(y);vis[y]=1;}}} }
}int Astar()
{int cnt=0;priority_queue<Node> heap;Node t;if(S==T)k++;if(d[S]==INF)return -1;t.f=d[S],t.g=0,t.to=S;heap.push(t);while(!heap.empty()){Node x=heap.top();heap.pop();if(x.to==T)cnt++;if(cnt==k)return x.g;for(int i=h[x.to];i!=-1;i=e[i].next){t.g=x.g+e[i].l;t.f=t.g+d[e[i].to];t.to=e[i].to;heap.push(t);}}return -1;
}int main()
{while(read(n)&&read(m)){memset(rh,-1,sizeof(rh));memset(h,-1,sizeof(h));for(int i=0;i<m;i++){int u,v,l;read(u);read(v);read(l);add(u,v,l);radd(v,u,l);}read(S);read(T);read(k);spfa();printf("%d\n",Astar());}return 0;
}
 

 

 

 

还有几题先放着吧.....如果有写了就更新

                                    

                                        这篇关于BUPT-SUMMER-TRAINING-搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
                                    

                                    

                                

                            

                            

                        

                    

                    

                        

                            

                            http://www.chinasem.cn/article/1102452。
                            
                        

                    

                    
                    

                        
                            
                        
                    

                

                

                    相关文章
                

                    

                        

                            

                                

                                    
                                        认识、理解、分类——acm之搜索
                                    
                                

                            

                            

                                

                                    认识、理解、分类——acm之搜索
                                

                                

                                    普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）；   搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        hdu1240、hdu1253（三维搜索题）
                                    
                                

                            

                            

                                

                                    hdu1240、hdu1253（三维搜索题）
                                

                                

                                    1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下：  #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        hdu 4517 floyd+记忆化搜索
                                    
                                

                            

                            

                                

                                    hdu 4517 floyd+记忆化搜索
                                

                                

                                    题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。  现在求，从起点出发，到达终点，在时间限制内，能得到的最大
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        2014 Multi-University Training Contest 8小记
                                    
                                

                            

                            

                                

                                    2014 Multi-University Training Contest 8小记
                                

                                

                                    1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包， 凸包上的点（ 注意不是端点 ） 才拥有无限的面积 注意 ：  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。  int  cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1  ;}struct poin
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        2014 Multi-University Training Contest 7小记
                                    
                                

                            

                            

                                

                                    2014 Multi-University Training Contest 7小记
                                

                                

                                    1003   数学 ， 先暴力再解方程。 在b进制下是个2 ， 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力  typedef   long  long  LL ;LL    n  ;int   ok(int b){LL m = n ;int  c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        2014 Multi-University Training Contest 6小记
                                    
                                

                            

                            

                                

                                    2014 Multi-University Training Contest 6小记
                                

                                

                                    1003  贪心 对于111...10....000 这样的序列，  a 为1的个数，b为0的个数，易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。  const  int  maxn = 100008 ;struct   Node{int
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        AI基础 L9 Local Search II 局部搜索
                                    
                                

                            

                            

                                

                                    AI基础 L9 Local Search II 局部搜索
                                

                                

                                    Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        hdu4277搜索
                                    
                                

                            

                            

                                

                                    hdu4277搜索
                                

                                

                                    给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        浙大数据结构：04-树7 二叉搜索树的操作集
                                    
                                

                            

                            

                                

                                    浙大数据结构：04-树7 二叉搜索树的操作集
                                

                                

                                    这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        【python计算机视觉编程——7.图像搜索】
                                    
                                

                            

                            

                                

                                    【python计算机视觉编程——7.图像搜索】
                                

                                

                                    python计算机视觉编程——7.图像搜索 7.图像搜索7.1 基于内容的图像检索（CBIR）从文本挖掘中获取灵感——矢量空间模型（BOW表示模型）7.2 视觉单词**思想****特征提取**：  创建词汇7.3 图像索引7.3.1 建立数据库7.3.2 添加图像 7.4 在数据库中搜索图像7.4.1 利用索引获取获选图像7.4.2 用一幅图像进行查询7.4.3 确定对比基准并绘制结果 7.
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2