wyxdrqc

未归档

题解(3)

/ 注册

全部文章 / 未归档（共64篇）

CF Round #580(div2)题解报告

CF Round #580(div2)题解报告 T1 T2 水题,不管 T3 构造题,证明大约感性理解一下我们想既然存在解 \(|a[n + i] - a[i]| = 1\) 这是必须要满足的既然这样,那么图必须是这样的 \(-\),是相邻的两个数中的较小的一个,\(+\)...

2019-08-19

0 360

[JSOI2009]瓶子和燃料

[JSOI2009]瓶子和燃料我们观察这个题面发现对于两个瓶子,他能够凑成的所有的数字是 \(x - ky\),\(2x - k'y\),\(3x - k''y\) 之后我们发现,这个和裴蜀定理的公式非常相似,而裴蜀定理的内容是 \(ax+by=c\)有解当且仅当 \((a,...

2019-08-18

0 523

拓展中国剩余定理

拓展中国剩余定理(EXCRT) 关于解决线型同余方程组的解有两种不同的方法 CRT和拓展CRT 这里重点介绍一下拓展中国剩余定理我们设前\(k - 1\)个方程的解是\(x'\),\(M = LCM_{i = 1}^{k - 1} b_i\) 则很明显,前\(k - 1\)个方程的通...

2019-08-16

0 443

概率期望从入门到入土

概率期望基础定义首先,对于独立事件\(A,B\),我们有\(E(AB) = E(A)E(B)\) 这个式子在非独立事件的前提下是不成立的另外\(A,B\)理解为随机变量,\(AB\)就是他们的乘积,一样理解为一个随机变量根据等比数列求和公式我们有 \[ \sum_{i = 0}...

2019-08-03

0 463

ZR8.2 DP

DP 1CF1101D 我们发现,最终答案一定和质因数有关我们发现\(w_i <= 2*10^5\)级别的树,他的素因子的个数不会非常多(\(<=10\)) 然后我们就设 gcd是\(dp_{u,v}\)表示\(u\)节点的第\(v\)个素因子的倍数答案很明显答案只能从相...

2019-08-02

0 951

ZR7.26

7.26 A 并查集维护,时间复杂度我写的貌似不大对,先鸽一鸽 B 敦爷:\(w\)是这个区间的最大值当且仅当他是这个区间内最大的我们发现结合昨天课件内的并查集发现我们每次不断合并的本质是把所有\(<=w\)的边连上我们将这条边连接的两个连通块连到一起时,连个联通块的大小就...

2019-07-26

0 585

并查集,分治,拓扑排序

并查集,分治,拓扑排序并查集 1:加边,查询两点什么时候连通考虑重构树,将连通变成查阅路径上的权值最大值动态加边可能需要LCT去维护 2:加边,询问第\(i\)时刻的\(x\)所在联通块大小继续考虑重构树实质上就是求边权第一次大于\(i\)的位置此时的点的size就是所求...

2019-07-25

0 623

莫队

# 莫队阶段小结首先,为什么要叫小结呢,因为我只学了一点点,后续可能更多 ## 莫队莫队是一种离线处理区间问题的神器.答题思路就是你将原数列分成$\sqrt{n}$块,将所有查询左端点定位,并按照左端点所在的块进行排序,相同则按照右端点排序大体就是这个样子 ```cpp inline...

2019-07-19

0 550

ZR7.17

7.17 F 认真读题吧 A 算法一: \(c = ab,x = a + b + c\) 所以 \(x = a + b + ab\) \(=(b + 1)a + b\) 所以我们枚举\(b\) \(O(1)\)check了但是这样是\(O(x)\)的之后我们由 \(x ...

2019-07-17

0 347

LuoguP5464 缩小社交圈

LuoguP5464 缩小社交圈背景:洛谷七月月赛T4 题目大意给定\(n\)个点,每个点的权值对应着一个区间\([l_i,r_i]\),两个点\(i,j\)有边当且仅当他们权值的并集不为空集,问有多少个点集\(S\)满足其连边后是一棵树 \(n <= 2*10^3,l_i<=r...

2019-07-16

0 524