首页 > 代码库 > 洛谷——基础搜索

洛谷——基础搜索

2024-09-22 11:11:18   203人阅读

 1.P1706 全排列问题

题目描述

输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入输出格式

输入格式：

n(1≤n≤9)

输出格式：

由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个常宽。

输入输出样例

输入样例#1：
3
输出样例#1：
    1    2    3    1    3    2    2    1    3    2    3    1    3    1    2    3    2    1

(⊙v⊙)嗯~ 代码：
#include<iostream>#include<cstdio>#include<iomanip>using namespace std;int n,num[1001],vis[1001];void print(int n){    for(int i=1; i<=n; i++){        cout<<setw(5)<<num[i];    }printf("\n");}void search(int s) {    for(int i=1; i<=n; i++) {        if(!vis[i]) {            num[s] = i;            vis[i] = 1;            if(s==n) print(s);            else search(s+1);            vis[i] = 0;         }    }}int main() {    scanf("%d",&n);    search(1);    return 0;}

2.P1531 I Hate It

题目背景

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

题目描述

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩

输入输出格式

输入格式：

第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。学生ID编号分别从1编到N。第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。接下来有M行。每一行有一个字符 C (只取‘Q‘或‘U‘) ，和两个正整数A，B。当C为‘Q‘的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。当C为‘U‘的时候，表示这是一条更新操作，如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。

输出格式：

对于每一次询问操作，在一行里面输出最高成绩

输入输出样例

输入样例#1：
5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
输出样例#1：
  5
659
思路：
　　类似于线段树
　　建树：要将父节点的值附为左孩子和右孩子的最大值，（便于询问区间的时候直接返回最大值）
　　询问：如果不在区间内，无意义，在区间内的返回最大值（也就是此节点的值），超出区间继续询问其子节点
　　修改：根据题意，要在当前节点的值与B中取大，如果在区间内，就取大，否则return，继续修改子节点
(⊙v⊙)嗯~ 代码：
#include<iostream>#include<cstdio>using namespace std;const int N = 200005;const int INF = 1<<30;int n,m,l,r,ans;char sty; struct Tree{    int l,r,w;}tree[5*N];void build(int k,int ll,int rr){    tree[k].l=ll,tree[k].r=rr;    if(ll==rr) {        scanf("%d",&tree[k].w);        return ;    }    int mid=(ll+rr)/2;    build(k*2,ll,mid);    build(k*2+1,mid+1,rr);    tree[k].w = max(tree[k*2].w , tree[k*2+1].w);}int ask(int k,int ll,int rr) {    if(tree[k].r<ll||tree[k].l>rr) return -0x7fffffff;    if(tree[k].l>=ll&&tree[k].r<=rr) return tree[k].w;    return max(ask(k*2,ll,rr),ask(k*2+1,ll,rr));}void change(int k,int ll,int rr) {    if(ll>=tree[k].l&&ll<=tree[k].r)     tree[k].w = max(tree[k].w,rr);    else return;    change(k*2,ll,rr);    change(k*2+1,ll,rr);}int main() {    scanf("%d%d",&n,&m);    build(1,1,n);    for(int i=1; i<=m; i++) {        cin>>sty>>l>>r;        if(sty==‘Q‘) {            printf("%d\n",ask(1,l,r));        }        if(sty==‘U‘) {            change(1,l,r);        }    }    return 0;}

3.P1162 填涂颜色

题目描述

由数字0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6X6的方阵（n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0    0 0 0 0 0 0

0 0 1 1 1 1    0 0 1 1 1 1

0 1 1 0 0 1    0 1 1 2 2 1

1 1 0 0 0 1    1 1 2 2 2 1

1 0 0 0 0 1    1 2 2 2 2 1

1 1 1 1 1 1    1 1 1 1 1 1

输入输出格式

输入格式：

每组测试数据第一行一个整数：n。其中n(1<=n<=30)

接下来n行，由0和1组成的nXn的方阵。

方阵内只有一个闭合圈，圈内至少有一个0。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式：

已经填好数字2的完整方阵。

输入输出样例

输入样例#1：
60 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 1
输出样例#1：
0 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1

说明

1<=n<=30

思路：

　　分别从四个角开始搜索，只搜索0，将能搜索到的0全都标记为3（不为0,1,2就行），则能搜到就为输出的0，仍然为0的就输出为2，

1不改变，输出。

^_^ 代码：
#include<queue>#include<cstdio>#include<iostream>using namespace std;int n,map[32][32];int mh[5]= {0,1,0,-1,0},           ml[5]= {0,0,1,0,-1};struct node {    int h,l;} now,nex;queue<node>car;void bfs(int h,int l) {    now.h=h,now.l=l;    map[h][l]=3;    car.push(now);    int hh,ll;    while(!car.empty()) {        now=car.front();        for(int i=1; i<=4; ++i) {            hh=now.h+mh[i],ll=now.l+ml[i];            if(hh>=1&&hh<=n&&ll>=1&&ll<=n&&map[hh][ll]==0) {                map[hh][ll]=3;                nex.h=hh,nex.l=ll;                car.push(nex);            }        }        car.pop();    }}int main() {    scanf("%d",&n);    for(int i=1; i<=n; ++i)        for(int j=1; j<=n; ++j)            scanf("%d",&map[i][j]);    for(int i=1; i<=n; ++i){        if(!map[i][1]) bfs(i,1);        if(!map[i][n]) bfs(i,n);        if(!map[1][i]) bfs(1,i);        if(!map[n][i]) bfs(n,i);    }    for(int i=1; i<=n; ++i) {        for(int j=1; j<=n; ++j) {            if(map[i][j]==3)                cout<<0<<" ";            else if(map[i][j]==0)                cout<<2<<" ";            else cout<<1<<" ";        }        cout<<endl;    }    return 0;}

