# C

# 题目大意

你现在有一个空字符串 $t$ ，给定一个字符串 $s$ ，你可以对 $t$ 做任意顺序的任意次的以下两种操作

在 $t$ 的末尾加一个 0
循环移位一位（往后移 +1 ）

请问，最少要多少步能使得 $t$ 变得和 $s$ 一样？

# 数据范围

$1 \le |S| \le 5 \times 10^5$

# 题解

数据范围到了 $5 \times 10^5$ ，肯定就不能暴力了
如果 $S_i > S_{i-1}$ ，那只能 $S_{i-1}$ 移动一整圈，在移动的过程中，把 $S_i$ 添进去
其余情况，在之前字符加的过程中，添加即可

代码其实很简单，我一开始想的是，连续升序只要加一个 10 ，连续降序加一个 s[i] - '0' ，但是这样就没有注意到，连续升序的话，必须是一个一个来，不能一次性把所有连续升序的都处理掉，因为如果都处理掉的话，那么同加的时候，添加的 $S_i$ 是必然大于后续添加的 $S_{i+1, i + 2....}$ 的

C++

void solve () {
    cin >> s, res = s.size() + s[0] - '0';
    
    for (int i = 1; i < s.size(); i++)
        if (s[i] > s[i - 1])
            res += 10;

    cout << res << '\n';
}

# D

# 题目大意

有一个 $H$ 行 $W$ 列的网格，每个格子上有一个非负整数 $A_{i,j}$
现在放置若干块（可以不放）多米诺骨牌，一张牌覆盖两个相邻的单元格，任意一个单元格不能被多张牌覆盖
对于一个摆放，其摆放分数定义为：未被任何骨牌覆盖的单元格中的所有整数的异或值
问，对于一个给定的图，其得分最大值为？

# 数据范围

$H·W \le 20$

# 题解

观察到，数据范围其实很小，考虑爆搜
暴力遍历每个格子，以当前格子为多米诺骨牌的左上角块，暴力搜索放 / 不放
这里有个记录状态的小技巧，当数据范围小的时候，可以把整个矩阵的搜索情况 $st$ 矩阵处理成字符串记录进 $set$

c++

int n, m, ans = 0;
vector<vector<bool>> st(21, vector<bool>(21, 0));
vector<vector<int>> a(21, vector<int>(21));
set<string> ts;

void dfs() {
    string tmp = "";
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            tmp += to_string(st[i][j]);
            
    if (ts.find(tmp) != ts.end())
        return;
    
    ts.insert(tmp);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            // 均以当前 (i, j) 作为左上角格子
            // 横着摆放
            if (j < m && (!st[i][j] && !st[i][j + 1])) {
                st[i][j] = st[i][j + 1] = true;
                dfs();
                st[i][j] = st[i][j + 1] = false;
            }
            // 竖着摆放
            if (i < n && (!st[i][j] && !st[i + 1][j])) {
                st[i][j] = st[i + 1][j] = true;
                dfs();
                st[i][j] = st[i + 1][j] = false;
            }
        }

    int t = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!st[i][j])
                t ^= a[i][j];
    
    ans = max(ans, t);
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    dfs();

    cout << ans << '\n';
}

# E

# 题目大意

给你一个长度为 $2N$ 的括号数列 $A$ ，定义其得分

对于所有 s[i] == ')' ， $A_i \leftarrow 0$
得分为上述操作后， $A$ 中所有元素的和

$A$ 是数列，把你操作后变为 $0$ 的看作 ) ，没操作的看作 ( ，操作后， $s$ 需要是一个合法的括号序列

请求出一个合法的括号序列 $s$ ，它得分的最大值

# 数据范围

$1 \le T \le 500$
$1 \le N \le 2 \times 10^5$

# 题解

题目是把 ) 直接变为 $0$
如果按一半左括号，一半右括号来算的话，那损失可能会达到最大，不妨把初始括号序列想成 ()()()...()()()
那么在遍历的时候，当找到 ( 时，可以观察其是否左端存在，值更大的 ) ，如果存在的话，可以替换掉当前这个 (
而这个找更大值的步骤，可以用优先队列实现

在写这类题目的时候，均可以用形如 ()()()()...()()() 的括号序列去遍历替换，因为一个左括号和其左侧的任意一个右括号交换的话，其结果都会是一个合法的括号序列，而维护值可以用优先队列，整个思想复杂度是 $O(n·log(n))$ 的、

c++

void solve () {
    cin >> n, a = vector<int>(2 * n + 1);
    int res = 0;
    priority_queue<int, vector<int>, less<int>> heap;

    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];

        if (i & 1) {
            if (!heap.empty() && heap.top() > a[i])
                res += heap.top(), heap.pop(), heap.push(a[i]);
                else res += a[i];
        }
        else
            heap.push(a[i]);
    }

    cout << res << '\n';
}

