HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 05-15

2021-05-18 20:42:34 By 张义丰

05-15——搜索 P3----------------

OJ-534 体积

自己写的

/*************************************************************************
    > File Name: 534.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 16 May 2021 04:54:55 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, ans, a[25];
bool e[1005];
void dfs(int ind, int s) {
    if (ind > n+1) return ;
    if (!e[s]){
        ans ++;
        e[s]= true;
    }
    dfs(ind+1, s+a[ind]);
    dfs(ind+1, s);
}
int main(){
    cin >> n;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
    }
    e[0] = true;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

根据235题代码改写的

/*************************************************************************
    > File Name: 235_2.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 06:39:57 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, ans, num[25], a[25];
bool e[1005] = {1};
void cal(int x){
    int sum = 0;
    for (int i=1; i<=x; ++i){
        sum += a[num[i]];
    }
    if (!e[sum]){
        e[sum] = true;
        ans ++;
    }
}
void func(int start, int ind) {
    for (int i = start; i<=n; ++i) {
        num[ind] = i;
        cal(ind);
        func(i+1, ind+1);
    }
}
int main(){
    cin >> n;
    for (int i=1; i<=n; ++i) cin >> a[i];
    func(1, 1);
    cout << ans << endl;
    return 0;
}

OJ-537 门票问题

自己写的程序

/*************************************************************************
    > File Name: 537.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 16 May 2021 06:06:16 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int L, C, tot;
char ch[30], store[20];
bool finish, used[30];
void dfs(int cnt, int start, int y, int f) {
    //cnt:0~L-1 密码的指针 start:本次搜索的起点 y:当前元音个数 f:当前辅音个数
    if (cnt ==  L){
        if (y > 0 && f > 1){
            for (int i=0; i<cnt; ++i) cout << store[i];
            cout << endl;
            tot ++ ;
            if (tot == 25000) finish = true;
        }
    }else {
        for (int i=start; i<C; ++i){
            if (used[i]) continue;
            store[cnt] = ch[i];
            used[i] = true;
            if (ch[i] == 'a' || ch[i] == 'e' || ch[i] == 'i' || ch[i] == 'o' || ch[i] == 'u'){
               dfs(cnt+1, i+1, y+1, f);
            } else {
                dfs(cnt+1, i+1, y, f+1);
            }
            used[i] = false;
            if (finish) break;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> L >> C;
    for (int i=0; i<C; ++i) cin >> ch[i];
    sort(ch, ch+C);
    dfs(0, 0, 0, 0);
    return 0;
}

这个程序调试了好久!

1、忘了加used[]进行标记

2、输出可能比较费时,加了ios::sync_with_stdio(false)

3、忘了25000的个数上限

4、最难找的错误:used[]才开了20,本地调试是对的,服务器上WA

OJ-539 速算游戏

/*************************************************************************
    > File Name: 539.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 18 May 2021 06:51:34 AM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
char ch[4], fh[7] = {'+', '-', '*', '/', '&', '|', '^'};
int num[4];
vector<string> ans;
int kl(int n1, int n2, char op) {
    switch (op) {
        case '+': return n1 + n2;
        case '-': return n1 - n2;
        case '*': return n1 * n2;
        case '/': if (n2 == 0 || n1 % n2) return 999999999;
                    else return n1 / n2;
        case '&': return n1 & n2;
        case '|': return n1 | n2;
        case '^': return n1 ^ n2;
    }
}
int cal(int f1, int f2, int f3, int cx){
    int a, b;
    switch (cx) {
        case 0: a = kl(num[0], num[1], fh[f1]);
                b = kl(a, num[2], fh[f2]);
                return kl(b, num[3], fh[f3]);
        case 1: a = kl(num[0], num[1], fh[f1]);
                b = kl(num[2], num[3], fh[f3]);
                return kl(a, b, fh[f2]);
        case 2: a = kl(num[1], num[2], fh[f2]);
                b = kl(num[0], a, fh[f1]);
                return (b, num[3], fh[f3]);
        case 3: a = kl(num[1], num[2], fh[f2]);
                b = kl(b, num[3], fh[f3]);
                return kl(num[0], b, fh[f1]);
        case 4: a = kl(num[2], num[3], fh[f3]);
                b = kl(num[1], a, fh[f2]);
                return kl(num[0], b, fh[f1]);
    }
}
char toch(int x) {
    if (x == 1) return 'A';
    if (x == 10) return 'T';
    if (x == 11) return 'J';
    if (x == 12) return 'Q';
    if (x == 13) return 'K';
    return x + '0';
}
string make(int f1, int f2, int f3, int cx) {
    string ret = "";
    switch (cx) {
        case 0: ret += "(((";
                ret.push_back(toch(num[0]));
                ret.push_back(fh[f1]);
                ret.push_back(toch(num[1]));
                ret.push_back(')');
                ret.push_back(fh[f2]);
                ret.push_back(toch(num[2]));
                ret.push_back(')');
                ret.push_back(fh[f3]);
                ret.push_back(toch(num[3]));
                ret.push_back(')');
                break;
        case 1: ret += "((";
                ret.push_back(toch(num[0]));
                ret.push_back(fh[f1]);
                ret.push_back(toch(num[1]));
                ret.push_back(')');
                ret.push_back(fh[f2]);
                ret.push_back('(');
                ret.push_back(toch(num[2]));
                ret.push_back(fh[f3]);
                ret.push_back(toch(num[3]));
                ret.push_back(')');
                ret.push_back(')');
                break;
        case 2: ret += "((";
                ret.push_back(toch(num[0]));
                ret.push_back(fh[f1]);
                ret.push_back('(');
                ret.push_back(toch(num[1]));
                ret.push_back(fh[f2]);
                ret.push_back(toch(num[2]));
                ret.push_back(')');
                ret.push_back(')');
                ret.push_back(fh[f3]);
                ret.push_back(toch(num[3]));
                ret.push_back(')');
                break;
        case 3: ret += "(";
                ret.push_back(toch(num[0]));
                ret.push_back(fh[f1]);
                ret.push_back('(');
                ret.push_back('(');
                ret.push_back(toch(num[1]));
                ret.push_back(fh[f2]);
                ret.push_back(toch(num[2]));
                ret.push_back(')');
                ret.push_back(fh[f3]);
                ret.push_back(toch(num[3]));
                ret.push_back(')');
                ret.push_back(')');
                break;
        case 4: ret += "(";
                ret.push_back(toch(num[0]));
                ret.push_back(fh[f1]);
                ret.push_back('(');
                ret.push_back(toch(num[1]));
                ret.push_back(fh[f2]);
                ret.push_back('(');
                ret.push_back(toch(num[2]));
                ret.push_back(fh[f3]);
                ret.push_back(toch(num[3]));
                ret.push_back(')');
                ret.push_back(')');
                ret.push_back(')');
                break;
    }
    return ret;
}
int main(){
    for (int i=0; i<4; ++i){
        cin >> ch[i];
        if (ch[i] == 'A') num[i] = 1;
        else if (ch[i] == 'T') num[i] = 10;
        else if (ch[i] == 'J') num[i] = 11;
        else if (ch[i] == 'Q') num[i] = 12;
        else if (ch[i] == 'K') num[i] = 13;
        else num[i] = ch[i] - '0';
    }
    sort(num, num+4);
    //cout << num[0] << ' ' << num[1] << ' ' << num[2] << ' ' << num[3] << endl;
    do {
        for (int i=0; i<7; ++i) {
            for (int j=0; j<7; ++j) {
                for (int k=0; k<7; ++k){
                    for (int t=0; t<5; ++t){
                        //cout << make(i, j, k, t) << "\t" << cal(i, j, k, t)<< endl;
                        if (cal(i, j, k, t) == 24){
                            ans.push_back(make(i, j, k, t));
                        }
                    }
                }
            }
        }

    } while (next_permutation(num, num+4));
    string ANS = "\127";
    for (int i=0; i<ans.size(); ++i){
        if (ans[i] < ANS) ANS = ans[i];
    }
    cout << ANS << endl;
    return 0;
}

OJ-540 生日购物

/*************************************************************************
    > File Name: 540.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 18 May 2021 06:13:27 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int N, X, a[45], s[2][2000000], cnt[2];
void dfs(int s_num, int start, int end, int sum) {
    if (sum > X) return ;
    for (int i=start; i<end; ++i) {
        sum += a[i];
        s[s_num][cnt[s_num]++] = sum;
        dfs(s_num, i+1, end, sum);//注意:这里的i+1一开始写成了start+1,找了半天没找出来!!!
        sum -= a[i];
    }
}
int main(){
    while (cin >> N >> X) {
        cnt[0] = cnt[1] = 1;
        for (int i=0; i<N; ++i) cin >> a[i];
        dfs(0, 0, N/2, 0);
        dfs(1, N/2, N, 0);
        sort(s[1], s[1]+cnt[1]);
        bool fnd = false;
        for (int i=0; i<cnt[0] && !fnd; ++i) {
            int target = X - s[0][i];
            int mid, l = 0, r = cnt[1] - 1;
            while (l <= r) {
                mid = (l + r) / 2;
                if (s[1][mid] == target) {
                    cout << "YES\n";
                    fnd = true;
                    break;
                }
                if (s[1][mid] < target) l = mid + 1;
                else r = mid - 1;
            }
        }
        if (!fnd) cout << "NO\n";
    }
    return 0;
}

本题还可以用01背包+压缩数组来做,可以试试

OJ-541 相遇问题

暴力

/*************************************************************************
    > File Name: 541.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 18 May 2021 06:42:10 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, arr[2][20][20], ans[2][1000000], cnt[2];
void func(int index, int now, int cost) {
    if (now == n) {
        ans[index][cnt[index]++] = cost;
    }else {
        for (int i=now+1; i<=n; ++i){
            if (arr[index][now][i]) {
                func(index, i, cost+arr[index][now][i]);
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for (int i=0; i<m; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        arr[0][a][b] = arr[0][b][a] = c;
        arr[1][a][b] = arr[1][b][a] = d;
    }
    func(0, 1, 0);
    func(1, 1, 0);
    sort(ans[0], ans[0]+cnt[0]);
    sort(ans[1], ans[1]+cnt[1]);
    for (int i=0; i<=cnt[0]; ++i) {
        int l = 0, r = cnt[1] - 1;
        while (l <= r) {
            int mid = (l+r)/2;
            if (ans[1][mid] == ans[0][i]) {
                cout << ans[0][i] << endl;
                return 0;
            }
            if (ans[1][mid] < ans[0][i]){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
    }
    cout << "IMPOSSIBLE\n";
    return 0;
}

本题也可以用unoderedset,但可能更慢

【搜索的状态】

dfs: 递归函数的参数

bfs: 队列中的节点

起点:所有起点存在一个数组中(类比线性筛)

终点:增加一个标记(类比素数筛)

/*************************************************************************
    > File Name: 542.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 18 May 2021 07:14:22 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int T, n, h, r, xyz[1005][3], down[1005], cnt, up[1005], arr[1005][1005], mark[1005];
int func(int now) {//深搜
    if (up[now] == 1){
        return 1;
    }
    for (int i=0; i<n; ++i){
        if (arr[now][i] && mark[i]==0){
            mark[i] = 1;
            if (func(i)){
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    cin >> T;
    while (T--) {
        cnt = 0;
        memset(up, 0, sizeof(up));
        memset(arr, 0, sizeof(arr));
        memset(mark, 0, sizeof(mark));
        cin >> n >> h >> r;
        for (int i=0; i<n; ++i){
            cin >> xyz[i][0] >> xyz[i][1] >> xyz[i][2];
            if (xyz[i][2] <= r){
                down[cnt++] = i;
            }
            if (xyz[i][2] + r >= h){
                up[i] = 1;
            }
            for (int j=0; j<i; ++j) {
                int t1 = xyz[i][0] - xyz[j][0];
                int t2 = xyz[i][1] - xyz[j][1];
                int t3 = xyz[i][2] - xyz[j][2];
                double t4 = sqrt(t1*t1 + t2*t2 + t3*t3);
                if (t4 <= 2*r) {
                    arr[i][j] = arr[j][i] = 1;
                }
            }
        }
      //下面尝试所有起点,看看能不能走到终点
        int flag = 0;
        for (int i=0; i<cnt; ++i){
            if (mark[down[i]] == 0){
                mark[down[i]] = 1;
                if (func(down[i])){
                    cout << "Yes\n";
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0){
            cout << "No\n";
        }
    }
    return 0;
}

注意:有些起点与终点是在奶酪外面的,不影响结果。因为他们之间如果能连通,必然经过真正的起点和终点

Leetcode-417 太平洋大西洋水流问题

逆向考虑,没做代码演示

Leetcode-529. 扫雷游戏

只能从[0,0]开始存地图,所以只能判断边界

class Solution {
public:
    struct node {
        int x, y;
    };
    int dir[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, 1, 1, -1, -1, -1, -1, 1};
    int n, m;
    int func(node &temp, vector<vector<char>> mmap){
        int cnt = 0;
        for (int i=0; i<8; ++i){
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (x<0 || y<0 || x==n || y ==m) continue;
            if (mmap[x][y] == 'M') cnt ++;
        }
        return cnt;
    }
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        n = board.size();
        m = board[0].size();
        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }
        queue<node> que;
        if (board[click[0]][click[1]] == 'E'){
            board[click[0]][click[1]] = 'B';
            que.push(node{click[0], click[1]});
        }
        while (!que.empty()){
            node temp = que.front();
            que.pop();
            int cnt = func(temp, board);
            if (cnt != 0) {
                board[temp.x][temp.y] = (char)(cnt + '0');
                continue;
            }
            for (int i=0; i<8; ++i){
                int x = temp.x + dir[i][0];
                int y = temp.y + dir[i][1];
                if (x<0 || y<0 || x==n || y==m) continue;
                if (board[x][y] == 'E'){
                    board[x][y] = 'B';
                    que.push(node{x, y});
                }
            }
        }
        return board;
    }
};

Leetcode-934. 最短的桥

最少步数问题,BFS, 没打代码

Leetcode-967. 连续差相同的数字

既可以用广搜,也可以用深搜

注意k==0时需要特殊处理

Leetcode-752. 打开转盘锁

注意:如果终点是死亡数字,不影响计算

Leetcode-127. 单词接龙

除了起始单词以外,所有过程中的单词必须都在字典中

Leetcode-864. 获取所有钥匙的最短路径

class Solution {
public:
    struct node {
        int x, y, step, status;
    };
    int n, m, cnt, sx, sy, mark[30][30][100];
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
    int b2[10] =  {1, 2, 4, 8, 16, 32, 64};
    int shortestPathAllKeys(vector<string>& grid) {
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; ++i){
            for (int j=0; j<m; ++j){
                if (grid[i][j] >= 'a' && grid[i][j] <= 'z') cnt ++ ;
                if (grid[i][j] == '@'){
                    sx = i, sy = j;
                    grid[i][j] = '.';
                }
            }
        }
        queue<node> que;
        que.push(node{sx, sy, 0, 0});
        mark[sx][sy][0] = 1;
        while (!que.empty()){
            node temp = que.front();
            que.pop();
            if (temp.status == b2[cnt] -1){
                return temp.step;
            }
            for (int i=0; i<4; ++i){
                int x = temp.x + dir[i][0];
                int y = temp.y + dir[i][1];
                if (x<0 || y<0 || x==n || y==m) continue;
                if (grid[x][y] == '.' && mark[x][y][temp.status]==0){
                    mark[x][y][temp.status] = 1;
                    que.push(node{x, y, temp.step+1, temp.status});
                }
                if (grid[x][y] >= 'A' && grid[x][y] <= 'Z' && (b2[grid[x][y]-'A']&temp.status)!=0 && mark[x][y][temp.status] == 0){
                    mark[x][y][temp.status] = 1;
                    que.push(node{x, y, temp.step+1, temp.status});
                }
                if (grid[x][y] >= 'a' && grid[x][y] <= 'z' && mark[x][y][temp.status] == 0){
                    mark[x][y][temp.status] = 1;
                    mark[x][y][temp.status | b2[grid[x][y]-'a']] = 1;
                    que.push(node{x, y, temp.step+1, temp.status | b2[grid[x][y]-'a']});
                }
            }
        }
        return -1;
    }
};

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。