CVBB ACM Team 2020-2021:teams:alchemist

2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1

Anonymous (anonymous@undisclosed.example.com) — 2020-07-16T23:33:03+0800

简况比赛链接 AC 5题，Rank 19th 总结与反思 cmx lpy xsy 题解 A 论文题，题解说最终的顺序是求出B-function以后的后缀数组的顺序，原理不懂。比赛时的想法是快速比较任意两个串的B-function，先把原串的B-function求出来，任意一个后缀的B-function都是原串B-function的一个后缀，再把第一个a和第一个b的位置变成0。\begin{gather*} & \max:b^{T}P &\\ & s.t:\sum_{i=1}^{N}e_{i}y_{i}^{2}\leq 1,e_{i}为D对角元 &\\ \end{gather*}$水题,取3倍maxlen比较,据说2倍就行,不会证明$$gamma$$\frac{1}{k}$$\frac{1}{k} \leq cap < \frac{1}{k+1}$$k+1$$TLE$…

2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T10:41:21+0800

简况比赛链接 AC 6题，Rank 39th 总结与反思 cmx 主要还是思维问题，EG两题一直在xsy卡题的时候思考，还是没有想出来。另外以后看一道题要把内容共享给队友，节省看题时间 lpy 题目最好全看完，没有思路可以去看看没看过的题目，不要盲目跟榜$cnt[next[i]] = cnt[next[i]] - cnt[i]$$O$$A, B, O$$OA, OB$$n$$\frac{n(n-1)}{2}$$O(n^2\log n)$$00:00:00$$(i,j)$$(i+K,j+K)$$(a,b)=(a+b,a)=(a,b+a)$$a, b$$x$$x$$x$$x$$x$$logN$$i>19$$ans[i]=ans[i-2]$$i \leq 19$$S_i$$S_i[j]=1$$A_i\ge B_j$$cur_i$$cur_i[j]$$$cur_i=(cur_{i+1}>>1|I_m)\&S_i$$$cur_i$$cur_i[0]$$S_i$$m+1$$O(nm/64)$…

2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T11:12:45+0800

