2023.8.19 考试

· · 个人记录

每次考试都考得贼拉胯，2023.8.23 考得更烂，直接倒数，每次都没那红烧肉高，我也是醉了。

update 2023/8/24：从明天开始，加训。

考得稀烂。还没小学生考得好。膜拜 ltx,lwz!

T1: 可持久化变量

\rm 10pts

直接暴力。

\rm 100pts

维护变量的历史版本，每次操作后用数组记录当前变量的值，回溯状态时直接调用数组。复杂度 O(q)。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 5;
int n, a[N], now;

signed main() {
    // freopen("persistent.in", "r", stdin);
    // freopen("persistent.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        int x;
        cin >> s >> x;
        if (s == "ADD") {
            now += x;
            a[i] = now;
        }
        if (s == "SUB") {
            now -= x;
            a[i] = now;
        }
        if (s == "SET") {
            now = x;
            a[i] = now;
        }
        if (s == "BACK") {
            now = a[i - x - 1];
            a[i] = now;
        }
        cout << now << ' ';
    }
}

T2: 填数游戏

\rm 40pts

根据排序不等式，可以想到直接排序来选的思路。但其实是错的，因为值域会有负数情况。

\rm 100pts

所以我们把负数放一块，正数放一块。最负的数和最负的数相乘，最正的数和最正的数相乘。

当然还剩下一些数，一个数组中必然全是非负数，另一个数组中必然全是非正数。这个时候就可以用排序不等式了。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2e5 + 5;
int n, m, a[N], b[N];
int a1[N], a2[N], a3[N], b1[N], b2[N], b3[N], a1l, a2l, b1l, b2l, a3l, b3l; 
int res;
map<int, int> vis1, vis2;
int ww[N], ww2[N], wl, wwl;

signed main() {
    // freopen("fill.in", "r", stdin);
    // freopen("fill.out", "w", stdout); 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], vis1[a[i]]++;
    for (int i = 1; i <= m; i++) cin >> b[i], vis2[b[i]]++;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) a1[++a1l] = a[i];
        if (a[i] < 0) a2[++a2l] = a[i];
        if (a[i] == 0) a3[++a3l] = a[i]; 
    }
    for (int i = 1; i <= m; i++) {
        if (b[i] > 0) b1[++b1l] = b[i];
        if (b[i] < 0) b2[++b2l] = b[i];
        if (b[i] == 0) b3[++b3l] = b[i]; 
    }
    if (a1l > b1l) {
        for (int i = 1; i <= b1l; i++) {
            res += a1[a1l - (b1l - i + 1) + 1] * b1[i];
            vis1[a1[a1l - (b1l - i + 1) + 1]]--;
            vis2[b1[i]]--;
        } 
    }
    if (a1l <= b1l) {
        for (int i = 1; i <= a1l; i++) {
            res += a1[i] * b1[b1l - (a1l - i + 1) + 1];
            vis1[a1[i]]--;vis2[b1[b1l - (a1l - i + 1) + 1]]--;
        }
    }
    if (a2l > b2l) {
        for (int i = 1; i <= b2l; i++) {
            res += a2[i] * b2[i];
            vis1[a2[i]]--,vis2[b2[i]]--;
        } 
    }
    if (a2l <= b2l) {
        for (int i = 1; i <= a2l; i++) {
            res += a2[i] * b2[i];
            vis1[a2[i]]--, vis2[b2[i]]--;
        }
    }
    for (auto i = vis1.begin(); i != vis1.end(); i++) {
        int t = i -> second;
        while (t) {
            ww[++wl]= i->first;
            t--;
        }
    }
    for (auto i = vis2.begin(); i != vis2.end(); i++) {
        int t = i -> second;
        while (t) {
            ww2[++wwl]= i->first;
            t--;
        }
    }
    for (int i = 1; i <= wl; i++) {
        res += ww[i] * ww2[wwl-(wl-i+1)+1];
    }
    cout << res << endl;
}

T3: 数数师

\rm 20pts

暴力 dfs，甚至你算最大子段和都可以三方来算。

\rm 50pts

可以计算答案 \leq k 的方案数减去答案 \leq k-1 的方案数。

