A 陷阱

我们可以从 \(l\) 枚举到 \(d\)，再计算是否满足要求，满足要求加入到数组中，输出第一个和最后一个

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int k;
int nums[N];
int main() {
    int l, d, x;
    cin >> l >> d >> x;
    for (int i = l; i <= d; i++) {
        int num = i;
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        if (sum == x)
            nums[k++] = i;
    }
    cout << nums[0] << endl;
    cout << nums[k - 1];
    return 0;
}

B 翻转元素

我们可以使用动态规划来解决这个问题，\(f[i]\) 表示前 \(i\) 个数能达到的最大值，那么我们再加一维表示是否翻转
\(f[i][0]\) 表示没有翻转，如果前面一个数没有翻转，直接加 \(x\)，如果翻转了加 \(-x\)
\(f[i][1]\) 表示翻转，如果前面一个数没有翻转，那么自己翻自己加 \(-x\)，否则加 \(x\)
初始化：\(f[i][0]=x\) 没有翻转 \(f[i][1]=-x\) 翻转了
由于最少两个数翻转，那么最后的答案只能是不翻转的 \(f[n][0]\)

#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int f[N][2];
signed main() {
    int n;
    cin >> n;
    int x;
    cin >> x;
    f[1][0] = x;
    f[1][1] = -x;
    for (int i = 2; i <= n; i++) {
        cin >> x;
        f[i][0] = max(f[i - 1][0] + x, f[i - 1][1] - x);
        f[i][1] = max(f[i - 1][0] - x, f[i - 1][1] + x);
    }
    cout << f[n][0];
    return 0;
}

C 移动棋子

我们可以发现，想让移动的步数最小，就要让空隙最小。我们干脆把所有空隙大的放一个棋子不去移动，然后只用一个棋子移动。
为了避免负数这种麻烦的情况，我们直接对原数组排序，然后用一个数组计算所有的空隙，从大到小排序，然后选出 \(n-1\) 个空隙最大的摆上棋子，其余的加起来就行了

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int x[N], nums[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) cin >> x[i];
    sort(x + 1, x + m + 1);
    int res = 0;
    for (int i = 1; i < m; i++) {
        res += x[i + 1] - x[i];
        nums[i] = x[i + 1] - x[i];
    }
    sort(nums + 1, nums + m, greater<int>());
    for (int i = 1; i < n; i++) res -= nums[i];
    printf("%d", res);
    return 0;
}

D 插队

单调栈搞熟了再来更新

#include <iostream>
#include <vector>
using namespace std;
const int N = 1000005;
int stk[N], res[N], h[N];
int tt;
vector<int> vec[N];
int main() {
    int n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &h[i]);
        while (tt && h[i] > h[stk[tt]]) tt--;
        vec[stk[tt]].push_back(i);
        stk[++tt] = i;
    }
    tt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vec[i].size(); j++) {
            int k = vec[i][j];
            while (tt && h[k] > h[stk[tt]]) tt--;
            res[k] = stk[tt];
        }
        stk[++tt] = i;
    }
    for (int i = 1; i <= n; i++) {
        int ans = res[i] + 1;
        printf("%lld\n", ans);
    }
    return 0;
}

E 小熊