#01 N皇后问题

题目描述:POJ 3239

#include <iostream>
using namespace std;
int n,ans,d[20],l[20],r[20],m[20];
void dfs(int dep){
    if(dep>n){
        for(int i=1;i<=n;i++) cout<<d[i]<<" ";
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        if(!m[i] && !l[dep+i] && !r[dep-i+n]){
            l[dep+i]=r[dep-i+n]=m[i]=1,d[dep]=i;
            dfs(dep+1);
            l[dep+i]=r[dep-i+n]=m[i]=0;
        }
    }
}
int main(){
    while(1){
        cin>>n;
        if(n==0) return 0;
        dfs(1); 
    }
}

#02 LCA 最近公共祖先

题目描述:Luogu 3379
先抛开ST表优化,使用RMQ求lca时,需要进行一次dfs求出 dfs序 + 时间戳 + 第一次访问时间
代码中生成的A[] B[] first[] 分别就是这三个作用。
搜索时注意在回溯时进行标记,具体看代码

#include <iostream>
#include <cstdio>
#include <vector>
#define N 500005
#define INF 99999999
using namespace std;
int n,m,s,x,y,xx,yy,A[2*N],B[2*N],first[N],vis[N],it,ans;
vector<int>G[N];
void add(int a,int b){G[a].push_back(b);}
int ask(int a,int b){
    xx=first[a],yy=first[b];
    if(xx>yy) swap(xx,yy);
    int ma=INF;
    for(int i=xx;i<=yy;i++){
        if(B[i]<ma){
            ma=B[i];
            ans=A[i];
        }
    }
    return ans;
}
void dfs(int now,int dep){
    if(!first[now]) first[now]=it+1;
    if(G[now].size()==1 && now!=s){
        A[++it]=now;
        B[it]=dep;
        return ;
    }
    for(int i=0;i<G[now].size();i++){
        if(!vis[G[now][i]]){
            vis[G[now][i]]=1;
            if(A[it]!=now){
                A[++it]=now;
                B[it]=dep;
            }
            dfs(G[now][i],dep+1);
            A[++it]=now;
            B[it]=dep;  
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    vis[s]=1;
    dfs(s,1);
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        cout<<ask(x,y)<<endl;
    }
    //for(int i=1;i<=15;i++) cout<<A[i]<<" ";
    //cout<<endl;
    //for(int i=1;i<=15;i++) cout<<B[i]<<" ";
    //cout<<endl;
    //for(int i=1;i<=n;i++) cout<<first[i]<<" ";
    return 0;
}

#03 FJSC 油滴拓展 (二周目)

题目描述:Luogu 1378
生成全排列时需要dfs,当然next_permutation()也可以做到;

#04 Telephone Lines (二周目)

题目描述:POJ 3662
最短路+二分答案+思考 讲解:二分答案的意义,改边,如果比mid大就是1,否则0,这样可以保证跑一次SPFA会产生在我只有mid元钱时,到终点电话公司免费安装线路的个数,这个数如果比k大,就说明我不能最小花mid元,需要左区间右移。这也就是二分答案的判断函数思路。

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#define N 1005
using namespace std;
struct edge{int t,v,w;}ee;
vector<edge>G[N];
queue<int>q;
int n,p,k,l=1,r,mid,ans;
int dis[N],vis[N];
void add(int x,int y,int z){ee.t=y,ee.v=z;ee.w=z;G[x].push_back(ee);}
bool ok(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<G[i].size();j++){
            if(G[i][j].w>mid) G[i][j].v=1;
            else G[i][j].v=0;
        }
    }
    dis[1]=0;
    vis[1]=1;
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<G[x].size();i++){
            int m=G[x][i].t,p=G[x][i].v;
            if(dis[x]+p<dis[m]){
                dis[m]=dis[x]+p;
                if(!vis[m]){
                    q.push(m);
                    vis[m]=1;
                }
            }
        }
        vis[x]=0;
    }
    if(dis[n]>k) return 0;
    else return 1;

}
void init(){
    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    while(!q.empty()) q.pop();
}
int main(){
    cin>>n>>p>>k;
    for(int i=1;i<=p;i++){
        int a,b,c;
        cin>>a>>b>>c;
        r=max(c,r);
        add(a,b,c);
        add(b,a,c);
    }
    while(l<r){
        init();
        mid=(l+r)/2;
        if(ok()) r=mid,ans=mid;
        else l=mid+1;
    }
    if(ans==0) cout<<-1<<endl;
    else cout<<ans<<endl;   
    return 0;
}

#05 FloodFill问题(二周目)

题目描述:给出一张仅有1或0的点阵图,你的任务是把所有被1包围的0都替换成1(有点像围棋的意思)

0 0 0 0 0  ->  0 0 0 0 0
0 1 1 1 0  ->  0 1 1 1 0
0 1 0 1 0  ->  0 1 1 1 0
0 1 1 1 0  ->  0 1 1 1 0
0 0 0 0 0  ->  0 0 0 0 0
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
#define N 1005
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int x,y,map[N][N],vis[N][N];
queue<int>qx,qy;
void bfs(){
    qx.push(0);qy.push(0);
    while(!qx.empty()){
        int xx=qx.front(),yy=qy.front();
        qx.pop();qy.pop();
        for(int i=0;i<4;i++){
            int newx=xx+dx[i],newy=yy+dy[i];
            if(!vis[newx][newy] && map[newx][newy]!=1){
                if(0<=newx && newx<=x+1 && 0<=newy && newy<=y+1){
                    qx.push(newx);qy.push(newy);
                    map[newx][newy]=2;
                    vis[newx][newy]=1;
                }
            }
        }
    }
}
int main(){
    cin>>x>>y;
    for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) cin>>map[i][j];
    vis[0][0]=1;
    bfs();
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            if(map[i][j]==2) map[i][j]=0;
            else if(map[i][j]==0) map[i][j]=1;
            cout<<map[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
/*
5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.