FUN WORLD

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 ...

回顾 基本数据类型 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，因为碰到大括号 ...

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 ...

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} ^ ...

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 和 ...

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 ...

Statement 给你一个长为 nnn 的序列 aia_iai​，mmm 次询问，每次询问给出 l,rl,rl,r，求 min⁡i,j∈[l..r]∧i≠j{∣ai−aj∣}\min_{i, j \in [l.. r] \land i \ne j}\{|a_i - a_j|\} i,j∈[l..r]∧i=jmin​{∣ai​−aj​∣} 数据范围：n≤105n \le 10^5n≤105，m≤3×105m \le 3 \times 10^5m≤3×105，0≤ai≤1090 \le a_i \le 10^90≤ai​≤109。 Solution 离线询问并按右端点升序排序，在 rrr 右移的过程中维护每个 lll 的答案。每次 r−1→rr - 1 \rightarrow rr−1→r 时，要加入 ara_rar​ 和前面的数的贡献。 下面考虑 ax≥ara_x \ge a_rax​≥ar​ 的情况，ax<ara_x < a_rax​<ar​ 的情况同理。 用主席树找到 [1..r−1][1.. r - 1][1..r−1] 中最大的 xxx 满足 ax≥a ...

T1. 假期计划 枚举 B, C 就行，预处理前三大的 A / D。时间复杂度 O(nm+n2)O(nm + n^2)O(nm+n2)。 T2. 策略游戏 按照 B 中是否有正负数分讨即可。 T3. 星战 判断的条件就是每个点出度都为 111。 给每个点随机一个权值 vali\text{val}_ivali​，对于每个点 vvv 维护 sv=∑(u,v)∈Evalus_v = \sum_{(u, v) \in E} \text{val}_usv​=∑(u,v)∈E​valu​，并维护 ∑sv\sum s_v∑sv​。每次检查 ∑sv\sum s_v∑sv​ 是否等于 ∑vali\sum \text{val}_i∑vali​ 即可。 感觉不稳的话就多随几次。 T4. 数据传输 k=2k = 2k=2 的时候中途的点不会跳出 sis_isi​ 到 tit_iti​ 的链上。矩乘加速是显然的。 k=3k = 3k=3 的时候中途的点可能会跳出 sis_isi​ 到 tit_iti​ 的链上，但是可以发现出去的点一定是这条链某个点的邻居。进一步可以发现，这个点一定是链上某个点所有 ...

Statement 有 nnn 根竹子，第 iii 根初始时高度为 hih_ihi​。你需要依次进行如下操作 mmm 轮： 重复 kkk 次，从 nnn 根竹子中选出一根，将它的高度减少 ppp。若当前 hi<ph_i<phi​<p，则将 hih_ihi​ 改为 000。 对于 ∀i∈[1..n]\forall i\in[1..n]∀i∈[1..n]，将第 iii 根竹子的高度增加 aia_iai​。 请你最小化所有操作结束时，最高的竹子的高度。 数据范围：n≤105n\le10^5n≤105，m≤5000m\le5000m≤5000，k≤10k\le10k≤10。 Solution 考虑二分答案后如何 check。不好做的是 hih_ihi​ 会改成 max⁡{hi−p,0}\max\{h_i-p,0\}max{hi​−p,0}。 尝试将整个函数向上平移，函数就变成了 hi+Δh_i+\Deltahi​+Δ 出发到 mid\text{mid}mid，一路上 hih_ihi​ 均 ≥0\ge0≥0。 因为最后时刻是确定的，因此倒序考虑，变成了『有 nnn 根 ...