[心之碎片] - 20240807模拟赛

柿子饼同学

总结与反思

A - 只需要判断 可行性/可解性 要考虑前缀 min/max

B - 数学找规律先打表

C - 刷表法转化为填表法更好优化

D - 树剖是为了让我们 log 级别跳到顶, 并且维护一整条重链的信息, 轻孩子暴力存 (由一个一个跳祖先启发过来)

A - 牛宫
我们想知道 r 前面是否有小于她的, 这里只需要取前缀 min 就好

#include <bits/stdc++.h>

using namespace std;

const int N = 400 + 5;
const int inf = 114514;

int n, m, a[N][N], s[N][N], res, st[N], t, b[N];

inline int w(int u, int d, int i) { return s[d][i] - s[u - 1][i]; }

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

    freopen("rec.in", "r", stdin);
    freopen("rec.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }
    for (int p = 1; p <= n; p++) {
        for (int q = p; q <= n; q++) {
            for (int i = 1; i <= m; i++) b[i] = min(b[i - 1], w(p, q, i));
            t = 0;
            for (int i = 1; i <= m; i++)
                while (t < i && w(p, q, i) >= b[i - t - 1]) t++;
            res = max(res, (q - p + 1) * t);
        }
    }

    cout << res;

    return 0;
}

B - GCD
选出两个正整数a，b,使得通过辗转相除求最大公约数时，递归调用次数最多。
斐波那契数列最大公约数定理(这谁知道啊...打表吧)
Gcd(F(m),F(n))=F(gcd(m,n))
然后就是高精度每次加一下即可

#include <bits/stdc++.h>
#define LL long long
using namespace std;
char str[20005];
int m, b;
LL num[2505], A[2505], B[2505], C[2505], P = 1e18;
bool Cmp() {
    if (b != m)
        return b > m;
    for (int i = b - 1; i >= 0; i--) {
        if (C[i] != num[i])
            return C[i] > num[i];
    }
    return false;
}
void Print(LL s[]) {
    int k = b;
    while (s[k] == 0) k--;
    printf("%lld", s[k--]);
    while (k >= 0) printf("%018lld", s[k--]);
}
LL getnum(int L, int R) {
    LL res = 0;
    for (int i = L; i <= R; i++) res = (res << 3) + (res << 1) + (str[i] ^ 48);
    return res;
}
int main() {
    freopen("gcd.in", "r", stdin);
    freopen("gcd.out", "w", stdout);

    scanf("%s", str);
    int n = strlen(str);
    int p = n % 18;
    m = (n + 17) / 18;
    int k = m - 1;
    if (p != 0) {
        num[k] = getnum(0, p - 1);
        k--;
    }
    for (int i = p, j = 0; i < n; i += 18) {
        num[k] = getnum(i, i + 17);
        k--;
    }
    A[0] = 1, B[0] = 1, b = 1;
    while (1) {
        for (int i = 0; i < b; i++) {
            C[i] += A[i] + B[i];
            if (C[i] >= P) {
                C[i] -= P;
                C[i + 1]++;
            }
        }
        if (C[b] > 0)
            b++;
        if (Cmp())
            break;
        for (int i = 0; i < b; i++) {
            A[i] = B[i];
            B[i] = C[i];
            C[i] = 0;
        }
    }
    Print(A);
    putchar(' ');
    Print(B);
    return 0;
}

C - 排列逆序对
构造 1-n 的排列, 使得逆序对为 k, 求方案数
线段树优化超时了, 后来发现改成填表法之间用前缀和优化即可

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

const int N = 5005;
const int P = 1e9 + 7;

int f[N], s[N];
int n, m;

// i(前 i 个数), j(现在要填的数), k(逆序对数)
// f(i, k + i - j) += f(i - 1, k)
// 刷表法不好优化, 转换一下
// f(i, k) += f(i, k - i + j)
// 即 f(i, k) = f(i, x), x 属于 [k - i + 1, k]
// 于是乎前缀和优化

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

    freopen("reverse.in", "r", stdin);
    freopen("reverse.out", "w", stdout);

    cin >> n >> m;
    // 逆序对为 0 永远只有一种情况
    s[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            s[k] = (f[k] + s[k - 1]) % P;
        }
        for (int k = 0; k <= m; k++) {
            if (k - i >= 0)
                f[k] = (s[k] - s[k - i] + P) % P;
            else
                f[k] = s[k];
        }
    }

    cout << f[m];

    return 0;
}

D - [2010国家集训队]Crash的旅游计划

20% 的分数满足：n和指令的条数都不超过 1e3。
另 30% 的分数满足：n和指令的条数都不超过1e5 ，且输入的第 i 条道路，连接着 i 号地点和 i+1 号地点（详见样例2）。
另 20% 的分数满足：n和指令的条数都不超过1e5 ，除了 1 之外，每个点 i 与 (i + 1)/2 连边，即形成一棵完全二叉树。
另 10% 的分数满足：n和指令的条数都不超过1e5 ，且任何一个地点到 1 号地点需要通过的道路条数不超过 40。
100% 的分数满足：n和指令的条数都不超过1e5 。
80 分比较简单, 分别用暴力, 区间 max/min , 每个点向上跳, 同时维护这个点到除了这个子树的最长路径
100 分在向上跳的基础上, 直接维护整个重链的答案, 存上每个点出发去往一个轻孩子的最长路径, 向上就是 logn 的

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

typedef pair<int, int> pii;

const int N = 1e5 + 5;

// Global
vector<int> e[N];
int val[N], n;

