shicj's blog

概括一下 强连通分量 1234567if(!V[v]){ tarjan(v); low[u]=min(low[u],low[v]);}else if(vis[v]){ low[u]=min(low[u],dfn[v]);} 点双连通分量 123if(low[v]>=dfn[u]){ 记录一个答案;} 边双连通分量 123456if(low[v]>dfn[u]){ 把 u<->v 这条边删掉;}int main(){ 洪水填充找连通块;} 割点（割顶） 1还是寒假讲的，真的忘了当初怎么想的了…… Code 强连通分量 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc++.h>using...

0x00 题目翻译 有一个长度为 nnn 的序列 aaa 和 qqq 个询问，每个询问给出一个区间 l,rl,rl,r 要求查询最大的 mmm 使得这个区间里所有数字模 mmm 的结果相同（如果 mmm 可以取得无穷大，输出 000）。 0x01 解题思路 这里要求余数全部相同，这样入手不好分析，那么尝试反向思考：如果余数已经相同，mmm 已经确定，那么序列会有什么性质？ 设原序列为 a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​，那么可以表示为 k1m+x,k2m+x,⋯ ,knm+xk_1m+x,k_2m+x,\cdots,k_nm+xk1​m+x,k2​m+x,⋯,kn​m+x，其中 xxx 是那个相同的余数。 观察到每一项带有相同的 xxx，尝试将它消掉，可以将相邻两项做差，求出一个差分序列 bbb，即 $0,\vert a_1-a_2\vert ,\vert a_2-a_3\vert ,\cdots,\vert a_{n-1}-a_n\vert $，也就是 $0,\vert k_1-k_2\vert m,\vert...

第九课 立体几何 注：所有立体几何图片均来源于高中数学书A版必修2 1. 斜二测画法（画直观图） 常令坐标轴的夹角为 45°45\degree45°，遵循横不变，纵减半的原则，如图 面积关系：S′=24SS'=\dfrac{\sqrt{2}}{4}SS′=42​​S 2. 常用基本事实 基本事实1 过不在一条直线上的三个点，有且只有一个平面 A,B,CA,B,CA,B,C 三点不共线 且 A,B,C∈αA,B,C\in\alphaA,B,C∈α ⇒\Rightarrow⇒ α\alphaα 唯一 基本事实2 如果一条直线上的两个点在一个平面内，那么这条直线在这个平面内 A∈l,B∈lA\in l,B\in lA∈l,B∈l 且 A∈α,B∈αA\in\alpha,B\in\alphaA∈α,B∈α ⇒\Rightarrow⇒ l⊏αl\sqsubset\alphal⊏α 基本事实3 如果两个不重合的平面有一个公共点，那么它们有且只有一条经过该点的公共直线 P∈α,Q∈βP\in\alpha,Q\in\betaP∈α,Q∈β 且...

第八课 复数 1. 复数的定义 复数集 \C=\{a+bi\vert a,b\in\R\} 代数形式 z=a+biz=a+biz=a+bi aaa 称为实部 Re(z)=aRe(z)=aRe(z)=a bbb 称为虚部 Im(z)=bIm(z)=bIm(z)=b iii 称为虚数单位 i2=−1i^2=-1i2=−1 b=0b=0b=0 为实数 b≠0b\neq 0b​=0 为虚数（a=0a=0a=0 为纯虚数） 几何形式：复平面 复数与复平面上的点、平面向量一一对应 模 z=a+biz=a+biz=a+bi ∣z∣=a2+b2\vert z\vert=\sqrt{a^2+b^2}∣z∣=a2+b2​ 共轭复数 实部相同，虚部互为相反数的复数互为共轭复数 z=a+biz=a+biz=a+bi z‾=a−bi\overline{z}=a-biz=a−bi 共轭复数的性质 ∣z∣=∣z‾∣\vert...

...

第七课 平面向量 1. 向量基础知识 定义 向量：既有大小，又有方向的量 数量：只有大小，没有方向的量 零向量：长度为 000 的向量，表示为 0⃗\vec{0}0，方向任意 单位向量：长度等于 111 个单位的向量，即 ∣a⃗∣=1\vert\vec{a}\vert=1∣a∣=1 相等向量：长度相等且方向相同的向量 相反向量：长度相等且方向相反的向量，即 a⃗+b⃗=0⃗\vec{a}+\vec{b}=\vec{0}a+b=0 平行向量：方向相同或相反的非零向量，零向量与任何向量平行，没有传递性 向量的表示 几何表示（有向线段） 小写字母（a⃗\vec{a}a） 坐标（a⃗=(x,y)\vec{a}=(x,y)a=(x,y)） 2....

...

第二章 排列与组合 四个基本计数原理 加法原理 将集合 SSS 划分为两两不相交的集合 S1,S2,⋯ ,SmS_1,S_2,\cdots,S_mS1​,S2​,⋯,Sm​，则 SSS 的对象数目可以通过确定它的每一个部分的数量并如此相加而得到： ∣S∣=∣S1∣+∣S2∣+⋯+∣Sm∣\vert S\vert=\vert S_1\vert+\vert S_2\vert+\cdots+\vert S_m\vert ∣S∣=∣S1​∣+∣S2​∣+⋯+∣Sm​∣ 乘法原理 令 SSS 是对象的有序对 (a,b)(a,b)(a,b) 的集合，第一个对象 aaa 来自大小为 ppp 的一个集合，而对于 aaa 的每一个选择，对象 bbb 有 qqq 种选择，于是，SSS 的大小为 p×qp\times qp×q： ∣S∣=p×q\vert S\vert=p\times q ∣S∣=p×q 减法原理 令 AAA 是一个集合，而 UUU 是包含 AAA 的更大的集合，设 A‾=U∖A={x∈U:x∉A}\overline{A}=U\setminus A=\{x\in...

dfn DFS序 low 向前可以到达的dfn最小的点 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;vector<int>G[50001];int n,m,tot,at;bool vis[50001],V[50001];int dfn[50001];int low[50001];vector<int>ans[50001];stack<int>s;void tarjan(int u){ s.push(u); vis[u]=true; dfn[u]=++tot; low[u]=dfn[u]; for(auto...

第六课 三角函数 123456789101112131415161718192021目录 [用 Ctrl+F 快速找到要找的内容]6.三角函数 6.1.任意角与弧度制 6.1.1.度量角的大小 6.1.2.角的分类 6.1.3.扇形 6.2.三角函数 6.2.1.定义 6.2.2.定义域与符号 6.2.3.同角三角函数之间的关系 6.2.4.诱导公式 6.2.5.图像与性质 6.2.6.图像变换 6.3.三角函数公式 6.3.1.和差角公式 6.3.2.二倍角公式 6.3.3.降幂公式 6.3.4.辅助角公式 6.3.5.常见的三角不等式 6.3.6.积化和差公式 6.3.7.和差化积公式 1. 任意角与弧度制 度量角的大小 角度制、弧度制 对于角度制的 n∘n^\circn∘ ，它所对的弧度制 α\alphaα 满足： α=lr=nπ180\alpha=\dfrac{l}{r}=\dfrac{n\pi}{180}α=rl​=180nπ​ 在一个半径为 rrr，圆心角为...