Jason Fan.

题意简述 给你一个 nnn 个点的树，mmm 次询问，每次询问删除 x,yx,yx,y 两子树后树的重心。 n,m≤100000n,m \le 100000 n,m≤100000 题解 一个很烂的正解，别看了 官方题解 std.cpp: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152 ...

92ce3867a25b048540c10275d83b5b1f6d70767663e8cb54fbcaac59a66ae62ee3c49b1e1d56c7f1d6fc7b05e0454beacc5edccf68f7a02c07c92e0b08970839d33e6c63d47c3b966bbc5096e809f6012f4f81d47a27782da866e7e92075602225e4421f15981d37e4334e3162097ab9de1777c41cac4d453e57a4f230f27e673c1cda738e537ac7b1c320bb0670e71add66742ee15484fb322c2bee67463cfd9d2c0d5512ccec58701a72df03cd7d6243cdf3cdb72bd340e667e051fc98ceac3cd676ffcde4c48acb5887081c860ada11575311415737d16227f465924c280787005e44b94f7ae4bc55bdf3d0ba02f609f46fc6cb5597b50 ...

[NOIP2020] 微信步数 暴力 先定义走完一次 1∼n1\sim n1∼n 的步骤为一轮。 考虑所有点一起按照步骤走下去，每步可能会使原本存在的点出界。我们维护每步后剩余的点，累加即可。具体地，每个维度互不干扰，且对与一个维度而言，删除的必然是从左一段连续的区间和从右一段连续的区间，若在该步下维度 iii 剩下 [li,ri][l_i,r_i][li​,ri​] ，那么剩余的总点数为 ∏i=1k(ri−li+1)\displaystyle\prod_{i=1}^{k} (r_i-l_i+1)i=1∏k​(ri​−li​+1) 。 我们只要一步一步模拟即可，直到没有点剩余。另外判断无穷步：在第一轮后回到起点且还有点剩余。 复杂度为 O(Tnk)O(Tnk)O(Tnk) ，其中 TTT 为最多跑了几轮。 CODE 1234567891011121314151617181920212223242526272829303132333435363738394041typedef long long ll;const int N = 500010;const int M = 16;const ...

给你 n+1n+1n+1 个点，求穿过它们的 nnn 次多项式。于是你想到了待定系数高斯消元，不过这 O(n3)O(n^3)O(n3) 的太烂了。于是我们引入拉格朗日插值法，通过构造法整出多项式。 拉格朗日插值法 记这 n+1n+1n+1 个点为 (x0,y0),(x1,y1),(x2,y2),…,(xn,yn)(x_0,y_0),(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) (x0​,y0​),(x1​,y1​),(x2​,y2​),…,(xn​,yn​) 定义拉格朗日基本多项式 ℓi(x)\ell_i(x)ℓi​(x) ℓj(x)=∏i≠jx−xixj−xi\ell_j(x)=\prod_{i\ne j}\frac{x-x_i}{x_j-x_i} ℓj​(x)=i=j∏​xj​−xi​x−xi​​ 很容易发现一个性质： ∀i≠j:ℓj(xi)=0\forall i\ne j :\ell_j(x_i)=0 ∀i=j:ℓj​(xi​)=0 ℓj(xj)=1\ell_j(x_j) =1 ℓj​(xj​)=1 于是我们得到拉格朗日插值多项式为： L(x)=∑j ...

