dp：ICPC2025沈阳D
dp：ICPC2025沈阳D LED Display Renovation - Problem - QOJ.ac 感觉这种题就是思维难度不高，但是细节很多，考场上很难在短时间内写出来，反正对目前的我来说场上写出来很难，赛后补不难 我们考虑设三个dp： f(i,j,0/1)f(i,j,0/1)f(i,j,0/1)（有两项 xxx 和 cntcntcnt）：前 iii 位，用 jjj 次，是否可以表示出全空下：最多表示出多少个数，同时有多少个方案。 F(i,j)F(i,j)F(i,j)：前 iii 位用 jjj 次，有多少种方案可以前面全空 G(i,j)G(i,j)G(i,j)：前 i...
Calculus - Limit 做题简记1
Calculus - Limit 做题简记1 T1：函数极限的一些求法 2.48 - 4 limx→1x3−1x2+e1x−1\lim_{x\to 1}\frac{x^3-1}{x^2+e^{\frac 1{x-1}}} x→1limx2+ex−11x3−1 犯错之处：采用了乘 ex−1e^{x-1}ex−1，但指数是相加不是相乘，导致出错 Squeeze Theorem中的绝对值法 上界是很好放的，但下界我们不能说明其 ≥0\ge 0≥0 我们的方法是，我们先求 ∣x3−1x2+e1x−1∣|\dfrac{x^3-1}{x^2+e^{\frac 1{x-1}}}|∣x2+...
均摊+推简单数论：ICPC2025沈阳A
均摊+推简单数论：ICPC2025沈阳A Square Kingdom - Problem - QOJ.ac 令 i>ji>ji>j，考虑 (i+ba)2−(j+ba)2=(i−j)(i+j+2ba)=(i−j)(ai+aj+2b)a\begin{align*}\left(i+\dfrac b a\right)^2-\left(j+\dfrac b a\right)^2 &= (i-j)\left(i+j+\dfrac {2b}a\right)\\ &=\dfrac{(i-j)(ai+aj+2b)}{a} \end{align*} (i+ab)2−...
Python Input & Output
Python Input & Output Input reads one line from stdin and returns a str Get an integer : s=int(input()) The usage of Prompt: EOF EOF = End of File 当读到EOF，input()会报出 EOFError，比如： 123456# 假设这段代码在等待输入try: s = input("请输入内容: ") print("你输入了:", s)except EOFError: print(...
Honors Calculus I - 2.3 Continuity
Honors Calculus I - 2.3 Continuity Continuous Functions fff is said to be continuous at aaa if limx→af(x)=f(a)\lim_{x\to a}f(x)=f(a)limx→af(x)=f(a) ε−δ\varepsilon-\deltaε−δ definition: For every ε>0\varepsilon >0ε>0, there exists a δ>0\delta >0δ>0 such that 0<∣x−a∣<δ0&l...
二阶差分生成函数优化dp + NTT + cdq优化NTT：CCPC2026网络赛G
二阶差分生成函数优化dp + NTT + cdq优化NTT：CCPC2026网络赛G Growing Prefix Span - Problem - QOJ.ac 哭了，这道题调了10多个小时，打了无数个补丁，终于调出来了 好，首先一开始肯定是要处理一下 [Li,Ri][L_i,R_i][Li,Ri]，变成合法区间，然后判断一下无解。 然后我们可以列一个很显然的 O(n2)O(n^2)O(n2) 的dp。f(i,j)f(i,j)f(i,j) 代表前 iii 个数长为 jjj，显然有： f(i,j)=f(i−1,j)×(j−i+1)+2∑k<jfi−1,kf(i,j)=f(...
Learning Reflection on Linear Algebra (Mostly about dimensions)
Learning Reflection on Linear Algebra (Mostly about dimensions) For a m×nm\times nm×n matrix, it has \rank A\le m If we need to know the minimum of dimNul A\dim \text{Nul}\;AdimNulA, it is same to know the maximum of \rank A. Row Operation will change Col A\text{Col}\; AColA , but not \rank...
![[Chapter 2 Summary] of Linear Algebra](https://raw.githubusercontent.com/zhangxixi2008/img/main/2026Q420261006154840443.jpg)
[Chapter 2 Summary] of Linear Algebra
[Chapter 2 Summary] of Linear Algebra Chapter 2 Matrix Algebra 1. Matrix Operations Diagonal entries a. Multiplication Definition: AB=A[b1 b2 … bp]=[Ab1 … Abp]AB = A[b_1 \ b_2 \ \dots \ b_p] = [Ab_1 \ \dots \ Ab_p]AB=A[b1 b2 … bp]=[Ab1 … Abp] Interpretation: AAA column is a linear combina...
整除分块 + 哈夫曼树优化：CCPC2026网络赛L
整除分块 + 哈夫曼树优化：CCPC2026网络赛L Logging Compression - Problem - QOJ.ac 这题其实就是让你实现哈夫曼树。 我们首先考虑压缩信息。如果一段区间每个数出现是相同的，我们就可以合并来存储他们。那样子在优先队列里我们记两个值：当前值 sss + 有多少个数是这样的 nnn。 我们考虑我们在小根堆里取出来的第一个东西，其 n≥2n\ge 2n≥2，那样子其实本质上有 $\lfloor\dfrac n 2\rfloor $ 对自己和自己合并。那我们直接把 (2s,⌊n2⌋)(2s,\lfloor\dfrac n 2\rfloor )(2s,⌊...
分治 + 计算几何 + 闵可夫斯基和：ABC478G
分治 + 计算几何 + 闵可夫斯基和：ABC478G G - Division Point Hull 考虑用坐标点来表示 Qi,jQ_{i,j}Qi,j: Qi,j=qp+qPi+pp+qPjQ_{i,j}=\frac q{p+q}P_i+\frac p {p + q}P_j Qi,j=p+qqPi+p+qpPj 我们考虑分治来处理。先递归得到左右两边 QQQ 组成的凸包 QL,QRQ_L,Q_RQL,QR 我们现在需要得到跨区间 QQQ。根据上面的式子，我们发现其实我们只需要得到左右两边 PPP 组成的凸包，然后左边缩小到 qp+q\dfrac q{p+q}p+qq...
