ACwing算法备战蓝桥杯——刷题_acwing刷题

BFS：

全球变暖：

你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
 
.......
.##....
.##....
....##.
..####.
...###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。
 
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
 
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
 
例如上图中的海域未来会变成如下样子：
 
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
 
输入格式
第一行包含一个整数N。
 
以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。
 
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
 
输出格式
一个整数表示答案。
 
数据范围
1≤N≤1000
输入样例1：
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1：
1
输入样例2：
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2：
1
 
代码：
#include <iostream>
#include <string>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int n;
char c[N][N];
bool st[N][N];//判断该岛屿是否遍历过
queue<PII> q;//队列
bool flage=true;//flage表示是否会当前陆地是否会沉没
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
bool check(int i,int j){
    bool F=true;
    for(int k=0;k<4;k++){
        if(c[i+dx[k]][j+dy[k]]=='.') F=false;
    }
    return F;
}
void bfs(int i,int j){
    //初始化
    PII start={i,j};
    q.push(start);
    bool judge=false;//是否有四个方向都是'#'的点;
    //遍历
    while(q.size()){
        PII t=q.front();
        q.pop();
        if(!judge) judge=check(t.x,t.y);
        st[t.x][t.y]=true;
        for(int k=0;k<4;k++){
            int x1=t.x+dx[k],y1=t.y+dy[k];
            if(x1<n-1&&x1>0&&y1<n-1&&y1>0&&!st[x1][y1]&&c[x1][y1]=='#'){//如果下一位置合法
                st[x1][y1]=true;
                PII temp={x1,y1};
                q.push(temp);
            }
        }
    }
    if(judge) flage=false;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%s",c[i]);
    }
    int res=0;
    for(int i=1;i<n-1;i++){
        for(int j=1;j<n-1;j++){
            if(!st[i][j]&&c[i][j]=='#'){//如果发现新岛屿,开始搜索,n大于等于3时才会有岛屿出现
                flage=true;//对于每个岛屿重置flage,是否会沉没
                bfs(i,j);
                if(flage) res+=1;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

DFS：

数字替换：

给定两个整数 n,x。
 
你可以对 x 进行任意次以下操作：
 
选择 x 的一位数字 y，将 x 替换为 x×y。
请你计算通过使用上述操作，将 x 变为一个 n 位数字（不含前导 0），所需要的最少操作次数。
 
例如，当 n=3,x=2 时，对 2 进行如下 4 次操作，即可使其变为 3 位数字：
 
将 2 替换为 2×2=4。
将 4 替换为 4×4=16。
将 16 替换为 16×6=96。
将 96 替换为 96×9=864。
输入格式
共一行，包含两个整数 n,x。
 
输出格式
一个整数，表示将 x 变为一个 n 位数字，所需要的最少操作次数。
 
如果无解，则输出 -1。
 
数据范围
所有测试点满足 2≤n≤19，1≤x<10n−1。
 
输入样例1：
2 1
输出样例1：
-1
输入样例2：
3 2
输出样例2：
4
输入样例3：
13 42
输出样例3：
12
 
朴素DFS：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
int anws=100;
int n;
void dfs(LL x,int c){
    int cnt=0;
    LL t=x;
    bool st[10];
    memset(st,0,sizeof st);
    while(t){
        st[t%10]=true;
        cnt++;
        t/=10;
    }
    if(cnt==n){
        anws=min(anws,c);
        return;
    }
    for(int i=2;i<=9;i++){
        if(!st[i]) continue;
        dfs(x*i,c+1);
    }
}
int main(){
    LL x;
    cin>>n>>x;
    dfs(x,0);
    if(anws==100) cout<<-1<<endl;
    else cout<<anws<<endl;
    return 0;
}
 
剪枝DFS：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
int anws=100;
int n;
void dfs(LL x,int c){
    if(c>=anws) return;
    int cnt=0;
    LL t=x;
    bool st[10];
    memset(st,0,sizeof st);
    while(t){
        st[t%10]=true;
        cnt++;
        t/=10;
    }
    if(c+n-cnt>=anws) return;
    if(cnt==n){
        anws=min(anws,c);
        return;
    }
    for(int i=9;i>=2;i--){
        if(!st[i]) continue;
        dfs(x*i,c+1);
    }
}
int main(){
    LL x;
    cin>>n>>x;
    dfs(x,0);
    if(anws==100) cout<<-1<<endl;
    else cout<<anws<<endl;
    return 0;
}

小猫爬山

翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。
 
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
 
翰翰和达达只好花钱让它们坐索道下山。
 
索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
 
当然，每辆缆车上的小猫的重量之和不能超过 W。
 
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
 
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
 
第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
 
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
 
数据范围
1≤N≤18,
1≤Ci≤W≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
代码：a
#include <iostream>
#include <algorithm>
using namespace std;
const int N=20;
 
int anws=19;
int n,m;
int w[N];
int sum[N];
 
void dfs(int u,int cnt){
    
    if(cnt>=anws) return;//最优性剪枝
    
    if(u==n){
        anws=cnt;
        return;    
    }
    
    //不增加新车
    for(int i=0;i<cnt;i++)
        if(sum[i]+w[u]<=m){//可行性剪枝
            sum[i]+=w[u];
            dfs(u+1,cnt);
            sum[i]-=w[u];//记得恢复现场
        }
    
    //增租新车
    sum[cnt]=w[u];
    dfs(u+1,cnt+1);
    sum[cnt]=0;//恢复现场
}
int main(){
 
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>w[i];
    
    //搜索顺序剪枝
    sort(w,w+n);
    reverse(w,w+n);
    
    dfs(0,0);
    
    cout<<anws<<endl;
    return 0;
}

带分数

100 可以表示为带分数的形式：100=3+69258714
还可以表示为：100=82+3546197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
 
类似这样的带分数，100 有 11 种表示法。
 
输入格式
一个正整数。
 
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
 
数据范围
1≤N<106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
 
代码：
#include <iostream>
using namespace std;
const int N=15;
int x,res;
int s[N];
bool st[N];
 
int Tran(int i,int j){//数组转换成数字
    int sum=0;
    while(i<=j){
        sum=sum*10+s[i++];
    }
    return sum;
}
 
void find(){//判断是否有满足条件的取法
    for(int i=0;i<7;i++){
        for(int j=8;j>i+1;j--){
            int a=Tran(0,i);
            int b=Tran(i+1,j-1);
            int c=Tran(j,8);
            if(c*x==c*a+b) res++;
        }
    }
}
 
void dfs(int c){//求全排列
    if(c==9){
        find();
        return;
    }
    for(int i=1;i<=9;i++){
        if(st[i]) continue;
        st[i]=true;
        s[c]=i;
        dfs(c+1);
        st[i]=false;
    }
}
 
int main(){
    cin>>x;
    
    dfs(0);
    
    cout<<res<<endl;
    return 0;
}

拓扑排序：

给定一个由 n 个点和 m 条边构成的图。
 
不保证给定的图是连通的。
 
图中的一部分边的方向已经确定，你不能改变它们的方向。
 
剩下的边还未确定方向，你需要为每一条还未确定方向的边指定方向。
 
你需要保证在确定所有边的方向后，生成的图是一个有向无环图（即所有边都是有向的且没有有向环的图）。
 
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
 
每组数据第一行包含两个整数 n,m。
 
接下来 m 行，每行包含三个整数 t,x,y，用来描述一条边的信息，其中 t 表示边的状态，如果 t=0，则表示边是无向边，如果 t=1，则表示边是有向边。x,y 表示这条边连接的两个端点，如果是有向边则边的方向是从 x 指向 y。
 
保证图中没有重边（给定了 (x,y)，就不会再次出现 (x,y) 或出现 (y,x)）和自环（不会出现 x=y 的情况）。
 
输出格式
对于每组数据，如果无法构造出有向无环图，则输出一行 NO。
 
否则，先输出一行 YES，随后 m 行，每行包含两个整数 x,y，用来描述最终构造成的有向无环图中的每条边的具体方向（x 指向 y），边的先后顺序随意。
 
注意，已经确定方向的边，不能更改方向。
 
如果答案不唯一，输出任意合理方案均可。
 
数据范围
对于前三个测试点，1≤n,m≤10。
对于全部测试点，1≤T≤20000，2≤n≤2×105，1≤m≤min(2×105,n(n−1)2)，0≤t≤1，1≤x,y≤n。
保证在一个测试点中，所有 n 的和不超过 2×105，所有 m 的和不超过 2×105。
 
输入样例：
4
3 1
0 1 3
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5
4 5
1 1 2
0 4 3
1 3 1
0 2 3
1 2 4
4 5
1 4 1
1 1 3
0 1 2
1 2 4
1 3 2
输出样例：
YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO
 
代码及部分题解：
#include <iostream>
#include <vector>
#include <cstring>
#define a first
#define b second
using namespace std;
 
typedef pair<int,int> PII;
 
const int N=2e5+10;
 
int n,m;
int h[N],e[N],ne[N],idex;//邻接表
int q[N],d[N];
int st[N];//存储在拓扑队列里的位置
 
void add(int a,int b){//有向边的加入
    ne[idex]=h[a],e[idex]=b,h[a]=idex++;
    d[b]++;
}
 
bool tuopusort(){//拓扑排序
    int l=0,r=-1;//模拟队列
    for(int i=1;i<=n;i++){
        if(!d[i]){
            q[++r]=i;
            st[i]=r;
        }
    }
    while(l<=r){
        int t=q[l++];
        for(int j=h[t];j!=-1;j=ne[j]){
            d[e[j]]--;
            if(!d[e[j]]){
                q[++r]=e[j];
                st[e[j]]=r;
            }
        }
    return l==n;//包括了无向边的点
    }
}
int main(){
    int T;
    cin>>T;
    
    while(T--){
        //主体
        //初始化
        vector<PII> O;
        memset(h,-1,sizeof h);
        memset(d,0,sizeof d);
        idex=0;
        
        scanf("%d%d",&n,&m);
        
        //输入数据
        while(m--){
            int t;
            int x,y;
            scanf("%d%d%d",&t,&x,&y);
            if(!t){
                PII temp;
                temp.a=x;
                temp.b=y;
                
                O.push_back(temp);
                
                continue;
            }
            add(x,y);
        }
        
        bool res=tuopusort();//拓扑排序
        
        //拓扑和连通没有关系，所以不加入无向边造成的不连通不会影响拓扑
        if(!res) puts("NO");//不存在拓扑序
        else{//存在拓扑序
            puts("YES");
            for(int i=1;i<=n;i++)
                for(int j=h[i];j!=-1;j=ne[j])
                    printf("%d %d\n",i,e[j]);
                    
            for(int i=0;i<n;i++) st[q[i]]=i;
            
            for(auto c:O){
                if(st[c.a]<st[c.b]) printf("%d %d\n",c.a,c.b);
                else printf("%d %d\n",c.b,c.a);
            }
        }
    }
    return 0;
}