# F

# 题目大意

给定一个长度为 $N$ 的数列 $A=(a_1,...,a_N)$ ，请针对所有 $1 \le k \le N$ ，计算

$A$ 数列中，长为 $k$ 的 $N-k+1$ 个连续子序列的最大值的和

# 数据范围

$1 \le N \le 2 \times 10^5$
$0 \le A_i \le 10^7$

# 题解

# 错解 - ST 表

时间复杂度直接爆炸了， $ABC$ 没给 $AC$ 一个点

C++

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10;
int dx[] = {0, 0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {0, 1, -1, 0, 0, 1, -1, 1, -1};

int n;
vector<int> a;
int f[N][30], preN[N];

void solve () {
    cin >> n, a = vector<int>(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i], f[i][0] = a[i];
    
    for (int j = 1; j < 30; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        
    for (int k = 1; k <= n; k++) {
        int res = 0;
        for (int i = 1; i <= n - k + 1; i++) {
            int l = i, r = i + k - 1, s = preN[r - l + 1];
            res += max(f[l][s], f[r - (1 << s) + 1][s]);
        }

        cout << res << '\n';
    }
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    preN[1] = 0, preN[2] = 1;;
    for (int i = 3; i < N; i++)
        preN[i] = preN[i / 2] + 1;

    int _ = 1;
    //cin >> _;

    while(_--)
       solve();

    return 0;
}

# 正解 - 单调栈 + 差分

利用单调栈，得到每一个 $a_i$ 能作用的区间 $[l_i, r_i]$ ， $a_i=\max\limits_{i=l_i}^{r_i}a_i$

最小的窗口大小是当子数组包含 $i$ $i$ 并且往两头尽量缩小
- $min(i - l_i, r_i-i)+1$
最大的窗口大小是当子数组包含整个 $[l_i,r_i]$ $[l_{i}, r_{i}]$
- $r_i-l_i+1$

对于 $a_i$ 及其作用区间 $[l_i,r_i]$ 有
记 $len = r_i - l_i + 1,~L=i-l_i+1,~R=r_i-i+1~minn=min(L,R),~maxx=max(L,R)$

$a_i$ 可贡献给 $k=1 \to k = len$ 的区间

$k = 1 \to k = minn$ $k = 1 \to k = m i n n$ 时
- $k$ 区间中任意一点，均能当作 $a_i$ ，所以答案就是 $k$
$k=minn \to k =maxx$ $k = m i n n \to k = m a x x$ 时
- $k$ 区间中，只有 $1 \to minn$ 能当作 $a_i$ ，所以答案是 $minn$
$k=maxx \to len$ $k = m a x x \to l e n$ 时
- 能贡献的越来越少，直到 $k=len$ ，只有一个贡献
贡献会像一个梯形，先单增，再不变，最后单减

用两次前缀和实现二阶差分即可（第一阶差分

\to

斜率，第二阶差分

\to

值）

C++

void solve () {
    cin >> n;
    vector<int> a(n + 2), l(n + 1), r(n + 1), ans(n + 3);
    stack<int> cl, cr;

    a[0] = a[n + 1] = 1e18;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    cl.push(0);
    for (int i = 1; i <= n; i++) {
        while (a[i] > a[cl.top()])
            cl.pop();
        l[i] = cl.top() + 1, cl.push(i);
    }

    cr.push(n + 1);
    for (int i = n; i >= 1; i--) {
        while (a[i] >= a[cr.top()])
            cr.pop();
        r[i] = cr.top() - 1, cr.push(i);
    }

    for (int i = 1; i <= n; i++) {
        int len = r[i] - l[i] + 1, minn = min(i - l[i], r[i] - i) + 1, maxx = max(i - l[i], r[i] - i) + 1;
        
        ans[1] += a[i], ans[minn + 1] -= a[i], ans[maxx + 1] -= a[i], ans[len + 2] += a[i];
    }

    for (int i = 1; i <= n; i++)
        ans[i] += ans[i - 1];
    for (int i = 1; i <= n; i++)
        ans[i] += ans[i - 1], cout << ans[i] << '\n';
}

贪心前缀和优先队列 DFS ABC 模拟暴力搜索差分栈单调栈

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

# F

# 题目大意

# 数据范围

# 题解

# 错解 - ST 表

# 正解 - 单调栈 + 差分

组合数-放球问题

ABC-408