https://wiki.cvbbacm.com/ 2026-04-30T03:43:13+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2021-03-06T10:58:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E7%BB%93%E8%AE%BA_1&rev=1614999519&do=diff 结论 1 1、树上最远距离 树上到每个点距离最远的距离一定为树上一条直径的两个端点之一。 分别从两个端点开始 $\text{dfs}$ 即可 $O(n)$ 求取每个点的树上最远点。 证明见 链接 或者可以考虑树形 $\text{dp}$，第一次 $\text{dfs}$$\text{dfs}$$v$$v$$u=fa(v)$$v$$edge(u,v)$$v$$u$$v$$u$$2\times edge(u,v)$$\text{dfs}$$u_1,u_2,u_3\cdots u_k$$\text{dis}(u_1,u_2)+\text{dis}(u_2,u_3)+\cdots\text{dis}(u_{k-1},u_k)+\text{dis}(u_k,u_1)$$v$$\text{dfs}$$v$$u_i,u_{i+1}$$\text{dis}(u_i,v)+\text{dis}(v,u_{i+1})-\text{dis}(u_i,u_{i+1})$$\sum_{i=1}^n i=m$$(n,m)=(1,1),(24,70)$$n$$1\sim n$$i$$$p=\frac{C_… text/html 2021-05-23T09:22:06+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E7%BB%93%E8%AE%BA_2&rev=1621732926&do=diff 结论 2 1、点对最远距离 给定 $n$ 个数，要求将 $n$ 个数进行排列，使得所有数值相同的点对的距离的最小值尽量大。 答案为 $\lfloor \cfrac {n-\text{cnt}}{\text{maxfreq}}\rfloor$，其中 $\text{maxfreq}$ 为相同数值的数出现的最大频率，$\text{cnt}$ 为出现频率为 $\text{maxfreq}$ 的数值的个数。$\text{maxfreq}$$a,b,c$$a,b,c,\ldots.a,b,c,\ldots.a,b,c,\ldots a,b,c$$a,b,c,1,4,7,10,a,b,c,2,5,8,11,a,b,c,3,6,9,a,b,c$$n$$m$$a_1\le a_2\le \cdots \le a_n$$a_1+a_2+\cdots a_n=m$$i$$a_1\sim a_i$$j$$i$$$\sum_{j=0}^{\infty} x^{ij}=\frac 1{1-x^i}$$$$[x^n]\prod_{i=1}^m \frac 1{1-x^i}$$$\text{dp}$$\text… text/html 2021-08-09T20:50:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E7%BB%93%E8%AE%BA_3&rev=1628513433&do=diff 结论 3 1、等差序列判定 给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。 等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。 证明：设 $g=\text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。 由于 $g\mid a_{i+1}-a_i,a_{i+2}-a_{i+1}\cdots a_j-a_{j-1}$，所以 $g\mid a_j-a_i$，得 $\text{gcd}(g,a_j-a_i)=g$。 于是 $g=\text{gcd}(a_i-a_j)(1\le i,j\le n)$。将 $a_i$ 从小到大排序得到 $b_1,b_2\cdots b_n$ ，则 $$ g\le \text{gcd}(b_2-b_1,b_3-b_2\cdots b_n-b_{n-1})\le \min(b_2-b_1,b_3-b… text/html 2020-08-01T10:17:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E9%94%99%E9%A2%98%E9%9B%86_1&rev=1596248241&do=diff 错题集 1 1、Fake Maxpooling 链接 题意 给定一个 $n\times m$ 矩阵，$a_{i,j}=\text{lcm}(i,j)$，设 $f(i,j)=\{\max a_{x,y}|i\le x\lt i+k,j\le y\lt j+k\}$，求 \begin{equation}\sum_{i=1}^{n-k+1}\sum_{j=1}^{m-k+1}f(i,j)\end{equation} 题解 记忆化搜索求 $\text{gcd}$，两次单调队列维护最大值。 第一次单调队列维护每行长度为 $k$ 的区间的最大值，第二次单调队利用 $k$ 列每行长度为 $k$$O(nm)$$2\times n$$1\sim n$$-1$$2$$0$$1$$0$$0$$1$$1\sim n$$n$$4$$6$$\text{dp}$$6$$1,2,\cdots n$$k$$k$$m$$t$$t\bmod m$$k$$k^{-1}\bmod m$$k\ast k^{-1}\equiv 1\bmod m$$n$$A,B$$A,B\subset \{1,2,\cdots n\… text/html 2020-08-09T00:16:40+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E9%94%99%E9%A2%98%E9%9B%86_2&rev=1596903400&do=diff 错题集 2 1、Ancient Distance 链接 题意 给一个有根树，在树上选择 $k$ 个关键点(根必须选)，使得所有点到最近关键祖先(可以是自己)距离的最大值最小。 求出 $k$ 分别为 $1\sim n$ 时答案的和。 题解 考虑贪心，假设已知最小距离为 $d$$d$$d$$d$$d$$O(\frac nd)$$O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$$O(\log n)$$O\left(n\log^2 n\right)$$a_i$$b_i$$val_i=b_i\ast$$i$$a_i$$b_i$$val_i$$mex$$a$$c_i$$a$$b_i=a$$val_i$$a,2a\cdots c_ia$$c_i$$\sum_{i=1}^n c_i=n$$i$$val_i$$O(n^2)$$\text{bitset}$$O(n^3)$$O(n^2)$$a_1,a_2\cdots a_n$$F(l,r)=a_l\text{&} a_{l+1}\text{&} \cdots a_r$$S(l,r)=\{l\le a\le b\… text/html 2020-08-31T18:12:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E9%94%99%E9%A2%98%E9%9B%86_3&rev=1598868778&do=diff 错题集 3 1、The Escape Plan of Groundhog 链接 题意 给定一个 $n\times m$ 的 $01$ 矩形，求满足下列条件的子矩阵数目： * 该子矩形的边界上没有 $0$ * 该子矩形中内部(即不含边界)的 $01$ 个数差不超过 $1$ * 该子矩形的长宽大于 $1$$O(n^2)$$O(n)$$1$$1$$0$$-1$$1$$O(n^3)$$n$$\frac 12$$\text{X}$$[x_1,x_2\cdots x_{m+1}]$$[x_i,x_{i+1}]$$y_i$$\cfrac {(y_l+y_{l+1}+\cdots +y_r)(y_l+y_{l+1}+\cdots +y_r)}{2^n}$$y_l\cfrac {y_l+y_{l+1}+\cdots +y_r}{2^n}+y_{l+1}\cfrac {y_l+y_{l+1}+\cdots +y_r}{2^n}+\cdots +y_r\cfrac {y_l+y_{l+1}+\cdots +y_r}{2^n}$$[x_i,x_{i+1}]$$[x_i,x_{i+1}]$… text/html 2021-02-28T19:08:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E9%94%99%E9%A2%98%E9%9B%86_4&rev=1614510527&do=diff 错题集 4 1、小V的序列 链接 题意 给定一个长度为 $n$ 的序列，保证序列中每个数取值随机。 接下来给定 $m$ 个询问，每次给定一个数 $b$，问序列中是否存在数与 $b$ 异或后二进制表示中 $1$ 的个数不超过 $3$$b$$16$$b$$1$$3$$b$$O\left(4\cfrac {nm}{2^{16}}\log v\right)$$n$$A$$1$$2$$f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)$$[l,r]$$\sum_{i=l}^r f(a_i)$$\begin{pmatrix}a_n \\a_{n+1}\\ \end{pmatrix}$$2\times 2$$v$$[l,r]$$\begin{pmatrix}0 & 1 \\ 1 & 1\\ \end{pmatrix}^v$$O(m\log n\log v)$$y$$x$$x$$x$$t$$\frac {t(t-1)}2$$y$$O(n^2\log v)$$n$$n$$S$$s_1$$w$$s_2$$S-w$$\frac S2$$\text{vis}$$a$$vis_{k+a}=v… text/html 2021-08-24T11:25:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E9%94%99%E9%A2%98%E9%9B%86_5&rev=1629775518&do=diff 错题集 5 1、Furukawa Nagisa's Tree 链接 题意 给定一个点权树，点 $i$ 点权为 $a_i$。 树上有向路径 $s\to t$ 被认为是好的当且仅当 $a_s+a_{v_1}x^1+a_{v_2}x^2+\cdots a_tx^k\equiv y(\bmod p)$，其中 $v_1,v_2\cdots$ 为 $s\to t$ 依次经过的点。 三元组 $(u,v,w)$ 被认为是好的当且仅当 $u\to v,u\to w,v\to w$ 三条路径都是好的或都是坏的。(不要求 $u,v,w$$G$$u\to v$$u\to v$$u\to v$$G$$2$$i$$\text{in}_1$$\text{out}_1$$\text{in}_0$$\text{out}_0$$i$$(u,v,w)$$i$$u$$u\to v_1$$u\to v_2$$(u,v_1,v_2),(u,v_2,v_1)$$i$$2\times \text{out}_0\text{out}_1$$i$$w$$i$$2\times \text{in}_0\text{in}_1$$i$…