文章

题目戳我_(:з」∠)_ 一开始想到了类似分治的做法，但还是 Naive 了 设我要合并出一个数值 $i$，被合并的区间左端点位置为 $j$，区间右端点的位置 $+1$等于 $f[i][j]$ 这里的位置指的是在初始数组中的下标 比如对于初始数组的第 $i$个元素 $a[i]$，$f 阅读更多…

题目链接：https://www.mina.moe/BZPRO/JudgeOnline/3792.html QAQ 大水题我都不会啊嘤嘤嘤 肯定要矩阵快速幂啦！ 先把无向边拆成有向边。 然后呢矩阵 $d[x][y]$表示第 $x$条有向边能否转移到第 $y$条有向边 然后防止从反向边转移就行啦。 最 阅读更多…

传送门 因为 qhy 太菜了所以只想 (hui) 做前四题 T1 redbag 发红包 签到题，随便推推，输出 $\frac w {2^k}$即可 #include<bits/stdc++.h> #define fo(i, a, b) for (int i = (a); i <= 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 本来是做 BZOJ 的最小求覆盖问题的，但是那题似乎 SPJ 有问题 A 不掉就来做这题了。 实际上可以用随机增量法做，可以做到 $O(n)$，但是求四个点的外接球有点太过麻烦，因此爬山即可 先随机一个球心位置，然后每次找到距离当前球心最远的点，它们之间的距 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 网上一篇题解都搜不到。。。 一份参考代码都没有 问题给出 $M, D, L, R$，求 $L \leq Dx \mod M \leq R$的最小正整数解，数据范围 $\leq 10 ^ 9$。 首先判断如果存在 $Dx \in [L, R],(Dx < 阅读更多…

这一道题显然是一道 RMQ 的题目，用一个三元素组 $（o，l，r）$表示：左端点为 o，右端点在 l 到 r 的区间内的最大子段，元素组用堆维护。 对于每个和弦的值，用前缀和在 $O(1)$的时间复杂度求出。 $ans$累加这个三元组的贡献。由于 $t$已经被选中，对于这个 $o$，$t$已经不能 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 似乎有很多很妙的正解我就不讲了 可以想到把初始的串正着建一个 Trie（即匹配前缀），反着再建一个 Trie（后缀匹配）然后维护每个 Trie 的节点的子树内的初始串出现情况，这个用线段树合并弄就行了。 询问就拿 s1 去前缀 Trie 里查询相应节点 a 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 好神的题啊 首先点数 $100000$太多了，我们可以想到 $m$条边中有的边无论你那 $k$条边怎么定价都是会出现的。 找出这些边的方法就是先把那 $k$条边加入一个空的图中，然后从小到大依次加入 $m$条边，如果加入某条边的时候它的两个端点没有联通，则说 阅读更多…

楼房重建 Abstract: 给你一堆数，求其从左往右单调上升的单调栈大小。会有修改元素大小的操作。 Ideas: 可以考虑分治。假设我们求出了一段区间的左半段的单调栈，以及右半段的单调栈，我们现在可以快速合并得到这段区间的单调栈。首先，左半段的全部元素都在新的单调栈里，右半段的元素如果比左半段的最 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 看上去非常难的样子，其实还好。 考虑枚举相似区间长度 $i$，计算每个 $i$对答案的贡献。 设 $f[i][j]$表示 $1,2,3,…,i$的排列中逆序对个数小于等于 $j$的有多少个。 $ans = \sum _ {i = 1} ^ {n} 阅读更多…