4.P1451 求细胞数量

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）?

输入输出格式

输入格式：

输入：整数m,n(m行，n列)

矩阵

输出格式：

输出：细胞的个数

输入输出样例

输入样例#1：
4  100234500067103456050020456006710000000089
输出样例#1：
4
思路：
    注意输入输出，（可以用标准库queue）。

 ↖(^ω^)↗ 代码：

#include<iostream>#include<cstdio>using namespace std;int n,m,vis[101][101],xbb[101][101],q[101][3],num;int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1};char xb[101];void bfs(int x,int y) {    int head=0,tail=1;    q[1][1]=x,q[1][2]=y;    num++;xbb[x][y]=0;    do{        head++;        for(int i=0; i<=3; i++) {            int xx=q[head][1]+dx[i],yy=q[head][2]+dy[i];            if(xx>=0&&xx<n&&yy>=0&&yy<m&&xbb[xx][yy]) {                tail++;                q[tail][1]=xx;                q[tail][2]=yy;                xbb[xx][yy]=0;            }        }    }while(head<tail);}int main() {    cin>>n>>m;    for(int i=0; i<n; i++)         for(int j=0; j<m; j++)            xbb[i][j]=1; 
    for(int i=0; i<n; i++) {        cin>>xb;         for(int j=0; j<m ;j++)            if(xb[j]==‘0‘) xbb[i][j]=0;     }        for(int i=0; i<n; i++) {        for(int j=0; j<m ;j++) {            if(xbb[i][j])            bfs(i,j);        }    }    cout<<num<<endl;    return 0;}

5.P1657 选书

题目描述

学校放寒假时，信息学奥赛辅导老师有1,2,3……x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。

输入输出格式

输入格式：

第1行：一个数x

第2行~第1+x行：每行两个数，表示ai喜欢的书的序号

输出格式：

只有一个数：总方案数total。

输入输出样例

输入样例#1：
51 34 52 51 43 5
输出样例#1：
2

说明

所有数据：x<=20

（世界上最难出数据的题目，没有之一……）

O(∩_∩)O~ 代码：

#include<iostream>#include<cstdio>using namespace std;int ans,n,love1,love2,like[21][21];int choose[21];void dfs(int n,int k){    for(int i=1; i<=n;i++) {        if(!choose[i]&&like[k][i]) {            choose[i]=1;            if(k==n) ans++;            else dfs(n,k+1);            choose[i]=0;        }    }}int main() {    cin>>n;    for(int i=1; i<=n; i++) {        cin>>love1>>love2;        like[i][love1]=1;        like[i][love2]=1;    }    dfs(n,1);    cout<<ans<<endl;    return 0;}

6.P2040 打开所有的灯

题目背景

pmshz在玩一个益(ruo)智(zhi)的小游戏，目的是打开九盏灯所有的灯，这样的游戏难倒了pmshz。。。

题目描述

这个灯很奇(fan)怪(ren)，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是告诉pmshz要全部打开这些灯。

例如

0 1 1

1 0 0

1 0 1

点一下最中间的灯【2,2】就变成了

0 0 1

0 1 1

1 1 1

再点一下左上角的灯【1,1】就变成了

1 1 1

1 1 1

1 1 1

达成目标。最少需要2步。

输出2即可。

输入输出格式

输入格式：

九个数字，3*3的格式输入，每两个数字中间只有一个空格，表示灯初始的开关状态。（0表示关，1表示开）

输出格式：

1个整数，表示最少打开所有灯所需要的步数。

输入输出样例

输入样例#1：
0  1  11  0  01  0  1
输出样例#1：
2

说明

这个题水不水，就看你怎么考虑了。。。。

（づ￣3￣）づ╭?～ 代码：
#include<iostream>#include<cstdio>using namespace std;int light[5][5],ans=10;int vis[5][5];bool choose(){    for(int i=1; i<=3; i++)         for(int j=1; j<=3; j++)           if(!light[i][j]) return 0;    return 1;}void dfs(int k){    if(k==10) return ;    for(int i=1; i<=3; i++) {        for(int j=1; j<=3; j++) {            if(!vis[i][j]) {                vis[i][j]=1;                light[i][j]=!light[i][j];                light[i+1][j]=!light[i+1][j];                light[i-1][j]=!light[i-1][j];                light[i][j+1]=!light[i][j+1];                light[i][j-1]=!light[i][j-1];                if(choose()) ans=min(ans,k);                dfs(k+1);                 vis[i][j]=0;                light[i][j]=!light[i][j];                light[i+1][j]=!light[i+1][j];                light[i-1][j]=!light[i-1][j];                light[i][j+1]=!light[i][j+1];                light[i][j-1]=!light[i][j-1];            }        }    }}int main() {    for(int i=1; i<=3; i++) {        for(int j=1; j<=3; j++) {            cin>>light[i][j];        }    }    if(choose()) ans=0;    dfs(1);    cout<<ans<<endl;    return 0;}

 

自己选的路，跪着也要走完！！！

洛谷——基础搜索


联系
我们