米哈游笔试前端9.14 AC C++

一个身高序列，排队，相邻两人身高平均数不是整数的，越多越好，输出最终队列

两种思路：

① 奇、偶身高分别一个栈，然后交替出栈入队，最后剩下的全入队。注意，因为每个人对左右都能产生共献，所以要人数多的先入队，比如【偶，奇，偶】

用到了O(N)的额外空间

#include <bits/stdc++.h>
using namespace std;

const size_t MAX_N = 100002;
uint a[MAX_N];

int main() {
    int n;
    cin >> n;
    stack<uint> odd, even;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] & 1) odd.push(a[i]);
        else even.push(a[i]);
    }

    vector<uint> order;
    while(odd.size() && even.size()) {
        if(odd.size() > even.size()) {
            order.push_back(odd.top());
            order.push_back(even.top());
        }
        else {
            order.push_back(even.top());
            order.push_back(odd.top());
        }
        odd.pop();
        even.pop();
    }

    while(odd.size()) {
        order.push_back(odd.top());
        odd.pop();
    }

    while(even.size()) {
        order.push_back(even.top());
        even.pop();
    }

    for(int i = 0; i < order.size(); i++)
        cout << order[i] << (i == order.size() - 1 ? "\n" : " ");
    return 0;
}

② 基本思路同上，但是奇偶各一个链表，少的往多的里面插，变成经典的合并链表，O(1)空间复杂度

代码略

给定字符串，查找存在连续k个"mihoyo"的最短字串，不存在输出-1，存在输出起始、末尾下标

基本思路：找到所有模式串的下标，保存到一个数组，然后按左右下标间隔k，遍历下标数组，计算最短长度

#include <bits/stdc++.h>
using namespace std;

const string TARGET = "mihoyo";
const size_t TARGET_LEN = TARGET.size();

int main() {
    int n, k;
    cin >> n >> k;
    string str;
    cin >> str;
    vector<size_t> mihoyoPosition;
    size_t p = -1;
    // 全部出现位置
    while((p = str.find(TARGET, p + 1)) != string::npos) mihoyoPosition.push_back(p);
    // 不足k个
    if(mihoyoPosition.size() < k) {
        cout << "-1\n";
        return 0;
    }
    // 找结果
    pair<int, int> answer;
    size_t minLength = UINT_MAX;
    int l = 0, r = k - 1;
    while(r < mihoyoPosition.size()) {
        size_t len = mihoyoPosition[r] - mihoyoPosition[l];
        if(len < minLength) {
            minLength = len;
            answer = {mihoyoPosition[l], mihoyoPosition[r] + TARGET_LEN - 1};
        }
        ++l, ++r;
    }
    cout << answer.first << ' ' << answer.second << '\n';
    return 0;
}

一个序列，每一次操作可以使一个数翻倍，使得序列成为严格递增的最少操作次数

计算每一个元素，严格大于前一个数需要翻倍的次数
设是的下一个数
对于，可以解出
再考虑对于每一个数被翻倍后，后面的数理应同等地一起进行翻倍（或者说，需要先翻完前一个数翻倍的次数，再去做“为了大于前一个数而进行的翻倍”）
因此将每一个数需要的存到一个数组里，然后计算前缀和，最后再求和
仔细考虑特殊情况：
① ，即已经满足了严格递增，解出的会是0或负数，负数实际有意义，说明前缀和累加到自己的时候，可以少翻几次。但是前缀和始终应当非负。
② 与恰好差了2的幂次倍数，为了“严格递增”，需要加一
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const size_t MAX_N = 100002;
int a[MAX_N], mark[MAX_N]; /* 记录每个数的k（大于前一个数需要翻倍的次数） */

int main() {
    size_t n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];

    for(int i = 1; i < n; i++) {
        int k = int(ceil(log2(a[i - 1]) - log2(a[i])));
        // 如果前后两个正好差2^t倍，多乘一个2（为了严格递增）
        double t = log2(a[i - 1] * 1.0 / a[i]);
        mark[i] = abs(ceil(t) - floor(t)) <= 1E-6 ? k + 1 : k;
    }
    LL ans = 0, sum = 0;
    for(int i = 1; i < n; i++) {
        sum = sum + mark[i];
        if(sum < 0) sum = 0;
        ans += sum;
    }
    cout << ans << '\n';
    return 0;
}