首页 > 其他分享 >模拟赛(&wzc)Round1 题解

模拟赛(&wzc)Round1 题解

时间:2023-02-08 20:57:50浏览次数:45  
标签:覆盖 标记 题解 线段 矩阵 修改 端点 wzc Round1

T1

二分答案,每次输出后 \(l \gets l + 1\), \(r \gets r + 1\)。

T2

每次计算时,显然对于 \(a,b\) 某一位都是 \(1\) 才会对答案产生贡献。

我们统计每一位的贡献,\(a\) 的第 \(i\) 位为 \(1\) 时,\(b\) 中初始位置比第 \(i\) 位高的 \(1\) 都会右移到这一位,对答案的贡献就是 \(b\) 中初始位置比第 \(i\) 位高的 \(1\) 的数量 \(\times\) 这一位的位权 \(2^i\)。

预处理一下 \(2\) 的次幂就可以了。

T3

我们对于线段树每个节点维护一个矩阵 \([sum_a, sum_b, 1]\) 记录信息,再维护一个 \(3 \times 3\) 矩阵表示懒标记,清空时赋值为 \(I\)(单位矩阵)。

区间修改时,我们让当前节点的信息矩阵和懒标记矩阵同时乘上修改矩阵。
标记下传时,让左右儿子的信息矩阵和懒标记矩阵同时乘上当前节点的懒标记矩阵。

可以看出,我们对于信息的修改就是乘上修改矩阵,而懒标记矩阵等同于所有未下传的修改乘积。
由于父亲节点的懒标记矩阵修改时间一定晚于儿子被遍历(否则直接下传了),矩阵乘法满足结合律,所以说乘上懒标记矩阵等同于乘上父亲所有未下传的修改。

修改矩阵很好推,这里不放了,可以看代码。

T4

T5

我们先构造一组特解

显然,每个人的位置的范围可以看做一条线段,每条线段覆盖一个点,要求每个点都被覆盖。
我们把线段按左端点排序,并对线段维护一个小根堆,堆按照线段右端点排序。
由于题目保证有解,我们从左到右遍历每个点,把以这个点为左端点的所有点加入堆,然后把堆顶拿出来覆盖这个点(因为右端点最小,留到后面不可能更优)。这样我们就有了一组特解。

我们继续找是否存在另一组解
显然,如果存在另一组解,一定存在一组解是由特解中交换两个点的线段得来的,这两个点的线段都能覆盖到另一个点。
因此,我们用 ST 表预处理出区间 \([l,r]\) 的点中右端点最大的线段所覆盖的点的位置,然后从左到右遍历每个点,看它的线段左端点到它之间,是否存在点满足该点线段可以覆盖到它,即在 ST 表上区间查询。这样我们保证每对点都被统计到。

标签:覆盖,标记,题解,线段,矩阵,修改,端点,wzc,Round1
From: https://www.cnblogs.com/Mysterious-Cat/p/17103253.html

相关文章

  • element plus + vue3表单第一次数据未清空的bug问题解决
    使用框架:elementPlus+vue3场景描述:场景一:表单的添加和修改功能,公用同一个弹框,点击修改后,点击添加表单显示的是上次修改的数据。场景二:点击修改,数据回显到表单,然后......
  • 【CCCC】L3-007 天梯地图 (30分),两次Dijkstra+路径打印(数据点2,4错因),90行最短题解
    problemL3-007天梯地图(30分)本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线......
  • P4870 [BalticOI 2009 Day1]甲虫 题解
    题目链接简要题意在一个数轴上有\(n\)滴露水,每滴露水初始水量为\(m\),每秒会蒸发一滴水,一个甲虫初始在原点,速度为1,水能瞬间喝完,问它最多能喝到几滴水。题目分析对于......
  • CF1693 ABCD 题解
    题目链接:https://codeforces.com/contest/1693这场的题都非常好啊……因为现在是从div1开始做了,所以可能刚开始会有点吃力(这场我就会做一个1B呜呜呜)1A先把后缀的极......
  • USACO 2023 January Contest, Platinum 题解
    TractorPaths题意:给定\(n\)个不交区间,两个区间之间有边当且仅当这两个区间的交非空。\(Q\)次询问,每次给定\(u,v\),求从\(u\)到\(v\)的最短路和最短路可能经过的点......
  • 黑苹果中Memory modules misconfigured问题解决
    问题大致和这个差不多,头一样,下面的不一样:大致意思是,你的内存出现了错误设置,要么成对安装,要么把模块全插满。以前版本没有这个信息,那就一定是配置造成的。按照https://dor......
  • CF14D题解
    CF14DTwoPaths题解题目链接传送门题意简述给定一棵树,找出两条不经过相同点的最长路径,使得他们的长度乘积最大。题目分析首先,如果在一棵树上,两条路径没有共同的点,那......
  • CF1785B Letter Exchange 题解(思维+模拟)
    题目链接难度:绿+。题意给定\(t\)组testcase,每组testcase如下。有\(m\)个长度为3的字符串,每个字符都是\(\text{w}\)、\(\text{i}\)、\(\text{n}\)中的一个,一......
  • HDU5126 stars题解
    HDU5126Description\(T\)组数据,给一个空的三维空间,\(Q\)次操作,分为插入一个点和查询某个立方体内点的个数。\(T\le10,Q\le5\times10^4\)Sol题目没说强制在线......
  • CF1333F Kate and imperfection 题解 线性筛
    题目链接:http://codeforces.com/problemset/problem/1333/F题目大意:kate有一个集合S,S中的元素是1到n的整数她认为集合S的一个子集M的集合的不完美值等于\(\max_{a,b\in......