SCUACM2023集训前训练-数据结构

这篇具有很好参考价值的文章主要介绍了SCUACM2023集训前训练-数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

传送门

本文juejin:https://juejin.cn/post/7224886702883160120/

本文CSDN:https://blog.csdn.net/hans774882968/article/details/130312953

作者:hans774882968以及hans774882968以及hans774882968

M-等价关系,并查集

交换操作是“等价关系”的经典模型,就连LC都考过,回去看了一下才发现是同一道题……《离散数学》中等价关系的定义:

  1. 自反性:x = x
  2. 对称性:x = y => y = x
  3. 传递性:x = y, y = z => x = z

交换操作满足传递性的证明,就是找到1 2 3 -> 3 2 1的一种方式,如下:1 2 3 -> 1 3 2 -> 3 1 2 -> 3 2 1。故“可交换”是等价关系。把等价关系看成无向边,则可以得到一系列连通分量,每个连通分量的元素两两可交换,即每个连通分量内部的元素可以任意排序。最后只需要求每个连通分量下标值和p[]值的交集。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e5 + 5;

int n, m, a[N], fa[N];
set<int> gi[N], ga[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

int find (int x) {
    return x == fa[x] ? x : (fa[x] = find (fa[x]) );
}

int main() {
    read (n, m);
    rep (i, 1, n) read (a[i]);
    rep (i, 1, n) fa[i] = i;
    while (m--) {
        int x, y;
        read (x, y);
        int fx = find (x), fy = find (y);
        fa[fx] = fy;
    }
    rep (i, 1, n) gi[find (i)].insert (i);
    rep (i, 1, n) ga[find (i)].insert (a[i]);
    int ans = 0;
    rep (i, 1, n) {
        int fi = find (i);
        if (i != fi) continue;
        vector<int> res;
        set_intersection (
            gi[fi].begin(), gi[fi].end(), ga[fi].begin(), ga[fi].end(),
            insert_iterator<vector<int>> (res, res.begin() )
        );
        ans += res.size();
    }
    printf ("%d\n", ans);
    return 0;
}

Z-线段树模板:区间加、区间查询,两种维护方式

无论考虑维护前缀和还是差分数组,发现树状数组都无法优化到nlogn。但线段树有这个能力。线段树节点维护一个区间的1的个数和懒标记:

struct Node {
    int c, tg, len;
} nd[N << 2];

懒标记nd[x].tg表示对区间进行若干次操作后相当于区间异或nd[x].tg。那么区间查询操作就是查询nd[x].c,区间修改操作就是修改c属性nd[x].c = nd[x].len - nd[x].c

懒标记还有一个小问题:nd[x].tg需要选取一个0和1以外的值来表示区间没有被修改过吗?不需要,因为异或的性质,区间修改两次和区间没修改过没有任何区别。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int N = 1e5 + 5;

int n, m;

struct Node {
    int c, tg, len;
} nd[N << 2];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

void build (int x, int l, int r) {
    if (l == r) {
        nd[x].len = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build (ls (x), l, mid);
    build (rs (x), mid + 1, r);
    nd[x].len = nd[ls (x)].len + nd[rs (x)].len;
}

void pushdown (int x) {
    nd[ls (x)].tg ^= nd[x].tg;
    nd[rs (x)].tg ^= nd[x].tg;
    if (nd[x].tg) {
        nd[ls (x)].c = nd[ls (x)].len - nd[ls (x)].c;
        nd[rs (x)].c = nd[rs (x)].len - nd[rs (x)].c;
    }
    nd[x].tg = 0;
}

void pushup (int x) {
    nd[x].c = nd[ls (x)].c + nd[rs (x)].c;
}

void mdy (int ql, int qr, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
        nd[x].c = nd[x].len - nd[x].c;
        nd[x].tg ^= 1;
        return;
    }
    pushdown (x);
    int mid = (l + r) >> 1;
    if (ql <= mid) mdy (ql, qr, ls (x), l, mid);
    if (qr > mid) mdy (ql, qr, rs (x), mid + 1, r);
    pushup (x);
}

int qry (int ql, int qr, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
        return nd[x].c;
    }
    pushdown (x);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (ql <= mid) ans += qry (ql, qr, ls (x), l, mid);
    if (qr > mid) ans += qry (ql, qr, rs (x), mid + 1, r);
    return ans;
}

