柿子饼同学 发表于 2024-8-10 13:59:15

[心之碎片] - 20240807模拟赛

本帖最后由 柿子饼同学 于 2024-8-10 13:59 编辑

总结与反思{:10_266:}{:10_250:}{:10_245:}
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, s, res, st, t, b;

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

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;
            s = s + s - s + a;
      }
    }
    for (int p = 1; p <= n; p++) {
      for (int q = p; q <= n; q++) {
            for (int i = 1; i <= m; i++) b = min(b, w(p, q, i));
            t = 0;
            for (int i = 1; i <= m; i++)
                while (t < i && w(p, q, i) >= b) 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;
int m, b;
LL num, A, B, C, P = 1e18;
bool Cmp() {
    if (b != m)
      return b > m;
    for (int i = b - 1; i >= 0; i--) {
      if (C != num)
            return C > num;
    }
    return false;
}
void Print(LL s[]) {
    int k = b;
    while (s == 0) k--;
    printf("%lld", s);
    while (k >= 0) printf("%018lld", s);
}
LL getnum(int L, int R) {
    LL res = 0;
    for (int i = L; i <= R; i++) res = (res << 3) + (res << 1) + (str ^ 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 = getnum(0, p - 1);
      k--;
    }
    for (int i = p, j = 0; i < n; i += 18) {
      num = getnum(i, i + 17);
      k--;
    }
    A = 1, B = 1, b = 1;
    while (1) {
      for (int i = 0; i < b; i++) {
            C += A + B;
            if (C >= P) {
                C -= P;
                C++;
            }
      }
      if (C > 0)
            b++;
      if (Cmp())
            break;
      for (int i = 0; i < b; i++) {
            A = B;
            B = C;
            C = 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, s;
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 属于
// 于是乎前缀和优化

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 = 1;

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

    cout << f;

    return 0;
}
D - 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;
int val, n;

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

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

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

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

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

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

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

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

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, rc, tot;
    Node t;

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

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

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

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

      int mid = (l + r) >> 1;
      if (p <= mid)
            Modify(lc, l, mid, p);
      if (p > mid)
            Modify(rc, 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;
      }

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

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

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

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

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

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

      sum += temp.sum;

      v = f];
      if (!v)
            break;

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

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

    return res;
}

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

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

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

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

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;
    }
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      e.emplace_back(v);
      e.emplace_back(u);
    }

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

    string op;
    int x, y;

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

    return 0;
}

很cool的阳 发表于 2024-8-18 10:00:57

{:7_113:}

cc885544 发表于 2024-10-7 22:56:41

{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}

额滴神 发表于 2024-11-6 18:49:15

学习中！！！
页: [1]
查看完整版本: [心之碎片] - 20240807模拟赛