首页 > 其他分享 >2024CCPC山东省赛补题记录

2024CCPC山东省赛补题记录

时间：2024-10-07 20:46:06浏览次数：11  
标签：int long ncnt seg maxn 补题 2024CCPC 山东省 define

前言

今天和队友VP了24CCPC山东省赛，最后9题，但是赛中7题左右我就隐身了，赛后看题解发现E题不难，赛时过的人太少导致有点畏手畏脚，看到题解一下就懂了，几分钟写好。这里主要补一下E和L的题解，这场比赛学到了维护区间信息，可以考虑把区间挂在线段树节点上，以及动态维护树直径的典。

E 传感器 sensors

https://codeforces.com/gym/105385/problem/E

题意

给定 \(n\) 个球，初始都是红色，有 \(m\) 个区间。一共 \(n\) 轮，每轮将其中一个红球变蓝，强制在线维护恰好有一个红球的区间的编号平方和。

分析

一开始和队友都是读错题，以为小球是从蓝变红，这样就太简单了，因为每个区间只会恰好被操作2次后就剃掉，所以直接分块啥的乱搞就行。后来发现是从都是红色慢慢减少，这样每次小球变化，都得操作很多区间，但是很多操作是没必要的，只需要在意可能导致区间和变1的那些操作。
然后一个很巧妙的操作就是，类似线段树分治思想，把 \(m\) 个区间挂在线段树的 \(mlogn\) 个节点里，那么一个操作有可能使某个区间和变1，仅当某个线段树节点的区间和变成1或0.而这样的变化只会有2次，总共又只有 \(mlogn\) 的关键节点，所以就可以标记那些关键节点，线段树每个节点开vector，里面存挂在这个节点的区间编号。之后若干次单点修改，push_up时候判断一下限度桉树节点的区间和，如果变为1或0，就遍历一下对应vector里面的所有编号，里面对应区间的权值和要么是减去 \(r - l + 1 - 1\)要么减一，如果区间权值和变为1或0，就对应维护一下答案的编号平方和，代码很好写。

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 998244353;
int val[maxn];
ll ans;
struct SegmentTree {
    struct Node {
        int sum;
        vector<int> vec;
    };
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
    vector<Node> t;
    SegmentTree (int n) {t.resize(n << 2);}
    void push_up(int rt) {t[rt].sum = t[ls].sum + t[rs].sum;}
    void build(int rt, int l, int r) {
        t[rt].vec.clear();
        if (l == r) {t[rt].sum = 1;return;}
        build(ls, l, mid), build(rs, mid + 1, r);
        push_up(rt);
    }
    void modify(int rt, int l, int r, int p, int q, int id) {
        if (p > r || q < l) return;
        if (p <= l && r <= q) {
            t[rt].vec.push_back(id);
            return;
        }
        modify(ls, l, mid, p, q, id);
        modify(rs, mid + 1, r, p, q, id);
    }
    void modify(int rt, int l, int r, int pos) {
        if (l == r) {
            t[rt].sum = 0;
            for (auto id : t[rt].vec) {
                val[id]--;
                if (val[id] == 1) ans += id * id;
                else if (val[id] == 0) ans -= id * id;
            }
            return;
        }
        if (pos <= mid) modify(ls, l, mid, pos);
        else modify(rs, mid + 1, r, pos);
        push_up(rt);
        if (t[rt].sum == 1) {
            for (auto id : t[rt].vec) {
                val[id] -= (r - l + 1) - 1;
                if (val[id] == 1) ans += id * id;
                else if (val[id] == 0) ans -= id * id;
            }
        } else if (t[rt].sum == 0) {
            for (auto id : t[rt].vec) {
                val[id]--;
                if (val[id] == 1) ans += id * id;
                else if (val[id] == 0) ans -= id * id;
            }
        }
    }
};
void solve() {
    int n, m; cin >> n >> m;
    SegmentTree seg(n);
    seg.build(1, 0, n - 1);
    for (int i = 1; i <= m; i++) {
        int l, r; cin >> l >> r;
        val[i] = r - l + 1;
        if (val[i] == 1) ans += i * i;
        seg.modify(1, 0, n - 1, l, r, i);
    }
    cout << ans << " ";
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        int pos = (x + ans) % n;
        seg.modify(1, 0, n - 1, pos);
        cout << ans << " \n"[i == n];
    }
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

L Intersection of Paths

https://codeforces.com/gym/105385/problem/L

题意

