投稿
  1. 云图网首页
  2. 技术专区
  3. 编程笔记

CF Round Hello 2022 部分题解

• 编程笔记 • 阅读 40


来补个档。

CF1621G Weighted Increasing Subsequences

先离散化。对每个上升子序列计算权值是困难的，我们考虑每个位置对答案的贡献。

即我们想要知道对于每个 /(a_p/)，/(i_k/) 最远能到哪里，使得存在一个 /(x /in (i_k, n]/) 满足 /(a_x > a_i/)。容易发现，若设 /(r_p/) 为最右端的满足 /(a_{r_p} > a_p/) 的下标，那么 /(i_k < r_p/)。

于是对于每一个 /(p/) 我们需要计算 “经过 /(p/)，且最后一个元素在 /(r_p/) 之前的” 上升子序列个数，这可以容斥成 “经过 /(p/)，且最后一个元素在 /(r_p/) 或 /(r_p/) 之后” 的上升子序列个数。但由于 /(r_p/) 的定义，对于任意 /(i /in (r_p, n]/) 都有 /(a_i /leq a_p/)，这意味着这些位置不可能成为上升子序列的结尾元素，于是我们只需要计算 “经过 /(p/)，且最后一个元素位置为 /(r_p/)” 的上升子序列个数。

接下来考虑如何计数。显然考虑把子序列拆成 /(p/) 之前和 /(p/) 到 /(r_p/) 两部分，前面是好算的。/(p/) 之后的部分我们考虑倒着处理，由于 /(r_p/) 是最靠右的满足条件的下标，所以任意一个从 /(p/) 开始的子序列结尾一定不超过 /(r_p/)，只需要维护 “从 /(p/) 开始以最远位置结尾” 的子序列的方案数即可。时间复杂度 /(O(n /log n)/)。

