文章列表

165 1 分钟

# [笔记] 概率论复习 # 统计定理 # 大数定律 通俗讲:样本数量越多,样本均值越接近期望。 样本均值收敛于真值。 是切比雪夫不等式的一种特殊应用。 # 切比雪夫不等式 # 贝叶斯定理 # 中心极限定理 通俗讲:独立同分布变量的标准化均值趋于标准正态分布。不受变量原始分布的影响。 适用条件: 所有变量相互独立 所有变量具有相同分布 变量的方差有限 # 随机过程 随机过程
1.5k 1 分钟

# OS 恶补笔记 Part1 并发 # 前情回顾 复习下 OS 里的一些基本知识点: # 并行 vs. 并发 并发性 (Concurrency): 同一时间段内执行多个任务 (but not necessarily simultaneously)。强调 “时间片段” 内的同时性,通过线程间的调度达到宏观上的 “同时进行”。 并行性 (Parallelism): 同一时刻执行多个任务。多 (核) 处理器出现后才有的概念,不同线程 (或指令片段) 在不同处理器上各自执行,实打实地同时进行。 没有并行,并发也是可能的。 # 多线程基础 #...
2.4k 2 分钟

# CCPC2022 Guilin J Permutation Puzzle # 题意 有一个长度为nnn 的排列ppp,其中的一些位置上的值未知。另有mmm 条约束关系(i,j)(i,j)(i,j),表示pi<pjp_i\lt p_jpi​<pj​。求一种可能的满足所有约束的排列。 #...
2.6k 2 分钟

# CCPC2022 Guilin G Group Homework # 题意 给出一个有点权的树,你需要选择两条链,收益为两条链并的权值和减去两条链交的权值和,使得收益最大。 # 题解 如果选择的两条链,交点多于111 个,那么我可以重新选择划分成两条不相交的链,使得收益比原来更大。所以情况只有两种:两条链有一个交点,两条链没有焦点。 对于两条链有一个交点的情况,做 dp 计算从每个点延伸出的前四大最长链。这里用 换根dp 实现。首先自下而上计算f0[x][0,1,2,3]f_0[x][0,1,2,3]f0​[x][0,1,2,3] 表示以111 为根时xxx...
2.5k 2 分钟

# [题解] ICPC2023 HongKong Sum of Numbers [线段树][扫描线] 也是好久没写博客了。最近学校各种事情太多了,基本每周都有事。 下周更是:CCSP 要来了,在此之前还有网综实验考试。。 好在网综实验貌似并不是太难,用了半个上午时间大概会了一半的分数了;老师也还算和善。 希望不出什么岔子。 # 题目大意 给定一个长度为nnn 的颜色数组aaa, 对于一个区间[l,r][l,r][l,r], 称其是不好的当且仅当区间内存在一个颜色ccc 且这个颜色恰好出现了kkk 次。问数组中一共有多少个好的区间。 # 题解 对于每一个颜色 c,将其出现位置抽离出来。记 pos...
5k 5 分钟

# [题解] 2023 杭电多校 King's Ruins [偏序][bitset][dp] # 题目大意传送门\footnotesize^{传送门}传送门 六维偏序dpdpdp。 # 高维偏序 bitset 做法 一维、二维、三维偏序分别有排序、排序 + 一维数据结构、CDQCDQCDQ 分治的做法,比较经典。维数再高点,多层嵌套的CDQCDQCDQ、多层嵌套数据结构,复杂度都不会太理想。 专门处理高维查询的数据结构K−DTreeK-D TreeK−DTree...
3.4k 3 分钟

# [题解] CF1864E Exotic Queries [区间问题][二维偏序] # 题目大意传送门\footnotesize^{传送门}传送门 给一个长度为nnn 的数组,有qqq 个询问,每次询问对于值域[L,R][L,R][L,R] 的所有元素,通过以下操作使得这些元素全部变为000 的最小操作次数。 指定操作(l,r,x)(l,r,x)(l,r,x):选取一段区间[l,r][l,r][l,r] 和一个正整数xxx, 将这段区间上的元素减去xxx。 你可以操作任意多次,但是对于所有操作区间,只存在包含、相离关系,不存在相交关系。 #...
2.5k 2 分钟

# [题解] CF1864E Guess Game [期望][Trie] # 题目大意传送门\footnotesize^{传送门}传送门 给一个长度为nnn 的数组,每次从中随机选取两个数a,ba,ba,b,进行游戏: Alice 得到aaa 和a∣ba|ba∣b 的值,Bob 得到bbb 和a∣ba|ba∣b 的值,从 Alice 开始,他们轮流猜aaa 和bbb 的大小关系。 如果不能确定就说 idk ,否则直接会说出a<ba\lt ba<b,a>ba\gt ba>b...
2.5k 2 分钟

# 矩阵类 struct Mat{ int **a; int r,c; Mat(const int &r,const int &c):r(r),c(c){ a=new int * [r]; for(int i=0;i<r;++i) a[i]=new int [c](); } Mat(const int &r,const int &c,const int &x):Mat(r,c){ for(int...
1.2k 1 分钟

# [题解] 2023 杭电多校 Do You Like Interactive Problems? [期望][分类讨论] # 题目大意传送门\footnotesize^{传送门}传送门 你需要猜一个在[1,n][1,n][1,n] 范围内的整数xxx,每次你随机选择一个y∈[1,n]y \in [1,n]y∈[1,n] 进行询问,并得到答案 y>x,y<x,y=xy>x,y<x,y=xy>x,y<x,y=x 其中之一,直到能确定xxx 的值停止询问。 问期望询问次数。 #...