2024TJUACM 3.18-3.31 第三—五周记录

ICPC-CCPC
字数统计: 8.4k   |   阅读时长≈ 37 分钟

本两周概要总结

比赛训练：

教学训练：线段树，树链剖分（重链），扫描线

RM-TR-1 SegmentTree

题目信息

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 ，分别表示该数列数字的个数和操作的总个数。

第二行包含 个用空格分隔的整数，其中第 个数字表示数列第 项的初始值。

接下来 行每行包含 或 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 内每个数加上 。
  2. 2 x y：输出区间 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

数据范围

对于 的数据：，。
对于 的数据：，。
对于 的数据：。

保证任意时刻数列中所有元素的绝对值之和 。

题目教学

线段树基础模板题，维护区间加以及区间和。

首先明确，线段树结点维护的是节点所代表区间的一个可递归下传以及递归合并后上传的信息，实现以区间为单位修改来节约大面积查询时间的目的。

对于一套线段树而言，其需要维护两个数组：一个记录区间维护信息的树节点数组，一个记录区间修改进行修改传递的懒惰标记_。

线段树核心的两个操作就是标记下传和迭代上传。对于一个区间的完成修改，我们可以通过记录区间所对应的_来表示对整个区间的修改并立即更新该区间树节点维护的信息。懒惰标记不操作于当前节点的信息，它提供的是当前区间的下级子区间尚且没有进行更新的维护内容，当前节点的区间信息已经在记录懒惰标记的同时就修改完毕了。等到某次涉及到子区间的访问时，我们再把懒惰标记上所记录的所有的记录（强调所有的记录，区间和的应用体现在懒惰标记的加法上）全部下传更新到目标节点以便统一数据版本。这样的操作实现了“按所需更新，不更新无所谓的节点”来大幅度压缩区间修改的时间。

同理，涉及一次标记下传就需要对应一次标记上传，通过子节点的当前更新信息来上传父节点以便统一该区间所影响到的全部上级结点的全部信息。

查询不需要进行标记上传更新，没有影响。

void push_down(long long p, int len)//必须是当前区间懒惰标记对子区间造成的影响修改，下传不修改当前区间
{
     if (len <= 1)
         return;
     tree[p << 1] += lazy_tag[p] * (len - len / 2); // 左侧偏多，是建树的时候决定的
     lazy_tag[p << 1] += lazy_tag[p];
     tree[p << 1 | 1] += lazy_tag[p] * (len / 2);
     lazy_tag[p << 1 | 1] += lazy_tag[p];
     lazy_tag[p] = 0;//传递后归零
     return;
}
void push_up(int x,int len)//递归下传后必须对应修改上传
{
    tree[p]=tree[p<<1]+tree[p<<1|1];//上传信息依据树节点维护信息决定
    return;
}

关于建树、修改和查询，如果结点区间不在范围内直接返回（0），节点区间完整的包含在目标区间内则直接返回对应信息，否则递归拆分处理。

void rangemodify_(int l, int r, T d, long long p, int cl, int cr)
{
     if (cl > cr || cl > r || cr < l)//不合法以及越界行为，把不准就画画区间。注意区间开闭问题
            return;
     if (cl >= l && cr <= r)
     {
         tree[p] += d * (cr - cl + 1);
         lazy_tag[p] += d;
         return;
     }
     push_down(p, cr - cl + 1);
     int mid = (cl + cr) >> 1;
     rangemodify_(l, r, d, p << 1, cl, mid);
     rangemodify_(l, r, d, p << 1 | 1, mid + 1, cr);//闭区间mid+1，开区间mid，维护离散区间信息。
    //像后文的涂色、扫描线区间连续的就要使用[l,r)形式区间维护连续信息
     push_up(p,cr-cl+1);
     return;
}
T query(int l, int r, long long p, int cl, int cr)
{
     if (cl > cr || cl > r || cr < l)
         return 0;
     if (cl >= l && cr <= r)
         return tree[p];
     push_down(p, cr - cl + 1);
     int mid = (cl + cr) >> 1;
     return query(l, r, p << 1, cl, mid) + query(l, r, p << 1 | 1, mid + 1, cr);
}

AC代码

RM-TR-2 Atlantis

题目信息

给定多个矩形的左下角和右上角坐标，求这些矩形面积的并。

输入格式

输入包括多组数据。

对于每一组数据，第一行一个整数，表示矩形个数。

