wyxdrqc
wyxdrqc
全部文章
分类
未归档(64)
题解(3)
归档
标签
去牛客网
登录
/
注册
wyxdrqc的博客
全部文章
(共67篇)
CF Round #580(div2)题解报告
CF Round #580(div2)题解报告 T1 T2 水题,不管 T3 构造题,证明大约感性理解一下 我们想既然存在解 \(|a[n + i] - a[i]| = 1\) 这是必须要满足的 既然这样,那么图必须是这样的 \(-\),是相邻的两个数中的较小的一个,\(+\)...
2019-08-19
0
278
[JSOI2009]瓶子和燃料
[JSOI2009]瓶子和燃料 我们观察这个题面 发现 对于两个瓶子,他能够凑成的所有的数字是 \(x - ky\),\(2x - k'y\),\(3x - k''y\) 之后我们发现,这个和裴蜀定理的公式非常相似,而裴蜀定理的内容是 \(ax+by=c\)有解 当且仅当 \((a,...
2019-08-18
0
423
拓展中国剩余定理
拓展中国剩余定理(EXCRT) 关于解决线型同余方程组的解 有两种不同的方法 CRT和拓展CRT 这里重点介绍一下拓展中国剩余定理 我们设前\(k - 1\)个方程的解是\(x'\),\(M = LCM_{i = 1}^{k - 1} b_i\) 则很明显,前\(k - 1\)个方程的通...
2019-08-16
0
361
概率期望从入门到入土
概率期望 基础定义 首先,对于独立事件\(A,B\),我们有\(E(AB) = E(A)E(B)\) 这个式子在非独立事件的前提下是不成立的 另外\(A,B\)理解为随机变量,\(AB\)就是他们的乘积,一样理解为一个随机变量 根据等比数列求和公式 我们有 \[ \sum_{i = 0}...
2019-08-03
0
343
ZR8.2 DP
DP 1CF1101D 我们发现,最终答案一定和质因数有关 我们发现\(w_i <= 2*10^5\)级别的树,他的素因子的个数不会非常多(\(<=10\)) 然后我们就设 gcd是\(dp_{u,v}\)表示\(u\)节点的第\(v\)个素因子的倍数答案 很明显答案只能从相...
2019-08-02
0
829
ZR7.26
7.26 A 并查集维护,时间复杂度我写的貌似不大对,先鸽一鸽 B 敦爷:\(w\)是这个区间的最大值当且仅当他是这个区间内最大的 我们发现结合昨天课件内的并查集 发现我们每次不断合并的本质是把所有\(<=w\)的边连上 我们将这条边连接的两个连通块连到一起时,连个联通块的大小就...
2019-07-26
0
472
并查集,分治,拓扑排序
并查集,分治,拓扑排序 并查集 1:加边,查询两点什么时候连通 考虑重构树,将连通变成查阅路径上的权值最大值 动态加边可能需要LCT去维护 2:加边,询问第\(i\)时刻的\(x\)所在联通块大小 继续考虑重构树 实质上就是求边权第一次大于\(i\)的位置 此时的点的size就是所求...
2019-07-25
0
460
P4173字符串
[**P4173** 残缺的字符串](https://www.luogu.org/problemnew/show/P4173) FFT在字符串匹配中的应用. 能解决大概这种问题: 给定长度为$m$的A串,长度为$n$的B串。问A串在B串中的匹配数 我们设一个函数(下标从...
2019-07-19
0
435
十二省联考2019]异或粽子
# [[十二省联考2019]异或粽子](<https://www.luogu.org/problemnew/show/P5283>) 先吐槽一下,在考场上完全没有将这道题和超级钢琴联系起来,然后$GG$,喜提$60$走人 赛后听说直接上可持久化$Trie$用堆维护就好了 ...
2019-07-19
0
521
LuoguP5464 缩小社交圈
# [LuoguP5464 缩小社交圈](P54)64 缩小社交圈 背景:洛谷七月月赛T4 题目大意给定$n$个点,每个点的权值对应着一个区间$[l_i,r_i]$,两个点$i,j$有边当且仅当他们权值的并集不为空集,问有多少个点集$S$满足其连边后是一棵树 $n <= 2*10^3,l...
2019-07-19
0
616
首页
上一页
1
2
3
4
5
6
7
下一页
末页