EricWan

分类

题解(18)

/ 注册

全部文章（共18篇）

题解 | #J

维护一个大小为的数组，维护当以当前节点为右端点时连续的次方的期望。计算新答案的时候无脑转移即可（需要预处理组合数）。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

0 277

题解 | #I

一段合法区间肯定唯一与一对朋友映射，朋友对合法当且仅当他们挨着或与同时合法。从距离小到大枚举朋友对，用一个 set 记录合法的朋友对数，最后输出 set.size() + n 即可满分。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

2 239

题解 | #C

找环，对于大小大于的环，通过一次操作使得它的大小减，如果大小小于就退出。会剩下一坨大小为的环，把这些环两两匹配进行操作即可。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

0 159

题解 | #A

带权并查集，在保证并查集的根节点为原图根节点时对于每个并查集根节点维护它到子树内最远的节点的距离，并对于每个点，维护它到它并查集上父亲的距离，记得在路径压缩上维护这个。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

0 195

题解 | #L

可以证明非边界的地方一定至少有一个，除了它，全放雷就可以。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

0 146

题解 | #J

倍增找到从一个位置开始，会从哪里结束，它的父亲就是结束位置的后面一个位置，建立基环森林，在基环森林的每一个节点倍增找到答案。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

0 165

题解 | #H

签到题。模拟即可，枚举幸运观众在哪一个组，为了让幸运观众排名高，让所有双票选手都躲着幸运观众。强推我的洛谷博客（或者说文章区）如果渲染格式有问题，去我的洛谷博客

2024-07-25

0 114

题解 | #G

首先可以把每一个数扔掉完全平方因数（记录一下价值）后的数的质因数分解分为“小质数”和“大质数”，以为边界，把“小质数”抽象成一个二进制数。我们考虑 DP（你可以把它叫 01 背包，但物品重量是按照异或来相加的）。先处理没有大质数因数的数，之后对于每一个大质数，进行处理，每一个大质数可以被抽象...

2024-07-19

1 201

题解 | #I

为了描述方便，我用图论的说法讲了。我们先把增加一，把原数组用两个套起来，这样我们就必须把数组用完了。节点对应卡片，节点编号对应卡片序号。第一步，我们先对于任何一个节点，向编号下一个节点连一个边权为“随意”的边。我们从两张卡片间隔小到大的卡片一次考虑，每一次考虑，我们计算从这种卡片的前...

2024-07-18

1 177

题解 | #H

先用前缀和预处理从第一个操作做到当前操作后到达的位置，倒序考虑，维护记录相对位置的桶子即可（桶子里面记录有关最近一个到达那个相对位置的操作序号之类的信息）。具体方法这题看代码更好理解： #include <bits/stdc++.h> #define int long long usi...

2024-07-18

1 208