计算几何？ 题意简述 给你 nnn 个点 pi=(xi,yi)p_i=(x_i,y_i)pi​=(xi​,yi​) ，问你有多少条过原点的直线满足：所有点在该直线上的投影呈轴对称。若有无穷个直线输出 −1-1−1 。 题解 考虑我们有一条直线 y=kxy=kxy=kx ，为了避免误差我们用向量表示 (a,b),k=ba(a,b),k=\dfrac{b}{a}(a,b),k=ab​ 。 考虑 nnn 个点在该直线上的投影，可以用 点积，考虑其几何意义：从原点到某点 pip_ipi​ 的向量在直线上的投影 乘上 向量 (a,b)(a,b)(a,b) 的长度。这可以表示每个点在直线上投影的相对位置。 我们已经把二维转化成一维了，接着要满足 nnn 个数在数轴上对称。若对称必然存在一个中心点为所有点的平均值，即 o=1n∑i=1naxi+byio = \frac{1}{n}\sum_{i=1}^n ax_i+by_io=n1​∑i=1n​axi​+byi​ ，易得其在二维平面上的点为 O(∑i=1nxin,∑i=1nyin)O\left(\dfrac{\sum_{i=1}^n x_i}{n} ...

初赛知识点，时间复杂度分析

CQOI2011 - 放棋子 题意 给你一个 n×mn\times mn×m 的棋盘，和 ccc 种颜色的棋子，每种棋子有 aia_iai​ 个。要求将所有棋子放到棋盘上，满足不同颜色棋子不能同行或同列。输出方案数，对 109+910^9+9109+9 取模。 1≤n,m≤30,1≤c≤10,∑ai≤max⁡(250,n×m)1\le n,m\le 30,1\le c\le 10, \sum a_i \le \max(250, n\times m) 1≤n,m≤30,1≤c≤10,∑ai​≤max(250,n×m) 题解 设计 DP 状态 f(i,j,k)f(i,j,k)f(i,j,k) 表示用了 1∼k1\sim k1∼k 种颜色的所有棋子，选了 iii 行 jjj 列填充的方案数。因为不同颜色棋子不能同行或同列，考虑枚举新颜色的棋子占了几行几列，这对原来棋子是无影响。 f(i,j,k)=∑l=0i−1∑r=0j−1(n−li−l)(m−rj−r)f(l,r,k−1)g(i−l,j−r,ak)f(i,j,k)=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}\bino ...

HEOI2013 SAO 题意 给出一颗边有方向的树，求该图的拓扑序数量。 n≤1000,mod=109+7n\le 1000,mod= 10^9+7n≤1000,mod=109+7 题解 f(u,i)f(u,i)f(u,i) 表示以 uuu 为根的子树，uuu 子树内排名为 iii 的方案数。 考虑转移，枚举 v∈son(u)v\in son(u)v∈son(u) ，将 f(v,j)f(v,j)f(v,j) 合并到 f(u,i)f(u,i)f(u,i)，（两列数，各自顺序不打乱的合并） vvv 在 uuu 前 再枚举 vvv 子树中有 k(k≥j)k(k\ge j)k(k≥j) 个排在 uuu 前面，对 f(u,i+j)f(u,i+j)f(u,i+j) 累加。 f(u,i+k)′←f(u,i+k)+(i+k−1i−1)(sizu+sizv−i−ksizv−k)f(u,i)f(v,j)f(u,i+k)' \gets f(u,i+k)+\binom{i+k-1}{i-1}\binom{siz_u+siz_v-i-k}{siz_v-k}f(u,i)f(v,j) f(u,i+k ...

笛卡尔树，树形dp。 SP3734 PERIODNI 题意 给定一个 NNN 列的表格，每列的高度各不相同，但底部对齐，然后向表格中填入 KKK 个相同的数，填写时要求不能有两个数在同一列，或同一行，下图中 b 是错误的填写， a 是正确的填写，因为两个 a 虽然在同一行，但它们中间的表格断开。 1≤N,K≤500, hi≤1061\le N,K \le 500,\,h_i\le 10^6 1≤N,K≤500,hi​≤106 题解 先考虑一个 n×mn\times mn×m 的矩形，选 kkk 个格子，不能出现同行同列的方案数。 (nk)×(mk)×k!\binom{n}{k}\times \binom{m}{k} \times k! (kn​)×(km​)×k! 考虑原题，因为连续的一行内只能放一个，所以可从下到上做如下切割（当前区间 [l,r][l,r][l,r] 选择区间最小的 hxh_xhx​，一刀切，得到左右两个独立的块 [l,x−1][l,x-1][l,x−1] 和 [x+1,r][x+1,r][x+1,r]。重复即可）。这个操作实际上对区间建笛卡尔树，树上每个节点对应一 ...

92ce3867a25b048540c10275d83b5b1faff7d55fde65ccf7bbd5bff198b17deb8102ef54f5b3ba935ae113d351b47be3c849f32dbfb8ec2b972d2e3ef8f17396813c853fc1e97b9cbcf816613122df16bee929042187fd9d4cb0f8f5f8f7f611b1ccfbbf83d8992402ec81aee116f7724ed6526339961267bf1c73e22068a89cbe01f4e1548333be59f061a87bbd661c7495018c91367ba6a7b5a2b4ca4b5b852a0fab072b5976454606af52b871ba39e6c8d497aba73783a92af47e02fd2506d368e0b2b47548144a9bf0a8ec32d5cd5b3197014d04611661d309a11c772ede6d279a78d1f35e729106fd7d45b7da5ac24d186dd0696980b ...