题单地址：【237题】算法基础精选题单_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网
老子的全排列呢
dfs+回溯
int n = 8;
int idx;
int record[10];
bool vis[10];void dfs(int num)
{if(num==n){for(int i=1;i<=n;i++) cout<<record[i]<<" ";cout<<endl;return ;}for(int i=1;i<=n;i++){if(!vis[i]){vis[i] = true;record[++idx] = i;dfs(num+1);record[idx--] = 0;vis[i] = false;}}}N皇后问题
O(n!)
借用一位博主的图说明x+y和x-y+n的
const int N = 15*2;
int n,ans;
int col[N],dig[N],undig[N];void dfs(int u)//u代表行数
{if(u == n){//已经搜索了n行ans++;return ;}for(int y=0;y<n;y++){if(!col[y] && !dig[u+y] && !undig[u-y+n]){col[y] = dig[u+y] = undig[u-y+n] = true;dfs(u+1);col[y] = dig[u+y] = undig[u-y+n] = false;}}
}void solve()
{cin>>n;dfs(0);cout<<ans<<endl;
}O(2^(n*n))
TLE的写法,想想就可怕
const int N = 15*2;
int n,ans;
int col[N],row[N],dig[N],undig[N];void dfs(int x,int y,int u)
{if(y==n){x++;y=0;}if(x==n){if(u==n) ans++;return;}//不放dfs(x,y+1,u);//放if(!col[y]&&!row[x]&&!dig[x-y+n]&&!undig[x+y]){col[y] = row[x] = dig[x-y+n] = undig[x+y] = true;dfs(x,y+1,u+1);col[y] = row[x] = dig[x-y+n] = undig[x+y] = false;}}void solve()
{cin>>n;dfs(0,0,0);cout<<ans<<endl;
}马踏棋盘
走迷宫的写法，和迷宫的上下左右稍有不同，深搜时注意别越界且前往的点上没走过即可
#define PII pair<int,int>
const int N = 15+2;
int n,m;
const PII dir[4] = {{1,2},{2,1},{-1,2},{-2,1}};
bool vis[N][N];
int ans;bool in(int x,int y)
{return (x>=1 && x<=n && y>=1 && y<=m);
}void dfs(int x,int y)
{if(x==n && y==m){ans++;return;}for(int i=0;i<4;i++){int tx = dir[i].first+x;int ty = dir[i].second+y;if(in(tx,ty) && !vis[tx][ty]){vis[tx][ty] = true;dfs(tx,ty);vis[tx][ty] = false;}}
}void solve()
{cin>>n>>m;vis[1][1] = true;dfs(1,1);cout<<ans<<endl;
}数独挑战
dfs+剪枝，棋盘格子看起来很多觉得会TLE，实际上考虑上数独的规则进行剪枝还是可以过的。
分为三部分记录棋盘信息：行、列、块，块分为
11 | 12 | 13
21 | 22 | 23
31 | 32 | 33
一共九个部分，(x,y)在某一块可以用[x/3][y/3]来确定位置
其余的部分和常规dfs相差无几，注意的是回溯的时候不能都置为0，只有你自己填的数可以删掉，题目原来给的数不能删，所以要额外开一个origin数组记录哪些位置是一开始就有数的
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fasten cin.tie(0),cout.tie(0);ios::sync_with_stdio(false)const int N = 10+2;
int g[N][N];
bool row[N][10];//第i行的1-9各有几个
bool col[N][10];
bool block[4][4][10];//左上角的块为1,1 依次为1,2 1,3 ...
int blank = 81;//待填的空格
int origin[N][N];//记录原始给定的数字，回溯时不能删除
void print(){for(int i=0;i<9;i++){for(int j=0;j<9;j++){cout<<g[i][j]<<" ";}cout<<endl;}
}
void dfs(int x,int y)
{if(y==9){y = 0;x++; }if(blank==0){print();return ;}if(g[x][y]!=0) dfs(x,y+1);bool flag = false;//记录该格子是否还能填数，不能的话该搜索路径不用搜索下去了for(int i=1;i<=9;i++){if(!block[x/3][y/3][i] && !row[x][i] && !col[y][i]){flag = true;g[x][y] = i;block[x/3][y/3][i] = row[x][i] = col[y][i] = true;blank--;dfs(x,y+1);blank++;//若是自己填的数就回溯为0，系统给定的数不能改动if(origin[x][y]) g[x][y] =origin[x][y];else g[x][y] = 0;block[x/3][y/3][i] = row[x][i] = col[y][i] = false;}}if(!flag) return ;}
void solve()
{for(int i=0;i<9;i++){for(int j=0;j<9;j++){cin>>g[i][j];origin[i][j] = g[i][j];if(g[i][j]!=0){int e = g[i][j];blank--;row[i][e] = true;col[j][e] = true;block[i/3][j/3][e] = true;}}}//debug// for(int i=1;i<=9;i++) cout<<i<<" ";// cout<<endl;// for(int i=0;i<3;i++){// for(int k=0;k<3;k++){// for(int j=1;j<=9;j++){// cout<<block[i][k][j]<<" ";// }// cout<<endl;// }// }dfs(0,0);}
signed main()
{fasten;
// freopen("stdin.txt","r",stdin);
// freopen("stdout.txt","w",stdout);solve();return 0;
}幸运数字Ⅱ
可以先用dfs把所有只含4or7且<=1e9的数处理出来放在一个容器内，然后再[l,r]内使用二分计算总和，用string比用long long快大约100倍左右
#define PII pair<int,int>
#define ll long long
vector<ll>v;void dfs(string s,int digit)
{if(digit>9){return ;}int tmp = 0;for(int i=0;i<s.length();i++){tmp = tmp*10+(s[i]-'0');}if(tmp<1e9){if(tmp!=0) v.push_back(tmp);dfs("4"+s,digit+1);dfs("7"+s,digit+1);}
}void solve()
{dfs("",0);v.push_back(4444444444);sort(v.begin(),v.end());// for(auto it:v){// cout<<it<<endl;// }long long l,r;cin>>l>>r;long long res = 0;for(ll i=l;i<=r;){auto it = lower_bound(v.begin(),v.end(),i);res += min(r-i+1ll,(*it-i+1ll))*(*it);i = *it+1;}cout<<res<<endl;
}[NOIP2017]奶酪
回溯dfs写法会超时，别写回溯写法
有的题目一定要回溯，但是有的题目不用回溯，选择不回溯可以优化算法
那什么时候不需要回溯？
当遇到一个选择时，一定要对它操作时，那么就不需要回溯。比如要标记求所有情况，找到了就要标记。如果取消标记，那么就会重复计算。在这道题中，小鼠尝试通过空洞从起点到终点，到达一个点时，小鼠需要知道该点范围内的可到达的点中有没有能到达终点的点，如果有的点不能到达终点，就不必再走那个点了。
如何知道该点能不能达到终点？
dfs搜索时会直接搜索到最深处，接着从底层一层一层往上反馈该点能不能通往终点。该点若已经搜索过，必定打上了标记（回溯则会把该标记划去，那就需要重复搜索了）
AC版本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fasten cin.tie(0),cout.tie(0);ios::sync_with_stdio(false)const int N = 1000+2;
int n;
int h,r;
bool vis[N];//记录该空洞有没有走过
bool g[N][N];
int x[N],y[N],z[N];
bool isfind = false;bool dfs(int i)
{if(z[i]+r>=h){return true;}if(vis[i]) return false;vis[i] = true;for(int j=0;j<n;j++){if(g[i][j] && dfs(j)) return true;}return false;
}void solve()
{int t;cin>>t;while(t--){memset(g,0,sizeof g);memset(vis,0,sizeof vis);cin>>n>>h>>r;for(int i=0;i<n;i++){cin>>x[i]>>y[i]>>z[i];}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i!=j)g[i][j]=g[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]) <=4*r*r;}}for(int i=0;i<n;i++){if(z[i]<=r){if(dfs(i)){puts("Yes");isfind = true;break;}}}if(!isfind) puts("No");isfind = false;}
}
signed main()
{fasten;
// freopen("stdin.txt","r",stdin);
// freopen("stdout.txt","w",stdout);solve();return 0;
}TLE版本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fasten cin.tie(0),cout.tie(0);ios::sync_with_stdio(false)class point
{
public:double x,y,z;point(){};point(int a,int b,int c){x=a,y=b,z=c;}
};double dist(point p1,point p2)
{double x = (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z);return sqrt(x);
}
const int N = 1000+2;
point a[N];
int n;
double h,r;
bool vis[N];//记录该空洞有没有走过
bool g[N][N];
bool isfind = false;void dfs(int x,int y,int z,int idx)
{if(z+r>=h){isfind = true;return ;}for(int i=0;i<n;i++){point tmp(x,y,z);if(!vis[i] && g[idx][i]){vis[i] = true;dfs(a[i].x,a[i].y,a[i].z,i);vis[i] = false;}}}
void solve()
{int t;cin>>t;while(t--){memset(g,0,sizeof g);cin>>n>>h>>r;for(int i=0;i<n;i++){cin>>a[i].x>>a[i].y>>a[i].z;}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i!=j)g[i][j] = dist(a[i],a[j])<=2*r;}}for(int i=0;i<n;i++){if(a[i].z<=r) dfs(a[i].x,a[i].y,a[i].z,i);}if(isfind) puts("Yes");else puts("No");isfind = false;}
}
signed main()
{fasten;
// freopen("stdin.txt","r",stdin);
// freopen("stdout.txt","w",stdout);solve();return 0;
}wyh的迷宫
迷宫问题不在赘述
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fasten cin.tie(0),cout.tie(0);ios::sync_with_stdio(false)
#define PII pair<int,int>
const int N = 500+2;
int n,m;
const PII dir[4] = {{0,1},{1,0},{-1,0},{0,-1}};
bool vis[N][N];
string s[N];
PII _begin,_end;
bool isfind = false;bool in(int x,int y)
{return (x>=1 && x<=n && y>=1 && y<=m);
}void dfs(int x,int y)
{//cout<<x<<" "<<y<<endl;if(x==_end.first && y==_end.second){isfind = true;return ;}for(int i=0;i<4;i++){int tx = dir[i].first+x;int ty = dir[i].second+y;if(in(tx,ty) && !vis[tx][ty] && s[tx][ty]!='x'){if(x==_end.first && y==_end.second){isfind = true;return ;}vis[tx][ty] = true;dfs(tx,ty);}}return ;
}void solve()
{int t;cin>>t;while(t--){memset(vis,0,sizeof vis);cin>>n>>m;for(int i=1;i<=n;i++) cin>>s[i],s[i]=" "+s[i];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='s') _begin = {i,j};else if(s[i][j]=='t') _end = {i,j};}}vis[_begin.first][_begin.second] = true;dfs(_begin.first,_begin.second);if(isfind) cout<<"YES"<<endl;else cout<<"NO"<<endl;isfind = false;}
}signed main()
{fasten;
// freopen("stdin.txt","r",stdin);
// freopen("stdout.txt","w",stdout);solve();return 0;
}Lake Counting
求连通分支的个数，可用并查集的知识
也可以直接搜索，标记访问过的点，查看有几块
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fasten cin.tie(0),cout.tie(0);ios::sync_with_stdio(false)
#define PII pair<int,int>
const int N = 100+5;
char s[N][N];
int n,m;
int ans;
const PII dir[8] = {{1,0},{1,1},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}};bool in(int x,int y)
{return (x>=0 && x<n && y>=0 && y<m);
}void dfs(int x,int y)
{s[x][y] = '.';//走过的修改成陆地for(int i=0;i<8;i++){//八个方向都可走int tx = x+dir[i].first;int ty = y+dir[i].second;if(in(tx,ty) && s[tx][ty]=='W'){dfs(tx,ty);}}return ;
}
void solve()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>s[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='W'){dfs(i,j);ans++;}}}cout<<ans<<endl;
}signed main()
{fasten;
// freopen("stdin.txt","r",stdin);
// freopen("stdout.txt","w",stdout);solve();return 0;
}
