网站开发公司需要那些硬件设备腾讯域名服务商

当前位置： 首页 > news >正文

网站开发公司需要那些硬件设备,腾讯域名服务商,广州企业网站设计公司,ps做的网站怎样在dw里打开有时候从一个点能扩展出来的情况很多#xff0c;这样几层之后搜索空间就很大了#xff0c;我们采用从两端同时进行搜索的策略#xff0c;压缩搜索空间。

1. 字串变换(190. 字串变换 - AcWing题库) 思路#xff1a;这题因为变化规则很多#xff0c;所以我们一层一层往外…有时候从一个点能扩展出来的情况很多这样几层之后搜索空间就很大了我们采用从两端同时进行搜索的策略压缩搜索空间。
2. 字串变换(190. 字串变换 - AcWing题库) 思路这题因为变化规则很多所以我们一层一层往外扩展的时候扩展几层后空间就会变得很大 那么就需要换一个思路我们这里采用双向广搜从两个方向来进行搜索具体执行的时候肯定得先从一个方向开始那么从哪里开始呢显然要从状态少的方向开始我们就比较两个队列从小的那个队列开始然后又有新问题了如果从一个方向开始什么时候判停去找下一个方向显然我们可以只往外扩展一层扩展结束或者两者头尾交汇的时候停止。 现在理一下我们需要哪些数据结构首先得有两个队列分别记录从头搜索和从尾搜索的队列另外要有两个数据结构来记录每个状态从头和从尾更新到它们时的距离。另外还要记录一下变换规则。 还有就是我们每次只往外扩展一层所以有交汇和不交汇两种情况如果交汇的话那么我们可以直接返回从头到这个点和从尾到这个点的步数和如果这个值小于10那么显然就是最小距离因为我们每次只从头或者从尾往外扩展一层下次扩展时找到的一定比当前扩展找到的多一步。当然也可能不交汇因为我们只往外扩展一层不交汇的时候返回一个大于10的数即可。同时我们每一次往外扩展都要记录步数当步数大于10的时候直接停下。因为题目要求的上限就是10步。 对了如果想把两个扩展函数写在一起一定要传入它们的更新规则两者的扩展规则是不一样的。 #includebits/stdc.h using namespace std; string a[10],b[10]; int n; int expend(queuestringq,unordered_mapstring,intdl,unordered_mapstring,intdr,string a[],string b[]) {int ddl[q.front()];while(q.size()dl[q.front()]d){auto tq.front();//couttendl;q.pop();for(int i0;in;i){for(int j0;jt.size();j){if(t.substr(j,a[i].size())a[i]){string tmpt.substr(0,j)b[i]t.substr(ja[i].size());if(dr.count(tmp)) return dl[t]dr[tmp]1;if(dl.count(tmp)) continue;q.push(tmp);dl[tmp]dl[t]1;}}}}return 11; } int bfs(string s,string e) {if(se) return 0;queuestringql,qr;unordered_mapstring,intdl,dr;ql.push(s),qr.push(e);dl[s]dr[e]0;int step0;while(ql.size()qr.size()){int t;if(ql.size()qr.size()) texpend(ql,dl,dr,a,b);else texpend(qr,dr,dl,b,a);if(t10) return t;if(step10) return -1;}return -1; } int main() {string s,e;cinse;n0;while(cina[n]b[n])n;int ansbfs(s,e);if(ans-1) coutNO ANSWER!;else coutans; } 另外这里补充一下substr()的用法 形式 s.substr(pos, len) 返回值 string包含s中从pos开始的len个字符的拷贝pos的默认值是0len的默认值是s.size() - pos即不加参数会默认拷贝整个s 异常 若pos的值超过了string的大小则substr函数会抛出一个out_of_range异常若posn的值超过了string的大小则substr会调整n的值只拷贝到string的末尾 参考链接C中substr()函数用法详解_substr c-CSDN博客 A—star算法 A—star算法也是对搜索空间进行压缩进而优化搜索。这里我们选择下一个搜索位置的时候并不是根据它们到起点的位置来选择的而是根据它们到起点的位置到终点的预估值来进行选择可以这么来理解我们之前的bfs都是假设到终点的预估值为0那么直接放入队列即可这里需要用到优先队列将从起点搜到的实际距离到终点预估距离作为权重放入优先队列。而预估距离要满足的条件就是小于真实距离而且要是答案有解的情况下才能使用这个算法否则不如bfs。 而且可以证明终点第一次出队的时候是得到的距离是最小距离。 参考链接 AcWing 178. 第K短路(A* 反向计算最短路作为到终点的估计值) - AcWing
3. 第K短路178. 第K短路 - AcWing题库 思路这道题要求起点到终点的第k短路我们已知终点第一次出队的时候是最短路那么第二次出队就是第儿短路因为这条路径是被其他点更新了放进队列的以此类推我们只要获得终点第k次出队时的距离则可以得到答案。 然后问题就是这里的预估距离该怎么处理因为终点固定所以我们可以用dijkstra算法计算各点到终点的距离作为预估距离。因为它满足小于等于真实距离的条件所以符合作为预估距离的要求。 #includebits/stdc.h using namespace std; const int N1010,M20010; typedef pairint,int pii; typedef pairint,pii piii; int n,m; int rh[N],h[N],e[M],ne[M],w[M],idx; int s,t,k; int d[N],st[N]; void add(int h[],int a,int b,int c) {w[idx]c,e[idx]b,ne[idx]h[a],h[a]idx; } void dijkstra() {memset(d,0x3f,sizeof d);d[t]0;priority_queuepii, vectorpii, greaterpii q;q.push({0,t});while(q.size()){auto itq.top();q.pop();int distit.first,vit.second;if(st[v]) continue;st[v]1;for(int irh[v];i!-1;ine[i]){int je[i];if(d[j]distw[i]){d[j]distw[i];q.push({d[j],j});}}} } int cnt[N]; int bfs() {priority_queuepiii, vectorpiii, greaterpiii q;q.push({d[s],{0,s}});while(q.size()){auto itq.top();q.pop();int distit.second.first,vit.second.second;cnt[v];if(vtcnt[v]k) return dist;for(int ih[v];i!-1;ine[i]){int je[i];if(cnt[j]k)q.push({distw[i]d[j],{distw[i],j}});}}return -1; } int main() {memset(h,-1,sizeof h);memset(rh,-1,sizeof rh);scanf(%d%d,n,m);for(int i1;im;i){int a,b,c;scanf(%d%d%d,a,b,c);add(h,a,b,c);add(rh,b,a,c);}scanf(%d%d%d,s,t,k);if(st) k;//因为最初s就会被放进去每条最短路中至少要包含一条边。dijkstra();coutbfs(); } 179. 八数码179. 八数码 - AcWing题库 这题是将棋盘整个视为一种状态我们每一个点最多只能扩展出四种状态我们可以用之前魔板那道题的写法稍微变一下变成双向广搜自然也可以用A—star算法因为状态还是有些许多。 A—star算法需要保证有解那么我们就提前预判一下是否有解如果有解再去进行查找。 八数码问题有个预判的技巧我们按行读入数字得到的一个数组中如果逆序对的数量为奇数那么就无解如果逆序对的数量为偶数那么就有解。 可以这么来理解如果我们在行内进行移动实际上并没有改变序列也就是并未改变逆序对数量如果在行与行之间进行移动那么相当于只改变了它前面或者后面两个数的位置我们以一种情况为例它实际上就只改变了3个数内部的相对顺序所以实际上逆序对的数量要么不变要么就多2或者少2所以起始状态和结束状态中逆序对的奇偶性相同我们可以顺序排列的时候逆序对的数量是0那么起始状态中逆序对的数量应该是偶数。 然后就是考虑估价函数我们计算出每个数当前位置和目标位置的曼哈顿距离很显然每次移动最好的情况只会让一个数和它的实际位置的曼哈顿距离减1所以我们可以将每个状态中每个数当前位置与目标位置的曼哈顿距离和算出来作为预估距离。  #includebits/stdc.h using namespace std; string s,e; char a[4][4]; unordered_mapstring,intd; unordered_mapstring,pairstring,charpre; char op[]{u,d,l,r};//x的位置 void toa(string t) {for(int i0;it.size();i){a[i/3][i%3]t[i];} } string tos() {string res;for(int i0;i3;i)for(int j0;j3;j)res a[i][j];return res; } string move0(string t)//u {toa(t);int x,y;for(int i0;i3;i)for(int j0;j3;j)if(a[i][j]x) xi,yj;if(x!0){swap(a[x][y],a[x-1][y]);}return tos(); } string move1(string t)//d {toa(t);int x,y;for(int i0;i3;i)for(int j0;j3;j)if(a[i][j]x) xi,yj;if(x!2){swap(a[x][y],a[x1][y]);}return tos(); } string move2(string t)//l {toa(t);int x,y;for(int i0;i3;i)for(int j0;j3;j)if(a[i][j]x) xi,yj;if(y!0){swap(a[x][y],a[x][y-1]);}return tos(); } string move3(string t)//r {toa(t);int x,y;for(int i0;i3;i)for(int j0;j3;j)if(a[i][j]x) xi,yj;if(y!2){swap(a[x][y],a[x][y1]);}return tos(); } typedef pairint,pairint,string piis; int tj(string g) {int cnt0;//逆序对数量for(int i0;ig.size();i){for(int ji1;jg.size();j){if(g[i]g[j]) cnt;}}return cnt; } void bfs() {priority_queuepiis,vectorpiis,greaterpiisq;int cnttj(s);q.push({cnt,{0,s}});d[s]0;if(se) return;while(q.size()){auto tq.top();q.pop();string tvt.second.second;int distt.second.first;// couttvendl;string tmp[5];tmp[0]move0(tv);tmp[1]move1(tv);tmp[2]move2(tv);tmp[3]move3(tv);for(int i0;i4;i){// couttmp[i]endl;if(d.count(tmp[i])) continue;d[tmp[i]]dist1;pre[tmp[i]]{tv,op[i]};cnttj(tmp[i]);q.push({cntd[tmp[i]],{d[tmp[i]],tmp[i]}});if(tmp[i]e) return;}//coutendl;} } int main() {string g;char c;while(cinc)//不会录入空格{s c;if(c!x) gc;}e12345678x;int cnt0;//逆序对数量for(int i0;ig.size();i){for(int ji1;jg.size();j){if(g[i]g[j]) cnt;}}if(cnt%2) coutunsolvable;else{bfs();//coutd[e]endl;if(d[e]){string res;while(e!s){res pre[e].second;epre[e].first;}reverse(res.begin(),res.end());coutres;}} } ps代码看似复杂但复用率极高只要把逻辑盘清楚实际上并不麻烦。 总的来说A—star可以提高效率但是估价函数一定要写明白。 另外补充一点cin录单个字符的时候不会把空格录进去如果没有更好的方法避免空格的话可以用cin。