简况比赛链接 AC 8题，Rank 49th 总结与反思 cmx 写东西胆子还是大一些，这场的H笛卡尔树几乎是个裸题，可惜信心不足，要是写出来了就幸福了。另外D其实是想到一个更简单搞法的，不知为啥脑抽了。$m/2/2,m/2-m/2/2$$[m/2-m/2/2,m/2/2*(m/2-m/2/2)]$$a,b > 1$$c > 1$$d$$2(a+b)+2c+2+4d=m,ab+c+d=n$$c+d$$ab$$2(a+b)+2c+2+4d=m,ab-e+c+d=n,0 \leq e < b$$(1,2)(3,4)\ldots$$4|n$$(1,4)(2,3)$$4\nmid n$$(1,4)(2,3)$$(1,2)(3,4)$$dp$$dp[i] = dp[i - 4] + (a[i] - a[i - 3]) * 2$$dp[i] = min(dp[i], dp[i - 6] + (a[i] - a[i - 5]) * 2)$$d=f$$gcd(a,b)>1$$(d,f)=x,\frac{c}{d}-\frac{e}{f}=\frac{c\frac{f}{x}-e\frac…

2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_4

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T11:23:38+0800

简况比赛链接 AC 5题，Rank 18th 总结与反思 cmx 学了这么久广义后缀自动机还是不会C题（最后用其他方法勉强过了），思维还是需要训练。 lpy 比较函数必须得返回一个准确大小关系，如果关键字全相同可能会炸内存(递归栈)$k$$x$$x$$k$$dfs$$ \times \log$$\leq \frac{n}{x + 1} + 1$$ \times \log$$O(n\log^2 n)$$c^{x的质因子个数}$$f(S,i,n)$$n$$j-i$$j-i$$10N$$S_i$$10N$$O(N*10*10)$$mlen[cur] - mlen[lnk[cur]]$$f(S,i,n)$$f(S,i,n)$$N*10*10$$O(N*10*10*10*log(N*10*10)+N*10*10*logN)$$\leq 9$$n$$\Leftarrow 1$$x \rightarrow x$$lcp+1$$\leq 9$$x \rightarrow x + 1$$9999x$$10000y$$x > y$$x \rightarrow x - 1, x > 1$$…

2020-2021:teams:alchemist:2020_self_training_1

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T10:38:49+0800

简况比赛链接 AC 9题，Rank 9th 总结与反思 cmx lpy 网络流多组数据初始化时得多加注意 xsy 总体还行，不过签到题因为数组开小和没开long long -2多少带点脑瘫。题解 A - Xiongnu's Land 签到题，可以利用差分维护一下一块土地对某个位置的贡献。$6^6$$source \rightarrow i$$i \rightarrow i'$$i' \rightarrow j$$j$$i$$target \rightarrow sink$$\infty$$4$$3$$next_permutation$$n$$n - 1$$n$$n$$n - 4$$f(2x)=3f(x),f(2x+1)=3f(x)+1$$f(x)$$3$$x$$2$$dp$…

2020-2021:teams:alchemist:front_page

Anonymous (anonymous@undisclosed.example.com) — 2020-08-28T14:14:45+0800

2020年五月，我们重新出发... 本页的个人内容链接建议加上个人的命名空间训练记录模板 ---------- 训练记录 2020年5月 2020/05/03 PKU Campus 2017 2020/05/04 PKU Campus 2019 2020/05/09 2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16) 2020/05/18 牛客假日团队赛41 2020年7月 2020/07/12 2020牛客暑期多校训练营（第一场） 2020/07/13 2020牛客暑期多校训练营（第二场） 2020/07/17 2015 ACM-ICPC Asia Beijing Regional Contest 2020/07/19 2020牛客暑期多校训练营（第三场） 2020/07/21 2020牛客暑期多校训练营（第四场） ---------- Max.D. Max.D.（陈铭煊）个人杂页个人战记 CF战记其他战记技能树字符串类 FFT/NTT/FWT相关 C…

2020-2021:teams:alchemist:fwt

Anonymous (anonymous@undisclosed.example.com) — 2020-05-24T20:53:57+0800

FWT(待更新) 简介 $\mathrm{FWT}$（快速沃尔什变换），是用来处理将按位运算作为操作符的多项式卷积，以及其衍生出来的一些问题。在接触之前，你必须已经基本掌握$\mathrm{FFT}$（快速傅里叶变换），两者的原理内核基本一致。$\mathrm{FWT}$$$ \begin{array}{l} C_{k}=\sum_{i | j=k} A_{i} * B_{j} \\ C_{k}=\sum_{i \& j=k} A_{i} * B_{j} \\ C_{k}=\sum_{i \wedge j=k} A_{i} * B_{j} \end{array} $$$\mathrm{FFT}$$\mathrm{FFT}$$\mathrm{FWT}(A)$$$ \mathrm{F W T}(C)=\mathrm{F W T}(A) * \mathrm{F W T}(B) $$$$ \begin{aligned} &A+B=\left(A_{0}+B_{0}, A_{1}+B_{1}, \dots \dots\right)\\ &\begin{array}{l} A-B=\lef…

2020-2021:teams:alchemist:maxdumbledore_others

Anonymous (anonymous@undisclosed.example.com) — 2020-05-06T16:17:42+0800

。

2020-2021:teams:alchemist:nowcoder_weekly_41

Anonymous (anonymous@undisclosed.example.com) — 2020-05-22T18:44:57+0800

简况比赛链接 AC 10题，Rank 3th 总结与反思 cmx 我个人认为自己很差劲的地方还是补题方面，这一场截至5月22日我仍然没有进行补题，包括之前训练的那些场我的补题习惯并不良好。以后我会督促自己，每天最最少化半个小时时间进行补题。

2020-2021:teams:alchemist:pku_campus_2017

Anonymous (anonymous@undisclosed.example.com) — 2020-05-08T22:40:25+0800

