luogu中文题面：https://www.luogu.com.cn/problem/CF1988D树形dp。我们只关心子树的根节点v什么时候被删去。dp[u][i]+=min(dp[v][1...i-1,i+1...T]).T是log(n)的。因为\(T\leqMex(u)\),而考虑要多少节点使\(Mex(u)=T\),有\(f_T=1+f_1+...f_{T-1}\)得\(T=log_2n\)不

  CODE:1#include<bits/stdc++.h>2#definerep(i,a,b)for(inti=a;i<=b;i++)3#definedwn(i,a,b)for(inti=a;i>=b;i--)4#defineMAXN1025015#defineinf999999996usingnamespacestd;7typedeflonglongll;8inlinein

A-Cake（神金，害我调了一个半小时）Alice和Bob玩一个游戏。游戏分为2阶段。阶段1：有一棵边权值为\(0\)或\(1\)的有根树，两人轮流走，Alice先走，走到叶子就停下来。记录下经过边的权值形成一个字符串\(S\)阶段2：Bob将一个蛋糕切成\(len(S)\)块，块可以为空。然后遍历\(S\)的

T4先把四组分成两组，左边两组叫\(L\)，右边两组叫\(R\)。直接爆搜每个数属于\(L\)还是\(R\)，过程中顺带\(01\)背包出两组分别能取到哪些子集异或和。接下来不妨设\(w_{f(A)}\gew_{f(B)}\)，\(w_{f(C)}\gew_{f(D)}\)。若\(w_{f(A)}\gew_{f(C)}\)，则答案为\(w_{f(A)}-w_

单峰数列题意对于一个整数数列，如果其先严格递增，然后在某一点后严格递减，我们称这个数列为单峰数列（严格递增和严格递减的部分均要是非空）。给定长度为n的整数数列\(a_1,a_2,…,a_n\)，请你支持q次操作：1lrx：将\(a_l,a_{l+1},…,a_r\)的每个数加x。2lr：判断\(a_l,a_{l

CF848CGoodbyeSouvenircdq分治求动态二维数点先考虑答案，对于一种颜色\(c\)，假设出现位置集合为\(S\)，每个位置的前继记为\(pre_i\)，那么可以写成：\[\sum\limits_{i\inS|pre_i\geL|i\leR}i-pre_i\]如果不修改，可以看到题目求的就是矩形横坐标\([1,R]\)到纵坐标\([L,n]\)

暑假集训CSP提高模拟4\(T1\)P134.WhiteandBlack\(0pts\)原题：[ARC148C]LightsOutonTree翻转方式：从根节点进行\(DFS\)，若遇到黑点就进行翻转。最后一定能使全树均为白点，即不存在无解的情况。进而有每个点仅会被主动翻转一次，且翻转顺序与最终结果无关。观察到

题意给长度为\(n\)的数组\(a\)，求长度不小于\(k\)的区间\([l,r]\)使得\(\gcd_{i=l}^ra_i\times\sum_{i=l}^ra_i\)最大，输出这个最大值。\(1\lek\len\le10^6,1\lea_i\le10^6\qquad\text{2.5s512MB}\)题解考虑分治（这是套路，想不到只能说做题少别打我）。

A编号为\(n\)的一定选，第二叠书在\(1\simn-1\)选最大的。voidsolve(){ cin>>n; for(inti=1;i<=n;++i){ cin>>a[i]; } intans=a[n]; intx=0; for(inti=1;i<n;++i){ x=max(x,a[i]); } cout<<ans+x<&

https://leetcode.cn/problems/block-placement-queries/description/有一条无限长的数轴，原点在0处，沿着x轴正方向无限延伸。给你一个二维数组queries，它包含两种操作：操作类型1：queries[i]=[1,x]。在距离原点x处建一个障碍物。数据保证当操作执行的时候，位置x处

杂数据结构选做持续更新ing...更新多少取决于我卷了多少似乎都是比较基础的东西，但是我数据结构太菜了，没办法╮（╯＿╰）╭#9016.CodeChefMINXORSEG有两种做法，我敲的后一种第一种先不考虑范围问题，考虑现在有三个点\(u,v,w\)，若它们的\(lcp\)为\(l\)，那么考虑第\(l+1\)位，根据

原题链接题解1.请务必读清题干意思2.如果以最顶端积木的位置为状态，是可以穷尽所有情况的，则状态为\(dp[i][l][r]\)，最顶端第\(i\)层只在区间\([l,r]\)内连续放置积木有几种方法3.状态转移方程$dp[i][l][r]=\sum_1^l\sum_r^mdp[i+1][x][y]$把\(x,y\)看成二维坐标上

A贸易题目保证输入的边\(u<v\)，说明题目中的图是一个有向无环图\(DAG\)，但是不一定连通。可以记录\(f[i]\)表示到达\(i\)之前能遇到的最小的价格，使用拓扑排序进行\(dp\)转移。对于每一个点\(i\),如果其价格为\(a[i]\),就可以用\(a[i]-f[i]\)更新答案，取最大值即

题意：称某个序列\(B=\{b_1,b_2,\cdots,b_n\}\)是另一个序列\(A=\{a_1,a_2,\cdots,a_m\}\)的拓展当且仅当存在正整数序列\(L=\{l_1,l_2,\cdots,l_m\}\)，将\(a_i\)替换为\(l_i\)个\(a_i\)后得到序列\(B\)。例如，\(\{1,3,3,3,2,2,2\}\)是\(\{1,3,3,2\}\)的拓展，

题目链接CodeforcesRound618(Div.1)A.AnuHasaFunction思路：我们把每个二进制位上的111看作是集合的不同的元素，二进制的位运算（按位与，按位或，按位异或）其实可以

原题链接题解太巧妙了！！层加式？code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lla[100005]={0};intmain(){llt;cin>>t;while(t--){lln;cin>>n;for(inti=1;i<=n;i++)cin>&g

原题链接题解这里和线性最大两段子段和不同，没有子段之间必须间隔一米，所以处理方式略有不同code#definelllonglong#include<bits/stdc++.h>usingnamespacestd;lla[200005]={0},pre[200005]={0},suf[200005]={0};intmain(){ios::sync_with_stdio(false);

原题链接题解代码量小的离谱，思维难度大的离谱对于两个原本不相邻的同色区域块，历经千辛万苦碰面的场景，我们可以描述成右边的区域块为左边的区域块消除的时候增添了长度设\(dp[i][j][suf]\)代表消除区域\([i,j]\)同时该区域的\(j\)增添了长度\(suf\)但是合并消除不一定

洛谷传送门CF传送门和CF1004FSonyaandBitwiseOR很像。考虑一次询问怎么做。考虑分治，每次只计算左端点在\([l,mid]\)，右端点在\([mid+1,r]\)的区间的贡献。对于每个\(i\in[l,mid]\)，维护最小的\(j\in[mid+1,r]\)使得\([i,j]\)的或\(\gev\)，那么\(\m

20240301由于笔者实力较弱，所以这只是Div2的题解。四年一次的比赛啊，还是要打。Dashboard-CodeforcesRound930(Div.2)-CodeforcesA.ShufflePartyYouaregivenanarray\(a_1,a_2,\ldots,a_n\).Initially,\(a_i=i\)foreach\(1\lei\len\).Theopera

CF1621GSolutionlink考虑对每个位置\(i\)作为\(i_j\)时计算贡献。\(i\)对一次答案有贡献当且仅当：设其子序列内最右端的位置为\(r\)，则要满足\(r\)右侧存在一个数大于\(a_{i}\)。即，设\(lst_i\)表示整个序列最右侧的大于\(a_i\)的数，要满足\(lst_i>r\)。现

代表元概念网络上没有明确的定义，只能在少量博客中找到一些信息大概是处理一类会算重的统计问题，在每个算重的集合中选出一个代表来统计以去重，就是代表元例子代表元只能说是一种思想，用于问题的转化与化简森林连通块数量可以用点数-边数快速计算但有些时候不好维护，于是我们考

模拟赛T1，纪念一下第一次场切紫。（话说场上这么多人切是不是都找到原了，就我这么傻想了半天）正难则反，很容易的将题目转化为选择若干种颜色，使这些颜色在原数组中的位置连续。设$pre_i$为颜色$i$最早出现的位置，$suf_i$为颜色$i$最晚出现的位置。假设通过选择若干颜色得到的位

解题思路贪心，能走距离最短的城市就一定走。分别考虑\(x>y\)和\(x<y\)的情况，两种情况分别是从后向前转移和从前往后转移，分别预处理一个前缀和和后缀和即可。AC代码#include<stdio.h>#include<stdlib.h>#include<valarray>#defineN100005#definelllonglongintn

Codeforcesdiv2C题补题1922C.ClosestCitiesC.ClosestCities很容易看出，端点的两个城市的最近城市就是他的直接后继和直接前驱，而中间的城市的最近城市就是他前驱和后继中距离绝对值最小的那个，因此我们可以先预处理出每个城市对应的最近城市，用map存储。然后因为区间可以从