int main() {
    read (n, m);
    build (1, 1, n);
    while (m--) {
        int op;
        read (op);
        if (op == 0) {
            int l, r;
            read (l, r);
            mdy (l, r);
        }
        if (op == 1) {
            int l, r;
            read (l, r);
            int ans = qry (l, r);
            printf ("%d\n", ans);
        }
    }
    return 0;
}

还有一个不需要用到nd[x].len的线段树做法:维护区间0和1的个数c0, c1,则区间异或1的操作,相当于c0, c1交换。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int N = 1e5 + 5;

int n, m;

struct Node {
    int c0, c1, tg;
} nd[N << 2];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

void pushdown (int x) {
    nd[ls (x)].tg ^= nd[x].tg;
    nd[rs (x)].tg ^= nd[x].tg;
    if (nd[x].tg) {
        swap (nd[ls (x)].c0, nd[ls (x)].c1);
        swap (nd[rs (x)].c0, nd[rs (x)].c1);
    }
    nd[x].tg = 0;
}

void pushup (int x) {
    nd[x].c0 = nd[ls (x)].c0 + nd[rs (x)].c0;
    nd[x].c1 = nd[ls (x)].c1 + nd[rs (x)].c1;
}

void build (int x, int l, int r) {
    if (l == r) {
        nd[x].c0 = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build (ls (x), l, mid);
    build (rs (x), mid + 1, r);
    pushup (x);
}

void mdy (int ql, int qr, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
        swap (nd[x].c0, nd[x].c1);
        nd[x].tg ^= 1;
        return;
    }
    pushdown (x);
    int mid = (l + r) >> 1;
    if (ql <= mid) mdy (ql, qr, ls (x), l, mid);
    if (qr > mid) mdy (ql, qr, rs (x), mid + 1, r);
    pushup (x);
}

int qry (int ql, int qr, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
        return nd[x].c1;
    }
    pushdown (x);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (ql <= mid) ans += qry (ql, qr, ls (x), l, mid);
    if (qr > mid) ans += qry (ql, qr, rs (x), mid + 1, r);
    return ans;
}

int main() {
    read (n, m);
    build (1, 1, n);
    while (m--) {
        int op;
        read (op);
        if (op == 0) {
            int l, r;
            read (l, r);
            mdy (l, r);
        }
        if (op == 1) {
            int l, r;
            read (l, r);
            int ans = qry (l, r);
            printf ("%d\n", ans);
        }
    }
    return 0;
}

AA-lg3396-分块

有两种暴力做法:

  1. 不维护数据结构,直接修改原数组。x较大时,复杂度较低。
  2. 维护sum[x][y]表示模xy池的总和。查询O(1)但修改复杂度高。x较小时好。

我们考虑将两种做法结合起来,x较小使用做法2,否则使用做法1。这就是分块的思想。注意:需要同时维护原数组和sum[x][y]。代码很简单,就不写了。

AE-每次选两个,抛弃一个的过程,可以建模为树

这题描述了每次选两个并抛弃一个的过程。这个过程可以建模为树:每次选择就是连一次有向边,被抛弃的为儿子。知道这个模型,这题就可以秒掉了:因为没有选择上的性质,所以相当于在一个完全图中求最大生成树。代码很简单,就不写了。

AF-约瑟夫环结论+线段树

考虑一个01数组,存活的人为1,每轮要把某个1修改为0。设需要维护的全局变量now为:这一轮从第now个1所在的下标开始报数(0-indexed),根据定义,初值now = 0。并约定每一轮的操作为:先根据now求出下一轮的now1,再根据now1找到这一轮要修改为0的下标,这个下标记为idx(0-indexed)。所求即idx + 1。设这一轮要修改为0的下标是第now0个1(0-indexed)。因为下一轮比这一轮少了一个1,所以now1等于now0,所以上述约定是合理的。

