2020.11.3 笔试题

记录一下2020.11.03银行的三道笔试题。

1. 大意是每购买完一件产品，记录的是已经购买完的所有产品的最大价值，但是只能记录最后连续k件的最大价格。输出记录的价格。

示例：

输入：
1
3 2
9 6 6

输出：
9 9 6

思路：类似滑动窗口最大值

#include <bits/stdc++.h>

using namespace std;

vector<int> helper(vector<int>& nums, int k) {
    vector<int> res;
    int n = nums.size();
    if (nums.empty())
        return res;
    deque<int> q;
    int i = 0;
    while(i < n){
        while (!q.empty() && nums[i] > nums[q.back()]){
            q.pop_back();
        }
        while (!q.empty() && (i-q.front()+1)>k) {
            q.pop_front();
        }
        q.push_back(i);
        res.push_back(nums[q.front()]);
        i++;
    }
    return res;
}

void printVec(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (i != (int)nums.size() - 1) {
            cout << nums[i] << " ";
        } else {
            cout << nums[i] << endl;
        }
    }
}


int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        vector<int> res;
        res = helper(nums, k);
        printVec(res);
    }
    return 0;
}

1. 漂流模拟，有n段陡坡，在进入每段陡坡瞬间，他们的皮划艇前进速度都会瞬间+1，而当通过陡坡时，由于惯性，皮划艇会保持当前速度前进。

在开始漂流时，初始速度为1，已知陡坡信息以及漂流总长度为L，请问他们耗时多久完成漂流。

示例

输入：
1
2 6
2 3
4 7

输出：3.000000

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, L;
        double t = 0.0;
        double v = 1.0;
        cin >> n >> L;
        vector<pair<int,int>> doupo;
        for (int i = 0; i < n; i++) {
            int l, r;
            cin >> l >> r;
            doupo.push_back({l,r});
        }
        double t1, t2;
        int start = 1;
        int end = L + 1;
        for (auto &p : doupo) {
            t1 = (p.first - start) / v;
            start = p.first;
            v += 1.0;
            t2 = (double)(p.second - start) / v;
            start = p.second;
            t = t + t1 + t2;
        }
        double t3 = (end - start) / v;
        t += t3;
        cout << fixed << setprecision(6) << t << endl;
    }
    return 0;
}

1. 迷宫有唯一的入口和唯一的出口，同时有若干个空地，障碍物，以及一些有效点，给一张地图，看能否从S走到T点，并且经过全部有效点，可以的话输出YES，否则输出NO。

示例：

输入：
1
3 3
S . X
. . X
X . T

输出：YES

#include <bits/stdc++.h>

using namespace std;

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool flag;
void dfs(vector<vector<char>> &g, vector<vector<int>> &vis, int n, int m, int i, int j, int &valid, int count) {
    if (g[i][j] == 'T' && valid == count) {
        flag = true;
        return;
    }
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];
        if ((x >= 0 && x < n && y >= 0 && y < m) && vis[x][y] == 0 && (g[x][y] =='.' || g[x][y] == 'X' || g[x][y] == 'T')) {
            if (g[x][y] == 'X') valid++;
            vis[x][y] = 1;
            dfs(g, vis, n, m, x, y, valid, count);
            if (g[x][y] == 'X') valid--;
            vis[x][y] = 0;
        }
    }
}

bool check(vector<vector<char>> &g, int count) {
    int n = g.size();
    int m = g[0].size();
    int valid = 0;
    vector<vector<int>> vis(n, vector<int>(m,0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') {
                dfs(g, vis, n, m, i, j, valid, count);
                if (flag) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<char>> g(n, vector<char>(m));
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> g[i][j];
                if (g[i][j] == 'X') count++;
            }
        }
        flag = false;
        if (check(g, count)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}