工程概率统计 学习笔记
Chapter 1. Basis
Basic Concepts
Random Experiment (随机试验)
Sample Point ω\omegaω (样本点): Each possible fundamental outcome.
Sample Space Ω\OmegaΩ (样本空间): A set that includes all sample points.
Random Event (随机事件): A subset of Ω\OmegaΩ.
Inclusion: A⊂BA \subset BA⊂B.
Sum / Union: A∪BA \cup BA∪B, A+BA + BA+B.
Product / Intersection: A∩BA \cap BA∩B, ABABAB.
Difference: A−BA - BA−B, A∖BA \setminus BA∖B.
Mutually Exclusive / Disjoint (互斥): A∩B=∅A \cap B = \varnothingA∩B=∅.
Complement (对立, 互补): A∩B=∅∧A ...
计算机网络 学习笔记
Chapter 1. Introduction
Internet
Network Edge: Hosts (主机) = End systems, e.g., phones, PC.
Normally, applications run only in network edge, rather than network core.
Network Core interconnects end systems, including:
Communication Links: Fiber, Copper, Radio, Satellite. Transmission rate: bandwidth (带宽).
Packet Switches: Routers (路由器), Switches (交换机).
Internet Service Provider (ISP, 互联网服务提供商): e.g., 中国电信, 中国移动.
Protocols (协议): HTTP (Web), streaming video, Skype, TCP/IP, WiFi, 4G, Ethernet. ...
数字逻辑 学习笔记
Number Systems
Digital Number Systems (Radix-rrr System)
Decimal (十进制)
Binary (二进制):
Octal (八进制): 00, 05, 013.
Hexadecimal (十六进制): 0x0, 0x9A, 0xCB.
Complements 补码
Diminished Radix Complement (反码): (r−1)(r - 1)(r−1)’s Complement
For Decimal System, DRC of 121212 can be 878787, 987987987…
For Binary System, it’s just a bitwise not (按位取反).
Radix Complement (补码): rrr’s Complement
For Decimal System, RC of 121212 can be 888888, 988988988…
For Binary System, equals to DRC +1+ 1+1.
Subtracti ...
线性代数 学习笔记
Chapter 1.
线性方程组 Linear System
相容（Consistent）：线性方程组有至少一组解。
行观点 Row Picture：方程组相容，则直线 / 平面相交。
列观点 Column Picture：列向量的和（线性组合）：uα⃗+vβ⃗+wγ⃗=b⃗u \vec\alpha + v \vec\beta + w \vec\gamma = \vec buα+vβ+wγ=b。
非奇异（Nonsingular）：线性方程组恰有一组解。
等价线性方程组（Equivalent Systems）：有相同解集的线性方程组。
高斯消元法
基本操作：
任意改变两行顺序。
同行乘以非零数。
某一行乘上一个非零数后加到另一行上。
不断进行操作 1、3，直到消为上三角矩阵，代入。
矩阵 Matrix：
A=[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn]=(aij)m×nA = \begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} ...
数理逻辑导论 学习笔记
Intro
History
Reduction to Absurdity 归谬法:
从一个主张推出了矛盾，则这个主张是错的。
Syllogism 三段论:
Major premise
Minor premise
Conclusion
The Validity of Reasoning:
Truth for statements
Validity for arguments / reasoning (推理过程)
Early Phase:
Natural language is not reliable for logical reasoning.
We need a “universal language”, “calculus of reasoning”
Development:
Propositional Logic (PL, 命题逻辑)
First-Order Logic (FOL, 一阶逻辑)
Introduction to Reasoning
Logic studies forms of reasoning.
Le ...
Java A 考前复习
回顾
基本数据类型
888 个，String 不是哦！
变量名命名规则
只能包含字母、数字、下划线、美元符号，且不能以数字开头。
编译
Java 源代码（.java 文件）-> 字节码（.class 文件）。字节码（bytecode）是一种中间代码，与平台（操作系统）无关，能被 Java 虚拟机（JVM）执行。
编译并运行：java Main.java arg0 arg1 arg2 ...，其中 arg0 arg1 arg2 ... 是 main 方法的参数，也就是 public static void main(String[] args) 中的 args 数组。
编译：javac Main.java。
运行：java Main arg0 arg1 arg2 ...。
printf 方法
switch-case
case 后的值必须是编译期已知的常量，不能使用变量或表达式。
如果省略 break，代码会继续执行下一个 case，称为贯穿（fall through）。而 default 可以没有 break，因为碰到大括号 ...
CF1476F. Lanterns
Statement
nnn 个灯笼排成一排，第 iii 个灯笼具有 pip_ipi 的亮度。每个灯笼要么朝向左，照亮左边编号为 [i−pi,i−1][i − p_i, i − 1][i−pi,i−1] 的灯笼；要么朝向右，照亮右边编号为 [i+1,i+pi][i + 1, i + p_i][i+1,i+pi] 的灯笼。
请你为所有的灯笼确定朝向，使得每一个灯笼至少被另外一个灯笼照亮，或判断无解。
数据范围：n≤3×105n \le 3 \times 10^5n≤3×105。
Solution
神仙 DP。
把可行性问题转化为最优性问题，设 f(i)f(i)f(i) 表示前 iii 个灯笼能覆盖的最长前缀。
转移考虑第 iii 个灯笼的朝向。如果向右，那么
f(i)={f(i−1),f(i−1)<imax{f(i−1),i+pi},f(i−1)≥if(i) = \begin{cases}
f(i - 1), &f(i - 1) < i \\
\max\{f(i - 1), i + p_i\}, &f(i - 1) \ge i
\en ...
CF840C. On the Bench
Statement
给你一个长度为 nnn 的序列 aia_iai。问有多少 1∼n1 \sim n1∼n 的排列 pip_ipi，满足 ∀i∈[2..n]\forall i \in [2.. n]∀i∈[2..n]，有 api−1×apia_{p_i − 1} \times a_{p_i}api−1×api 不为完全平方数。答案对 109+710 ^ 9 + 7109+7 取模。
数据范围：n≤300n \le 300n≤300，1≤ai≤1091 \le a_i \le 10 ^ 91≤ai≤109。
Solution
每个数去掉平方因子后，条件等价于没有两个相等的数相邻。
Algorithm 1
把相同的数分类，假设共 mmm 种不同的数，其中第 iii 种有 cic_ici 个。记 f(i,j)f(i, j)f(i,j) 表示填入前 iii 种数，有 jjj 对相同的数相邻的方案数；g(i,j)g(i, j)g(i,j) 表示将第 iii 种数拆分成块内块间均有序的 jjj 块的方案数。下面设 si=∑j=1icjs_i = \sum_{j = 1} ^ ...
CF888F. Connecting Vertices
Statement
有一个正 nnn 边形，顶点顺时针编号为 1∼n1\sim n1∼n。问用 n−1n-1n−1 条边连接这 nnn 个顶点，使它们连成一棵树，有多少种方法。
连边时有以下限制：
给出一个 n×nn\times nn×n 的 01 矩阵 AAA，Ai,j=1A_{i,j}=1Ai,j=1 表示顶点 iii 和顶点 jjj 可以直接相连，而 Ai,j=0A_{i,j}=0Ai,j=0 时则不能。保证 Ai,i=0A_{i,i}=0Ai,i=0，Ai,j=Aj,iA_{i,j}=A_{j,i}Ai,j=Aj,i。
两条线段不能在顶点之外的地方相交，如不能同时连 (1,3)(1,3)(1,3) 和 (2,4)(2,4)(2,4)。
数据范围：n≤500n\le500n≤500。
Solution
计数 DP 的一般套路是要构造一个“不可划分的整体”。—— sol1
考虑区间 DP，因为如果 iii 和 jjj 有边，则 i+1∼j−1i+1\sim j-1i+1∼j−1 中不可能有连出去的边。
记 f(i,j)f(i,j)f(i,j) 表示 iii 和 ...
P7044. [MCOI-03] 括号
Statement
定义一个括号串的 000 级偏值为将该括号串修改为合法括号串需要的最小操作数。一次操作你可以在一个位置添加一个括号或删除一个位置的括号。
定义一个括号串的 iii（1≤i≤n1 \le i \le n1≤i≤n）级偏值为该串所有子串的 i−1i - 1i−1 级偏值之和。
给你一个长度为 nnn 的括号串 sss 和一个正整数 kkk，求 sss 的 kkk 级偏值。答案对 998244353998244353998244353 取模。
数据范围：1≤n,k≤1061 \le n, k \le 10 ^ 61≤n,k≤106。
Solution
下面的 kkk 在题面的基础上 −1-1−1。
将一个括号串修改为合法括号串需要的最小操作数，等于它不匹配的括号个数。
一个子串的 000 级偏值中，一个左括号有贡献，一定是没有与之匹配的右括号。右括号同理。
那么一个子串 s[l:r]s[l : r]s[l:r] 的贡献就是 (l−1+kk)⋅(n−r+kk)⋅f(s[l:r])\binom{l - 1 + k} k \cdot \binom{n - r + k} k ...