https://wiki.cvbbacm.com/ 2026-04-29T23:32:10+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-09-03T19:55:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84&rev=1599134126&do=diff 后缀数组 基本定义与概念 后缀：$suf(i)$ 代表字符串 $s$ 从 $i$ 位置开始的后缀（由 $s[i] ~ s[n-1]$ 组成的字符串） $sa[i]$ ：是一个一维数组，保存了对字符串 $s$ 所有后缀排序后的结果。$sa[i]$ 代表第 $i$ 小的串在原串中的位置。$rnk[i]$$rnk[i]$$suf(i)$$(ps: rnk[sa[i]] = i)$$hgt[i]$$(LCP)$$O(n^2logn)$$hehehda$$2^0$$2^1$$i$$2^0$$i+2^0$$i+2^0 ≥ n$$-1$$2^2$$logn$$O(nlognlogn)$$[-1,n)$$nlogn$ text/html 2020-05-08T18:23:42+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%AF%B9%E6%95%B0%E5%87%BD%E6%95%B0&rev=1588933422&do=diff 问题描述 给定一个n-1次多项式$f(x)$，保证$a_0=1$。求$\ln(f(x))$对$x^n$取模的结果。系数模998244353 $\ln(f(x))$定义为其幂级数展开，对$x^n$取模为其幂级数的前n项和。 解决方法 前置知识 多项式乘法（NTT），多项式求逆，多项式求导、积分（这个所有人都会）$g(x)=\ln(f(x))$$g'(x)\equiv\frac{f'(x)}{f(x)}\equiv f'(x)f^{-1}(x)\pmod{x^n}$$f^{-1}(x)$$x^n$$f'(x)$$f'(x)f^{-1}(x)$$g'(x)$$x^n$$g(x)$$n\log n$ text/html 2020-05-22T17:34:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:%E5%B8%A6%E8%8A%B1%E6%A0%91&rev=1590140058&do=diff 带花树 带花树是解决一般图的最大匹配的算法。 增广路 由于涉及到最大匹配，我们这里对增广路进行一个简短的介绍： 1.如果在一个 $M$ 匹配的图 $G$ 中，有一个点 $v$ 是孤立的指没有与其匹配的点。一条在$G$$alternating path$$augmenting path$$P$$M1=M xor P $$M$$G$$B$$G$$2k+1$$k$$M$$v$$w$$w$$w$$w$$o$$out of M$$i$$o$$o$$G'$$G$$B$$M'$$G'$$M$$G'$$M'$$G$$M$$M'$$G'$$P'$$G$$M$$P'$$V_B$$B$$P'$$G'$$u \rightarrow V_B \rightarrow w$$G$$u \rightarrow (u'\rightarrow \ldots\rightarrow w') \rightarrow w$$u'$$w'$$B$$u' \rightarrow w'$$u'$$B$$M$$w' \rightarrow w$$P'$$V_B$$G$$u \rightarrow (u' \rightarro… text/html 2020-05-22T18:22:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:%E6%9D%9C%E6%95%99%E7%AD%9B&rev=1590142955&do=diff 问题描述（洛谷4213） 给定$N(N<2^{31}$)，求1到N的欧拉函数和莫比乌斯函数之和 解决方法 定义 对函数$f(n),g(n)$，定义$(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})$为f与g的狄利克雷卷积 引理1 $\sum_{i=1}^n(f*g)(i)=\sum_{i=1}^n\sum_{d\mid i}f(d)g(\frac{i}{d})=\sum_{d=1}^n f(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}g(i)=\sum_{d=1}^nf(d)S(\lfloor \frac{n}{d}\rfloor)$，其中$S(n)=\sum_{i=1}^n g(i)$ 引理2 设$f(n)=1,g(n)=\phi (n)$，则有$(f*g)(n)=n$ 引理3 设$f(n)=1,g(n)=\mu (n)$，则有$(f*g)(n)=[n=1]$ 具体解决 由引理1得，$f(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^nf(d)S(\lflo… text/html 2020-07-17T16:11:42+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:%E7%9F%A9%E9%98%B5%E6%A0%91&rev=1594973502&do=diff 问题描述 给定无向图，求生成树个数 矩阵树定理 内容 设图的邻接矩阵为A（若i,j相连，则$A_{ij}=1$），度矩阵为B（$B_{ii}$为第i个点的度数）。则答案为$B-A$的任意代数余子式 证明 暂时先鸽子了 text/html 2020-07-17T15:25:42+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder1&rev=1594970742&do=diff 比赛信息 * 日期：2020.7.12 * 比赛地址： 传送门 * 做题情况：lxh(I)，tyx(F)，gyp(HJ) 题解 A - solved by written by 题意 数据范围 题解 B - Infinite Tree solved by -, upsolved by tyx 题意 有一棵有无限个节点的树，这棵树的根节点是1，每个数$x$$\frac{x}{f(x)}$$f(x)$$x$$m$$1!,2!,3! \ldots m!$$m$$w_i$$p$$\sum_{i=1}^m w_i \times dis(p, i!)$$dis$$1 \le m \le 10^5$$0 \le w_i \le 10^4$$\sum m \le 10^6$$1!,2!,3! \ldots m!$$(i-1)!$$i!$$i$$i$$i$$(i-1)!$$x^TAx\le 1$$x^Tb$$(x^Tb)^2$$n\le200$$x^TAx=1$$x^Tb$$A(\lambda x)=b$$x^Tb=\lambda x^TAx=\lambda$$(… text/html 2020-07-17T17:11:07+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder2&rev=1594977067&do=diff 比赛信息 * 日期：2020.7.13 * 比赛地址： 传送门 * 做题情况：lxh(-)，tyx(DF)，gyp(BJ) 题解 A - All with Pairs solved by -, upsolved by tyx 题意 给出$n$个字符串，定义函数$f(s,t)=i$，其中$i$是最大的自然数使得$s_{1 \ldots i} = t_{|t|-i+1 \ldots |t|}$，也就是说$s$$t$$\sum_{i=1}^n \sum_{j=1}^n f(s_i,s_j)^2$$1 \le n \le 10^5$$1 \le |s_i| \le 10^5$$\sum |s_i| \le 10^6$$aba$$a$$aba$$Next$$cnt[Next[i]] -= cnt[i]$$n \le 100000$$cnt$$dfn$$i$$cnt/2+i$$cnt/2$$dfn$$n \times n$$A_{ij} = lcm(i,j)$$k$$k \times k$$1 \le n,m \le 5000$$1 \le k \le min\{n,m… text/html 2020-07-24T15:00:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder3&rev=1595574036&do=diff 比赛信息 * 日期：2020.7.18 * 比赛地址： 传送门 * 做题情况：lxh(CG)，tyx(BDL)，gyp(AEF) 题解 A - All with Pairs solved by -, upsolved by tyx 题意 数据范围 题解 B - Classical String Problem solved by tyx 题意 $k$$k$$x$$1 \le |s| \le 2 \times 10^6$$1 \le Q \le 8 \times 10^5$$20$$9$$10$$n$$n$$m$$1 \le T \le 1000$$1 \le n \le 50$$1 \le m \le 200$$4 \times n$$x \times x$$n$$m > 4 \times n$$m$$m$$m$$m$$ 2 \le n \le 800005 $$ 1 \le m \le 800005 $ text/html 2020-07-24T15:09:30+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder4&rev=1595574570&do=diff 比赛信息 * 日期：2020.7.20 * 比赛地址： 传送门 * 做题情况：lxh(A)，tyx(F)，gyp(BH) 题解 A - Ancient Distance solved by lxh 题意 我们定义远古距离为其到其最近的有标记的祖先的距离（自己有标记则为0）。现在依次给 $1~n$$n \le 2e5 $$k$$k$$1~n$$AB$$CD$$C$$D$$|AC|,|AD|,|BC|,|BD|$$AB//CD$$AB//DC$$1 \le |AC|,|AD|,|BC|,|BD| \le 1000$$|AD|$$|BC|$$AB//CD$$AD//DC$$n$$\frac{1}{S}$$30 \le n \le 300$$20 \le S \le 100$ text/html 2020-07-31T16:29:59+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder5&rev=1596184199&do=diff 比赛信息 * 日期：2020.7.25 * 比赛地址： 传送门 * 做题情况：lxh(D)，tyx(EF)，gyp(BI) 题解 A - solved by 题意 数据范围 题解 B - Graph solved by gyp,tyx 题意 给定一棵树。每次可以添加一条边或删去一条边。保证任何时候一定是连通图，每个环上的边异或和为0。求所有边的和最小是多少$2\le n \le 10^5$$0 \le w < 2^30$$a_i$$a_i \bigoplus a_j$$\sum_{i=1}^k a_i=n$$\sum_{i=1}^k b_i=m$$P=\prod_{i=1}^kmin(a_i,b_i)$$T\le 100$$1\le n,m\le 10^6,1\le k\le min(n,m)$$c_i\le min(a_i,b_i)$$S=\sum_{i=1}^kc_i$$C_{n-S+k-1}^{k-1}\cdot C_{m-S+k-1}^{k-1}$$n$$P$$n$$A$$A_i = A_{P_i}$$1 \le n \le 10^5$$P… text/html 2020-07-31T16:51:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder6&rev=1596185496&do=diff 比赛信息 * 日期：2020.7.27 * 比赛地址： 传送门 * 做题情况：lxh(-)，tyx(EJK)，gyp(BC) 题解 A - solved by 题意 数据范围 题解 B - Binary Vector solved by gyp 题意 从0和1构成n维向量里随机选n个，求这n个线性无关的概率$1\le n\le 2\cdot 10^7$$2^n-2^m$$2^n\cdot \prod{i=1}^{n-1} (2^n-2^i)$$1\le m,n \le 200$$1$$n$$1 \le i \le n$$i$$\mod \ n = k$$1 \le n \le 5000$$0 \le k < n$$n$$k=0$$n$$k=\frac{n}{2}$$n$$n,1,n-1,2,n-2 \ldots$$n$$n,\frac{n}{2},1,n-1,2,n-2 \ldots$$0\le a\le b\le n$$S(a)>S(b)$$n\le 10^100$$O(100000\cdot l)$$1,2 \ldots n$$m$$x$$K$… text/html 2020-08-07T16:26:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder7&rev=1596788792&do=diff 比赛信息 * 日期：2020.8.1 * 比赛地址： 传送门 * 做题情况：lxh(C)，tyx(J)，gyp(BDH) 题解 A - solved by 题意 数据范围 题解 B - Mask Allocation solved by gyp 题意 给定n,m。将$n\times m$拆成若干个数，使得可以凑成n个m或m个n。输出字典序最大的一种方案$n,m\le 10^4$$n\ge m$$m\times (n%m)$$i$$j$$w[i]-dis(i,j)$$min(价值，0)$$1 \le n(点数)、m(询问数) \le 5e4$$1$$w-dep[x]-dep[p]+2*dep[k]$$x$$w-dep[x]$$sum$$dep[p]$$2*dep[k]$$x$$+1$$1\le a\le n,1\le b\le k$$1\le n,k\le 10^{12}$… text/html 2020-08-07T16:37:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder8&rev=1596789459&do=diff 比赛信息 * 日期：2020.8.3 * 比赛地址： 传送门 * 做题情况：lxh(A)，tyx(AG)，gyp(EIK) 题解 A - All-Star Game solved by tyx,lxh 题意 有$n$个球员和$m$个粉丝，每个粉丝有可能是多个球员的粉丝，如果一个粉丝是某个球员$i$$i$$i$$q$$1 \le n,m,q \le 2 \times 10^5$$\le 5 \times 10^5$$q$$1\le T\le 10^4,1\le n\le 10^5$$a_1，m$$a_1,m$$3\le k\le m$$\lfloor \frac {k-1}2 \rfloor$$m\le k\le 2m-3$$\lfloor \frac {2m-k-1}2 \rfloor$$N$$*$$1 \le T \le 1000$$N \le 256$$O(N^3)$… text/html 2020-08-14T13:01:07+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder9&rev=1597381267&do=diff 比赛信息 * 日期：2020.8.8 * 比赛地址： 传送门 * 做题情况：lxh(K)，tyx(AE)，gyp(FIJ) 题解 A - Groundhog and 2-Power Representation solved by tyx 题意 给出一个正整数的二进制表示，其中只含有加号，括号和1，2，例如$137=2(2(2)+2+2(0))+2(2+2(0))+2(0)$$[10,10^{180}]$$a,b,c,d,x,y$$\prod_{i=a}^b \prod_{j=c}^d \gcd(x^i,y^j) \mod 998244353$$0 \le a \le b \le 3 \times 10^6$$0 \le c \le d \le 3 \times 10^6$$0 < x,y \le 10^9$$x,y$$\sqrt{x}$$\sqrt{y}$$i(a \le i \le b)$$j \in [c,d]$$1$$n$$t$$n$$ 1 \le n \le 1e5 $… text/html 2020-08-14T13:04:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020nowcoder10&rev=1597381461&do=diff 比赛信息 * 日期：2020.8.10 * 比赛地址： 传送门 * 做题情况：lxh(E)，tyx(-)，gyp(A) 题解 A - solved by 题意 数据范围 题解 B - solved by 题意 数据范围 题解 C - solved by 题意 数据范围 题解 $1 × 1$$a_i$$ 1 \le n \le 1e5$ text/html 2020-08-14T11:56:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020summer&rev=1597377377&do=diff 2020.7.12 2020牛客暑假多校训练营（第一场） prob:4/8/10 rank:56/1115 2020.7.13 2020牛客暑假多校训练营（第二场） prob:4/9/11 rank:162/1158 2020.7.18 2020牛客暑假多校训练营（第三场） prob:8/8/12 rank:36/1174 2020.7.20 2020牛客暑假多校训练营（第四场） prob:4/5/10 rank:46/1111 2020.7.23 2020-2021 BUAA ICPC Team Supplementary Training 01 pro: 2/2/11 2020.7.25 2020牛客暑假多校训练营（第五场） prob:5/6/11 rank:113/1115 2020.7.27 2020牛客暑假多校训练营（第六场） prob:5/7/10 rank:124/1018 2020.8.1… text/html 2020-07-24T16:27:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020supplementarytraining1&rev=1595579277&do=diff 比赛信息 * 日期：2020.7.23 * 比赛地址： 传送门 * 做题情况：lxh(H)，tyx(-)，gyp(G) 题解 A - solved by 题意 数据范围 题解 B - solved by 题意 数据范围 题解 C - solved by 题意 数据范围 题解 $a,b$$[a,b]$$1 \le a,b \le 10^{18}$$b$$b$$m$$(c_i,d_i)$$n$$(a,b)$$(c_i,d_i)$$a \times c_i + b \times d_i$$1 \le n,m \le 5\times 10^5$$0 \le a_i,b_i \le 10^9$$1 \le c_i,d_i \le 10^9$$- \frac{a}{b}$ text/html 2020-08-07T16:08:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:2020supplementarytraining2&rev=1596787698&do=diff 比赛信息 * 日期：2020.8.6 * 比赛地址： 传送门 * 做题情况：lxh(A)，tyx(C)，gyp(G) 题解 A - solved by 题意 数据范围 题解 B - solved by 题意 数据范围 题解 C - Crazy Dreamoon solved by tyx 题意 给出$N$$N \le 2000$$[0,2000]$ text/html 2020-05-09T12:53:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200502-200508&rev=1589000016&do=diff 2020/05/02——2020/05/08周报 团队训练 2020.5.2 ACM Google Cup 2011 Invitational Programming Contest prob:4/6/10 rank:11/69 林星涵 专题 树套树 ps:以前的一些链接搬运中，还有一个坑待填 陶吟翔 专题 最小生成树 拓扑排序 郭衍培 专题 多项式对数函数 本周推荐 林星涵： 洛谷P4278 带插入区间K小值 树套树、块状链表模板，代码量较大，仅作练习代码能力食用。$n$$i$$c_i$$i$$j$$(k_i+k_j) \times d$$d$$\sum^n_{i=1}\text{lcm}(n,i)$$n\sum_{d|n}\sum^d_{i=1}i[\gcd(i,d)=1]$$\sum^d_{i=1}i[\gcd(i,d)=1]=\frac{\phi(d)}{2}d$… text/html 2020-05-15T19:23:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200509-200515&rev=1589541829&do=diff 2020/05/09——2020/05/15周报 团队训练 2020.5.9 CTU Open Contest 2016 prob:5/6/10 rank:5/89 林星涵 专题 暂无 个人练习 Codeforces Round #641 (Div. 2) prob:5/6 rank:170 陶吟翔 专题 Tarjan 题目 * Codeforces641Div2-E（同本周推荐） * Codeforces642Div2-D * 题目大意：给出一串数，每次可以把区间$[l,r]$$k$$k$$k$$k$$k$$k$$k$$n \times m (n,m \le 500)$$T(T \le 10^6)$$(i,j)$$p$$O(1)$$O(nm+T)$$n\times m$ text/html 2020-05-22T18:27:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200516-200522&rev=1590143267&do=diff 2020/05/16——2020/05/22周报 团队训练 由于周末三个人的时间没有凑好所以没有举办。 林星涵 专题 带花树 陶吟翔 专题 回路问题 郭衍培 专题 杜教筛 本周推荐 陶吟翔： EducationalCodeforcesRound 76 - E 题目大意：三个人在打ACM比赛，一共有$N$$1$$N$$1$$k$$p$$N$$p \ge k$$N$$10^{-6}$$n\le 10^5，k\le 100$$dp[i+1][j]=\frac{k-1}{k}dp[i][j]+\frac{1}{k}(\frac{1}{j+1}(dp[i][j+1]+j)+\frac{j}{j+1}(dp[i][j]+\frac{j+1}{2}))$$O(n^2)$$10^{-6}$$10^{-16}$$O(500n)$… text/html 2020-05-29T18:06:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200523-200529&rev=1590746784&do=diff 2020/05/23——2020/05/29周报 团队训练 2020.5.23 Nordic Collegiate Programming Contest 2015 prob:7/7/10 rank:1/29 林星涵 专题 本周无 陶吟翔 专题 本周无 个人训练 Codeforces Round #645 (Div. 2) prob:4/5/6 rank:523 郭衍培 专题 本周无 本周推荐 林星涵： 题目链接 题意：有n个区间，选择区间，使得在保证任意时刻不会有超过k个区间重合的情况下区间最多。 $1 \le k < n \le 100000$$k$$k+1$$n$$p$$n \le 10^5,p \le 2 \times 10^4,r_{max} \le 100$$\lfloor \frac n2 \rfloor$$\lfloor \frac n2 \rfloor$$\lfloor \frac n2 \rfloor$$k>\lfloor \frac n2 \rfloor$$\lceil \frac n2 \rceil$$l_i$$k_m=\min_… text/html 2020-06-05T16:38:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200530-200605&rev=1591346297&do=diff 2020/05/30——2020/06/05周报 团队训练 由于周末事情太多所以没有进行。 林星涵 专题 陶吟翔 专题 对偶图 郭衍培 专题 本周无 本周推荐 林星涵：Codeforces Round #647 (Div. 1) - A 题目大意：给定$n$个点$m$$n,m \le 5 \times 10^5$$O(n)$$O(n \log n)$$a_1,\ldots,a_n$$p^{a_1},p^{a_2},\ldots,p^{a_n}$$10^9+7$$p^{a_i-1}$$p^{a_i}$ text/html 2020-06-12T19:37:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200606-200612&rev=1591961864&do=diff 2020/06/06——2020/06/12周报 团队训练 由于周末有数分小测和工图期末所以没有进行。 林星涵 专题 陶吟翔 专题 树的直径和重心 郭衍培 专题 本周推荐 林星涵：「2017 山东二轮集训 Day6」汇合 传送门 题目大意：求任意两点的最近公共祖先。$n$$\le$$m$$\le$$Mib$$2s$$900000$$nlogn$$MLE$$n$$n \le 200$$O(n)$$f_{u,i}$$u$$i$$u$$f_{u,i}=\sum_{v \in son_u} \sum_{j=1}^{min(i-1,size_v)} f_{u,i-j} \times f_{v,j}$$\sum_{j=1}^{min(size_{g_x},size_{g_y})} f_{g_x,i} \times f_{g_y,i}$$f$$F_{i,j}$$i$$j$$F_{i,i}=\sum_{v \in son_g} f_{v,i}$$1 \le k \le i$$F_{i,max(j,k)}+=F_{i-j,k} \times f_{v,j}$$1 + \sum_… text/html 2020-06-23T15:28:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200613-200619&rev=1592897315&do=diff 2020/06/13——2020/06/19周报 团队训练 由于周末有期末考试所以没有举办 林星涵 专题 陶吟翔 专题 本周无 郭衍培 专题 本周推荐 林星涵： 陶吟翔： 郭衍培： text/html 2020-06-29T20:47:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200620-200626&rev=1593434855&do=diff 2020/06/20——2020/06/26周报 团队训练 2020.6.26 German Collegiate Programming Contest 2015 prob:10/10/11 rank:1/29 林星涵 专题 无 陶吟翔 专题 本周无 郭衍培 专题 本周推荐 林星涵：A Journey to Greece 题意 一共有 $ N $ 个点，其中有 $ P $ 个是要观看的，有 $M$ 条边，有 $G$$T$$G$$0$$0$$ N\le 20000 $$ P \le 15 $$ M \le 1e5 $$ G \le 1e5$$DP$$N$$a$$\frac{1}{s}$$a$$s$$S=\frac{e_1}{s} \times \frac{e_2}{s} \times sin\alpha$$s^2$$s$$n\le 50000,m\le 50000$… text/html 2020-07-17T17:16:04+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200711-200717&rev=1594977364&do=diff 2020/07/11——2020/07/17周报 团队训练 2020.7.12 2020牛客暑假多校训练营（第一场） prob:4/7/10 rank:56/1115 2020.7.13 2020牛客暑假多校训练营（第二场） prob:4/9/11 rank:162/1158 林星涵 专题 无 比赛 2020.07.11 AIsing Programming Contest 2020 prob:4/5/6 rank:590 题目 * atcoder E - Camel Train * 分类：贪心 * 题目大意：对于一个队列，里面每个元素有 $li,ri,ki$$ki$$li$$ri$$li-ri$$ki$$n-ki$$n$$a_i$$x$$T \le 1000$$1 \le n \le 10^5$$1 \le a_i,x \le 10^9$$O(n \log n)$$n$$a_i$$x$$k$$y$$1 \le k \le n \le 2 \times 10^5$$1 \le x,y \le 10^9$$k$$k$$y \times k < x$$k$… text/html 2020-07-24T16:43:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200718-200724&rev=1595580233&do=diff 2020/07/18——2020/07/24周报 团队训练 2020.7.18 2020牛客暑假多校训练营（第三场） prob:8/8/12 rank:36/1174 2020.7.20 2020牛客暑假多校训练营（第四场） prob:4/5/10 rank:46/1111 2020.7.23 2020-2021 BUAA ICPC Team Supplementary Training 01 prob: 2/2/11 林星涵 专题 本周无 比赛 2020.7.21 Codeforces Round #658 prob:4/5/6 rank:599 题目 * Codeforces Round 658 D - Unmerge$n$$t \le 1000$$1 \le n \le 2000$$n$$n$$m$$a_i$$b_i$$T \le 1000$$1 \le n,a_i,b_i \le 10^9$$a_i$$a_i$$O(m \log m)$$n$$k$$w_i$$T \le 10^4$$1 \le k,w_i \le n$$w_1+w_2+ \ldots … text/html 2020-07-31T16:23:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200725-200731&rev=1596183829&do=diff 2020/07/25——2020/07/31周报 团队训练 2020.7.25 2020牛客暑假多校训练营（第五场） prob:5/6/11 rank:113/1115 2020.7.27 2020牛客暑假多校训练营（第六场） prob:5/7/10 rank:124/1018 林星涵 专题 本周无 比赛 2020.7.29 Educational Codeforces Round #92 prob:3/4/7 rank:2331 题目 本周无 陶吟翔 专题 本周无 比赛 $n$$[l1,r1],[l2,r2]$$k$$1 \le n \le 2e5 ,1 \le k\le 1e9 ,1\le l \le r \le 1e9$$n$$2 \le n \le 10^5$$w < 2^{30}$$a_i$$n$$O(n \log n)$$O(\log n)$$O(n \log^2 n)$$O(n \log n)$$O(log n)$$O(n \log^2 n)$$1\le n \le 2\cdot 10^5$$1\le l_i \le r_i \le 10^9$… text/html 2020-08-07T16:24:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200801-200807&rev=1596788677&do=diff 2020/08/01——2020/08/07周报 团队训练 2020.8.1 2020牛客暑假多校训练营（第七场） prob:5/5/10 rank:46/1090 2020.8.3 2020牛客暑假多校训练营（第八场） prob:5/5/11 rank:16/684 2020.8.6 2020-2021 BUAA ICPC Team Supplementary Training 02 pro: 3/3/11 林星涵 专题 本周无 比赛 2020.8.2 Atcoder Beginner Contest 174 prob:6/6/6 rank:433 题目 本周无 陶吟翔 专题 本周无$i$$j$$w[i]-dis(i,j)$$min(价值，0)$$1 \le n(点数)、m(询问数) \le 5e4$$1$$w-dep[x]-dep[p]+2*dep[k]$$x$$w-dep[x]$$sum$$dep[p]$$2*dep[k]$$x$$+1$$n$$m$$i$$i$$i$$q$$1 \le n,m,q \le 2 \times 10^5$$\le 5 \t… text/html 2020-08-14T15:01:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200808-200814&rev=1597388517&do=diff 2020/08/08——2020/08/14周报 团队训练 2020.8.8 2020牛客暑假多校训练营（第九场） prob:6/6/12 rank:68/974 2020.8.10 2020牛客暑假多校训练营（第十场） prob:2/2/10 rank:194/904 林星涵 专题 本周无 比赛 2020.8.9 Atcoder Beginner Contest 047 prob:2/3/6 rank：415 题目 本周无 陶吟翔 专题 本周无 比赛 本周无$n$$[1,n]$$T \le 100$$2 \le n \le 10^5$$\sum n 10^5$$n \times m$$1 \le n,m \le 2000$$dp_{i,j}$$(i,j)$$dp_{i,j}=min\{dp_{i-1,j-1},dp_{i-1,j+1},dp_{i-2,j}+1\}$$i$$1 \le j < i$$p_j > p_i$$i < j \le n$$p_j > p_i$$i$$j$$3 \le n \le 10^6$$n$$2^{n-1}$$n$$S_i$$… text/html 2020-08-23T13:13:51+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200815-200821&rev=1598159631&do=diff 2020/08/15——2020/08/21周报 团队训练 本周无 林星涵 专题 ac自动机 比赛 本周无 题目 本周无 陶吟翔 专题 树上差分 比赛 本周无 题目 本周无 郭衍培 专题 本周无 比赛 本周无 题目 * Codeforces Round #664(Div.1) - Boboniu Walks on Graph$\{c_k\}$$1\le c_i \le i$$1\le k\le 9$$1\le n,m\le 2\cdot 10^5$$c_i=j$$n$$m$$1 \le n,m \le 10^5$$2 \times 10^5$$n\le 2\times 10^5$$1\le h,t\le 10^6$ text/html 2020-08-28T17:21:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200822-200828&rev=1598606470&do=diff 2020/08/22——2020/08/28周报 团队训练 本周无 林星涵 专题 本周无 比赛 2020.8.22 AtCoder Beginner Contest 176 prob:5/6 rank：889 题目 P3796 【模板】AC自动机（加强版） 题意：对模式串在主串中出现的次数计数，输出出现次数最多的串。 解法：标准的 $ac$$trie$$next$$n$$T \le 10^4$$1 \le n \le 10^5$$\sum n 10^5$$n$$k$$k$$T \le 100$$2 \le n \le 10^5$$\sum n 10^5$$k$$H×W ，H、W \le 3e5$$(n \le min(H×W,3e5))$$n$$a_1,a_2 \ldots a_n$$(i,j,k,l)$$i < j < k < l$$a_i = a_k,a_j = a_l$$1 \le T \le 100$$4 \le a_i,n \le 3000$$O(n^2)$$i$$k$$k$$a_i=a_k$$2^n$$k$$i$$[(i-1)\cdot 2^k+1,i… text/html 2020-09-04T14:47:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:200829-200904&rev=1599202059&do=diff 2020/08/29——2020/09/04周报 团队训练 本周无 林星涵 专题 后缀数组 比赛 2020.8.30 Codeforces Round #666 prob:2/2/5 rank:778 题目 本周无 陶吟翔 专题 本周无 比赛 2020.8.29 Atcoder Beginner Contest 177 prob:5/6/6 rank:638 2020.8.30 Codeforces Round #666 prob:2/2/5 rank:845 题目 2020 TCO Algo Round 2B - DIV1 第二题$(H+1) \times W$$i$$A_i$$B_i$$2$$H+1$$1 \le H,W \le 2 \times 10^5$$i$$i-1$$i$$[A_i,B_i]$$B_i+1$$n\times n$$1\le n\le 10^9$$0\le m,d_i\le 10$$201 \times 201$… text/html 2020-08-07T15:54:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:abc174&rev=1596786868&do=diff Atcoder Beginner Contest 174 A - Air Conditioner 题目大意 给出一个$X$，问$X$是否大于等于30 数据范围 $-40 \le X \le 40$ 解题思路 直接一个if B - Distance 题目大意 给出$N$个点的坐标和$D$，问有几个点和原点的距离小于等于$D$$1 \le N \le 2 \times 10^5$$0 \le D \le 2 \times 10^5$$O(n)$$K$$K$$K$$1 \le K \le 10^6$$K$$K$$2 \le N \le 2 \times 10^5$$N$$A_i$$K$$1 \le N \le 2 \times 10^5$$0 \le K \le 10^9$$1 \le A_i \le 10^9$$O(n)$$O(n \log n)$$N$$Q$$[l_i,r_i]$$1 \le N,Q \le 5 \times 10^5$$\le 5 \times 10^5$… text/html 2020-09-04T12:27:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:abc177&rev=1599193678&do=diff Atcoder Beginner Contest 177 A - Don't be late 题目大意 给出$D,T,S$，求$\lceil \frac{D}{S} \rceil$是否小于等于$T$ 数据范围 $1 \le D,S,T \le 1000$ 解题思路 直接判断 B - Substring 题目大意 给出字符串$s,t$，问$t$最少修改几个字符可以变成$s$的一个子串 数据范围 $1 \le |t| \le |s| \le 1000$$O(|t|^2)$$N$$A_1 \ldots A_n$$\sum_{1 \le i < j \le N} A_i * A_j$$10^9+7$$2 \le N \le 2 \times 10^5$$A_i \le 10^9$$N$$M$$2 \le N,M \le 2 \times 10^5$$N$$A_1 \ldots A_n$$N,A_i \le 10^6$$(H+1) \times W$$i$$A_i$$B_i$$2$$H+1$$1 \le H,W \le 2 \times 10^5$$i$$i-1$$i$$[… text/html 2020-08-26T15:44:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:ac%E8%87%AA%E5%8A%A8%E6%9C%BA&rev=1598427857&do=diff AC自动机 引入 $AC$ 自动机是一种多模式串匹配算法，一般用于解决对于在文本串中匹配一系列模式串（例：给一个文本串和一系列模式串，问模式串在文本串中一共出现了多少次） 构造 具体的构造方法我们可以参考 $KMP$$i$$fail(i)$$fail(i)$$i$$AC$$trie$$i$$i'$$i$$c$$fail(i')$$c$$fail(i)$$fail(7)=1,fail(8)=2$$fail$$fail(i)$$i$$c$$i$$c$$fail$$i$$fail(i)$$nxt(i)$$i$$fail(i)$$nxt(i)=fail(i)$$nxt(i)=nxt(fail(i))$$i$$c$$c$$Trie$… text/html 2020-05-09T18:16:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:acmgooglecup2011invitationalprogrammingcontest&rev=1589019393&do=diff 比赛信息 * 日期：2020.5.2 * 比赛地址： 传送门 * 做题情况：lxh(BG)，tyx(D)，gyp(J) 题解 A - Avaricious Maryanna solved by -, upsolved by tyx,lxh,gyp 题意 给定T个询问，每次询问一个$N$，要求输出所有$N$位的数$x$$x*x$$N$$x$$x$$i$$N \le 500$$T \le 1000$$(N*N*4*10)$$T$$1-n$$N \le 80$$T \le 2500$$T$$(T \le 200)$$s(|s| \le 1000)$$k(1 \le k \le |s|)$$1$$|s|$$N \le 1000$$T \le 200$$i\ mod\ (i\ -\ next[i])\ ==\ 0$$O(n^2T)$$T \le 10^4$$N$$N = 10$$T$$N \le 1000$$T \le 200$$O(n^2T)(n \le 1000,T \le 200)$… text/html 2020-08-14T12:55:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:agc047&rev=1597380916&do=diff Atcoder Grand Contest 047 比赛链接 A - Integer Product 题目大意 给出 $n$ 个实数 $A_i$，问有多少两两相乘得到整数 数据范围 $2 \le n \le 200000$ $0 < A_i < 1e4 $ ps: $A_i$ 小数位后最多有9位 解题思路 我们不妨将 $A_i$ 都乘以 $1e9$, 然后对其质因数分解统计 2 和 5 的个数（初始显然是 -9），之后排序扫描一维树状数组统计一维计算答案即可。$n$$S_i$$ 2 \le n \le 2e5$$ S_i \ne S_j$$ |S_1+S_2\ldots+S_n| \le 1e6$$\sum_{1\le i<j\le n}(a_i\times a_j\%200003)$$1\le n\le 200000$$a_i$$2^k_i$$2^k\equiv a_i \pmod {200003}，k\le 200001$$2^i$… text/html 2020-09-04T09:43:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:aspirine&rev=1599183815&do=diff $2^{10}=1024$ 多项式对数函数 置换群论 杜教筛 5.14个人比赛 矩阵树定理 Codeforces Round #658 Educational Codeforces Round #92 Codeforces Round #666 text/html 2020-08-28T13:07:20+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:atcoderbc176&rev=1598591240&do=diff AtCoder Beginner Contest 176 A - Takoyaki 题目大意 给 $n,x,t$ ,问 $n/x$ 取上整乘 $t$. 解题思路 模拟 B - Multiple of 9 题目大意 给定一个长为 $n \le 2e5$ 的数，问其是否是9的倍数。 解题思路 每位的数相加看能否整除9即可。$n \le 2e5$$H×W ，H，W \le 1000$$5×5$$H×W ，H、W \le 3e5$$(n \le min(H×W,3e5))$$n\le 2000$$O(n^3)$$f_i$$cnt+max\{mx,dp[a[3n]][a[3n]]\}$ text/html 2020-07-05T16:46:14+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:burnside%E5%BC%95%E7%90%86%E5%92%8Cpolya%E5%AE%9A%E7%90%86&rev=1593938774&do=diff 声明：本知识点为帮助大家更好地理解置换群论这一抽象的内容，一些定义中掺杂了撰写者自身的理解，和严格的数学定义有些出入，基本为数学定义的缩小解释和限制解释。 另外，统一一些符号的使用。$g^{-1}$$g$$\frac 1n \sum^n_{i=1} n^{gcd(i,n)}$\[ \mathbf{\sigma} = \left( \begin{array}{cccc} 1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\\ \end{array} \right) \]$i_1,i_2,\ldots ,i_n$$i_1$$i_2$$i_n$$(i_1,i_2,\ldots,i_n)$$G=\{g_1,g_2,\ldots,g_n\}$$\forall i,j$$g_i*g_j$$g_i$$g_j$$(G,*)$$N=n^n$$g（g\in G）$$1\le k\le N$$\forall g\in G，x\in \{1,2,\ldots,N\}，f(g,x)=[g(x)=x]$$h(g_i)=\sum^N_{k=1}f(g_i,k)$$g_i(k… text/html 2020-05-20T21:05:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:circuit&rev=1589979939&do=diff 问题概述 回路问题指的是有向或无向图中的欧拉回路和哈密顿回路问题。 欧拉回路问题 定义 在一个有向或无向图$G$中，所有边都经过一次且仅经过一次的通路称为欧拉通路，若起点与终点相同，则称为$G$$G$$G$$V_0$$P_0=V_0$$P_i=V_0e_1V_1e_2V_2 \ldots e_iV_i$$V_i$$E(G)-\{e_1,e_2 \ldots e_i\}$$e_{i+1}$$e_{i+1}$$V_i$$e_{i+1}$$G-\{e_1,e_2 \ldots e_i\}$$N$$\frac{N}{2}$$\frac{N}{2}$$[\frac{N}{2}]$$G=\langle V,E \rangle$$V$$S$$|S|$$S$$G-S$$G$$S$$W(G-S) \le |S|$$W(G-S)$$G-S$$S$$T$$S$$v$$v$$S \rightarrow T$$v \rightarrow S \rightarrow T$$v$$S$$S$$T$$S$$T$$S \rightarrow T$$S$$T$$S \rightarrow T$$S \righta… text/html 2020-05-15T17:45:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforces641div2&rev=1589535902&do=diff Codeforces Round #641 (Div. 2) A.Orac and Factors 题目大意 对于一个数 $n ≤ 10^6$ ，找到它最小的不是1的约数，然后加在这个值上，重复 $k ≤ 10^9 $次 解题思路 首先对于偶数，这个数一定是 2，而对于奇数，一次操作之后就会变成偶数，答案是显然的。$ a_n (n \le 1e6) $$a_j > a_i $$ O( nlogn ) $$ s_n (n \le 100000) $$ t = \{ lcm({a_i,a_j})|i < j \} $$ gcd(t) $$ lcm,gcd $$ a_n (n \le 100000 ，1 \le a_i \le 1e9) $$k (1 \le k \le 1e9) $$ k $$ k $$ k $$ k $$ k $$ k $$ k $$ k $$\ge k$$k$$k$$k$$ n \times m 的 01 矩阵 (1 \le n,m \le 1000)$$ (0 \rightarrow 1, 1 \rightarrow 0) $$ t \le 100000… text/html 2020-05-29T14:16:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforces645div2&rev=1590732995&do=diff Codeforces Round #645 (Div. 2) A - Park Lighting 题目大意 有一个$n \times m$的网格，可以在一条边上放一个灯照亮有这条边的两个或一个格子，问最少放几个可以全照亮 解题思路 如果$n \times m$是奇数就是除以2再加1，否则就是直接除以2。$n$$n$$a_i$$a_i$$a_i$$a_i \Leftarrow i$$O(n \log n)$$(x_1,y_1)$$(x_2,y_2)$$(x_2-x_1) \times (y_2 - y_1)$$n$$d_i$$x$$x$$x$$x$$O(n)$$n$$\lceil \frac{n}{2} \rceil$$\lfloor \frac{n}{2} \rfloor$$k$$n$$k$… text/html 2020-07-22T14:04:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforces658div2&rev=1595397873&do=diff A - Common Subsequence 问题描述 给定两个序列$\{a_n\}$，$\{b_m\}$，求一个最小公共子序列 数据范围 $n,m\le 1000$ 解题思路 如果存在$a_i=b_j$，则输出这个，否则不存在 B - Sequential Nim 问题描述 n堆石子排成一列，第i堆有$a_i$个。两人轮流，从最前面的一堆中拿任意个。问谁必胜。$n\le10^5$$n\le10^5$$a[n]\neq b[n]$$a[1]\neq b[n]$$a[1]=b[n]$$O(n^2)$$n\le 2000$$O(n^2)$$n\le10^5$ text/html 2020-07-31T15:31:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforces660div2&rev=1596180699&do=diff A - Captain Flint and Crew Recruitment 问题描述 给出一个$n$，问$n$能不能分成四个不同的数，其中至少三个是伪质数，伪质数指存在质数$p,q$满足$p < q$且$p \times q = x$的$x$，如果可以构造方案 数据范围 多组数据，$1 \le T \le 1000$，$1 \le n \le 2 \times 10^5$ 解题思路 $f(x)$$x$$f(729)=111101001$$x$$n$$f(x)$$n$$1 \le T \le 1000$$1 \le n \le 10^5$$\sum n \le 2 \times 10^5$$f(x)$$x$$x$$n$$(n / 4) + (n\ mod\ 4 != 0)$$n$$m$$h_i$$h_1$$h_n$$1 \le T \le 10000$$1 \le n \le 10^5$$\sum n \le 2 \times 10^5$$1 \le m \le 10^9$$-10^9 \le h_i \le 10^9$$h_i$$n$$a,b$$i(1 \le i \le … text/html 2020-09-04T22:15:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforces666div1&rev=1599228929&do=diff A - Multiples of Length 题意 给定一个长度为n的序列。一次操作要选中一个区间，将这个区间里的每个数加上区间长度的整数倍。构造一个三次操作将序列全变为0的方案。 限制 $1\le n \le 10^5$ 题解 第一次操作选第一个数，加$-a_1$$(n-1)a_i$$1\le n \le 100,1\le a_i \le 100$$a_i$$r_1$$r_2$$r_3$$1\le n \le 10^6$$1\le r_1 \le r_2 \le r_3$ text/html 2020-05-15T17:18:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforces_round&rev=1589534288&do=diff A - Most Unstable Array 题意 给定n和m。问长度为n且总和为m的非负整数数列，相邻两项差的绝对值之和最大为多少。 思路 贪心。n=1时答案为0，n=2时答案为m，n>2时答案为2m B - Two Arrays And Swaps 题意 $n\times n$$dp[i]=\min(dp[i-k]+s1[i-1]-s1[i-k],s1[i-1])$$dp[i]=\min(dp[i-k]+s1[i-1]-s1[i-k],s1[i-1])+1$$\min(dp[i]+s2[i+1],s1[n])$$n\times m$ text/html 2020-07-31T15:37:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforceser92&rev=1596181077&do=diff A - LCM Problem 问题描述 给定l,r。求一组x,y满足$l\le x<y \le r$,$l\le lcm(x,y)\le r$ 数据范围 $1\le l<r \le 10^9$ 解题思路 因为x<y，所以$lcm(x,y)\ge 2x$。若$r<2l$则无解，否则输出$l,2l$。 B - Array Walk 问题描述 给定长为n序列a。一开始在第一格，分数是$a_1$。每次可以向左或向右走一格，但最多一共向左走z次，且不能连续向左走两格。问走k次后最大分数。$2\le n\le 10^5$$1\le k\le n-1$$0\le z\le 5$$t_2t_3t_4\cdots t_{n-1}t_nt_1$$t_nt_1t_2\cdots t_{n-2}t_{n-1}$$2\le|s|\le 2\cdot 10^5$$t_1=t_2=\ldots=t_n$$t_1=t_3=\ldots=t{n-1}$$t_2=t_4=\ldots=t_n$$t_1,t_2$$O(|s|)$$[l_1,r_1]$$[l_2,r_2]$$\sum_{i=1}^n（a_… text/html 2020-09-01T20:21:23+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:codeforceser94&rev=1598962883&do=diff A - String Similarity 问题描述 给定一个长度为$2n-1$的01串$s$，定义一个串和另一个串相似当且仅当它们至少有一位相同，构造一个和$s_{1 \ldots n}, s_{2 \ldots n+1} \ldots s_{n \ldots 2n-1}$都相似的串 数据范围 多组数据，$1 \le T \le 1000$，$n \le 50$ 解题思路 直接把$s$的第1,3,5...$cnt_s$$cnt_w$$s$$w$$p$$f$$1 \le T \le 10^4$$1 \le s,w,p,f \le 10^9$$1 \le cnt_s,cnt_w \le 2 \times 10^5$$w$$w$$s$$x$$w_{i+x}$$w_{i-x}$$s_i$$s_i$$s$$x$$w$$1 \le T \le 1000$$2 \le |s| \le 10^5$$s$$w$$w$$s$$n$$a_1,a_2 \ldots a_n$$(i,j,k,l)$$i < j < k < l$$a_i = a_k,a_j = a_l$$1 \le T \le 10… text/html 2020-05-29T13:14:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:ctuopencontest2016&rev=1590729242&do=diff 比赛信息 * 日期：2020.5.9 * 比赛地址： 传送门 * 做题情况：lxh(B)，tyx(J{G})，gyp(FI) 题解 B - Hot Air Ballooning solved by lxh 题意 给出一系列数字，两个数字不同当且仅当出现的数字不同，问一共有多少种不同的数字。$“<”, “>”, “^”, “v”, “o”, “x”, “|”, “-”, “/”, “\backslash”$$n×n$$“<”, “>”$$ “|”, “-”, “/”, “\backslash”$$"<"顺时针翻转后为“v”$$n≤100$$≤1000000$$2\le m\le n\le 200$$O(nm^2)$$M \times M$$N$$M \times M$$M \le 10^9,N \le 10^6$$O(N \log N)$$n\le 10^5，m\le 10$$10^6$$O(n\log n m)$$O(nm)$$N \times N$$N$$3 \le N \le 26$… text/html 2020-06-11T12:35:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:diameterandweight&rev=1591850127&do=diff 树的直径及其性质 树$T= \langle E, V \rangle$的直径定义为$max\{ \delta(u,v) \} u,v \in V$。其中$\delta(u,v)$表示点$u$和点$v$之间的简单路径。简单来说，在树上任取两个点可以得到它们之间的距离，而最大的那个距离就是直径。 树的直径有这些性质： 1.两端点一定是叶子节点。$u$$v$$a$$b$$v$$\delta(a,b)$$u$$v$$v$$\delta(a,b)$$\delta(a,b)$$p$$dis(u,v)>dis(u,p)+dis(p,b)$$dis(a,v) = dis(a,p) + dis(p,u) + dis(u,v) > dis(a,p) + dis(p,b) = dis(a,b)$$\delta(a,b)$$O(n)$$f_1[i]$$i$$f_2[i]$$i$$max\{ f_1[i] + f_2[i] \}$$a,b$$a \le b$$ b \ge a+3 $$ b $$ b == a+2 $$b$$b+1$$b$$ b == a+1 $$ b+1 $$O(n)$… text/html 2020-06-03T14:59:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:dualgraph&rev=1591167579&do=diff 问题概述 对偶图可以把最小割、最大流等问题转化为普通的最短路问题，从而明显降低算法的复杂度。 对偶图的定义 对偶图是与平面图相伴的一种图。对于给定的平面图$G = \langle E,V \rangle$，设G的面为$F_1,F_2 \ldots F_e$，当图$G^*$$G^* = \langle E^*,V^* \rangle$$G$$G$$F_i$$v_i^* \in V^*$$F_i,F_j$$e_x$$v_i^*$$v_j^*$$e_x^*$$e_x$$e_x$$F_i$$v_i^*$$e_x$$O(EV^2)$$O(V \log V)$$n \times m$$(1,1)$$(n,m)$ text/html 2020-07-16T13:07:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:front_page&rev=1594876020&do=diff tyx的个人页面 lxh的个人页面 gyp的个人页面 各季度训练计划及训练记录 2020春季组队训练记录 2020夏季组队训练记录 周报及推荐 团队技能树 text/html 2020-05-06T12:31:01+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:front_page_lxh%E7%9A%84%E4%B8%AA%E4%BA%BA%E7%95%8C%E9%9D%A2&rev=1588739461&do=diff 2333 text/html 2020-06-26T17:53:42+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:germancollegiateprogrammingcontest2015&rev=1593165222&do=diff 比赛信息 * 日期：2020.6.26 * 比赛地址： 传送门 * 做题情况：lxh(ADE)，tyx(BK)，gyp(CFGIJ) 题解 A - A Journey to Greece solved by lxh written by lxh 题意 一共有 $ N $ 个点，其中有 $ P $ 个是要观看的，有 $M$ 条边，有 $G$$T$$G$$0$$0$$ N\le 20000 $$ P \le 15 $$ M \le 1e5 $$ G \le 1e5$$DP$$N$$N \le 10^3$$n\le 100$$0.25<r<1$$10^8$$1-r$$s^2$$(W × H)$$wi,hi$$ W, H \le 100 $$ N \le 7$$N$$1$$N$$N \le 10000$$M \le 1000000$$1$$N$$++d[x],++d[y]$$ d[x] > 2$$d[1]==2||d[n]==2$$N\le10^{18}$$10^7$$a^{p-1}\equiv 1\pmod p$$n\le 1024$$g,c,n\le 100… text/html 2020-07-22T13:39:52+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:lca&rev=1595396392&do=diff 问题概述 LCA的全称是Least Common Ancestors，顾名思义，LCA问题就是求树上两个点的最近公共祖先的问题。由定义，两个点的最近公共祖先是满足这两个点都在其子树中的点里面深度最大的那个，因此有可能这两个点的最近公共祖先就是其中一个。$O(n)$$O(\log n)$$f[i][j]$$i$$2^j$$f[i][0]$$i$$f[i][j] = f[f[i][j-1]][j-1]$$2^{j-1}$$2^{j-1}$$2^j$$f[i][0]$$f$$O(\log n)$$O(\log n)$$x$$(x,y)$$y$$y$$LCA(x,y)=z$$x$$z$$y$$z$$x$$y$$z$$z$$x$$y$$f[i][j]$$i$$2^j$$LCA(x,y)$$x$$y$… text/html 2020-09-03T19:57:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:lotk&rev=1599134232&do=diff 数据结构 树套树 带花树 ac自动机 后缀数组 个人练习 Codeforces Round #641 (Div. 2) prob:5/6 rank:170 2020.8.9 Atcoder Beginner Contest 047 prob:2/6 rank：415 AtCoder Beginner Contest 176 prob:5/6 rank：889 text/html 2020-05-08T16:28:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:lotk_%E4%B8%BB%E5%B8%AD%E6%A0%91&rev=1588926515&do=diff 主席树 引入 给定一个数列，每次询问[L,R],求区间的kth。 如何解决？ 暴力：对于每一个询问，排个序，就行了，时间复杂度$O(nmlogn)$ 莫队+树状数组：树状数组可以求给定区间kth,使用二分+树状数组，具体不展开，但是多个区间的话，需要不断地进行树状数组的add/del操作，那么使用莫队来优化区间端点的移动问题，时间复杂度$O((n+m)\sqrt{n}logn)$$O((n+m)\sqrt{n}logn)$$O(nlogn)$$O(logn)$$4n^2$$logn$$O(nlogn)$$log^2n$$O(nlog^2n)$… text/html 2020-05-08T16:53:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:lotk_%E6%A0%91%E5%A5%97%E6%A0%91&rev=1588927983&do=diff 树套树 线段树套线段树 虽然称为线段树套线段树，其实大多是通过树状数组套主席树来实现的(没错就是[带修主席树](<http://hotpot.clatisus.com/LOTK%ef%bc%88lxh%ef%bc%89/>主席树))，用以实现查询k在区间内的排名，查询区间内排名为k的数，修改某一位的值，查询某一位的前驱后继等。$log$$log$ text/html 2020-07-31T15:58:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:m-solutionsprogrammingcontest2020&rev=1596182296&do=diff M-SOLUTIONS Programming Contest 2020 A - Kyu in AtCoder 题目大意 给出一个$x$，根据$x$除以200的结果输出不同的结果 数据范围 $400 \le x \le 1999$ 解题思路 水题，若干个if即可解决 B - Magic 2 题目大意 给出$A,B,c$，每次操作可以把某个数乘以2，问能不能再$K$$A < B < C$$1 \le A,B,C,K \le 7$$n$$A_i$$K + 1$$K-1$$K$$1 \le n \le 200000$$1 \le K \le N-1$$1 \le A_i \le 10^9$$i$$i-K$$O(n)$$n$$1 \le n \le 80$$100 \le A_i \le 200$$a_i$$n\le 15$$n\times 3^15$$1 \le n,X_i,Y_i \le 200000$… text/html 2020-09-04T12:09:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:misakatao&rev=1599192557&do=diff $2 \bigoplus 10= 8$ 图论 最小生成树 拓扑排序 Tarjan算法 回路问题 对偶图 树的直径和重心 LCA问题 树链剖分 树上差分 个人训练 Codeforces645 Div2 prob:4/5/6 rank:523 2020.7.17 AIsing Programming Contest 2020 prob:4/5/6 rank:933 2020.7.21 Codeforces Round #658 prob:5/5/6 rank:114 2020.7.24 Topcoder SRM 788 DIV2 prob:3/3/3 2020.7.25 M-SOLUTIONS Programming Contest 2020 prob:5/5/6 rank:282 2020.7.30 Codeforces Round #660 prob:4/4/5 rank:261 2020.8.2 Atcoder Beginner Contest 174 prob:6/6/6 rank:281 2020.8.29… text/html 2020-05-09T12:47:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:mst&rev=1588999649&do=diff 问题概述 生成树问题是指在一个连通图中选择若干条边，是这些选择的边和所有图中的点组成一棵树的问题。而如果这个连通图是带权连通图，那么最小生成树指的就是所有生成树中边权之和最小的生成树。$s$$G=\langle E,V \rangle$$V$$S,T$$S \cup T = V$$S \cap T = \emptyset$$S={s}$$T$$S$$T$$S$$n-1$$O(V^2)$$O(E \log V)$$O(E+V \log V)$$n-1$$O(E \log E)$$n$$i$$c_i$$i,j$$(k_i + k_j) \times d$$d$$c_i$ text/html 2020-05-29T18:03:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015&rev=1590746613&do=diff 比赛信息 * 日期：2020.5.23 * 比赛地址： 传送门 * 做题情况：lxh(AG)，tyx(BCF)，gyp(DE) 题解 A - Adjoin the Networks solved by lxh,tyx written by lxh 题意 给出一个森林，求一种链接方式，将森林连成一棵树，并让树的直径最短。$ 0 \le c \le 10000$$a,b$$a \le b$$ b \ge a+3 $$ b $$ b == a+2 $$b$$b+1$$b$$ b == a+1 $$ b+1 $$n$$n$$n$$1 \le n \le 8$$n$$n+1$$s$$|s| \le 300$$O(n)$$n$$k$$n,k \le 10^5$$O(n)$$1 \le k < n \le 100000$$k$$k+1$$T + 1$$T \le 10^4$$n \le 100$$f \le 10$$L$$L$$T + 1$$O(Tnf)$$\le 10^5$$\le 2\times 10^4$$0 \le xi,yi \le 10^4$$ r \le … text/html 2020-05-06T12:53:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2016&rev=1588740783&do=diff 比赛信息 * 日期：2020.3.13 * 比赛地址： 传送门 * 做题情况：lxh(AB)，tyx(ACGJ)，gyp(EF) 题解 * A - Artwork * solved by tyx,lxh * 题意：在一张图上染色，每次给出$xi,yi,xj,yj$,将从$(xi,yi)$到$(xj,yj)$的路径染黑(保证有$xi==xj||yi==yj$)，问每次这样操作后将图分成了多少个不连通的白块。$1 \le n,m \le 1000$$1 \le q \le 10^4$$w[i][j]+=1$$w[i][j]==0$ text/html 2020-05-06T14:42:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:planandrecord&rev=1588747341&do=diff (占位用) text/html 2020-05-06T14:37:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:skilltree&rev=1588747077&do=diff (占位用) text/html 2020-06-26T16:46:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:spring_training&rev=1593161197&do=diff 2020.3.13 Nordic Collegiate Programming Contest 2016 prob:7/9/11 rank:4/202 2020.5.2 Acm Google Cup 2011 Invitational Programming Contest prob:4/6/10 rank:11/69 2020.5.9 CTU Open Contest 2016 prob:5/6/10 rank:5/89 2020.5.23 Nordic Collegiate Programming Contest 2015 prob:7/7/10 rank:1/29 2020.6.26 German Collegiate Programming Contest 2015 prob:10/10/11 rank:1/29 text/html 2020-05-13T20:25:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:tarjan&rev=1589372739&do=diff 问题概述 Tarjan算法是一种由Robert·Tarjan（罗伯特·塔杨）发明的在有向图中求强连通分量的算法。 概念描述 如果在一个有向图中，任意两个顶点都可以相互到达，则称这个有向图为强连通图，非强连通图的极大强连通子图称为强连通分量。$N$$M$$(a,b)$$a$$b$$a$$b$$b$$c$$a$$c$ text/html 2020-07-31T12:09:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:topcodersrm788div2&rev=1596168565&do=diff Topcoder SRM 788 DIV 2 300 - NextOlympics 题目大意 已知2021东京奥运会要在7月23日举行，给出一个日期，求离这个日期还有几天 数据范围 略 解题思路 直接模拟即可 500 - StarsInTheSky 题目大意 平面上有$n$$(x_i,y_i)$$1 \le n \le 15$$O(n^4)$$n \times n$$A_{ij}$$1 \le n \le 25$$1 \le A_{ij} \le 100$$1$$100$$O(100 \times n^2 \times \log 100)$ text/html 2020-05-17T09:23:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:toposort&rev=1589678608&do=diff 问题概述 拓扑排序是一种一般在有向无环图(DAG)上实现的算法，其主要目的是把这一有向无环图的顶点排列成一个线性的序列，并且对于图中的任意一条单向边$\langle u,v \rangle$，点$u$在点$v$之前。 算法实现 拓扑排序的流程如下。$<u,v>$$u$$v$$O(n)$$O(n)$$O(n)$ text/html 2020-07-22T13:52:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:treechain&rev=1595397173&do=diff 问题概述 不知道从什么时候开始很多序列问题都可以“上树”，“上树”的意思就是在树上进行询问。比如把非常常见的区间求和\最值或者带修改区间求和\最值放到树上，变成树上两个点之间的路径上的权值求和\最值。而树链剖分可以在不错的时间内实现序列问题上树的求解，其具体方式就是把树按照某种方式分成多条链，然后把这些链排成一个一维区间，只要我们能够保证不跨链操作，问题就又变回了序列问题。$i$$f_i$$dep_i$$size_i$$i$$O(\log n)$$x$$y$$size_y \le \frac{1}{2} \times size_x$$O(\log n)$$O(\log n)$$top_i$$O(\log n)$$O(\log n)$$O(\log^2 n)$$O(\log n)$$i$$f_i$$f_i$$dep_i$$O(\sqrt{n})$$k$$k$$k$$k$$k$$n$$O(n)$$x$$k$$k$$k_b$$x$$k_b$$x′$$k - k_b < \frac{k}{2}$$x′$$k_b$$k-k_b$$x′$$k-k_b$$x′$$k-k_b$… text/html 2020-08-21T15:31:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:treediff&rev=1597995070&do=diff 问题概述 差分一般是用来解决修改多而查询少的区间问题，而树上差分顾名思义就是把差分的思想应用到树上从而使我们算法的复杂度可以降低 普通差分 我们首先介绍最简单的差分情况来描述差分的思想。$O(n \log n)$$i$$a_i$$d_i = a_i - a_{i-1}(i \ge 2)$$d_1 = a_1$$a_i$$d_i$$d_i$$[l,r]$$x$$d_i$$a_l - a_{l-1}$$d_l$$x$$a_{r+1}-a_r$$d_{r+1}$$x$$d_i$$a_i$$O(q+n)$$q$$x$$O(n \log^2 n)$$x$$x$$O(q \log n + n)$$+2x$$-2x$$+2x$$-x$$x$$x$$2x$… text/html 2020-07-17T16:03:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:tyxaisingprogrammingcontest2020&rev=1594973014&do=diff AIsing Programming Contest 2020 A - Number of Multiples 题目大意 给出$L,R,d$，问$[L,R]$中有多少$d$的倍数 数据范围 $1 \le L \le R \le 100$，$1 \le d \le 100$ 解题思路 数据范围只有100，直接枚举即可 Comment 非常纯粹的水题 B - An Odd Problem 题目大意 $n$$a_i$$i$$a_i$$1 \le n,a_i \le 100$$f(n)$$x^2+y^2+z^2+xy+yz+zx=n$$(x,y,z)$$n$$f(1),f(2) \ldots f(n)$$1 \le n \le 10^4$$n$$x,y,z$$(x,y,z)$$N$$n$$O(100^3)$$f(x)$$x$$x$$x\ mod\ f(x)$$x$$n$$n$$i$$1 \le n \le 2 \times 10^5$$n$$f(x)$$O(n^2)$$n$$K_i,L_i,R_i$$n$$K_i$$L_i$$R_i$$1 \le T,n \le 10^… text/html 2020-09-03T19:46:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:hotpot:weeklyreport&rev=1599133584&do=diff 2020/05/02——2020/05/08周报 2020/05/09——2020/05/15周报 2020/05/16——2020/05/22周报 2020/05/23——2020/05/29周报 2020/05/30——2020/06/05周报 2020/06/06——2020/06/12周报 2020/06/13——2020/06/19周报 2020/06/20——2020/06/26周报 2020/07/11——2020/07/17周报 2020/07/18——2020/07/24周报 2020/07/25——2020/07/31周报 2020/08/01——2020/08/07周报 2020/08/08——2020/08/14周报 2020/08/15——2020/08/21周报 2020/08/22——2020/08/28周报 2020/08/29——2020/09/04周报…