- 博客(394)
- 收藏
- 关注
RSS订阅
原创 【个人向】计算建模 补充材料
计算建模是HIT大三秋季计院计算机科学方向的专业核心课，内容cover了随机过程、优化、信号处理等topic这里是笔者对课余参考的一些补充材料的collection，主要是一些概念如果不求甚解（不追求严格的数学证明）地看下来会发现其实随机过程挺自然的，没什么和intuition相悖的地方，基本上都能make sense。
2022-10-24 23:22:33
1155
5
原创 Summary of Signal and System
Chapter 1冲激信号δ(t)\delta(t)δ(t)Dirac定义：∫−∞+∞δ(t)=1\int_{-\infty}^{+\infty}\delta(t)=1∫−∞+∞δ(t)=1, δ(t)=0(t≠0)\delta(t)=0(t\neq 0)δ(t)=0(t=0)性质：f(t)δ(t−t0)=f(t0)δ(t−t0)f(t)\delta(t-t_0)=f(t_0)\delta(t-t_0)f(t)δ(t−t0)=f(t0)δ(t−t0)δ(at)=1∣a∣δ(t)\del
2022-05-24 11:30:54
181
原创 Dyson Sphere Program 戴森球计划 个人心得
基本概况一倍资源平平无奇种子，母星系无珍奇无潮汐锁定，母星（第三行星）为第二行星冰巨星的卫星，此外母星系第一行星为熔岩星，第四行星猩红冰湖（感觉算是最没用的星种了）母星系资源情况，铜矿石矿钛矿严重过剩，铁矿不足，硅矿奇缺（全星系只有三处硅矿脉，储量都不大）中期电力问题大概指从黄糖阶段起直到白糖期间过渡的这段时期这个时候发电有很多种思路，比如拉太阳能腰带，扩展火电，发展核电，射电接受站+戴森云，地热发电等等。风电由于量太小且太占地方，所以直接pass。某些神种有潮汐锁定星，直接无脑选太阳能，向阳面
2022-04-27 22:38:11
1399
1
原创 Fourier series, Fourier transform, Laplace transform etc.
Today I watched lots of learning materials related to Fourier series, Fourier transform, Laplace transform etc. To sum up, I post the links here.3Blue1Brown : A visual intro to Fourier transformHeinrich : Intro to Fourier Analysis马同学 : How to understand
2022-03-05 22:33:43
138
原创 Notes for Formal Languages and Automata Theory
AlphabetNon-empty finite set of symbolsΣ\SigmaΣStringsfinite sequence of symbols of Σ\SigmaΣempty string : ϵ\epsilonϵΣ∗\Sigma^*Σ∗ : the set of all strings over alphabet Σ\SigmaΣ (including ϵ\epsilonϵ)Σ∗\Sigma^*Σ∗ is monoid with respect to concatenat
2022-02-23 11:34:16
331
2
原创 Notes for Abstract Algebra
Some notation\circ for ∘\circ∘\bull for ∙\bull∙\cdot for ⋅\cdot⋅\odot for ⊙\odot⊙\oplus for ⊕\oplus⊕对称性几何图形的对称性、根的对称性群SSS是一个非空集合，∘\circ∘ 为封闭二元运算 i.e. ∘:S×S→S\circ : S \times S \rightarrow S∘:S×S→S若 ∘\circ∘ 满足结合律，则称(S,∘)(S, \circ)(S,∘)为半群幺元含幺
2022-02-22 20:49:30
85
原创 Git Low Level Logic
Pseudocode from " MIT missing semester of CS education "// a *file* is a bunch of bytestype blob = array<byte>// a *directory* contains named files and directoriestype tree = map<string, tree | blob>// a *commit* has parents, metadata, a
2022-02-21 10:53:36
74
原创 CSAPP datalab
/* * CS:APP Data Lab * * Cervoliu HIT * * bits.c - Source file with your solutions to the Lab. * This is the file you will hand in to your instructor. * * WARNING: Do not include the <stdio.h> header; it confuses the dlc * comp.
2022-01-23 17:51:44
128
原创 折腾日记（补档）
本人在Surface Pro 7上使用ubuntu接近一年，这个寒假终于把linux-surface内核成功安装，修复了surface在默认内核下的不少bug和失效feature，心情大好。近日发现一年前换的源出现了种种问题，一查才发现版本不对，于是乎心血来潮想把踩过的坑记录下来。换源指南首先执行如下命令查看版本名，我的是ubuntu20.04，所以是focal>lsb_release -c备份原来的源sudo cp -v /etc/apt/sources.list /etc/apt/s
2022-01-18 12:09:21
644
原创 《survivesjtumanual》 读书笔记
神书！后悔没有更早读到它应把《manual》当作葵花宝典，不时翻看一下金句如果一个人把政策评分作为自己的至高追求，那么他就是这个政策的牺牲品。大学四年留给你的是你的人生，在你毕业之时，那一串苍白的分数其实就已经作废了。为什么要上课？学习最需要的，不是悲壮的毅力，而是对无限未知的渴求。最终来说，学习知识的目的是为后继的知识铺垫，以及培养创造性的思维。所谓有效率的学习，应当是以最高的效率获取知识，服务这两个目标。从现状来看，我们想要把什么都搞扎实的学习习惯，其效率是极端低下的，而在我们通过
2021-12-04 22:27:57
671
原创 Notes for Mathematical Logic
Chapter 1 绪自然语言 歧义 不适合演绎（deduction）形式化公理系统形式语言（Formal Languages，或符号（symbolic）语言）程序设计语言、分子式、乐谱都是形式语言语法（Syntax，或语构）语义（Semantic）Chapter 2 命题逻辑命题逻辑（Propositional Logic）VS 谓词逻辑（Predicate Logic）命题逻辑：推理中只分析命题之间的关系，不需要把命题分解为构成命题的各种非命题成分2.1 命题与联结词Def. 命题
2021-11-27 22:55:35
270
1
原创 Proof of Master Theorem
Master Theorem：T(n)=aT(nb)+f(n)T(n)=aT\left(\dfrac{n}{b}\right)+f(n)T(n)=aT(bn)+f(n)where a≥1,b>1a\geq 1, b>1a≥1,b>1, a,ba,ba,b is constant, nb\dfrac{n}{b}bn can be either ⌊nb⌋\lfloor \dfrac{n}{b} \rfloor⌊bn⌋ or ⌈nb⌉\lceil \dfrac{n}{b} \rcei.
2021-11-26 16:53:32
152
原创 【HIT数据结构复习】外部排序
IntroQ：为什么需要外部排序？A：因为数据规模太大，光读入都会爆内存…“需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序，在排序过程中需要多次进行内存和外存（磁盘）之间的交换。这种排序方法就称为外部排序。”由于磁盘IO比内存IO慢得多（大概慢5个数量级），所以瓶颈完全在于前者，故为了方便时间开销主要考虑前者的次数Merge sort外部排序通常采用归并排序法，分为两个阶段：一，形成初始归并段；二，多路归并形成初始归并段：将待排文件根据内存大小合理切片，分别读入内
2021-11-22 22:04:45
977
原创 2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest 部分题解
B简单计算几何，求一下线段长再求一下夹角就做完了E大模拟，注意题目描述有一点小瑕疵u1s1这题提供的 2-3-4 tree 还是很精妙的老年码力苦手表示很淦H经典题，定义性价比=ATK/HP，按性价比从高到低打怪即可Kn=36，相当经典的数据范围，容易想到折半对于两个n=18的集合S,T分别预处理出其内部合法的染色方案，枚举S的状态，根据S与T之间的边确定T中染色最少的合法状态，我们只需要对T的合法状态预处理一个高位前缀和就可以快速计算答案了，复杂度O(2nn2)O(2^n n^2)O
2021-01-19 21:31:05
222
原创 2020-2021 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 20) 部分题解
E先考虑每行个数相同的情形，只需 O(n)O(\sqrt n)O(n)扫一遍因子再考虑类似美国国旗的情形，也就是一行个数为xxx，一行为x+1x+1x+1，依次排下去对于这种情形，可以将每行的个数视作x+0.5x+0.5x+0.5，行数不变，那么最后与nnn误差不超过0.50.50.5所以我们分别对n∗10+5n*10+5n∗10+5，n∗10n*10n∗10，n∗10−5n*10-5n∗10−5质因数分解，并将其分拆成个位数为555的因子ppp与因子qqq的乘积，并用abs(p div
2021-01-15 11:48:00
578
原创 2020-2021 ACM-ICPC, Asia Seoul Regional Contest 部分题解
Preface感谢shadowice1984和__23333两位佬带我飞A听说是大模拟B签到题C答案即为虚树中的点数，边权没卵用E经过一些转化，题目变成：你有两个bool变量x和y，遇到1可以选择任意一个xor 1，遇到2需要保证x xor y = 1，末尾需要保证x = y = 0. 扫一遍用奇偶性判断即可.H问ai+ck=2bja_i+c_k=2b_jai+ck=2bj的三元组(i,j,k)(i,j,k)(i,j,k)的个数，ai,bi,cia_i,b_i,c_iai,bi
2021-01-13 18:36:23
2448
原创 【AGC 049C】Robots
对于B[i]>=A[i]的robot，称其为dangerous的若无dangerous的robot，则答案为0我们有两种方法消灭一个dangerous，一，把它变成safe，二，用另一个踩死它对于一个dangerous的robot，显然消灭该robot的代价最多为1（花费至多1的代价踩死他）找出safe能覆盖的极长的区间，在safe区间内的dangerous显然可以被消灭掉。…考虑只用第二种方法消灭dangerous，那么答案等于没有被safe区间覆盖到的dangerous个数考虑用第一
2020-11-22 07:52:03
221
原创 多项式exp，ln，求逆板子
题目是jzoj 5923#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;algorithm&gt;#define fo(i,a,b) for(int i=a;i&lt;=b;++i)#define fd(i,b,a) for(int i=b;i&gt;=a;--i)#define max(x,y) ((x
2019-02-16 20:56:49
241
原创 【类欧几里得算法】【JZOJ 6025】Cannon
DescriptionAnalysis一个很自然的想法是，由于k很大，我们二分一个分数，统计网格有多少个比它大先不考虑如何二分分数，假装我们已经得到了分数ab\dfrac{a}{b}ba，如何统计比它大的个数呢？直线上整点个数，妈妈我会类欧类欧我们要求的是这个f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum_{i=0}^n \lfloor \dfrac{...
2019-02-16 20:22:20
225
原创 任意模数FFT & 第一类斯特林数模板
JZOJ 5688#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;algorithm&gt;#include&lt;cmath&gt;#define fo(i,a,b) for(int i=a;i&lt;=b;++i)#define fd(i,a,b) for(int i=a;i&
2019-01-17 17:52:20
278
原创 【JZOJ 5992】万家灯火
Description给定一棵N(N<=1e5)个点树，每个点有0/1的权值，有M(M<=1e5)次操作1 x表示将x点的权值xor 12 x d表示查询与x点距离不超过d的点集中的连通块数，其中两个点之间右边当且仅当这两个点权值都为1，特别地x点与任何点没有边相连Analysis0->白，1->黑连通块数=点数-边数动态点分治+树状数组维护各个深度的黑点数/...
2019-01-11 22:45:19
263
原创 tree
Description给你一棵n个点的树，你需要在树上选择恰好m条点不相交的，点数至少为k的路径，使得路径所覆盖的点权和尽可能大。求最大点权和。数据保证有解。n&lt;=1.5e5凸优化+长链剖分 存档题Code#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;algorithm&gt;#include&
2019-01-10 16:27:17
189
原创 【JZOJ 5990】Bear
DescriptionlinkAnalysis朴素dp是逐行逐格转移注意到nnn较小，mmm较大一个显然的想法是看看能否逐列逐格转移，很可惜不行，因为考虑棋盘覆盖顺序，行的限制优先于列但是考虑行和列覆盖情况什么时候会冲突，只可能是形如2*2的小正方形里，左下和右上对右下格覆盖的时候冲突了，并且我们知道右上的优先级更高这启示了我们可以以左往右逐个斜线，每条斜线再从上到下的顺序来dp，记...
2019-01-07 21:47:20
196
原创 【Codeforces 1097G】Vladislav and a Great Legend
Description原题链接Analysis∑Xf(X)k=∑X∑i=0kS(k,i)i!(f(X)i)\sum_{X}f(X)^k=\sum_X \sum_{i=0}^k S(k,i) i! {f(X) \choose i}X∑f(X)k=X∑i=0∑kS(k,i)i!(if(X))考虑对于i=1…k，dp出(f(X)i){f(X) \choose i}(if(X))dp选...
2019-01-05 20:55:37
349
原创 NOIP 2018 退役记
Day 0一年过去，又从二中回到了六中，还换了酒店。吃饭自行解决好评。我年龄越是增长，心态反而越无所谓。不知道这样是好是坏。由于当天没有写代码，晚上睡前写了一道题找找手感。Day 1国际酒店没有西式早餐差评可以试机好评六中键盘差评8:30准时开始8:31发现T1是原题，主程序3行秒了8:32发现T2不会做8:35发现T2重要结论，然后就会做了8:40写完前两题然后心态有...
2018-11-13 12:30:19
580
原创 【UOJ #390】【UNR #3】百鸽笼
Description给定nnn个正整数aia_iai，令N+1=∑aiN+1=\sum a_iN+1=∑ai将执行NNN次操作，每次等概率随机选择一个非零的aia_iai并令其减一，显然NNN次操作结束之后有且仅有一个ai=1a_i=1ai=1对于一开始的nnn个aia_iai，分别求出它们最后为111的概率n,ai≤30n,a_i \leq 30n,ai≤30Analys...
2018-11-06 15:07:00
707
原创 【bzoj 2122】【jzoj 5936】逛公园
共q组询问，n,q<=4e4Analysis任意起点终点不好做，先考虑fix了起点终点后，对于给定x0，从l走到r的答案。不妨设它为f(l,r,x0)对于任意给定x0，f(l,r,x0)均可以O(r-l)求出，这样我们得到了一个O(nq)的暴力接下来需要发现一个本题最关键的性质：f(l,r,x0)=min(f(l,r,+∞),x0+s(l,r)),s(l,r)=dl+...+drf...
2018-10-29 16:55:37
318
原创 NOIP 2018 前的几场模拟
10/20从15号到今天20号，我打了4场模拟，中间有一场我是验题人总的来说还是比较悲惨的整体的一个现象是，我做比赛的时候很少写对拍。现在想想，虽有挂分，但是都不多。包括之前很多正式比赛我也很少写对拍，主要是因为有大样例/pretest/实时看成绩赛制的存在，外加时间紧迫导致的。常常高估自己的代码能力，导致出现写不完正解又没写暴力，前面的水题还没拍的情况。不管是NOIP考场上还是平时模...
2018-10-20 22:11:05
276
原创 新·自我剖析
基于上一年写的update思维能力对于数学论相关的反应迟钝 对于特别抽象的会有畏难心理 对于繁琐讨论会有逃避心理（不一定是坏事，可能换个脑子会想到更简单的做法） 比较喜欢在普通模型上深入思考训练方面: **计数**，树上问题（包括dp，数据结构等），多项式 泛做“中国式”题目：从近年NOI-&gt;THU/PKU-WC/SC-&gt;CTSC-&gt;各省省选 每日一题，限...
2018-09-05 21:33:52
502
原创 「NOI2018」冒泡排序
Description给定1~n的排列p，求所有长度为n的字典序严格大于p的排列中有多少个能被拆分成不超过两个上升子序列。（其实原题是，求有多少个排列进行冒泡排序后交换次数恰为一个下界12∑1≤i≤n|i−pi|12∑1≤i≤n|i−pi|\frac{1}{2}\sum_{1\leq i \leq n} |i-p_i|，这和上面是等价的，可以通过打表找规律发现）n<=6e5A...
2018-08-21 22:17:13
556
原创 Trie上的后缀数组
亦称为广义后缀数组DefinitionLCS=Longest Common Suffix LCP=Longest Common Preffix SvSvS_v表示Trie上节点v到根的路径形成的字符串Intro由于在Trie上，自带去重功能 显然LCS(Su,Sv)=deplca(u,v)LCS(Su,Sv)=deplca(u,v)LCS(S_u,S_v)=dep_{lc...
2018-08-15 21:38:20
336
原创 【JZOJ 5746】一道比较强的 自然数幂和 板题
Description给定m,km,km,k，共TTT次询问，每次输入一个nnn，求∑ni=1ik∑i=1nik\sum_{i=1}^ni^k在 modmmodm\bmod m意义下的值 mmm的最大质因子≤3∗105≤3∗105\leq 3*10^5 2≤n,m,k≤1018,1≤T≤3∗1032≤n,m,k≤1018,1≤T≤3∗1032\leq n,m,k\leq 10^{18},1...
2018-05-28 22:16:33
281
原创 CTSC/APIO 2018 咕咕记
Preface省选结束后还能继续逃几天文化课的学习，还是很资瓷的 日期从5.6一直到5.14号，时间很长就不用Day x的形式了 本文大概是记录每天日程的流水账5.5坐车到广州机场附近住了一晚，一个人一间房体验极佳（除了经常有飞机飞过） 由于忘带电脑晚上基本上是看番度过的5.6早上的飞机，5.75.85.95.105.115...
2018-05-15 12:35:24
511
原创 GDOI 2018 绝望记
Preface考前的三轮模拟稳步前进，感觉状态调整不错 NOIP考了个竞争力很低的分数，所以进队只可能靠运气 目标大致是被卡校线？能Au就已经是超越自我了，省队毕竟太难在中山一中，我们也算是主场参赛。占据地利，每天可以回家休息。Day1看了座位表，左边坐着爷稳稳(yww)神犇，心态崩了 开场半个小时试机，先作死打了一发半年没打过的SA，因为记不得了打得很慢，20min终于...
2018-05-02 12:48:08
883
3
原创 HNOI 2018 游记
#前言为什么我又现在才写一个星期前的游记QAQ，马上都要自己省的省选了还来这里吹水。。。还有，这是今年第几次来长沙了？。。为什么一点紧张感都没有啊，吃枣药丸啊#Day0上午坐高铁出发，几乎全程补ditf+ 打sif酒店在长沙市中心，旁边就是雅礼，放眼望去发现雅礼占地面积真的小，却有着与面积不成比例的清北人数。。。可怕来的时候还有些下雨，下午顶着大风大雨跟着一堆人跑去五一广场浪，鞋子湿...
2018-04-23 12:33:19
255
原创 子树合并背包类型的dp的复杂度证明
状态形如f[x][j]f[x][j]f[x][j]表示xxx子树内选了jjj个，转移形如f[x][j+k]=∑f[x][j]∗f[y][k]f[x][j+k]=∑f[x][j]∗f[y][k]f[x][j+k]=\sum f[x][j]*f[y][k] 假设树上有n个点，第二维限制为k（最多选k个） 我们熟知，这样dp复杂度上界是n^2的。因为合并大小为a,b的子树复杂度是a*b，可以看成a子...
2018-04-08 16:48:51
6018
4
原创 3.27~3.31训练阶段性小结
3/27拉格朗日乘数法 解决：多元函数在一定条件下的极值问题设多元函数f(xi),满足条件g(xi)=0 则乘数函数F(xi,lamda)=f(xi)+lamda*g(xi) 当将xi看成未知数时，+号后面一项为0 对每个xi求偏导，都满足偏导为0 对lamda求偏导，也满足偏导为0（因为lamda偏导等于g(xi)，g(xi)=0） 因此可以列出若干方程，解方程得到lamda...
2018-03-31 22:25:09
342
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人