SMU Autumn 2023 Round 3(Div.1)

A. Find The Array

要满足“b数组内任意一个元素满足可以被数组两边的元素整除”这个条件，我们很容易想到1是万能的，所以我们只需要把a数组某些元素改成1就可以了
条件二要满足a，b方差够小，那其实我们只用把a数组内奇数位，偶数位分别相加对比，如果偶数位和大，就把奇数位改成1，如果奇数大则相反

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        i64 sum1 = 0, sum2 = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (i & 1)sum1 += a[i];
            else sum2 += a[i];
        }

        if (sum1 < sum2) {
            for (int i = 1; i <= n; i += 2)
                a[i] = 1;
        } else {
            for (int i = 2; i <= n; i += 2)
                a[i] = 1;
        }

        for (int i = 1; i <= n; i++)
            cout << a[i] << " \n"[i == n];

    }
    return 0;
}

B. Busy Robot

题意是机器人初始在一数轴上的原点某时刻接受命令并朝命令方向前进每秒前进$1$距离在未到达当前命令的终点时忽略当前时刻的其他命令若机器人在 $[ t_i , t_{i + 1} ]$时间内移动到 $x_i$ 位置视为完成一次指令 (被忽略的命令可能会成功执行),给出一系列的指令问机器人能完成多少次

记录每次指令的起点 $st$ 和终点$ed$ 下一次停止的时间 $next$ 上一次接收到可执行命令的时刻 $last$,遍历每个指令如果当前指令的时刻大于等于 $next$说明可以执行当前指令更新 $next,st,ed,last$,否则判断机器人是否能在 $[ t_i , t_{ i + 1} ]$时间内移动到 $x_i$ 位置具体判断依据为在 $t_i$ 时刻到 $t_{i+1}$时刻机器人是否经过 $x_i$

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<i64> tim(n + 1), pos(n + 1);
        for (int i = 0; i < n; ++i)
            cin >> tim[i] >> pos[i];
        tim[n] = 1e10;

        i64 next = 0, st = 0, ed = 0, last = 0, res = 0;

        for (int i = 0; i < n; ++i) {
            if (tim[i] >= next) {

                next = tim[i] + abs(pos[i] - ed);
                st = ed, ed = pos[i];
                last = i;
                if (next <= tim[i + 1])
                    res++;
            }
            else {
                if (st >= ed) {
                    int y = st - (tim[i] - tim[last]);
                    int x = max(ed, st - (tim[i + 1] - tim[last]));
                    if (pos[i] >= x && pos[i] <= y)res++;
                }
                else {
                    int x = st + (tim[i] - tim[last]);
                    int y = min(ed, st + tim[i + 1] - tim[last]);
                    if (pos[i] >= x && pos[i] <= y)res++;
                }
            }
        }
        cout << res << endl;

    }
    return 0;
}

C. Building a Fence

题意是用 $n$ 个宽度为 $1$ 高度为 $k$ 的木板构建一段栅栏,第 $i$ 个木板下面的地面高度等于 $h_i$,第一个和最后一个木板必须在地面上,其他的木板底端可能位于地面或者不高于地面 $k-1$的高度上,相邻的两个木板必须有公共边,也即有重合的部分,问有没有可能建造一个符合所有规则的围栏

设 $l,r$ 分别为当前栅栏下端的最小高度和最大高度,因为每段栅栏高度都为 $k$,可知下一段栅栏底边高度的范围为 $[ l − k + 1 , r + k − 1 ] $,又因为栅栏底边最低要在地上,即 $a[i]$ 最高只能达到 $a[i] + k - 1$, 所以我们可维护$l = max(l - k + 1, a[i])$,$r = min(r + k - 1, a[i] + k - 1)$,如果 $l \leq r$ 说明可行,否则不可行,最后特判一下最后一块栅栏(只能建造在地上),即判断一下 $a[n]$ 是否在 $[ l , r ]$ 的范围内

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i)
            cin >> a[i];

        bool flag = true;
        int l = a[1], r = a[1];

        for (int i = 2; i <= n; ++i) {
            l = max(l - k + 1, a[i]);
            r = min(r + k - 1, a[i] + k - 1);
            if (l > r) {
                flag = false;
                break;
            }
        }
        if (a[n] < l || a[n] > r)
            flag = false;

        cout << (flag ? "YES\n" : "NO\n");

    }
    return 0;
}

D. Program

只要求出每个前缀和每个后缀和变换过程能得到的最大值和最小值，就可以求出总体变换过程中的上界下界，然后就得出变换数字的个数。

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<i64> pre(n + 2), pre_mi(n + 2), pre_mx(n + 2);
        vector<i64> suf(n + 2), suf_mi(n + 2), suf_mx(n + 2);
        string s;
        cin >> s;
        s = " " + s;

        for (int i = 1; i <= n; i++) {
            int now = 1;
            if (s[i] == '-') now = -1;
            pre[i] = pre[i - 1] + now;
            pre_mi[i] = min(pre_mi[i - 1], pre[i]);
            pre_mx[i] = max(pre_mx[i - 1], pre[i]);
        }
        suf[n + 1] = suf_mi[n + 1] = suf_mx[n + 1] = 0;
        for (int i = n; i >= 1; i--) {
            int now = 1;
            if (s[i] == '-') now = -1;
            suf[i] = suf[i + 1] + now;
            suf_mx[i] = max(0ll, suf_mx[i + 1] + now);
            suf_mi[i] = min(0ll, suf_mi[i + 1] + now);
        }

        for (int i = 1; i <= m; i++) {
            int l, r;
            cin >> l >> r;
            i64 mx = 0, mi = 0;
            mx = max(mx, pre_mx[l - 1]);
            mi = min(mi, pre_mi[l - 1]);
            int res = pre[l - 1];
            mx = max(mx, suf_mx[r + 1] + res);
            mi = min(mi, suf_mi[r + 1] + res);
            cout << mx - mi + 1 << '\n';
        }

    }
    return 0;
}