给定一棵树，每条边有边权，多次询问，每次询问临时改变一条边的边权，并给出参数 \(k\)， 要求在树上选 \(k\) 条端点各不相同的路径，使得所有路径的交集部分的边权和最大。

分析

注意到对于一次询问的特定的 \(k\)， 能选择的边，得满足它两侧连通块的点数都得大等于 \(k\), 才能选对应路径，包括上这边。那么把所有的合法边连起来，会形成一棵树。容易发现最终路径的交集肯定只能是一条链，所以问题等价于去找这棵树的最大边权和的链，也就是树的直径。然后关注到一个关键性质，这棵树的大小会随着 \(k\) 的变化单调变化，所以可以离线下来，将询问排序，对询问的 \(k\) 从小到大处理，等价于初始一棵完整的树，不断把边的 \(k\) 较小的删掉，然后维护树的直径，可以dfs把边的k也预处理出来，对边排序，然后用个指针维护，每次问到一个询问，判断指针处的边的 \(k\) 是否满足条件，不满足则删掉这条边，指针右移。

动态维护树直径CF1192B

然后就变成这个典题(也是看到题解说了才知道有这个典)，直接看题解，大概就是利用了欧拉序性质，在边权都正的前提下，树的直径等价于 \(max(dep[l] + dep[r] - 2 \times dep[a]), l \leq a \leq r\) ，然后用线段树维护这个东西，合并时候按照区间最大最小值，以及 \(dep[l , r] - 2 \times dep[a]\) 的最大值来合并，整棵树的直径就是线段树1号节点的对应答案。然后边权的变化，就是欧拉序，让儿子的子树里深度全部加上一个变化量，即可。

1192B代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 998244353;
vector<pii> G[maxn];
int dfn[maxn], ncnt, dep[maxn], L[maxn], R[maxn], fa[maxn];
tii edge[maxn];
void dfs(int u, int f) {
    dfn[++ncnt] = u;
    L[u] = R[u] = ncnt;
    fa[u] = f;
    for (auto [v, w] : G[u]) {
        if (v == f) continue;
        dep[v] = dep[u] + w;
        dfs(v, u);
        dfn[++ncnt] = u;
        R[u] = ncnt;
    }
}
struct SegmentTree {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
    struct Node {
        int ans, mx, mn, rm, lm, laz;
    };
    vector<Node> t;
    SegmentTree(int n) {t.resize(n << 2);}
    void push_up(int rt) {
        t[rt].ans = max({t[ls].ans, t[rs].ans, t[ls].lm + t[rs].mx, t[rs].rm + t[ls].mx});
        t[rt].mx = max(t[ls].mx, t[rs].mx);
        t[rt].mn = min(t[ls].mn, t[rs].mn);
        t[rt].lm = max({t[ls].lm, t[rs].lm, t[ls].mx - 2 * t[rs].mn});
        t[rt].rm = max({t[ls].rm, t[rs].rm, t[rs].mx - 2 * t[ls].mn});
    }
    void fun(int rt, int l, int r, int k) {
        t[rt].mx += k, t[rt].mn += k;
        t[rt].lm -= k, t[rt].rm -= k;
        t[rt].laz += k;
    }
    void push_down(int rt, int l, int r) {
        if (t[rt].laz) {
            fun(ls, l, mid, t[rt].laz);
            fun(rs, mid + 1, r, t[rt].laz);
            t[rt].laz = 0;
        }
    }
    void build(int rt, int l, int r) {
        if (l == r) {
            t[rt].ans = 0;
            t[rt].mx = t[rt].mn = dep[dfn[l]];
            t[rt].rm = t[rt].lm = -dep[dfn[l]];
            return;
        }
        build(ls, l, mid), build(rs, mid + 1, r);
        push_up(rt);
    }
    void modify(int rt, int l, int r, int p, int q, int k) {
        if (p > r || q < l) return;
        if (p <= l && r <= q) {
            fun(rt, l, r, k);
            return;
        }
        push_down(rt, l, r);
        modify(ls, l, mid, p, q, k), modify(rs, mid + 1, r, p, q, k);
        push_up(rt);
    }
};
void solve() {
    int n, q, w; cin >> n >> q >> w;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
        edge[i] = tii(u, v, w);
    }
    dfs(1, 0);
    SegmentTree seg(ncnt);
    seg.build(1, 1, ncnt);
    int lst = 0;
    for (int i = 1; i <= q; i++) {
        int d, e; cin >> d >> e;
        d = (d + lst) % (n - 1);
        e = (e + lst) % w;
        auto& [u, v, prew] = edge[d];
        if (fa[v] == u) swap(u, v);
        int delta = e - prew;
        prew = e;
        seg.modify(1, 1, ncnt, L[u], R[u], delta);
        lst = seg.t[1].ans;
        cout << lst << "\n";
    }
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

