携程-9月9日后端笔试-3/3ak

题目1

思路

使用vector<string>模拟一个栈就行了</string>

1. cd s相当于进栈
2. cd ..相当于出栈
3. pwd命令打印出vector中的内容

代码

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<algorithm>
#include<numeric>
#include<queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    string a;
    string b;
    vector<string> dir;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (a == "cd") {
            cin >> b;
            if (b == ".." && dir.size()) dir.pop_back();
            if (b!="..") dir.push_back(b);
        }
        if (a == "pwd") {
            if(dir.empty()) cout<<"\\";
            else {
                for (auto ss : dir) {
                    cout << "\\" << ss;
                }
            }
            cout << endl;
        }
    }

题目2

思路

从不平衡度限制来进行考虑，检验k个段是否可以满足该不平衡度的需求。不平衡度越小，限制越大，所期望的k越大。举个例子，若不平衡为0，序列为[1,2,3,4,5]，需要的k为5才能满足，若不平衡度限制为1，则需要3个可以满足，划分为[1,2],[3,4][5]。基于这个角度，然后使用二分查找即可。
（这个题目是有点绕，想清楚了就很简单）

代码

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<algorithm>
#include<numeric>
#include<queue>
using namespace std;

//检验k能够满足不平衡度为ret的需求
bool ub_satisfied(vector<int>& nums, int ret, int k) {
    int index = 0;
    int min_v = 1e5;
    int max_v = 0;
    for (; index < nums.size(); index++) {
        max_v = max(max_v, nums[index]);
        min_v = min(min_v, nums[index]);
        if (max_v - min_v > ret) {
            --k;
            max_v = min_v = nums[index];
        }
        if (k == 0) break;
    }
    if (index == nums.size()) return true;
    else return false;
}
//标准二分，没啥好说的
int bin_search(vector<int>& nums,int k,int l=0,int r=1e5) {
    if (l == r) return l;
    int mid = (l + r) / 2;
    if (ub_satisfied(nums, mid, k)) {
        return bin_search(nums, k, l, mid);
    }
    else {
        return bin_search(nums, k, mid+1,r);
    }
    return -1;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int ret = bin_search(nums, k);
    cout << ret << endl;
}

题目3

思路

首先问题可以转换为子问题，由于题目是连续的1进行拆分，最大化分数。首先提取出每段连续1的长度，以111111001111101111为例，划分为三个连续1子串，长度分别为6,5,4，这三个子问题之间互不干扰。每个子问题就是给定一个数字n（代表着连续1的长度），进行拆分，使其分数最大化，这是标准的dp，dp[n]=max(dp[n],score(c)+dp[n-c]) for all c. score(c)代表着消除c个1的分数。

代码

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<algorithm>
#include<numeric>
#include<queue>
using namespace std;

vector<int> dp;

int max_score(int num, vector<vector<int>>& score) {
    if (num < score[0][0]) return 0;
    if (dp[num]) return dp[num];
    int ret = 0;
    for (int i = 0; i < score.size(); i++) {
        if (num < score[i][0]) break;
        ret = max(ret, score[i][1] + max_score(num - score[i][0], score));
    }
    dp[num] = ret;
    return ret;
}

int main() {
    int n, m;
    cin >> n >> m;
    dp.resize(n+1);
    vector<vector<int>> score(m, vector<int>(2, 0));
    string ss;
    int ret = 0;
    cin >> ss;
    for (int i = 0; i < m; i++) {
        cin >> score[i][0] >> score[i][1];
    }
    sort(score.begin(), score.end());
    for (int i = 0; i < ss.length(); i++) {
        if (ss[i] == '0') continue;
        int s = i;
        while (i < ss.length() && ss[i] == '1') {
            i++;
        }
        ret += max_score(i - s, score);
    }
    cout << ret << endl;
}