美团316笔试3,4题

第三题

当时没做出来，后面听说可以2的幂打表，按这个思路重写了一遍，但是无法验证对不对。求找bug。

#include <iostream>
using namespace std;
int main() {
    int n,q;
    cin >> n >> q;
    vector<int> arr(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    vector<int> action(n + 1, q); // 每个元素翻倍了几次
    for (int i = 0; i < q; i++) {
        int tmp;
        cin >> tmp;
        action[tmp]--;
    }
    vector<int> dir(q + 1, 1); // 2的次方打表
    for (int i = 1; i <= q; i++) {
        dir[i] = dir[i - 1] * 2 % 1000000007;
    }
    long outcome = 0;
    for (int i = 1; i <= n; i++) {
        outcome += (long)arr[i] * dir[action[i]] % 1000000007;
    }
    cout << outcome % 1000000007;
}

第四题

通过率70%，不知道怎么优化双指针。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> arr(n + 1, 0);
    vector<int> nums_2(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        if (arr[i] == 2) {
            nums_2[i] = nums_2[i - 1] + 1;
        }
        else {
            nums_2[i] = nums_2[i - 1];
        }
    }
    int outcome = 0;
    for (int left = 1; left <= n; left++) {  // O(n^2)
        for (int right = left; right <= n; right++) {
            int sum_2 = nums_2[right] - nums_2[left - 1];
            if (sum_2 > right - (left - 1) - sum_2) { // 如果2的个数多于1的个数
                outcome += 2;
            }
            else {
                outcome += 1;
            }
        }
    }
    cout << outcome;
}