接下来行每行四个数字，表示第个矩形的左下角和右上角坐标。

输入若干组数据后，以​结尾终止输入。

输出格式

对于第组数据，输出如下内容：

Test case #(the number of the testcase,normally i)
Total explored area:(the answer of testcase i,exact to two digits to the right of the decimal point.)

样例输入

2
10 10 20 20
15 15 25 25.5
0

样例输出

Test case #1
Total explored area: 180.00

题目教学

扫描线是基于线段树的一个实现，其前置内容为线段树求线段的并。

先解决上述问题。

给定长度为的一条直线，次询问，按以下要求操作。

操作：将区间所表示的线段加入集合或删除集合。保证均为整数。

操作​：查询集合内线段所覆盖的总长度。

通过线段树维护区间内当前所有的线段的总长度即可。

对于区间，维护区间线段总和以及区间线段覆盖层数​.

修改操作：

修改完整区间的信息时，直接按要求对​修改（加或减).

修改不完整区间，线段树二分划分修改。

下传操作：

由于充当了懒惰标记的部分性能，并且因为​只表示当前线段重叠了几条，不计算子线段拼起来部分。

所以num不下传，没有_函数.

举个例子，现在集合里面有和两条线段，但是没有的完整线段。两个已有线段倒是能拼成一个的线段，但是这个不算完整线段。所以.

上传操作：

如果区间，表示区间有完整线段存在，直接更新区间.

否则，区间内所含的线段长度由两个子区间内所包含的线段长度相加得到。

查询操作：

直接返回的值。

因为查询线段的并必定是查询区间内线段的总长度。

然后就不用查询函数了，只考虑建树的复杂度,查询是常数级别。

需要注意的一点事带开区间的线段树要开倍大小。

：

不保证为整数。

离线下来后离散化，然后再按顺序加入、删除、查询。

（强制在线先打问号？）

扫描线就是在上述内容基础之上。

img

这个动图已经足够说明意思了。扫描线从低向上扫，每两次修改之间计算当前线段并扫过部分的面积。扫到底边添加线段，扫到顶边不添加线段。

需要注意的是涉及到离散化的操作，这里有个问题就是离散化的时候没必要离散化​,否则常数会过于巨大。

离散化操作细节详见代码，这样操作后相当于变成了.

AC代码

RM-TR-3 Minimize Sum of Distances

题目信息

给你一棵有 个顶点的树。顶点的编号为 至 ， -th 边连接顶点 和 。

给出一个长度为 的正整数序列 。设 是顶点 和 之间的边数，而 的边数为 。

求出 .

题目教学

不难想到随便找一个点将整棵树挂起来之后先算出来一个值，然后在节点之间的转移。

问题是如何实现的转移。

举个例子，你有以下情况的树存在(样例2）：

Figure_1

然后把结点挂起进行了一次计算后，我想进行的转移到将结点挂起时的结果。不难发现这一步操作要减去以节点为根的子树的节点值总和以及加上剩余其他节点的节点值总和​。

如何快速查询总和？显然将子树的结点全部编号成连续号就可以扔到前缀和或者树状数组里面解决了。

那么，重链剖分() 就是这样的一种编号方式。

重链剖分可以将树上的任意一条路径划分成不超过条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 为链的一个端点)。以及最关键的，重链剖分还能保证划分出的每条链上的节点 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

剖分实现过程

给出一些定义：

定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

定义 轻子节点 表示剩余的所有子结点。

从这个结点到重子节点的边为 重边。

到其他轻子节点的边为 轻边。

若干条首尾衔接的重边构成 重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

HLD

很明显，这样进行划分后，树具有以下的性质：

  1. 树上每个节点都属于且仅属于一条重链。

  2. 重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。

  3. 所有的重链将整棵树 完全剖分。

  4. 在剖分时 重边优先遍历，最后树的 DFS 序上，重链内的 DFS 序是连续的。按 DFN 排序后的序列即为剖分后的链。

  5. 一颗子树内的 DFS 序是连续的。

  6. 当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。因此，对于树上的任意一条路径，把它拆分成从分别向两边往下走，分别最多走次，因此，树上的每条路径都可以被拆分成不超过条重链。

剖分实现方法：

进行两次.

第一次扫出来每个节点的父节点、各节点子树大小、各节点重儿子以及当前树深度。

