字节8.28后端笔试

//第一题，因为都是2的n次方，所以取对数转乘法为加法
int main(){
    int n;
    cin >> n;
    unordered_map<int, int> cache;
    for(int i = 0; i <= 10; ++i){
        cache[1 << i] = i;
    }
    cache[0] = -1;
    for(int i = 0; i < n; ++i){
        int m;
        cin >> m;
        vector<int> nums(m);
        for(int j = 0; j < m; ++j){
            cin >> nums[j];
            nums[j] = cache[nums[j]];
        }
        int max_val = INT_MIN;
        int prefix = 0;
        int prev = -1;
        int left = 0, right = 0;
        for(int k = 0; k < m; ++k){
            if(prev == -1){
                prev = k;
            }
            if(nums[k] == -1){
                prefix = 0;
                prev = -1;
            }else{
                prefix += nums[k];
            }
            if(prefix > max_val){
                max_val = prefix;
                left = prev;
                right = k;
            }
        }
        //此处max避免极端输出是[1,1]的情况
        cout << max(0,left) + 1 << " " << right + 1 << endl;
    }
    return 0;
}

//第二题拓扑排序
int main(){
    int line;
    cin >> line;
    cin.ignore();
    string str;
    getline(cin, str);
    stringstream ss(str);
    vector<int> judge;
    int num;
    while(ss >> num){
        judge.emplace_back(num);
    }

    vector<vector<int>> edge(10);
    vector<int> in_degree(10);

    for(int i = 0; i < line - 1; ++i){
        string str_line;
        getline(cin, str_line);
        stringstream line_ss(str_line);
        int cur;
        int cnt = 0;
        int node = -1;
        while(line_ss >> cur){
            if(cnt != 0){
                edge[cur].emplace_back(node);
            }else{
                node = cur;
            }
            ++cnt;
        }
        in_degree[node] = cnt - 1;
    }

    queue<int> q;
    unordered_set<int> vis;
    for(int i = 1; i <= 9; ++i){
        if(in_degree[i] == 0){
            q.emplace(i);
        }
    }

    while(!q.empty()){
        int node = q.front();
        q.pop();
        vis.emplace(node);
        for(auto& next : edge[node]){
            if(--in_degree[next] == 0){
                q.emplace(next);
            }
        }
    }

    for(auto& num : judge){
        if(vis.count(num)){
            cout << 1 << " ";
        }else{
            cout << 0 << " ";
        }
    }
    cout << endl;
    return 0;
}

//第三题
//左右算一次最大数组和
//这里采用左边以i结尾,右边可以不以i+1开头
//也可以采用右边是以i开头,左边可以不以i-1结尾
int main(){
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i){
        cin >> nums[i];
    }
    vector<int> dp(n);
    dp[0] = nums[0];
    for(int i = 1; i < n; ++i){
        dp[i] = max(dp[i-1], 0) + nums[i];
    }

    int res = dp.back();
    int right = nums.back();
    int right_max = right;

    for(int i = n - 2; i >= 0; --i){
        res = max(res, right_max + dp[i]);
        right = max(0, right) + nums[i];
        right_max = max(right, right_max);
    }
    cout << res << endl;
}

//第四题单调队列,滑动窗口时维护k+1个数的窗口中的最小值
int main(){
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i){
        cin >> nums[i];
    }

    deque<int> q;
    int prefix = 0;
    int res = INT_MIN;
    for(int i = 0; i < n; ++i){
        prefix += nums[i];
        while(!q.empty() && i - q.front() + 1 > k + 1){
            q.pop_front();
        }
        while(!q.empty() && nums[i] < nums[q.back()]){
            q.pop_back();
        }
        q.emplace_back(i);
        if(i >= k){
            res = max(res, prefix - nums[q.front()]);
            prefix -= nums[i - k];
        }
    }
    cout << res << endl;
}