A 倒序求和

题目非常简单，学习一下怎么获得整数的每一位就行了，这里因为是三位数直接算就行了

#include <iostream>
using namespace std;
int main() {
    int x;
    cin >> x;
    int res = x;
    res += x % 10 * 100;
    x /= 10;
    res += x % 10 * 10;
    x /= 10;
    res += x % 10;
    cout << res;
    return 0;
}

B 找AC

区间类的问题我们一般都可以使用前缀和优化，在这题中，我们以A为点，计算贡献值，判断一下后面那个是不是C，如果是贡献值就加一
最后求的时候要集体往左偏移一格

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
char s[N];
int pre[N];
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + (s[i] == 'A' && s[i + 1] == 'C');
    for (int i = 1; i <= q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", pre[r - 1] - pre[l - 1]);
    }
    return 0;
}

C 黑板公约数

首先我们是不可能算出应该换成哪个数的，我们可以分析一下，想替换掉一个数使得最大公约数最大，那么最大公约数也就是它前面的所有数与它后面所有数的最大公约数，所以说我们可以使用前缀和，预处理出最大公约数，然后枚举替换的数的位置取最大值就行了

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int pre[N], suf[N], a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = __gcd(pre[i - 1], a[i]);
    }
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        suf[i] = __gcd(suf[i + 1], a[i]);
        ans = max(ans, __gcd(pre[i - 1], suf[i + 1]));
    }
    cout << ans;
    return 0;
}

D 做任务

由于数据范围的限制，所以我们不能使用01背包，我们使用贪心的思想
我们枚举天数，然后将可以做的任务加入到优先队列中，每次取出可以做的任务的最大值，然后弹出，注意只执行一次，因为一天只能做一个任务
这样也解决了天数少工资还高的问题

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct node {
    int day, money;
} a[N];
priority_queue<int> pq;
bool cmp(node a, node b) { return a.day < b.day; }
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].day >> a[i].money;
    sort(a + 1, a + n + 1, cmp);
    int cur = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        while (a[cur].day <= i && cur <= n) {
            pq.push(a[cur].money);
            cur++;
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;
    return 0;
}

E 整理书架1.0

状态表示：1维
集合：前 \(i\) 本书最小的高度和
属性：高度和的最小值
状态计算枚举 \([1,i]\) 跟哪些书组成书架
注意要判断宽度是否够，我们可以使用前缀和来优化
状态转移方程 \(f[i]=min(f[i],f[j-1]+maxx)\) \(maxx\) 为高度的最大值
注意这里不是 \(f[j]\)，我们要的是 \(f[j-1]\) 前一个书架的高度最小值，累加起来便得到和
最后输出 \(f[n]\) 就搞定了

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2005;
int pre[N], h[N], w[N], f[N];
int main() {
    int n, l;
    cin >> n >> l;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> w[i];
        pre[i] = pre[i - 1] + w[i];
    }
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int maxx = h[i];  //最高的书
        for (int j = i; j >= 1; j--) {
            if (pre[i] - pre[j - 1] <= l) {
                maxx = max(maxx, h[j]);
                f[i] = min(f[i], f[j - 1] + maxx);
            }
        }
    }
    cout << f[n];
    return 0;
}

F 地牢

偏模板的一道题，洛谷上的难度仅为 普及- ，我们只需要抽象出另一维就行了，坐标可以看代码，不会的学一下二维走迷宫

#include <iostream>
#include <queue>
using namespace std;
const int N = 35;
int dx[] = { 0, 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, 0, -1, 1 };
int dz[] = { 1, -1, 0, 0, 0, 0 };
char mp[N][N][N];  //地图
bool st[N][N][N];  //记录障碍物和是否走过
struct node {
    int x, y, z;  //行列层
    int u;        //时间
};
queue<node> q;
int l, r, c;
//是否出界
bool isoutside(node a) {
    if (a.x > 0 && a.x <= r && a.y > 0 && a.y <= c && a.z > 0 && a.z <= l && !st[a.z][a.x][a.y])
        return false;
    return true;
}
void bfs() {
    while (!q.empty()) {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 6; i++) {
            node tmp;
            tmp.x = t.x + dx[i];
            tmp.y = t.y + dy[i];
            tmp.z = t.z + dz[i];
            tmp.u = t.u + 1;
            //终点
            if (mp[tmp.z][tmp.x][tmp.y] == 'E') {
                cout << tmp.u;
                exit(0);
            }
            if (isoutside(tmp))
                continue;
            st[tmp.z][tmp.x][tmp.y] = 1;
            q.push(tmp);
        }
    }
    cout << "Trapped!";
}
int main() {
    node start;  //起点
    cin >> l >> r >> c;
    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= r; j++) {
            scanf("%s", mp[i][j] + 1);
            for (int k = 1; k <= c; k++) {
                if (mp[i][j][k] == '#')
                    st[i][j][k] = 1;
                if (mp[i][j][k] == 'S') {
                    st[i][j][k] = 1;  //起点（走过了）
                    start.x = j;
                    start.y = k;
                    start.z = i;
                    start.u = 0;  //时间初始化
                }
            }
        }
    }
    q.push(start);
    bfs();
    return 0;
}