使用动态规划解决，设 f(i,j) 为长为 i，最大后缀和为 j 的方案数。那么转移可以通过枚举下一个数是什么解决。即从 -m 到 m 枚举下一个数 x，若要求的是最大子段和 \leq k 的方案数，那么如果 j+x\leq k，那么 f(i,j) 可以转移到 f(i+1,\max(j+x,0))。

\rm 100pts

容易发现这个转移可以使用前缀和优化将复杂度优化成 O(nk)。

#include <bits/stdc++.h>
using namespace std;

const int N = 2005, mod = 998244353;
int n, m, k, dp1[N], dp2[N];

int get(int x) {
    memset(dp1, 0, sizeof dp1);
    dp1[0] = 1;
    int t = max(0, x);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= t; j++) dp2[j] = 0;
        for (int j = 1; j <= t; j++) dp1[j] = (dp1[j] + dp1[j - 1]) % mod;
        for (int j = -m; j <= x; j++) {
            if (j > m) dp2[max(j, 0)] = (dp2[max(j, 0)] + dp1[min(j + m, t)] - dp1[j - m - 1] + mod) % mod;
            else dp2[max(j, 0)] = (dp2[max(j, 0)] + dp1[min(j + m, t)] ) % mod;
        }
        for (int j = 0; j <= t; j++) dp1[j] = dp2[j];
    }
    int res = 0;
    for (int i = 0; i <= 2000; i++) res = (res + dp1[i]) % mod;
    return res;
}

int main() {
    cin >> n >> m >> k;
    cout << (get(k) - get(k - 1) + mod) % mod << endl;
}

T4：Modulus

\rm 50pts

范围 n\leq 10^5，线段树直接维护。

\rm 100pts

考虑他取模很有规律的样子？

于是我们打出 n=1000 的所有 i(1\leq i \leq 1000) 求出 n\%i 来找规律。

找规律会发现这 1000 个数会分成一些段，每个段居然是等差数列！但是我们还需要求出每个段的区间范围。

找规律会发现区间范围为 [\lfloor \dfrac{1000}{i+1}\rfloor+1 , \lfloor\dfrac{1000}{i} \rfloor]。实际上这是数论分块！

然后就线段树加二分乱维护就行。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 5; 
int n, m, l[N], r[N], maxn[N], len;

struct edge {
    int l, r, Max;
}tree[N * 4];

void push_up(int p) {
    tree[p].Max = max(tree[p * 2].Max, tree[p *2 + 1].Max);
}

void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        tree[p].Max = maxn[l];
        return;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    build(p * 2,  l, mid);
    build(p * 2 + 1, mid + 1, r);
    push_up(p);
} 

int query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) return tree[p].Max;
    int res = 0, mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) res = max(res, query(p * 2, l, r));
    if (r > mid) res = max(res, query(p * 2 + 1, l, r));
    return res;
}

signed main() {
    cin >> n >> m;
    int id =0 ;
    for (int i = 1; i <= n; i++) {
        int t1 = n / (i + 1) + 1, t2 = n / i;
        if (t1 > t2) break;
        l[++len] = t1, r[len] = t2;
//      cout << min(t1, t2) << ' ' << t2 << endl;
    }
    for (int i = l[len] - 1; i >= 1; i--) l[++len] = i, r[len] = i;
    for (int i = 1; i <= len; i++) maxn[i] = n % r[i] + (r[i] - l[i]) * i;
    reverse(l + 1, l + len + 1);
    reverse(r + 1, r + len + 1);
    reverse(maxn + 1, maxn + len + 1);
    build(1, 1, len);
    while (m--) {
        int L, R;
        cin >> L >> R;
        int LL = 1, RR = len;
        while (LL < RR) {
            int mid = (LL + RR + 1) >> 1;
            if (l[mid] <= L) LL = mid;
            else RR = mid - 1; 
        }
        int t1 = LL;
        LL = 1, RR = len;
        while (LL < RR) {
            int mid = (LL + RR + 1) >> 1;
            if (l[mid] <= R) LL = mid;
            else RR = mid - 1; 
        }
        int t2 = LL;
//      cout << t1 << ' ' << t2 << endl;
        if (t1 == t2) cout << n % L << endl;
        else if (t1 + 1 == t2) cout << max(n % L, n % l[t2]) << endl;
        else cout << max(n % L, max(query(1, t1 + 1, t2 - 1), n % l[t2])) << endl;
    }
}