int dfs1(int u, int dep)
{
    depth[u] = dep;
    Size[u] = 1;
    for (auto p : connects[u])
    {
        if (p == father[u])
            continue;
        father[p] = u;
        Size[u] += dfs1(p, dep + 1);
        if (Size[p] > Size[hson[u]])
            hson[u] = p;
    }
    return Size[u];
}

第二次扫出来每条链链顶、各节点目标序以及其反函数。初始化根节点

void dfs2(int u, int t)
{
    top[u] = t;
    dfn[u] = ++tot;
    invdfn[tot] = u;
    if (hson[u])
    {
        dfs2(hson[u], t);
        for (auto p : connects[u])
            if (father[u] != p && hson[u] != p)
                dfs2(p, p);
    }
    return;
}

RM-1 Oddly Similar

题目信息

有长度为 的 个序列，表示为 。长度为 的序列由 个整数 表示。

长度为 的两个序列 和 如果且仅当 的索引 的个数为奇数时，才可以说这两个序列是相似的。

求满足 的一对整数 中， 和 相似的个数。

数据范围

  • 所有输入值均为整数。

题目分析

AC代码

RM-2 Medicines on Grid

题目信息

有一个网格，网格中有 行和 列。让 表示从上往下第 行，从左往上第 列的单元格。每个单元格的状态由字符 表示，其含义如下：

  • .:空单元格。
  • #:一个障碍物。
  • S:空单元格和起点。
  • T:空单元格和目标点。

高桥可以通过消耗 能量从当前单元格移动到垂直或水平相邻的空单元格。如果能量为 ，他就无法移动，也无法离开网格。

网格中有 种药物。 -th药品位于空格 处，可以用来将能量设置为 。注意，高桥可以选择路过该点但不使用此药物。他可以在任何一次经过该空格时使用这一格中药物，但是药物只能使用一次，使用后立刻消失。

高桥以 的能量从起点开始，并希望到达目标点。请判断这是否可行。

数据范围

  • 是 .、 #、 S 和 T 中的一个。
  • 在 中，每个 S 和 T 都恰好存在一次。
  • 如果 .
  • 不是 #.

题目分析

AC代码

RM-3 Popcount and XOR

题目信息

给你非负整数 ， 和 。请判断是否有一对非负整数 满足以下五个条件。如果存在，请打印一个。

这里， 表示按位XOR。

如果多对 满足条件，则可以打印其中任意一对。

什么是 popcount？

对于非负整数 ， 的 popcount 是 的二进制表示中 的个数。更确切地说，对于 这样的非负整数 ，我们有 。

例如， 的二进制表示是 "1101"，所以是 。

题目解析

纯暴力模拟，使用或者数组暴力模拟每一位。推荐，省心。

假设,初始状态置为，为.

注意到的差值一定产生在对应为的位上。因为对应为的位置、要么都是，要么都是，只有为的位置上会有之间的差。

显然最大可能差值为，如果最大差值和目标差值的差为奇数或者为负数，显然无解，因为每一次间的对换都会让当前的差值减小.

贪心的从高到底对换到目标差值后，计算当前和目标值的差为多少，开始在对应均为的位置上补充.

需要明确的边界条件是，目标差值对换和目标值填充 的流程都不能越过最高位 和最低位 的界限，超界限了还没完成则无解。

AC代码

RM-4 Set Add Query

题目信息

有一个长度为 的整数序列 ，其中所有元素的初始值都设为 。此外，还有一个初始为空的集合 。

依次执行以下 查询。在处理完所有 查询后，找出序列 中每个元素的值。 -th 查询的格式如下：

  • 给出一个整数 。如果 中包含整数 ，则从 中删除 。否则，在 中插入 。然后，如果 包含 ，则将 添加到 中。

这里， 表示集合 中的元素个数。例如，如果是 ，那么就是 。

题目解析

只要在中，就会一直加。

这不就一区间求和？