Code 
/*
最黯淡的一个　梦最为炽热
万千孤单焰火　让这虚构灵魂鲜活
至少在这一刻　热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v, n) memset(x, v, sizeof(int) * (n))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;

inline int read() {
	int x = 0, w = 1;char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}

inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

const int MN = 2e5 + 5;
const int Mod = 1e9 + 7;

inline int qPow(int a, int b = Mod - 2, int ret = 1) {
    while (b) {
        if (b & 1) ret = ret * a % Mod;
        a = a * a % Mod, b >>= 1;
    }
    return ret;
}

// #define dbg

int N, M, a[MN], pre[MN], suf[MN], ans;
vector <int> vr;

inline void add(int &x, int y) {
    x += y; if (x >= Mod) x -= Mod;
}
inline void dec(int &x, int y) {
    x -= y; if (x < 0) x += Mod;
}

int c[MN], mx[MN], mxv[MN];
inline void Add1(int x, int v) { for (; x <= N; x += x & -x) add(c[x], v); }
inline int Qry1(int x) { int res = 0; for(; x; x -= x & -x) add(res, c[x]); return res; }
inline void Add2(int x, pii v) {
    for (; x; x -= x & -x) {
        if (mx[x] < v.fi) mx[x] = v.fi, mxv[x] = 0;
        if (mx[x] == v.fi) add(mxv[x], v.se);
    }
}
inline pii Qry2(int x) {
    int Mx = 0, Mxv = 0;
    for (; x <= N; x += x & -x) {
        if (Mx < mx[x]) Mx = mx[x], Mxv = 0;
        if (Mx == mx[x]) add(Mxv, mxv[x]);
    }
    return mp(Mx, Mxv);
}
inline void Work() {
    N = read();
    vr.clear(), ans = 0;
    for (int i = 1; i <= N; i++) a[i] = read(), vr.pb(a[i]);
    for (int i = 1; i <= N; i++) c[i] = mx[i] = mxv[i] = 0;
    sort(vr.begin(), vr.end());
    vr.erase(unique(vr.begin(), vr.end()), vr.end());
    for (int i = 1; i <= N; i++) a[i] = lob(vr.begin(), vr.end(), a[i]) - vr.begin() + 1;
    for (int i = 1; i <= N; i++) Add1(a[i], pre[i] = Qry1(a[i] - 1) + 1);
    for (int i = 1; i <= N; i++) c[i] = 0;
    for (int i = N; i >= 1; i--) {
        Add1(N - a[i] + 1, suf[i] = Qry1(N - a[i]) + 1);
        pii cur = Qry2(a[i] + 1);
        if (!cur.se) cur = mp(i, 1);
        dec(suf[i], cur.se), Add2(a[i], cur);
    }
    for (int i = 1; i <= N; i++) add(ans, pre[i] * suf[i] % Mod);
    printf("%lld/n", ans);
}

signed main(void) {
    int T = read();
    while (T--) Work();
    return 0;
}

CF1621H Trains and Airplanes

注意到从任意一点 /(x/) 开始，其在每个区域被查的次数是固定的，设为 /(s_{x,i}/)，那么 /(f(v)/) 可以写成：

/[f(v) = /sum_{i /neq z_v} /min(fine_{v,i} /times s_{v,i},pass_{v,i})
/]

但是询问很奇怪，直接写成上式并不好处理询问。考虑在同一个询问中的所有点它们的 /(s_{v,i}/)，对于这些点来说，往上走时经过的所有区域在时间轴上都形成一段区间，而 /(s_{v,i}/) 计算的就是在这段区间中 /(T/) 的倍数点出现的次数。考虑把这些线段在 /(/mathrm{mod} / T/) 意义下处理，根据每个点的深度不同，时间轴和线段的位置也不相同。设在询问中 /(s_{v,i}/) 的最小值为 /(mn_{i}/)，容易发现 /(s_{v,i}/) 的值只可能为 /(mn_i/) 或 /(mn_i + 1/)，并且当线段在 /(/mathrm{mod} / T/) 意义下左右端点相对位置不变时取 /(mn_i/)，否则取 /(mn_i + 1/)。

也就是说，在同一次询问中，不同的 /(s_{v,i}/) 至多只有 /(O(2^k)/) 种，但还是太多了。更进一步地，考虑一个类似扫描线的过程，不难发现线段的移动是连续的，同样在 /(/mathrm{mod} / T/) 意义考虑，取 /(mn_i/) 的位置恰是一个区间！也就是说，这 /(k/) 个区域把 /(/mathrm{mod} / T/) 的环分成了 /(O(k)/) 个部分，这样在同一次询问中只会有 /(O(k)/) 种不同的 /(s_{v,i}/)。

接下来只需要模拟这个过程就行了：对每个位置预处理出 /(s_{v,i}/)，然后对每个位置处理出一个二进制状态 /(/mathrm{mask}/) 表示每个区域是取 /(mn_i/) 还是取 /(mn_{i+1}/)，这样的状态至多只有 /(O(k)/) 个。然后从下往上合并出每次询问需要的状态，处理询问就很容易了。时间复杂度 /(O(nk /log k + qk^2)/)，听说能更快，但反正过了就不管了。

Code 
/*
最黯淡的一个　梦最为炽热
万千孤单焰火　让这虚构灵魂鲜活
至少在这一刻　热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;

inline int read() {
	int x = 0, w = 1;char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}

inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

const int MN = 2e5 + 5;
const int MK = 30;
const int Inf = 2e18;
const int Mod = 1e9 + 7;

inline int qPow(int a, int b = Mod - 2, int ret = 1) {
    while (b) {
        if (b & 1) ret = ret * a % Mod;
        a = a * a % Mod, b >>= 1;
    }
    return ret;
}

// #define dbg

int N, T, K, Q, zone[MN], pass[MN], fine[MN]; char s[MN];
int dis[MN], fa[MN], ord[MN], dfc, up[MN], lim[MN], coef[MN][MK], mask[MN];
vector <pii> G[MN];
vector <int> vr[MN];

inline void DFS(int u) {
    ord[++dfc] = u;
    for (auto [v, w] : G[u]) {
        if (v == fa[u]) continue;
        fa[v] = u;
        dis[v] = dis[u] + w;
        DFS(v);
    }
}
inline void Work() {
    N = read();
    for (int i = 1; i < N; i++) {
        int u = read(), v = read(), w = read();
        G[u].pb(mp(v, w));
        G[v].pb(mp(u, w));
    }
    fa[1] = -1;
    DFS(1);
    K = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= N; i++) zone[i] = s[i] - 'A' + 1;
    for (int i = 1; i <= K; i++) pass[i] = read();
    for (int i = 1; i <= K; i++) fine[i] = read();
    T = read();
    mem(up, -1);
    for (int j = 1; j <= dfc; j++) {
        int i = ord[j];
        if (fa[i] != -1) {
            if (zone[i] != zone[fa[i]]) {
                up[i] = fa[i];
            } else {
                up[i] = up[fa[i]];
            }
        } else {
            up[i] = -1;
        }
        int p = up[i];
        while (p != -1) {
            int nxt = up[p];
            int L = dis[i] - dis[p];
            int R = (nxt == -1 ? dis[i] : dis[i] - dis[nxt]);
            int c = (R + T - 1) / T - (L + T - 1) / T;
            int mx = (R - L + T - 1) / T;
            coef[i][zone[p]] += mx;
            if (c < mx) {
                mask[i] |= (1 << zone[p]);
            }
            p = nxt;
        }
    }
    for (int j = dfc; j >= 1; j--) {
        int i = ord[j];
        vr[i].pb(mask[i]);
        sort(vr[i].begin(), vr[i].end());
        vr[i].resize(unique(vr[i].begin(), vr[i].end()) - vr[i].begin());
        if (fa[i] != -1 && zone[i] == zone[fa[i]]) {
            vr[fa[i]].insert(vr[fa[i]].end(), vr[i].begin(), vr[i].end());
        }
    }
    for (int i = 1; i <= K; i++) lim[i] = pass[i] / fine[i];
    Q = read();
    while (Q--) {
        int op = read();
        if (op == 1 || op == 2) {
            string ch;
            cin >> ch;
            int id = ch[0] - 'A' + 1;
            (op == 1 ? pass[id] : fine[id]) = read();
            lim[id] = pass[id] / fine[id];
        } else {
            int u = read();
            int ans = Inf;
            for (int ms : vr[u]) {
                int cur = 0;
                for (int j = 1; j <= K; j++) {
                    int c = coef[u][j];
                    if (ms & (1 << j)) c--;
                    if (c <= lim[j]) {
                        cur += c * fine[j];
                    } else {
                        cur += pass[j];
                    }
                }
                ans = min(ans, cur);
            }
            printf("%lld/n", ans);
        }
    }
}

signed main(void) {
    int T = 1;
    while (T--) Work();
    return 0;
}

原创文章，作者：端木书台，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/278510.html

赞 (0)
0 0
上一篇 2022年8月2日 20:55
下一篇 2022年8月2日 20:57

相关推荐

发表回复

登录后才能评论