郑州网站建设工作室,西安推广公司,做外贸的网站域名怎么买,wordpress熊账号目录 今日知识点#xff1a;
使用并查集映射点#xff0c;构造迷宫的连通块
vis计时数组要同步当回合的处理
递归求先序排列
基于不相邻的取数问题#xff1a;dfs回溯
n个相同球放入k个相同盒子#xff1a;dfs的优化分支暴力
01迷宫
血色先锋队
求先序排列
取数游…目录 今日知识点
使用并查集映射点构造迷宫的连通块
vis计时数组要同步当回合的处理
递归求先序排列
基于不相邻的取数问题dfs回溯
n个相同球放入k个相同盒子dfs的优化分支暴力
01迷宫
血色先锋队
求先序排列
取数游戏
数的划分 01迷宫 思路1
其实啊在写这个题的时候总觉得这个题没法做感觉时间复杂度非常高。因为一共(n*m)^4一共这么格子然后每个格子有4种选择…………
然后我犯了一个错误其实dfs的复杂度不是这么看的因为其实很多分支根本就没走。远远达不到那种耗时。就比如说正常的走迷宫问题设置一个vis数组然后dfs的复杂度最大也就整张地图罢了根本不会达到每个点都做那么多个分支的情况数。所以哈。dfs的实际复杂度还得看实际的效果扯远了……………… 设置dfs(int x,int y,int z,int t)进行四个方向的暴搜就行因为最多也就是搜1000次然后本次搜索过的之后就不需要再搜索了完全不会超时。
#include bits/stdc.h
using namespace std;
char s[1005][1005];
int n,m,ans[100005],f[1005][1005];
void dfs(int x,int y,int z,int t){if(x0||y0||xn||yn||f[x][y]!-1||s[x][y]-0!z)return ;ans[t];f[x][y]t;dfs(x-1,y,!z,t);dfs(x,y-1,!z,t);dfs(x1,y,!z,t);dfs(x,y1,!z,t);
}
int main(){cinnm;int x,y;memset(f,-1,sizeof(f));for(int i0;in;i)cins[i];for(int i0;im;i){scanf(%d%d,x,y);x--;y--;if(f[x][y]-1){dfs(x,y,s[x][y]-0,i); }else{ans[i]ans[f[x][y]]; } }for(int i0;im;i)printf(%d\n,ans[i]);
}
其实你也看到了 就是一道连通块的题扫一下每个连通块内有多少个块罢了。
思路2
既然都是连通块的题了并查集做才最合理!
操作就是不断的去合并两个点合并点的话需要进行映射说白了就是找一个东西来唯一的表示这个点最直接做法的就是映射成一维。最后合并的时候一边维护fa一边维护cnt就行了。
注意千万不能从(00)开始不然会映射失败。
#include bits/stdc.h
using namespace std;
string s[1005];
int n,m;
int dx[]{0,-1,0,1},dy[]{1,0,-1,0};
int fa[1005*1005],cnt[1005*1005];
int real (int i,int j){return (i-1)*nj;}int find(int x){if(x!fa[x])fa[x]find(fa[x]);return fa[x];
}
int main(){cinnm;for(int i1;in;i)cins[i],s[i]0s[i];int x,y,f1,f2;for(int i1;in*n;i)fa[i]i,cnt[i]1;for(int i1;in;i)for(int j1;jn;j)for(int k0;k4;k){xidx[k];yjdy[k];if(x1y1xnyns[x][y]!s[i][j]){f1find(real(i,j));f2find(real(x,y));if(f1!f2){fa[f2]f1;cnt[f1]cnt[f2];}}}while(m--){scanf(%d%d,x,y);printf(%d\n,cnt[find(real(x,y))]);}
} 血色先锋队 思路 有一种特别直接的做法其实想找领主的最早感染时候不过就是直接曼哈顿距离就能求出来了。那么求一个领主需要O(a)时间找b个领主需要O(a*b)时间不好意思直接会超时的。
所以这不是最聪明的做法而是做不好的做法。
虽然说感染源很多但是我们可以把这个感染源一起进行扩散然后扩散整个图的时候所有领主的感染时间也就确定了。仅需要一张图的时间罢了。
这里有个bug改了好久才发现vis标记一定要同步于当回合处理。
(果然迷迷糊糊的时候尽量不要敲代码啊)
#include bits/stdc.h
using namespace std;
int a,b,n,m;
int vis[550][550];
struct node{int x;int y;};
int dx[]{1,0,-1,0},dy[]{0,1,0,-1};
int main(){cinnmab;int x,y,t0;memset(vis,-1,sizeof(vis));queuenodeq;for(int i1;ia;i){scanf(%d%d,x,y);q.push(node{x,y});vis[x][y]t;//入队就标记一定要当回就标记避免下回合开始之后上回合还没有标记}while(!q.empty()){int szq.size();t;while(sz--){node curq.front();q.pop();for(int i0;i4;i){int txcur.xdx[i],tycur.ydy[i];if(tx1||ty1||txn||tym||vis[tx][ty]!-1)continue;q.push(node{tx,ty});vis[tx][ty]t;//在利用队列中点进行下一层处理时候当前队列的所有点均已经安全标记} }}for(int i1;ib;i){scanf(%d%d,x,y);printf(%d\n,vis[x][y]);}
} 求先序排列 思路
一道dfs题的老朋友了。
直接模拟就行给个例子中序ACGDBHZKX后序CDGAHXKZB
找到主根B然后左子树(ACGD,CDGA)重复操作右子树(HZKX,HXKZ)重复操作即可。
然后注意输出是先序所以先输出根然后递归左边最后是右边。
最最后注意结束条件就行了长度为1就结束不要进入错误操作 #include bits/stdc.h
using namespace std;void dfs(string s1,string s2){int sz1s1.size(),sz2s2.size();if(sz11){couts1;return ;}string s11,s12,s21,s22;char chs2[sz2-1];int is1.find(ch);s11s1.substr(0,i);s12s1.substr(i1); s21s2.substr(0,i);s22s2.substr(i,sz2-i-1);coutch;if(s11.size())dfs(s11,s21);if(s12.size())dfs(s12,s22);
}
int main(){string s1,s2;cins1s2;dfs(s1,s2);
} 取数游戏 思路
我一开始的思路是dfs(x1,y1,x2,y2)然后转移到下一个(i,j,i1,j1)也就是用i1,j1来标记走过的状态。嗯~ 后面再一看我去这样子只能不与上一个状态冲突那么和上上个状态就冲突。反正就是必须整个图都要进行标记我标记的不够。
那么就dfs回溯进行全图标记。 首先装模装样的分析一下dfs的时间复杂度首先基于回溯的话每个格子妥妥的要跑2种状态。一共36个格子所以2^36??? 等等因为是跳着走的所以因为2^18左右吧其是不是很会
#include bits/stdc.h
using namespace std;
const int d[8][2]{1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};
int ans,n,m,t;
int vis[8][8],a[8][8];void dfs(int x,int y,int mx){if(ym1){dfs(x1,1,mx);return ;}if(xn1){ansmax(ans,mx);return ;}dfs(x,y1,mx);if(vis[x][y]0){for(int i0;i8;i){vis[xd[i][0]][yd[i][1]];}dfs(x,y1,mxa[x][y]);for(int i0;i8;i){vis[xd[i][0]][yd[i][1]]--;}}
}
int main(){cint;while(t--){ans0;memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));cinnm;for(int i1;in;i)for(int j1;jm;j)cina[i][j];dfs(1,1,0);coutans\n;}
}数的划分 思路
两种做法
第一种动态规划
题目可以理解成把n个相同球放入k个相同盒子然后因为球都是相同的就不能再对最后一个球进行讨论了。应该对应一类球
设置a[i][j]表示i个球放入j个盒子的方案数。
第一种情况有一个盒子只有一个球那么就对应了a[i-1][j]
第二种情况每个盒子都至少有两个球那么就对应看a[i-j][j]
所以a[i][j]a[i-j][j]a[i-1][j-1]
第二种dfs
在已经放了i时候每次可以放1~n-i个所有dfs(i)有n-i个分支这个复杂度很高别着急只需要把无效分支剔除即可很快。
仔细观察7的拆法
1 1 5
1 2 4
1 3 3
2 2 3
2 3 2重复了哟
所以你发现了要想不重复 就必须后面选的数比前面的大(很早的时候我们再输出组合数的时候就是这样子去重的只需要安排升序即可)所以在dfs(i)也就是选了i的时候后面选的数都必须比i大那么有了sumi*(k-cnt)n这个分支优化。
dfs的速度就变快了很多。
#include bits/stdc.h
using namespace std;
int n,k,ans0,a[205][70];
//int main(){
// cinnk;
// for(int i1;in;i)a[i][1]1;
// for(int i2;in;i)
// for(int j2;j(i,k);j){
// a[i][j]a[i-1][j-1];
// if(i2*j)a[i][j]a[i-j][j];
// }
// couta[n][k];
//}
void dfs(int cnt,int up,int sum){if(cntk){if(sumn)ans;return ;}for(int iup;sumi*(k-cnt)n;i){dfs(cnt1,i,sumi);}
}
int main(){cinnk;dfs(0,1,0);coutans;
}