说实话，写线段树貌似没啥必要。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int INF = 1e18;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr)
const int maxn = 3e5 + 1;
int num[maxn], qu[maxn], tree[maxn << 2LL], a[maxn];
void push_up(int p)
{
    tree[p] = tree[p << 1LL] + tree[p << 1LL | 1LL];
}
int n, q;
void build(int p = 1, int cl = 1, int cr = q)
{
    if (cl > cr)
        return;
    if (cl == cr)
    {
        tree[p] = num[cl];
        return;
    }
    int mid = (cl + cr) >> 1LL;
    build(p << 1LL, cl, mid);
    build(p << 1LL | 1LL, mid + 1, cr);
    push_up(p);
    return;
}
int query(int l, int r, int p = 1, int cl = 1, int cr = q)
{
    if (cl > cr || cl > r || cr < l)
        return 0;
    if (cl >= l && cr <= r)
    {
        return tree[p];
    }
    int mid = (cl + cr) >> 1LL;
    return query(l, r, p << 1LL, cl, mid) + query(l, r, p << 1LL | 1LL, mid + 1, cr);
}
signed main()
{
    IOS;
    cin >> n >> q;
    set<int> s;
    for (int i = 1; i <= q; i++)
    {
        cin >> qu[i];
        if (!s.count(qu[i]))
            s.insert(qu[i]);
        else
            s.erase(qu[i]);
        num[i] = s.size();
    }
    build();
    map<int, int> mp;
    for (int i = 1; i <= q; i++)
    {
        if (!mp[qu[i]])
        {
            mp[qu[i]] = i;
        }
        else
        {
            a[qu[i]] += query(mp[qu[i]], i - 1);
            mp.erase(qu[i]);
        }
    }
    for (auto p : mp)
    {
        a[p.first] += query(p.second, q);
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    system("pause");
    return 0;
}

RM-5 Piano

问题陈述

有一个无限长的钢琴键盘。在这个键盘中，是否存在一个由 个白键和 个黑键组成的连续部分？

假设 是由无限重复的字符串 wbwbwwbwbwbw 构成的字符串。

在 中，是否有一个子串是由出现了 次的 w 和出现了 次的 b 组成的？

什么是 的子串？对于两个正整数 和 而言， 的子串是由 的 -th, -th, , ​ -th 字符按此顺序连接而成的字符串。

数据范围

  • 和 是整数。

题目分析

纯sb题，不用分类讨论，枚举种起点暴力加，字符串最多翻倍到的长度就行了。

分类讨论丢了​的情况，这个是需要重复写两遍字符串才能看出来的。

RM-6 Gomamayo Sequence

问题陈述

给你一个长度为 的字符串 ，它由 0 和 1 组成。

长度为 的字符串 由 0 和 1 组成，当且仅当它满足以下条件时，它是一个**好的字符串：

  • 恰好有一个整数 使得 和 的 -th 和 -th 字符相同。

对于每个 ，您可以选择是否执行一次下面的操作：

  • 如果 的 -th 字符是 "0"，则将其替换为 "1"，反之亦然。如果执行此操作，代价是 。

求使 成为一个好字符串所需的最小总成本。

题目分析

最后要求只有一组两个相同的字符挨着。

那么这个目标串一定是由或者中间随便某个位置插入一个或者实现。称前两种为基串

对于偶数长度目标串，其基串一定是或者​​（例子）。

对于奇数长度目标串，其基串一定是或者。

在第个位置插入,维护其前缀费用和后缀费用即可。

奇偶数分开讨论（涉及前后缀开头不一样），特判。

注意位运算挂括号。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int INF = 1e18;
const int maxn = 2e5+3;
int pre1[maxn], suf1[maxn];
int pre0[maxn], suf0[maxn];
int a[maxn];
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr)
signed main()
{
    IOS;
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (s[i] & 15)
        {
            pre1[i] += pre1[i - 1] + ((i + 1) & 1) * a[i];
            pre0[i] += pre0[i - 1] + (i & 1) * a[i];
        }
        else
        {
            pre1[i] += pre1[i - 1] + (i & 1) * a[i];
            pre0[i] += pre0[i - 1] + ((i + 1) & 1) * a[i];
        }
    }
    for (int i = n, j = 1; i >= 1; i--, j++)
    {
        if (s[i] & 15)
        {
            suf1[i] += suf1[i + 1] + ((j + 1) & 1) * a[i];
            suf0[i] += suf0[i + 1] + (j & 1) * a[i];
        }
        else
        {
            suf1[i] += suf1[i + 1] + (j & 1) * a[i];
            suf0[i] += suf0[i + 1] + ((j + 1) & 1) * a[i];
        }
    }
    if (n == 2)
    {
        if (s[1] != s[2])
        {
            cout << min(a[1], a[2]) << endl;
        }
        else
            cout << 0 << endl;
        system("pause");
        return 0;
    }
    int ans = INF;
    if (n & 1)
    {
        for (int i = 2; i <= n; i++)
        {
            int t = pre1[i - 1] + suf0[i + 1];
            if (((i - 1) & 1) != (s[i] & 15))
                t += a[i];
            ans = min(ans, t);
        }
        for (int i = 2; i <= n; i++)
        {
            int t = pre0[i - 1] + suf1[i + 1];
            if ((i & 1) != (s[i] & 15))
                t += a[i];
            ans = min(ans, t);
        }
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            int t = pre1[i - 1] + suf1[i + 1];
            if (((i - 1) & 1) != (s[i] & 15))
                t += a[i];
            ans = min(ans, t);
        }
        for (int i = 2; i <= n; i++)
        {
            int t = pre0[i - 1] + suf0[i + 1];
            if ((i & 1) != (s[i] & 15))
                t += a[i];
            ans = min(ans, t);
        }
    }
    cout << ans << endl;
    system("pause");
    return 0;
}