简况比赛链接 AC 7题，Rank 9th 总结与反思 cmx lpy 计算几何还需加强(C题) 要选择正确的容器以及判断是否快读(E题) xsy 构造题做的太慢了，规律应该能更早看出来，分类讨论的时候一定要注意全面。$(1, 2)$$(2, 1)$$AA$$n*m$$1*2$$n*m$$n 5$$n > 4$$n$$m$$n > 4$$m > 4$$n = 5, m = 6$$n = 6, m = 6$$n$$(m - 1, n)$$n$$n > 5$$m$$m$$n = 5$$n = 5, m = 6$$n = 5, m = 8时$$P$$C$$\overrightarrow{PC}$$F$$PF$$\Gamma$$Q$$\Gamma$$P,Q$$D$$PQ$$C$$G$$r=DP=DQ=DG,DG=R-r,DP+DG=R$$设f(D)=DP+DG在垂直平分线上应该是至多存在两点D_{1},D_{2},s.t\quad f(D_{i})=R$$f(D)$$f(D)$$D_{0}(为最小值)$$D_{i…

2020-2021:teams:alchemist:pku_campus_2019

Anonymous (anonymous@undisclosed.example.com) — 2020-05-08T10:54:43+0800

简况比赛链接 AC 5题，Rank 26th 总结与反思 cmx lpy xsy F题让输出id输出了序号，C题加绝对值给自己加晕了导致白给WA。 C题最开始的时候考虑到了改$y$但是咋就没想到改$x$，弄了一个假的贪心乱WA。像个憨批。$l$$l$$2$$1$$2N$$1\leq x \leq N, 1 \leq y \leq 2$$2N$$y>2$$(x,2)$$y<1$$(x,1)$$x$$1\leq x \leq N, 1 \leq y \leq 2$$\{a_{i}\}_{i=1}^{n}$$(l,r,x)$$\sum_{i=l}^{r}[gcd(a_{i},x)==1]$$[1,r]$$1-n中与m互素的数的个数$$\mu(d)\neq 0$$1-1e5$$\mu(d)\neq 0的d$$f[r][d]表示a_{1}\sim a_{r}中,\{i:d|a_{i}\}的集合大小$$\sigma_{0}(x)\leq 128$$f[r][d]$$d$$f[r][d]$$r$$a_{r}$$\sigma_{0}(a_{r})$$d$$d$$upper_bo…

2020-2021:teams:alchemist:sppc_16

Anonymous (anonymous@undisclosed.example.com) — 2020-05-10T22:35:58+0800

简况比赛链接 AC 9题，Rank 21th 总结与反思 cmx 这次还是犯了太急躁的毛病，没有想完全就直接上手了，结果发现问题重重。以后切记耐心。 lpy 以前鸽掉了$FFT$匹配字符串算法,导致C题卡在预处理上 $n$$x$$y$$[l, r)$$ l < r \leq 10^6, r - l \leq 10^5$$x$$i$$i$$x$$O(r)$$r$$n=1$$i$$i + 1$$U(Uncertain)$$\land,\lor,\rightarrow,\equiv$$\mathscr{C}: \mathscr{A} \rightarrow \mathscr{B}$$\land,\lor,\rightarrow,\equiv$$x \rightarrow x, x \equiv x; x \land x, x \lor x$$\leq 1$$\leq 2$$\leq n$$\leq 2n$$t$$x$$x + t$$n$$[l,r]$$[lmin,rmax]$$[l,r]$$l_{i_{1}}\leq r_{i_{1}} \leq l_{i_{2}} \le…

2020-2021:teams:alchemist:teamskill

Anonymous (anonymous@undisclosed.example.com) — 2020-05-15T20:02:13+0800

团队技能树感谢i_dont_know_png队提供的技术支持。图论知识点 Max.D. Hardict MountVoom 最短路 Dijstra Y SPFA Y

2020-2021:teams:alchemist:training_record_template

Anonymous (anonymous@undisclosed.example.com) — 2020-05-06T17:45:33+0800

简况比赛链接 AC ?题，Rank ?th 总结与反思 cmx lpy xsy 题解 A. XXXX ... by cmx 补题

2020-2021:teams:alchemist:weekly_digest_1

Anonymous (anonymous@undisclosed.example.com) — 2020-05-12T01:11:15+0800

本周推荐陈铭煊 Max.D. 子集卷积简介一般我们有如下一类的状压dp方程，如$dp[i]=\sum dp[j]*w[k]$ ($i,j,k$满足$j\lor k=i,j \land k=0$，这里符号表示按位与和按位或。如果暴力枚举位的子集，那么效率是$3^n$的，难以承受。实际上这个已经很接近一个FWT卷积的形式了，只不过是还要$j\land k=0$$j$$k$$i$$dp$$$ dp[cnt_i][i]=\sum_{(j|k)==i}dp[cnt_j][j]*w[cnt_i-cnt_j][k] $$$cnt_i$$cnt_i$$i$$dp$$w$$cnt$$dp$$dp[cnt_i]$$cnt_i$$dp$$n$$n^2$$O((2^n*n)*n+n^2*2^n)=O(n^2*2^n)$$i|j$$(i|j)+k$$((i|j)+k)\otimes h$$\mu(i) \neq 0$$\pm epsilon$$\{a_{i}\}_{i=1}^{n}$$f[n]=1+\sum_{1\leq i

2020-2021:teams:alchemist:weekly_digest_2

Anonymous (anonymous@undisclosed.example.com) — 2020-05-19T16:24:19+0800

个人总结陈铭煊 Max.D. 本周是比较摸的一周，主要学习了一下广义后缀自动机（不敢说自己已经会了），稍微写了下FWT的知识库。龙鹏宇 Hardict 摸鱼ing 学习了递推容斥系数计算,学习了三次剩余(非BSGS)$\log n$$\log n$$平面图边数至多为3|V|-6(V+F-E=2,F至多2|V|-4)$$P(x)=\sum_{i=0}^{\infty} p_{i}x^{i},p_{i}为概率i,p_{i}具有线性递推关系,那么期望即P^{'}(1)$$考虑H(x)=P(x)G(x),G(x)为递推的联接多项式,后|G(x)|项都应为0$$P^{'}(1)=\frac{H^{'}(1)G(1)-H(1)G^{'}(1)}{G(1)^{2}}$$实际计算时,若P(x)截取2n项,G(x)由BM算法不超过n项,H(x)也应该只截取前2n项$…

2020-2021:teams:alchemist:weekly_digest_3

Anonymous (anonymous@undisclosed.example.com) — 2020-05-24T21:14:33+0800

个人总结陈铭煊 Max.D. 这一周的话主要打了两场牛客的比赛，其余的话没有学习知识龙鹏宇 Hardict 肖思炀 MountVoom 这个人已经死在计网实验了本周推荐陈铭煊 Max.D. 来推荐一道方法很神仙的题目，$(u,v),s.t: \exists t \neq u,v,t在(u,v)简单路径上,且(u,t),(t,v)分别黑白平衡$$(u,v)$$边权值:黑:1;白:-1$$dis(u,v)=0$$r$$(x,y)$$dis(r,x)=-dis(r,y),\exists z 为x或y的祖先,s.t:dis(r,x/y)=dis(r,z)$$z$$f[d][0]与g[-d][1]组合,f[d][1]与g[-d][0/1]组合$…

2020-2021:teams:alchemist:weekly_digest_4

Anonymous (anonymous@undisclosed.example.com) — 2020-06-06T23:23:09+0800

个人总结陈铭煊 Max.D. 无龙鹏宇 Hardict 肖思炀 MountVoom 这个人还没从计网实验中活过来本周推荐陈铭煊 Max.D. 无龙鹏宇 Hardict 肖思炀 MountVoom 无

2020-2021:teams:alchemist:weekly_digest_5

Anonymous (anonymous@undisclosed.example.com) — 2020-06-06T23:40:58+0800

个人总结陈铭煊 Max.D. 这周还是很忙，暂无进一步的学习记录。龙鹏宇 Hardict 肖思炀 MountVoom 这个人还没从计网实验中活过来本周推荐陈铭煊 Max.D. 推荐这样一道题：https://ac.nowcoder.com/acm/contest/5633/D$a$$p$$i$$p[i]\neq a[i]$$a[i]=i$$g(x)$$x$$p[i]$$f(x)=x!$$g(x)\times f(n-x)$$x$$$ \sum_{i=0}^{n}(-1)^{i} * g(x) * f(n-x) $$$h_i$$i$$p$$$ g(0)=1, g(k)=0(k>1) $$$dp$$i$$x$$p[i]$$g(x)=dp[n][x]$$dp[i][x]=dp[i-1][x]+dp[i-1][x-1]*h[i]$$g(i)$$O(n^2)$…

2020-2021:teams:alchemist:weekly_digest_6

Anonymous (anonymous@undisclosed.example.com) — 2020-07-18T10:21:10+0800

个人总结陈铭煊 Max.D. 本周学习了一点计算几何，带花树算法，补了两次牛客竞赛的题各两道。其他暂无。龙鹏宇 Hardict 复习了下最大流的最大权闭合子图复习min25筛肖思炀 MountVoom 本周主要做了两场牛客，和zzh队一起训练了一套区域赛。$10^3$$n$$(u, v)$$v = n$$a[n]$$n$

2020-2021:teams:alchemist:weekly_digest_7

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T20:16:05+0800

Summer Tranning Week 2 2020/07/17 2015 ACM-ICPC Asia Beijing Regional Contest pro 7/7/10 rank 9/??? 2020.07.18 2020牛客暑期多校训练营（第三场） pro 8/9/12 rank 49/??? 2020.07.20 2020牛客暑期多校训练营（第四场） pro 5/6/10 rank 18/???$O(n^{\frac{2}{3}})$$min25$$S$$m$$T_1,T_2,\ldots,T_m$$q$$l,r,p_l,p_r$$S$$[p_l,p_r]$$T_l,T_{l+1},\ldots,T_r$$1\le |S|\le 5\times10^5,1\le m\le 5\times 10^4,1\le \sum^m_{i=1}|T_i|\le 5\times 10^4,1\le q\le 5\times 10^5$$6s$$S$$T_1,\ldots,T_m$$[p_l,p_r]$$[1,p_r]$$lnk$$T_i$$cur$$T_i$$S$$S$$S$$[1…

2020-2021:teams:alchemist:weekly_digest_8

Anonymous (anonymous@undisclosed.example.com) — 2020-07-31T11:43:12+0800

Summer Tranning Week 3 比赛简记 2020.07.25 2020牛客暑期多校训练营（第五场） pro 5/6/11 rank 46/??? 2020.07.27 2020牛客暑期多校训练营（第六场） pro 7/8/11 rank 35/??? Max.D. 专题本周暂无比赛主要是两场CF，一场涨了一场跌了，基本等于没打（苍天啊）$n$$n-1$$i$$p_i$$1$$h_i$$h_i,p_i$$1\le t\le 10000,1\le n\le 10^5,1\le m=\sum p_i\le 10^9,-10^9\le h^i\le 10^9, \sum n\le 2*10^5$$p_i$$h_i$$i$$[0,p_i]$$h$$p$$-p_i$$T\leq 10^5$$\sum_{i=0}^{m}C_{n}^{i}$$1\leq n,m\leq 10^5$$pre[n][m]=\sum_{i=0}^m C_n^i$$pre[n][m]=pre[n][m-1]+C_n^m,pre[n][m]=\sum_{i=0}^m (C_{n-1}^i+…

2020-2021:teams:alchemist:weekly_digest_9

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T17:05:40+0800

Summer Tranning Week 4 比赛简记 2020.08.01 2020牛客暑期多校训练营（第七场） pro 5/6/10 rank 27/??? 2020.08.03 2020牛客暑期多校训练营（第八场） pro 4/5/11 rank 42/??? 2020.08.06 2020-2021 BUAA ICPC Team Supplementary Training 02 $\log$$T$$n$$F(x)=0$$m$$x$$w$$w-dist(x,i)$$dist(x,i)$$x$$i$$x$$\min(F(x),0)$$F(x)$$1\le T\le 5,1\le n,m\le 5 \times 10^4,0\le w\le 10000$$3$$S,dp,ddp$$S[i]$$i$$1$$dp[i]$$i$$i$$pa[i]$$i$$pa[i]=i$$ddp[i]$$i$$i$$1$$F(x)$$dist$$x$$pa[u]$$u$$x$$pa[u]$$u$$pa[u]$$ddp[pa[u]]-dp[u]$$x$$pa[u]$$ddp$$dp$$Dis$$\…

2020-2021:teams:alchemist:weekly_digest_10

Anonymous (anonymous@undisclosed.example.com) — 2020-08-14T22:11:23+0800

Summer Tranning Week 5 比赛简记 Max.D. 专题本周暂无比赛百度之星复赛（凉凉，只写了两题没拿到衣服）一场cf div2，rating小涨题目暂无 Hardict 专题无比赛百度之星一场题目暂无$n$$[L_i,R_i]$$a$$|[L_{a_1},R_{a_1}]\cap[L_{a_2},R_{a_2}]\cap\ldots\cap[L_{a_m},R_{a_m}]|^2$$998244353$$1\le n\le 5\times 10^5,0\le L_i\le R_i\le 10^9$$dp$$i$$i$$（原子区间长度乘以左边的点的个数的和的两倍+原子区间长度平方）\times（2^{覆盖数}-1）$$O(n^2)$$dp$$dp[i][j][0/1]$$i$$X$$j$$X$$dp[i][j][0/1]=dp[i-1][j][0/1]\ (jR[i])$$dp[i][j][0]=dp[i-1][j][0]\times 2+(j-L[i])^2,dp[i][j][1]=dp…

2020-2021:teams:alchemist:weekly_digest_11

Anonymous (anonymous@undisclosed.example.com) — 2020-08-21T17:24:16+0800

Week 11 比赛简记 Max.D. 专题学习了一点计算几何比赛一场atcoder,一场cf global round rating小涨题目暂无 Hardict 专题无比赛 cf div2 题目暂无 MountVoom 专题无比赛打了atcoder，rating小涨。$n(1\le n \le 10^6)$$h$$h_{i+1}-h_i\ge 2$$i(1\le i< n)$$h_i=h_i+1,h_{i+1}=h_{i+1}-1$$h'$$1$$h_i,h_{i+1}$$1$$h_i$$1\sim i$$h_i$$h_{i-1},h_i$$1\sim i-1$$1$$h_{i-1},h_i$$1\sim i-1$$h_k,h_{k+1}$$h_{k+1},h_{k+2}$$1$$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$$b_{i}$$A=-sum{a[i]}$$f(x+A)$$f(x+A)$$b_j=…

2020-2021:teams:alchemist:weekly_digest_12

Anonymous (anonymous@undisclosed.example.com) — 2020-08-28T17:26:09+0800

Week 12 比赛简记 Max.D. 专题暂无比赛一场cf edu, 好惨好惨题目暂无 Hardict 专题无比赛 cf div2 涨回原rating 题目暂无 MountVoom 专题无比赛 cf edu, 算错了复杂度浪费了半个小时。$n$$L_i$$1000000007$$1\le n\le 10^5,\sum L_i\le 10^6$$dp$$dp[i][j]$$i$$j(0\le j \le L_i)$$i$$j=L_i$$O(n*\sum L_i)$$dp$$nxt$$nxt[i]$$i$$p,q$$nxt$$O((n+\log\sum L_i)*\log \sum L_i)$$4$$S_i$$C_i$$x_i$$x_i$$N$$w=x_1 \oplus x_2 \oplus x_3 \oplus x_4$$C_i$$w=0$$x_i$$N$$x_1$$x_2$$x_1=x_2$$S_i$$Hash:h(S_i,x_1)=c_k$$x_1=x_2$$x_1$$Hash$${x_2}$$原像碰撞$$x_1$$D$$…