举个例子:

7 4
5
9
8
5
// 5 1 4 6

a[] = 1 1 1 1 1 1 1。样例第1轮表示把a[4]修改为0,1 1 1 1 0 1 1,则now = 4, idx = 4。第2轮把a[0]修改为0,0 1 1 1 0 1 1now = 0, idx = 0。第3轮把a[3]修改为0,0 1 1 0 0 1 1now = 3, idx = 3。第4轮把a[5]修改为0,0 1 1 0 0 0 1now = 3, idx = 5

不难归纳出要进行的操作:now1 = (now + k - 1) % n, n -= 1n表示当前所剩1的个数。因此我们需要一个数据结构,能够:

  1. 单点修改。
  2. 求出第now个1所在的下标。

在线段树上二分即可。但因为只需要单点修改,所以可以用一种码量更少的非递归线段树来实现,名为zkw线段树。zkw线段树的思想如下:把二叉树补全为满二叉树,利用这条性质:当二叉树是1-indexed,则x左右孩子可表示为x << 1, x << 1 | 1。于是走向左右孩子和走向父亲的操作都很简单。

普通线段树

注意:上述描述是0-indexed,我实现的线段树输入约定为1-indexed。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int N = 5e5 + 5;

int n, m;

int nd[N << 2];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

void pushup (int x) {
    nd[x] = nd[ls (x)] + nd[rs (x)];
}