RM-7 SSttrriinngg in StringString

问题陈述

对于长度为 的字符串 ，让 表示重复 次字符串 得到的字符串， 表示依次重复 次第一个字符、第二个字符、 、 的 个字符得到的字符串。例如，如果 abc, 那么 abcabc, abcabcabcabc，以及 aaabbbccc。另外，对于任意字符串 而言， 和 都是空字符串。

给你一个正整数 和字符串 和 。求最大的非负整数 ，使得 是 的子序列（不一定连续）。注意，根据定义， 总是 的子序列。

什么是子序列？字符串 的子序列（不一定连续）是指从 中删除 0 个或多个字符，然后在不改变顺序的情况下将剩余元素连接起来得到的字符串。例如，ac、atcoder和（空字符串）都是atcoder的子序列，但ta不是。

题目分析

如果是子序列，一定是。满足单调性，采用二分分析。

判断是否是子序列，暴力判断最小的满足的的是否小于等于，更进一步的，判断其长度是否大于。

记录每一个字母开始计数时指针所在的位置，按倍数筛去字符串。如果剩余的目标字母数量比一个完整少的时候，搜索其位置。

为方便搜索，按顺序记录中每个字母出现的对应位置。同时为了防止串中间搜到下一个串的开头，位置记录时记录两个连续的，并做好模运算处理。

注意二分起点设大一点。

AC代码

// freopen("data.in", "r", stdin);
//  freopen("data.out", "w", stdout);
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int INF = numeric_limits<int>::max();
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr)
string s, t;
int n;
vector<vector<int>> calc;
vector<vector<int>> place;
bool judge(int k)
{
    if (k == 0)
        return true;
    int pt = 0, rem = 0, nowpos = 0;
    for (int i = 0; i < t.size(); i++)
    {
        if (calc[0][t[i] - 'a'] == 0)
            return false;
        int len = (k / calc[0][t[i] - 'a']);
        rem = k % calc[0][t[i] - 'a'];
        if (!rem)
        {
            len--, rem = calc[0][t[i] - 'a'];
        }
        pt += len * s.size();
        int cnum = lower_bound(place[t[i] - 'a'].begin(), place[t[i] - 'a'].end(), nowpos) - place[t[i] - 'a'].begin();
        pt += (place[t[i] - 'a'][cnum + rem - 1] - nowpos + 1);
        nowpos = (place[t[i] - 'a'][cnum + rem - 1] + 1) % s.size();
    }
    if (pt > n * s.size())
        return false;
    return true;
}
signed main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    IOS;
    cin >> n;
    cin >> s >> t;
    place = vector<vector<int>>(26);
    for (int i = 0; i < 2 * s.size(); i++)
    {
        place[(s[i % s.size()] - 'a')].push_back(i);
    }
    calc = vector<vector<int>>(s.size() + 1, vector<int>(26));
    for (int i = s.size() - 1; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            calc[i][j] += (calc[i + 1][j]);
        }
        calc[i][(s[i] - 'a')]++;
    }
    int l = 0, r = 2e18;
    while (l < r)
    {
        if (r - l == 1)
        {
            cout << l << endl;
            break;
        }
        int mid = (l + r) >> 1;
        if (judge(mid))
            l = mid;
        else
            r = mid;
    }
    system("pause");
    return 0;
}

RM-S

RM-S-1 ABC348G (max,+)卷积

RM-S-2 ABC347G 网络流拆点

RM-S-3 ABC347F 巧妙分割+二维线段树

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2024 栾博越
  • 访问人数: | 浏览次数:

      请我喝杯咖啡吧~

      支付宝
      微信