kuangbin带你飞专题一

ACM

我也想好好刷题，但是没人监督


kuangbin带你飞专题一

B

一个简单的bfs，就是退出的条件有一点不懂啊
在while里面写成这样:

1
2
3
if(q.empty()){
            return -1;
        }

就是错误的emmm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
int c, n, m;
const int maxn = 35;
char mp[maxn][maxn][maxn];
int dz[6] = {0, 0, 0, 0, 1, -1};
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int sx, sy, sz;
int tx, ty, tz;
bool vis[maxn][maxn][maxn];
struct Node{
    int x, y, z;
    int tot;
    Node(int a, int b, int c, int num):x(a), y(b), z(c), tot(num){};
};
bool judge(int x, int y, int z){
    if(vis[z][x][y] == true) return false;
    if(x<0||x>=n) return false;
    if(y<0||y>=m) return false;
    if(z<0||z>=c) return false;
    if(mp[z][x][y] == '#') return false;
    if(z == sz&&x == sx&&y == sy) return false;
    return true;
}
int bfs(int x, int y, int z){
    Node temp = Node{x, y, z, 0};
    queue<Node> q;
    q.push(temp);
    vis[z][x][y] = true;
    while(!q.empty()){
        Node temp1 = q.front();
        q.pop();
        if(temp1.x == tx&&temp1.y == ty&&temp1.z == tz){
            return temp1.tot;
        }
        for(int i=0; i<6; i++){
            int nx = temp1.x+dx[i];
            int ny = temp1.y+dy[i];
            int nz = temp1.z+dz[i];
            int step = temp1.tot+1;
            if(judge(nx, ny, nz)){
                vis[nz][nx][ny] = true;
                q.push(Node{nx, ny, nz, step});
            }
        }
    }
    return -1;
}
int main()
{
    while(cin>>c>>n>>m&&(n+m+c)!=0){
        getchar();
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<c; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<m; k++){
                    cin>>mp[i][j][k];
                    if(mp[i][j][k] == 'S'){
                        sz = i, sx = j, sy = k;
                        //cout<<sz<<" "<<sx<<" "<<sy<<endl;
                    }
                    else if(mp[i][j][k] == 'E'){
                        tz = i, tx = j, ty = k;
                        //cout<<tz<<" "<<tx<<" "<<ty<<endl;
                    }
                }
            }
        }
        int tot = bfs(sx, sy, sz);
        if(tot!=-1){
            printf("Escaped in %d minute(s).\n", tot);
        }
        else printf("Trapped!\n");
    }
    return 0;
}

c

一个简单的bfs状态搜索，但是卡了我一个下午！！
函数一定要在最外面有一个返回值！！！！！！！return 0；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5+10;
bool vis[maxn];
int n, k;
struct Node{
    int x, step;
    Node(){
        this->step = 0;
        this->x = -1;
    }
};
int bfs(){
    Node s;
    s.step = 0;
    s.x = n;
    queue<Node> q;
    q.push(s);
    vis[n] = true;
    while(!q.empty()){
        Node temp = q.front();
        q.pop();
        if(temp.x == k) return temp.step;
        Node temp1;
        int nex;
        for(int i=0; i<3; i++){
            if(i == 0) nex = temp.x-1;
            if(i == 1) nex = temp.x+1;
            if(i == 2) nex = temp.x*2;
            if(nex<0||nex>100000) continue;
            if(!vis[nex]){
                vis[nex] = true;
                temp1.x = nex;
                temp1.step = temp.step+1;
                q.push(temp1);
            }
        }
    }
    return 0;//必须要在外面返回一个值，不然就要gg!!
}
int main(){
    while(~scanf("%d%d", &n, &k)){
        memset(vis, 0, sizeof(vis));
        printf("%d\n",bfs());
    }
    return 0;
}

E find the multiple

用dfs然后超时了emmmm
打表大法好啊
把主程序放上来吧
有一个小的知识点就是超大整数判断能否整除一个整数，要用到模拟除法的运算过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
int n;
const int maxn = 105;
char ans[maxn];
char ans1[201][maxn];
bool judge(char* ch, int len){
    int num = 1;
    num %= n;
    for(int i=1; i<=len; i++){
        num = num*10+ch[i]-'0';
        num %= n;
    }
    if(num == 0) return true;
    else return false;
}
bool dfs(char* ch, int index){
    if(index>=100){
        return false;
    }
    if(judge(ch, index)){
        ch[index+1] = '\0';
        printf("%s\n", ch);
        return true;
    }
    else{
        ch[index+1] = '0';
        if(dfs(ch, index+1)){
            return true;
        }
        ch[index+1] = '1';
        if(dfs(ch, index+1)){
            return true;
        }
    }
    return false;
}
int main()
{
    ans[0] = '1';
    freopen("ans.out", "w", stdout);
    for (n=1; n<=200; n++)
    {
        dfs(ans, 0);
    }
    return 0;
}

F find prime path

一个很裸的bfs

注意vis[]的访问顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1e6+10;
bool prime[maxn];
void init(){
    memset(prime, 0, sizeof(false));
    for(int i=2; i<=maxn; i++){
        if(!prime[i]){
            for(int j=2*i; j<=maxn; j+=i){
                prime[j] = true;
            }
        }
    }
}
int n, m;
bool vis[maxn];
int ans[maxn];
int trans(int n, int i, int j){
    int ans[4];
    ans[0] = n/1000;
    ans[1] = (n/100)%10;
    ans[2] = (n/10)%10;
    ans[3] = n%10;
    if(ans[i] == j) return -1;
    ans[i] = j;
    return ans[0]*1000+ans[1]*100+ans[2]*10+ans[3];
}
int bfs(int n){
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    ans[n] = 0;
    q.push(n);
    vis[n] = true;
    while(true){
        int temp = q.front();
        q.pop();
        if(temp == m){
            return ans[temp];
        }
        for(int i=0; i<4; i++){
            for(int j=0; j<=9; j++){
                int new_num = trans(temp, i, j);
                if(new_num<=1000) continue;
                else if(new_num == -1) continue;
                else if(vis[new_num]||prime[new_num]) continue;
                else {
                    q.push(new_num);
                    vis[new_num] = true;
                    ans[new_num] = ans[temp]+1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    init();
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        printf("%d\n", bfs(n));
    }
    return 0;
}


# 未解决的问题

本文标题:kuangbin带你飞专题一

文章作者:Babydragon

发布时间:2018-04-03, 16:47:22

最后更新:2018-04-15, 20:07:09

原始链接:http://baolintian.github.io/2018/04/03/kuangbin带你飞专题一/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. B
  2. 2. c
  3. 3. E find the multiple
  4. 4. F find prime path
{{ live2d() }}