https://wiki.cvbbacm.com/ 2026-04-30T02:29:48+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-09T01:15:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:mian:gary:codeforces_round_638_div_2&rev=1588958108&do=diff Codeforces Round #638 (Div. 2) Codeforces Round #638 (Div. 2) D. Phoenix and Science 题意 一个细菌，初始大小为$1$，每个周期内可选择分裂与否，周期结束时所有细菌大小$+1$，$T$组数据,给出$n$求最快多少周期可达到，输出每个周期分裂的数量$1 \le t \le 1000,2\le n \le 1e9$$n$$S=\Sigma 2^k$$S_t$$n$$n-S_k$$1,2,4,···,n-S_k,···，2^{t-1},2^t$$n$$a_i$$b_i$$k$$1 \le n,k \le 500,1\le a_i,b_i\le 1e9$$t$$t-1$$f(i,j)$$i$$j$$S_i$$i$$S_i-f(i,j)*k-j$$num_1$$k-num_1$$t_1=j-num_1+a_i,t_2=S_i-f(i,j)*k-j-k+num_1+b_i$$f(i+1,t_1\%k)=max(f(i+1,t_1\%k),f(i,j)+1+t_1/k+t_2/k)$… text/html 2020-05-28T22:27:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:mian:gary:mos_algorithm_tree&rev=1590676037&do=diff 树上莫队 总结时用到的博客： https://blog.csdn.net/qq_39759315/article/details/88553210 https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html 分块方式 首先需要解决$bzoj1086$王室联邦，此题的解法即为分块的方法 下只简述过程，每块内的节点个数在$[B,3B]$之间，操作方式为维护一个栈，从根节点开始$dfs$，对于某一点$x$$flg$$top-flg\ge B$$stack[flg+1]$$stack[top]$$x$$dfs$$i$$i$$i$$in[i]$$A$$out[i]$$i$$x$$y$$in[x]<in[y]$$lca(x,y)=x$$A[in[x]],\ldots,A[in[y]]$$lca(x,y)\neq x$$A[out[x]],\ldots,A[in[y]]$$lca(x,y)$$lca(x,y)$$vis$$(u_1,v_1)$$(u_2,v_2)$$(u_1,u_2)$$(v_1,v_2)$$vis$$lca$$lca$…