7.1做题笔记

复习 DFS 以及 BFS 算法，并进行了相对应题型的训练。

P8604 [蓝桥杯 2013 国 C] 危险系数 数据范围不大，可以用邻接矩阵存储，并暴力 DFS，时间复杂度为 $O(n^2)$，可以通过本题。 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,i,u,v,s,ans,a[N][N],vis[N],f[N];
void dfs(int t){
    int i;
    if(t==v){
        s++;
        for(i=1;i<=n;i++)if(vis[i])f[i]++;
        return;
    }
    for(i=1;i<=n;i++)if(a[t][i]&&!vis[i])vis[i]=1,dfs(i),vis[i]=0;
}
int main(){
 cin>>n>>m;
 for(i=1;i<=m;i++)cin>>u>>v,a[u][v]=a[v][u]=1;
    cin>>u>>v;
    dfs(u);
    if(!s)return cout<<-1,0;
    for(i=1;i<=n;i++)if(f[i]==s)ans++;
    cout<<ans-1;
}

P1030 [NOIP2001 普及组] 求先序排列 思路：反复找主根，再分成 $2$ 棵子树，继续找每棵树的主根，如此往复，不难实现。 代码：

#include<bits/stdc++.h>
using namespace std;
string a,b;
void _(string a,string b){
    if(a.size()){
        char root=b[b.size()-1];
        cout<<root;
        int k=a.find(root);
        _(a.substr(0,k),b.substr(0,k));
        _(a.substr(k+1),b.substr(k,a.size()-k-1));
    }
}
int main(){
 cin>>a>>b;
    _(a,b);
}

P1294 高手去散步 数据范围很小，考虑直接暴力遍历，可以通过本题。 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e2,inf=INT_MAX;
int n,m,i,u,v,w,s,ans=-inf,a[N][N],vis[N];
void dfs(int t){
    int i;
    for(i=1;i<=n;i++)if(a[t][i]&&!vis[i])vis[i]=1,s+=a[t][i],dfs(i),s-=a[t][i];
    ans=max(ans,s);vis[t]=0;
}
int main(){
 cin>>n>>m;
 for(i=1;i<=m;i++)cin>>u>>v>>w,a[u][v]=a[v][u]=w;
    for(i=1;i<=n;i++)memset(vis,0,sizeof vis),vis[i]=1,dfs(i);
    cout<<ans;
}

P1331 海战 最有思维含量的一题。 考虑到不合法（船相撞）的情况只有如下 $4$ 种：

##    ##    #.    .#
#.    .#    ##    ##

因此只需要开头特判，然后使用 $O(n^2)$ 的循环算法暴力解决。 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,i,j,ans;
char a[N][N];
bool check(int x,int y){
 int s=0;
 if(a[x][y]=='#')s++;
 if(a[x+1][y]=='#')s++;
 if(a[x][y+1]=='#')s++;
 if(a[x+1][y+1]=='#')s++;
 return s==3;
}
int main(){
 cin>>n>>m;
 for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>a[i][j];
 for(i=1;i<n;i++)for(j=1;j<m;j++)if(check(i,j))return cout<<"Bad placement.",0;
 for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]=='#'&&a[i-1][j]!='#'&&a[i][j-1]!='#')ans++;
 cout<<"There are "<<ans<<" ships.";
}