题解

A - 地毯

标准的二维差分前缀和，定义 \(s_{i,j}\) 为当前格子的权值，然后根据题目模拟题意进行差分求和即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10, mod = 1e9 + 7;
int s[N][N];
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        s[a][b] ++, s[a][d + 1] --, s[c + 1][b] --, s[c + 1][d + 1] ++;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            cout << s[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

B - FBI树

根据题意模拟，首先把节点数变成应该的长度即 \(2^n\)，进行两边 \(dfs\)，第一遍类似于线段树保存节点以及区间信息，这里注意如果两个儿子相同也有可能是 F，因为有一个是F那么就是F。接下来进行第二遍 \(dfs\)，首先判断叶子节点，然后判断左右儿子，最后判断根节点。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct node{
    int l, r;
    char val;
};
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    n = 1 << n;
    string s; cin >> s;
    s = " " + s;
    vector<node> tr(n * 4 + 1);
    function<void(int, int, int)> dfs1;
    dfs1 = [&](int u, int l, int r) -> void{
        if(l == r){
            if(s[l] == '1') tr[u] = {l, r, 'I'};
            else if(s[l] == '0') tr[u] = {l, r, 'B'};
            else tr[u] = {l, r, 'F'};
            return;
        }
        tr[u] = {l, r};
        int mid = l + r >> 1;
        dfs1(u << 1, l, mid), dfs1(u << 1 | 1, mid + 1, r);
        if(tr[u << 1].val == tr[u << 1 | 1].val){
            if(tr[u << 1].val == 'I') tr[u].val = 'I';
            else if(tr[u << 1].val == 'B') tr[u].val = 'B';
            else tr[u].val = 'F';
        }
        else tr[u].val = 'F';
    };
    function<void(int)> dfs2;
    dfs2 = [&](int u) -> void{
        if(tr[u].l == tr[u].r){
            cout << tr[u].val;
            return;
        }
        dfs2(u << 1), dfs2(u << 1 | 1);
        cout << tr[u].val; 
    };
    dfs1(1, 1, n);
    dfs2(1);
    return 0;
}

H - 良好的感觉

本题稍微有点怪，本来以为是 \(dp\)，虽然列出方程之后发现 \(1~i\) 之间的最小值与区间和乘积较难维护，于是考虑贪心是否可行，我们可以直接考虑枚举最小值，这样的枚举次数为 \(O(n)\)，定义一个结构体维护信息: 权值 \(val\) 和位置 \(id\)，接下来考虑如何去贪心。

考虑由一个最小值组成的答案是一定的，也就是从最小值这个位置向左右扩展，左边和右边直到遇到一个比它小的位置停止，那么明显的，这个区间即是我们钦定这个最小值能做到的最大贡献，统计即可，这样做一定是对的，因为不存在另一个以这个数为最小值的更大区间。

那么我们从小到大排序，每枚举一个数就打上标记，那么我们在左右扩展中遇到标记过的就停止即可，那么一共打上了 \(n\) 个标记，时间复杂度为 \(O(nlogn + n)\)，但是由于题目中的数值均不大于 \(10^6\)，故我们可以使用桶排序优化到 \(O(n + n)\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct node{
    int val, id;
    bool operator<(const node &w) const{
        return val < w.val;
    }
}a[N];
int s[N];
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        int x; cin >> x; 
        a[i] = {x, i};
        s[i] = s[i - 1] + a[i].val;
    }
    sort(a + 1, a + 1 + n);
    int res = a[1].val * s[n];
    vis[0] = true, vis[a[1].id] = true;
    for(int i = 2; i <= n; i++){
        int l = a[i].id, r = a[i].id;
        while(l && !vis[l - 1]) l --;
        while(r < n && !vis[r + 1]) r ++;
        res = max(res, a[i].val * (s[r] - s[l - 1]));
        vis[a[i].id] = true;
    }
    cout << res << '\n';
    return 0;
}