几何计算笔记
凹凸多边形的判断重要知识：叉积几何意义：符号代表了叉积两个向量的转向： > 0 逆时针 < 0 顺时针 = 0 共线 基本原理对于连续三个点A、B、C：叉积 = (B.x - A.x) (C.y - B.y) - (B.y - A.y) (C.x - B.x)要是是向量的话是：a.x b.y- a.y b.x 这个叉积实际上计算的是向量 AB 到向量 BC 的旋转方向。 实现方法可视化解释考虑四边形$ABCD$，我们按顺序（如逆时针）检查每个顶点： 如果所有顶点的叉积都保持同号（全部为正或全部为负），说明多边形所有顶点都朝同一个方向”拐弯”，这就是凸多边形。 1234C(2,2) ────── D(0,2)│ ││ │B(2,0) ────── A(0,0) 在顶点A处： 向量DA = A - D = (0-0, 0-2) = (0, -2) 向量AB = B - A = (2-0, 0-0) = (2, 0) DA × AB = 0 0 - (-2) 2 = 4 > 0（逆时针） 在顶点B处： 向量A...
程C笔记
1. 头文件和命名空间C++ 中的 string 类定义在头文件 string 中，通常使用 std 命名空间。 123456s3=strcat(s1,s2);//加在后面int x=strcmp(s1,s2)//返回三种情况,见下面cout<<strlen(s1)<<endl;//输出的是长度，等同于s1.length()strcpy(s1+x1,s2+x2);//把前面的对应部分添加到前面去，完全覆盖之前的内容memcpy(a+x1,b+x2,sizeof(int)*8);//也是把后面的放到前面，只不过需要规定放入的内容sizeof(s1);//考虑后面的'\0'，比strlen大1. x=strcmp(s1,s2)= \begin{cases} -1 \ \ \ \ \ s1 \leq s2\\ 0\ \ \ \ s1=s2\\ 1\ \ \ \ s1 \geq s2 \end{cases}memcpy例子：12345int a[8]={1,2,3,4,5,6,7,8};int b[10]={...
定积分笔记
定义式\Sigma_{i=1}^nf(\xi_i)\Delta x_i几何意义曲线和x轴，直线$x=a$,$x=b$围成的面积 用定义式写简单积分例题：\int_0^1x^2\,dx首先先把$[0,1]$分成n等份，每份是$\frac{1}{n}$然后按照定义式，取$xi=\frac{i}{n},\xi_i=\frac{i}{n}$所以：$$\int_0^1x^2\,dx=\Sigma{i=1}^nf(\xii)\Delta x_i=\Sigma{i=1}^n(\frac{i}{n})^2·\frac{1}{n}=\frac{1}{n^3}\Sigma_{i=1}^ni^2=\frac{1}{n^3}\frac{1}{6}(n+1)(2n+1)=\frac{n(n+1)(2n+1)}{6n^3}=\frac{1}{3}$$最后记得对n取一下极限就行了 把极限改写成积分形式由于积分是可以转化为极限的，那么同样也可以反过来计算。 例题：这里需要弄清改把什么看作是$\xi_i$,什么又看做是$\Delta x_i$不过通常是取相同的数 1.\lim_{n\to \infty}\fra...
时空间复杂度笔记
2秒时间限制下的可执行操作数一般经验估算 保守估计：C++在2秒内可执行约 $210^8-410^8$ 次基本操作（加减、比较、赋值等） 实际表现： 简单循环操作：约$110^8-210^8$ 复杂操作（除法、取模、函数调用）：约$0.510^8-110^8$ 浮点运算：约$0.310^8-0.510^8$不同复杂度对应的最大数据规模123456789O(1) -> 几乎无限（>10^9）O(logn) -> 几乎无限（>10^9）O(n) -> 约 2×10^8O(nlogn) -> 约 2×10^7（2000万）O(n√n) -> 约 2×10^6（200万）O(n²) -> 约 2×10^4（2万）O(n³) -> 约 2×10^3（2000）O(2ⁿ) -> 约 n ≤ 25O(n!) -> 约 n ≤ 11 实战参考表 数据规模 可接受的复杂度 常见算法 n ≤ 10 任意（包括O(n...
容斥原理笔记
容斥原理的定义以及计算方式 容斥原理是十分有用的一种计算方法，通常用于子集统计中 该原理通过交替加减不同层次交集的大小，确保每个元素在并集中只被计算一次。虽然描述中的“只被两个集合重复的”可能指恰好属于两个集合的元素，但容斥原理实际处理的是所有交集（包含属于更多集合的元素），并通过后续的加减进行修正。 原理：整体减空白的思想，不过也有韦恩图的一点思想，当子集数量大于3时，就有些抽象了，这时我们就需要总结一下规律。基本公式 |A_1\cup A_2\cup ··· \cup A_n|=\Sigma|A_i|-\Sigma|A_i\cap A_j|+\Sigma|A_i\cap A_j\cap A_k|+(-1)^{n+1}|A_1\cap A_2 \cap ···\cap A_n| 先加上所有子集，再减去每两个子集的重叠部分，再加上每三个子集的重叠部分···最后再是所有子集的交集。重要观察：每一个求和前面的符号只和选择了几个集合有关，所以在写代码的时候就会变得简单了。代码实现 以题目Count Good Numbers为例：题目要求我们统计因子里不含2,3,5,7的所有在区间$...
前缀和笔记
前缀和定义 前缀和（Prefix Sum）是一种重要的预处理技术，能在O(1)时间内查询区间和，在算法竞赛和面试中应用广泛。以下是前缀和的主要应用场景和变种： 1. 基本前缀和 计算$\Sigma_{i=1}^n a_i$的值，用来求区间和 例如：1234567// 一维前缀和vector<int> pre(n+1, 0);for (int i = 1; i <= n; i++) { pre[i] = pre[i-1] + a[i];}// 查询区间[l, r]的和int sum = pre[r] - pre[l-1]; 2. 二维前缀和用于计算矩阵的和$\Sigma{i=1}^n\Sigma{j=1}^na_{ij}$ 12345678vector<vector<int>> pre(m+1, vector<int>(n+1, 0));for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { ...
DP笔记
DP题目的特点 数据较小，至少有一维是可以接受的，比如每一步的决策小于3，总数小于1000等等 每一步的答案可以由之前的答案得到，比如数字三角形 DP题目的大致做法设DP数组 明确DP数组的含义，保证每次求解的答案都是这个含义，不然就可能出错(这也是我之前的一大误区) 分类讨论 明确有几种决策方案，明确这一步的答案是怎么推断出来的(非常重要!!!) 接下来编写代码就行了 举例：迎新赛M题 题目传送门： ZJUTOJ | 2024ZJUT迎新赛-决赛-M. 三色小屋 题目理解： 首先发现每一步的方案数可以接受，并且这一步的答案只由上一步转移而来，所以可以使用DP 每个位置只能填R/G/B三种颜色，而且之和上一步和相邻的颜色有关，几种方案互不影响，符合动态规划的特点 分类讨论： 分为两大类，因为开头要初始化，所以单独讨论 dp[i][j] = \begin{cases} i==1\begin{cases} c[i]==\ '0' & \text{可以用的颜色为1} \\ c[i]\ !=\ \ '0' & \text{这个颜色为1} \end{ca...
ACM训练
简单题 对于简单题目，最好还是仔细一点，或者使用最暴力的解法，而不是投机取巧，或者构造高级方法，通常样例数据都是片面的，常常会有坑。 sleeping through classes 比如这一题，数据没有包含i+k中间有1的情况，直接i+=k导致错误。 中等题目 中等题目就需要强观察力和trick技巧了 Niko’s Tactical Cards 这一道题目是动态规划的变种，虽然要求每一步最优，但是可能发生最小值突然转变成最大值的情况，因此，计算最小值也是必要的。只要计算这两个值就行了。 Kanade’s Perfect Multiples 这题希望我们构造一个满足要求的B，这个就有点类似于筛法求素数了，实际上两者的代码几乎是一样的，但是在做的时候要注意区分原始数据和v数组，一个一个遍历就行了，找不到就可以直接退出，因为不然当前确定的最小值就无法被覆盖了。 Merging the Sets 你想选择其中的一些集合（可能一个都不选，也可能全部都选），使得 1 和 m 之间的每个整数都包含在个所选集合中的至少一个中。思维误区，不用一边读入一边判断，因为数据保证$l\leq 2*1...
第一类换元积分
重要公式基本积分公式：不要忘记加C!!! $\xi \ \delta \ \alpha \ \beta \ \pi \ \theta \ \in \ \notin$$\Delta$ $\int k \, dx = kx + C$$\int x^n \, dx = \frac{x^{n+1}}{n+1} + C \quad (n \neq -1)$$\int \frac{1}{x} \, dx = \ln|x| + C$ 指数函数：$\int e^x \, dx = e^x + C$$\int a^x \, dx = \frac{a^x}{\ln a} + C$ 三角函数：$\int \sin x \, dx = -\cos x + C$$\int \cos x \, dx = \sin x + C$$\int \tan x \, dx = -\ln|\cos x| + C$$\int \cot x \, dx = \ln|\sin x| + C$$\int \sec^2 x \, dx = \tan x + C$$\int \csc^2 x \, dx = -\cot x ...
有理函数积分
基本方法 凑成能第一类换元积分的式子 例如$\frac{1}{…}$类的部分分式分解有理函数积分适用条件 有理函数积分当被积函数是有理函数（两个多项式的商）时：$\int \frac{Q(x)}{P(x)}\,dx$其中 $P(x)$ 和 $Q(x)$ 都是多项式。 分母可因式分解 部分分式分解是处理有理函数积分的系统方法，特别适用于： 分母可明确因式分解 没有更简单的特殊技巧 需要精确解析表达式 当分母 $Q(x)$ 可以分解为一次因式和不可约二次因式的乘积时： 一次因式：$(x-a)$ 不可约二次因式：$(x^2+px+q)$，其中 $p^2-4q<0$具体分解规则对于一次因式 $(x-a)^k$： 对应部分为： \frac{A_1}{x-a}+\frac{A_2}{(x-a)^2}+···+\frac{A_k}{(x-a)^k}对于二次因式 $(x^2+px+q)^m$：\frac{B_1x+C_1}{x^2+px+q}+\frac{B_2x+C_2}{(x^2+px+q)^2}+···+\frac{B_mx+C_m}{(x^2+px+q)^...