// QTREE
int dfn[N], siz[N], hc[N];
int L[N], R[N], f[N], rdfn[N], tot;
// L, R -> u 所在的重链的两端点编号, L 即 top

void dfs0(int u, int pa) {
    f[u] = pa;
    siz[u] = 1;

    for (auto v : e[u]) {
        if (v == pa)
            continue;
        dfs0(v, u);

        siz[u] += siz[v];
        if (siz[hc[u]] < siz[v])
            hc[u] = v;
    }
}

void dfs1(int u, int t) {
    L[u] = t;
    dfn[u] = ++tot;
    rdfn[tot] = u;

    if (hc[u])
        dfs1(hc[u], t), R[u] = R[hc[u]];
    else
        R[u] = u;

    for (auto v : e[u]) {
        if (v == f[u] || v == hc[u])
            continue;
        dfs1(v, v);
    }
}

// s[u] 存和 u 相连的属于轻链的点, 第一个存该点所能拓展的最长路径, 第二个是她的编号
multiset<pii, greater<pii> > s[N];
// 如果这个点是重链的 top, rt[u] 就是对应线段树根
int rt[N];

struct Node {
    int sum, lmax, rmax;

    Node(){};
    // sum 这个链的路径和
    // lmax 这个链从上往下走, 再从轻孩子中下去的最长路径
    // rmax 这个链从下往上走的最长路径
    Node(int a, int b, int c) { sum = a, lmax = b, rmax = c; }

    // t 在下面
    Node operator+(const Node& t) {
        return Node(sum + t.sum, max(lmax, sum + t.lmax), max(t.rmax, t.sum + rmax));
    }
};

// SGT
struct SGT {
    int lc[N << 2], rc[N << 2], tot;
    Node t[N << 2];

    void Up(int u) { t[u] = t[lc[u]] + t[rc[u]]; }

    void Build(int& u, int l, int r) {
        if (!u)
            u = ++tot;
        if (l == r) {
            // 一个点的时候 s 就是答案
            t[u].sum = val[rdfn[l]];
            t[u].lmax = t[u].rmax = val[rdfn[l]] + s[rdfn[l]].begin()->first;
            return;
        }

        int mid = (l + r) >> 1;
        Build(lc[u], l, mid);
        Build(rc[u], mid + 1, r);
        Up(u);
    }

    void Modify(int u, int l, int r, int p) {
        if (l == r) {
            t[u].sum = val[rdfn[l]];
            t[u].lmax = t[u].rmax = val[rdfn[l]] + s[rdfn[l]].begin()->first;
            return;
        }

        int mid = (l + r) >> 1;
        if (p <= mid)
            Modify(lc[u], l, mid, p);
        if (p > mid)
            Modify(rc[u], mid + 1, r, p);
        Up(u);
    }

    Node Query(int u, int l, int r, int ql, int qr) {
        if (qr < ql)
            return Node(0, 0, 0);
        if (ql <= l && r <= qr) {
            return t[u];
        }

        int mid = (l + r) >> 1;
        if (qr <= mid)
            return Query(lc[u], l, mid, ql, qr);
        if (ql > mid)
            return Query(rc[u], mid + 1, r, ql, qr);
        return (Query(lc[u], l, mid, ql, qr) + Query(rc[u], mid + 1, r, ql, qr));
    }
} sgt;

void Init(int u) {
    s[u].emplace(0, u);

    for (auto v : e[u]) {
        if (v == f[u] || v == hc[u])
            continue;
        // 存的是轻孩子
        Init(v);
        s[u].emplace(sgt.t[rt[v]].lmax, v);
    }

    if (hc[u])
        Init(hc[u]);
    else
        sgt.Build(rt[L[u]], dfn[L[u]], dfn[u]);
}

int Query(int u) {
    int res = s[u].begin()->first + val[u];
    int sum = val[u], v;
    Node temp;

    while (u) {
        // 从上往下走
        temp = sgt.Query(rt[L[u]], dfn[L[u]], dfn[R[u]], dfn[u] + 1, dfn[R[u]]);
        res = max(res, temp.lmax + sum);
        // 从下往上走
        temp = sgt.Query(rt[L[u]], dfn[L[u]], dfn[R[u]], dfn[L[u]], dfn[u] - 1);
        res = max(res, temp.rmax + sum);

        sum += temp.sum;

        v = f[L[u]];
        if (!v)
            break;

        // 这样写的原因是第一个点取不到
        sum += val[v];
        auto it = s[v].begin();
        if (it->second == L[u])
            it++;

        res = max(res, it->first + sum);
        u = v;
    }

    return res;
}

void Modify(int u, int x) {
    val[u] = x;
    int v, last;

    // 一个点的更新会带动它上面的重链底点更新
    while (u) {
        v = L[u];
        last = sgt.t[rt[v]].lmax;
        sgt.Modify(rt[v], dfn[L[u]], dfn[R[u]], dfn[u]);

        // 无法造成影响就退
        if (sgt.t[rt[v]].lmax == last || v == 1) {
            break;
        }

        s[f[v]].erase(make_pair(last, v));
        s[f[v]].emplace(sgt.t[rt[v]].lmax, v);
        u = f[v];
    }
}

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

    freopen("lycoris.in", "r", stdin);
    freopen("lycoris.out", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }

    dfs0(1, 0);
    dfs1(1, 1);
    Init(1);

    string op;
    int x, y;

    while (1) {
        cin >> op;
        if (op[0] == 'D') {
            break;
        } else if (op[0] == 'Q') {
            cin >> x;
            cout << Query(x) << '\n';
        } else {
            cin >> x >> y;
            Modify(x, y);
        }
    }

    return 0;
}

很cool的阳

cc885544