void build (int x, int l, int r) {
    if (l == r) {
        nd[x] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build (ls (x), l, mid);
    build (rs (x), mid + 1, r);
    pushup (x);
}

int mdy (int ql, int cur = 0, int x = 1, int l = 1, int r = n) {
    if (l == r) {
        nd[x] = 0;
        return l;
    }
    int mid = (l + r) >> 1;
    int vl = nd[ls (x)];
    int ans;
    if (cur + vl >= ql) ans = mdy (ql, cur, ls (x), l, mid);
    else ans = mdy (ql, cur + vl, rs (x), mid + 1, r);
    pushup (x);
    return ans;
}

int main() {
    read (n, m);
    build (1, 1, n);
    int now = 0;
    re_ (cas, 0, m) {
        int x;
        read (x);
        now = (now + x - 1) % (n - cas);
        int ans = mdy (now + 1);
        printf ("%d\n", ans);
    }
    return 0;
}

zkw线段树

注意zkw线段树有补全为满二叉树的操作,空间要求是2的幂。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int N = (1 << 20) + 5;

int n, m;

int nd[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    read (n, m);
    int tot = 1;
    for (; tot < n; tot <<= 1);
    re_ (i, 0, n) nd[tot + i] = 1;
    dwn (i, tot - 1, 1) nd[i] = nd[ls (i)] + nd[rs (i)];
    int now = 0;
    while (m--) {
        int x;
        read (x);
        now = (now + x - 1) % (n--);
        int ans = 1, cur = 0;
        while (ans < tot) {
            if (cur + nd[ls (ans)] > now) ans = ls (ans); // now + 1, so use >
            else cur += nd[ls (ans)], ans = rs (ans);
        }
        nd[ans] = 0;
        printf ("%d\n", ans - tot + 1);
        do {
            ans >>= 1;
            nd[ans] = nd[ls (ans)] + nd[rs (ans)];
        } while (ans);
    }
    return 0;
}

zkw线段树-最简版

和上面的代码等价,只不过做了些简化。文章来源地址https://www.toymoban.com/news/detail-423066.html

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int N = (1 << 20) + 5;

int n, m;

int nd[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    read (n, m);
    int tot = 1;
    for (; tot < n; tot <<= 1);
    re_ (i, 0, n) nd[tot + i] = 1;
    dwn (i, tot - 1, 1) nd[i] = nd[ls (i)] + nd[rs (i)];
    int now = 0;
    while (m--) {
        int x;
        read (x);
        now = (now + x - 1) % (n--);
        int ans = 1, cur = 0;
        while (ans < tot) if (cur + nd[ans <<= 1] <= now) cur += nd[ans], ans |= 1;
        printf ("%d\n", ans - tot + 1);
        while (ans) --nd[ans], ans >>= 1;
    }
    return 0;
}

到了这里,关于SCUACM2023集训前训练-数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构刷题训练——链表篇(二)

    目录 前言 1.题目一:链表分割 1.1 思路 1.2 分析  1.3 题解 2. 题目二:相交链表 2.1 思路 2.2 分析 2.3 题解 3. 题目三:环形链表 3.1 思路 3.2 分析 3.3 题解 总结         本期继续分享链表相关的OJ题目,在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步

    2024年02月14日
    浏览(40)
  • 数据结构刷题训练——链表篇(三)

    目录 文章目录 前言 1. 题目一:环形链表Ⅱ 1.1 思路 1.2 分析 1.3 题解 1.4 方法二 2. 题目二:复制带随机指针的链表 2.1 思路 2.2 分析 2.3 题解 总结         在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步提高解题能力。同时,我们也将分享一些刷题

    2024年02月13日
    浏览(37)
  • 数据结构刷题训练——链表篇(一)

    目录 前言 题目一:链表的中间节点 思路 分析 题解  题目二:链表中倒数第k个结点 思路 分析  题解 题目三:合并两个有序链表 思路 分析 题解  方法二 题解  题目四:链表的回文结构 思路 分析 题解 总结         今天我将开启一个新的专栏,数据结构与算法刷题训练营

    2024年02月14日
    浏览(33)
  • 数据结构刷题训练:队列实现栈

    目录 前言 1. 题目:使用队列实现栈 2. 思路 3. 分析  3.1 创建栈 3.2入栈 3.3 出栈 3.4 栈顶数据 3.5 判空和 “ 栈 ” 的销毁  4. 题解 总结         我们已经学习了栈和队列,也都实现了它们各自的底层接口,那么接下我们就要开始栈和队列的专项刷题训练。 题目描述:  题

    2024年02月13日
    浏览(39)
  • 数据结构Pta训练题函数题详解

    感谢你这么帅(漂亮)​还支持我 pta网站:PTA | 程序设计类实验辅助教学平台 (pintia.cn) 文章内容较长,建议搭配目录使用 给定一个顺序存储的线性表,请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储,并且相对位置不能改变。 函数接

    2024年02月12日
    浏览(50)
  • 数据结构pta训练题-编程题1

    感谢你这么帅(漂亮)​还支持我 训练网站:PTA训练平台 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

    2024年02月10日
    浏览(43)
  • 数据结构刷题训练——二叉树篇(一)

    📙 作者简介:  清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。 📘 相关专栏: C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正! ✨每一次努力都

    2024年02月07日
    浏览(52)
  • 数据结构刷题训练:设计循环队列(力扣OJ)

    目录 文章目录 前言 1. 题目:设计循环队列 2. 思路 3. 分析  3.1 定义循环队列  3.2 创建队列  3.3 判空和判满  3.4 入队  3.5 出队  3.6 取队头队尾数据  3.7 销毁队列  4. 题解 总结         当谈到队列数据结构时,很多人可能会想到普通的队列,即先进先出(FIFO)的数据结

    2024年02月13日
    浏览(47)
  • 数据结构刷题训练:用栈实现队列(力扣OJ)

    目录 前言 1. 题目:用栈实现队列 2. 思路 3. 分析  3.1 定义 “ 队列 ”  3.2 创建队列 3.3 入队  3.4 队头数据  3.5 出队  3.6 判空和销毁 4.题解 总结         栈和队列是数据结构中的两个重要概念,它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用

    2024年02月13日
    浏览(38)
  • 数据结构和算法-2023.07.03

      由于工作量加大,加之每天要写博客的内容上,深度可能没有那么深度了,但是为了保持这个日更的习惯,还是要坚持更新一些,我也发现了,其实写这个博文,更让我从某种程度上我重新的安静下来,重新的去理解和审视之前学习过的知识,之前的薄弱点在哪里,即使在

    2024年02月12日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包