回到L，转化后跟这个典就没啥大区别了，比较巧妙的一个是删边等价于让边权等0，然后要注意的是，询问里临时改变边权，如果是已经删掉的边，那么不能改边权，否则可能让直径偏大。

L代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
struct EDGE {
    int u, v, w, k;
} edge[maxn];
vector<pii> G[maxn];
int ncnt, n, q, L[maxn], R[maxn], dfn[maxn], siz[maxn], dep[maxn], fa[maxn];
void dfs(int u, int f) {
    siz[u] = 1, fa[u] = f;
    dfn[++ncnt] = u;
    L[u] = R[u] = ncnt;
    for (auto[v, id] : G[u]) {
        if (v == f) continue;
        dep[v] = dep[u] + edge[id].w;
        dfs(v, u);
        dfn[++ncnt] = u;
        R[u] = ncnt;
        siz[u] += siz[v];
        edge[id].k = min(siz[v], n - siz[v]);
    }
}
struct SegmentTree {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
    struct Node {
        int ans, mx, mn, lm, rm, laz;
    };
    vector<Node> t;
    SegmentTree (int n) {t.resize(n << 2);}
    void push_up(int rt) {
        t[rt].ans = max({t[ls].ans, t[rs].ans, t[ls].lm + t[rs].mx, t[rs].rm + t[ls].mx});
        t[rt].mx = max(t[ls].mx, t[rs].mx);
        t[rt].mn = min(t[ls].mn, t[rs].mn);
        t[rt].lm = max({t[ls].lm, t[rs].lm, t[ls].mx - 2 * t[rs].mn});
        t[rt].rm = max({t[ls].rm, t[rs].rm, t[rs].mx - 2 * t[ls].mn});
    }
    void fun(int rt, int l, int r, int k) {
        t[rt].mx += k, t[rt].mn += k;
        t[rt].lm -= k, t[rt].rm -= k;
        t[rt].laz += k;
    }
    void push_down(int rt, int l, int r) {
        if (t[rt].laz) {
            fun(ls, l, mid, t[rt].laz);
            fun(rs, mid + 1, r, t[rt].laz);
            t[rt].laz = 0;
        }
    }
    void build(int rt, int l, int r) {
        if (l == r) {
            t[rt].ans = 0;
            t[rt].mx = t[rt].mn = dep[dfn[l]];
            t[rt].lm = t[rt].rm = -dep[dfn[l]];
            return;
        }
        build(ls, l, mid), build(rs, mid + 1, r);
        push_up(rt);
    }
    void modify(int rt, int l, int r, int p, int q, int k) {
        if (p > r || q < l) return;
        if (p <= l && r <= q) {
            fun(rt, l, r, k);
            return;
        }
        push_down(rt, l, r);
        modify(ls, l, mid, p, q, k), modify(rs, mid + 1, r, p, q, k);
        push_up(rt);
    }
};
bool cmp(EDGE a, EDGE b) {return a.k < b.k;}
struct Query {
    int a, b, k, id;
} query[maxn];
int ans[maxn];
tii preedge[maxn];
void solve() {
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
        edge[i] = EDGE{u, v, w, 0};
        preedge[i] = tii(u, v, w);
    }
    dfs(1, 0);
    SegmentTree seg(ncnt);
    seg.build(1, 1, ncnt);
    sort(edge + 1, edge + n, cmp);
    for (int i = 1; i <= q; i++) {
        int a, b, k; cin >> a >> b >> k;
        query[i] = Query{a, b, k, i};
    }
    sort(query + 1, query + 1 + q, [](Query a, Query b) {return a.k < b.k;});
    int lst = 1;
    for (int i = 1; i <= q; i++) {
        auto[a, b, k, id] = query[i];
        while (lst < n && edge[lst].k < k) {
            // 删除这条边
            auto [u, v, w, k2] = edge[lst];
            if (fa[v] == u) swap(u, v);
            seg.modify(1, 1, ncnt, L[u], R[u], -w);
            lst++;
        }
        auto[u, v, prew] = preedge[a];
        if (fa[v] == u) swap(u, v);
        if (min(siz[u], n - siz[u]) >= k) {
            seg.modify(1, 1, ncnt, L[u], R[u], -prew);
            seg.modify(1, 1, ncnt, L[u], R[u], b);
        }
        ans[id] = seg.t[1].ans;
        if (min(siz[u], n - siz[u]) >= k) {
            seg.modify(1, 1, ncnt, L[u], R[u], prew);
            seg.modify(1, 1, ncnt, L[u], R[u], -b);
        }
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

标签：int,long,ncnt,seg,maxn,补题,2024CCPC,山东省,define
From： https://www.cnblogs.com/TJUHuangTao/p/18450574

相关文章

  • 10.5组队训练赛-2024CCPC山东省赛
    10.5组队训练赛-2024CCPC山东省赛成绩4排名8（差3题）写在前面Ika是简单题，但是因为a爆longlong一直没有看出来，导致交了很都发。出现的问题就是代码能力太弱，不能保证一遍过。改错的能力也很弱，没有及时发现出错的地方，一直在题意理解和算法方面打转。浪费时间。J题想了......
  • 补题报告5
    背景2024-10-5做\(CSP-J\)复赛模拟,作补题报告。成绩\(T1\)\(AC\)\(T2\)\(40\)\(T3\)\(0\)\(T4\)\(0\)\(T1\)牛奶(\(milk\))经典\(T1\)赛时\(A\).概述要采购牛奶，有\(n\)种，每种有各自的\(a_i\)和\(b_i\)，需要\(m\)盒，求最小花销思路题目描述中说，作为一只学......
  • 补题报告4
    背景CSP-J模拟赛考得最好的一次得分\(T1\):\(AC\)\(T2\):\(AC\)\(T3\):\(0\)\(T4\):\(20\)总分:\(220\)致敬传奇\(180\)分以上就请吃饭的......
  • KDY-二轮模拟-ZHX补题报告
    1.比赛情况T1三个T2合体T3矩形T4数对总分100pts70pts20pts20pts210pts2.赛中概况第一第二题比较简单，用了1小时搞定。（第一题全体AK）第3，4题难度飙升，想了好久最后改用暴力，共得40分，符合预期。3.题目解析 T1暴力出奇迹1.1问题描述现在科学家在培养 A,B,C三种微生......
  • CSP-J模拟赛一补题报告
    IAKIOI！！！前言考的最好的一回：240pts首先开T1，45min干掉了然后T2，45min挂了然后T3，40min又挂了然后发呆了一会把T4骗分打了，此时已过去一坤时40minT2切了，最后20min打了T3骗分又发呆了一会T1：100ptsT2：100ptsT3：30ptsT4：10pts《正文》01011010101001010010101011010100011......
  • DAY3-补题
    一题之计在于补呐补题很快乐的一点就是看不懂且听不明白但是写注释中理解到了。果然学会一道题最简单的方式是给一个纯萌新讲。说在前面今天%你赛手感非常好，可能是换了一个位置的原因（玄首先T1没有读错题是一个比较大的进步，因为DAY1和2都是因为差不多这个原因寄掉了，读对题目果......
  • 补题报告3
    背景2024-10-3上午打的比赛（CSP-J模拟2），作赛后总结报告。IP地址（\(ip\)）赛时AC。概述每个设备有一个对应的\(IP\),先给出对应的设备与\(IP\),再给出几个\(IP\)，求对应的设备。思路\(map\)存储，映射我的代码代码(点左边三角展开)#include<map>#include<cstdio>#includ......
  • CSP-J模拟赛补题报告
    前言最SB的一次&做的最差的一次T1：AC100pts......
  • 补题报告2
    背景2024-10-2上午打的比赛（CSP-J模拟2），作赛后总结报告。下棋（\(chess\)）赛时AC。概述高星\(x\)中星\(y\)低星\(z\)\(3\timesz=y\)\(3\timesy=x\)阵容强度：\(18\timesx+3\timesy+z\)求转换完后强度的顺序思路１.将能转的低星英雄转高星２.结构体排序输出......
  • DAY2-补题
    我补题AK了，但你出言不逊是非常好的一套题，让我的大脑旋转啊。不太想开一个文章单独屑，所以扔到随笔里面。敲字速度有待加强。说在前面题目难度单调递减，分数单调递减。果然屑死了。T1再次读题失误，正确的来说是代码敲得非常抽象。T2DP但没骗到分非常不好，T3场上想出正解了，但推一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99