题面传送门提供一种和其他题解完全不同的解法。记\(P_0\)为题中给出的序列，\(P_1\)为\(P_0\)取反的结果。记\(S_{l\simr}\)表示\(S_lS_{l+1}\dotsS_{r}\)。方便起见，\(P\)下标从\(0\)开始，其余的串都是从\(1\)开始。这里用\(P_{0,i}=\operatorname{popcount(i)}

Day\(-1\)早上开了场CFDiv1+2VP，ABCD都一眼秒，E假了一发，然后仔细差分了一下才过。中午吃得有点饱，感觉车上要吐。上车和fls看了一下CSP2023大巴车上没看完的《爱乐之城》，然而看到一半眼皮撑不住了，电脑耳机给了fls，开始睡大觉。睡醒的时候fls刚好看完，不知道好不好看

二维structvec{ intx,y; vec(inta=0,intb=0):x(a),y(b){}};vecoperator+(constvec&a,constvec&b){ returnvec(a.x+b.x,a.y+b.y);}vecoperator-(constvec&a,constvec&b){ returnvec(a.x-b.x,a.y-b.y);}vecoperator*(constvec

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e5+10,M=2e5+10,Inf=1e9;namespaceFlow{ constllINF=1e18; constintV=N,E=M*2+N*2*2; ints,t,kk,head[V],cur[V],vis[V]; lld[V]; structedges{ intto,c,w,nex; }edg

思路来自这里。\(\operatorname{fib}(1)=\operatorname{fib}(2)=1,\operatorname{fib}(n)=\operatorname{fib}(n-1)+\operatorname{fib}(n-2),n\ge3\)那么：\(\sum\limits_{i=1}^n\operatorname{fib}^2(i)=\operatorname{fib}(n)\operatorname{fib}(n+1)\)可以考虑一下几

做了半天，然后打开题解发现里面全是\(O(n^3)/O(n^2)\)的。然后我的原来\(O(n^5)\)的前缀\(\max\)优化成\(O(n^4)\)的就非常

平衡树好题。考虑整体直接模拟操作。l-1x\(x\in[1,l]\)：不用动；\(x\in(l,2l]\)：整体减去\(l\)之后暴力插回去；\(x\in(2l,+\infty)\)：整体减\(l\)与第一段合并。lrx：区间加即可复杂度显然是2log的，考虑重新插入一次的时候值会减半。代码#include<bits/stdc++.h

题很简单，一遍写对却比较困难。犯的错误：预处理\({base}^i\)时应该要处理到\(\max\{n,m\}\)；去重的时候（reduce函数）特判\(m=1,2\)。代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=2e3+10,mod=1e9+7,base=23333;intn,m;chara

妙妙题。首先可以有一个\(O(kn^2)\)的dp，但是显然不行。但是，发现其中的大多数转移都浪费在自环上了，所以考虑不要这个东西。这个dp一共有三种转移：左右端点一起向内移动一格；左端点或右端点单独移动；左右端点都不动。所以考虑加一维\(k\)表示走了\(k\)次转移1

有一个显然的\(O(n^3q)\)的做法：设\(f_{i,l,r,x}\)表示\(i\)次操作过后，区间\([l,r]\)的数\(\lex\)，\(a_{l-1},a_{r+1}>x\)的方案数。转移：$$f_{i,l,r,x}=f_{i-1,l,r,x}\timesg_{l,r}+\sum\limits_{j<l}f_{i-1,j,r,x}\times(j-1)+\sum\limits_{j>r}f_{i-1,l

这类问题大概长这样：求一个排列\(p_{1\simn}\)，最小（大）化如下值：\[\sum\limits_{i=1}^{n-1}f(p_i,p_{i+1})\\f(i,j)= \left\{ \begin{array}{**lr**} g(i)+h(j),i<j\\ h(i)+g(j),i>j \end{array} \right.\]那么就可以用如下方法\(O(n^2)\)解决：从小到大向序列中

好像没做过DAG计数的题。首先看到数据范围，考虑状压。方便起见，记\(cnt_{S,T}=\sum\limits_{(u,v)\inE}[u\inS\andv\inT]\)。设\(f_S\)表示\(S\)为强连通分量的选边方案数，由于正面很难算。考虑反面：\[f_S=2^{cnt_{S,S}}-\sum\limits_{\varnothing\subsetneqqT\s

link思维+容斥计数。首先的转化比较妙，二分图转化为\(n\timesn\)的网格图染色。与网络流的转化方向相反，值得注意。然后发现两种颜色（红、蓝）如果独立染色，同一个格子可能会重复染色。考虑容斥，式子很好列，直接容斥即可。\[ans=\sum\limits_{i=0}^n(-1)^n\times\binom{n}{i

发现根节点一定是\(1\)，所以考虑两边的子树深度，然后发现只需要考虑一段后缀或前缀的深度即可。所以循环位移后，可以从中间往两边构建笛卡尔树，实时维护深度即可。代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=2e5+10;intn,a[N],ans[N];

解题思路容易想到从小到大加数，维护每个点的子树大小。可转化为维护每个点为\(\max\)时的\([L,R]\)区间。然后需要写一个支持【区间+1】、【区间取min】、单点加入、全局查询。上个吉司机线段树即可。注意点吉司机线段树下推\(fi\)的标记的时候要注意\(fi\)的变化

tarjan多测的时候dfn数组要清空！！！树剖多测的时候son数组要清空！！！点双tarjan时可用vector建边，边双时用vector需要无重边本题直接建圆方树，然后答案就是关键点构成的虚树上非关键原点个数。代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;

赛时想写60pts，结果cxr似乎少算了一点空间，导致我一直没把空间卡过去QWQ。当时不会dfs求拓扑序，这里讲一下。枚举所有非访问过的点依次dfs，每次进行下列操作：找出\(v\)的一个未访问过的入点\(u\)，调用dfs(u)；找不到\(u\)的时候，把\(v\)加入拓扑序列中。代码#inc

要点不多，记一下即可。\(G\)的对偶图记为\(G^*\)。\(G^*\)为连通图，若\(G\)联通，则\(G^{*}{^*}=G\)\(G^*\)中的简单环对应着\(G\)中的极小割，（简单对应极小），利用该性质，可以把平面图上的最小割问题转化为对偶图上的最短路问题平面图欧拉公式：\(V-E+F-C=1\)，点数-边数+面

本题转化为梯形面积就已经不是很好想了（赛时切掉，开心！）进阶为静态区间查询。使用不删除莫队+凸包合并凸包合并就是把散块和整块的凸包合并注意这里两个凸包的横坐标值域是无交的于是可以使用二分套二分解决此问题代码咕着，感觉非常难写

有如下背包问题：\(n\)种物品，体积为\(v_i\)，价值为\(w_i\)，不限量，要求选\(m\)件物品，且总体积为\(V\)，求总价值的最大（小）值。解决方法：不妨令\(v_i\)升序，首先先选\(m\)个\(1\)号物品，计算体积\(V_0=m\timesv_1\)，然后每选一件物品，就替换掉一件\(1\)号物品。转移式：\(

link前置知识：Prufer序列，二分图别的题解都是直接给答案，没有比较易懂的思路。首先，考虑Prufer序列，发现右边点删除一定会加入一个左边点，另一边类似。且生成Prufer序列的最后一定会留下左右边各一个点。所以左边点在Prufer序列中出现的次数即为\(m-1\)，右边即为\(n-1\)。

linkT1转化为\((b_i,a_i)\)与\((b_j,a_j)\)之间的斜率。发现性质（省略），只需要计算相邻两个点之间的答案即可，用set就行了。T2先找性质，发现即为\(a,b,c\)各有某一位是“独特”（即其他两个数这一位与之不一样）的。直接\(O(8^2n)\)记录各个状态，预处理转移优化一下即可。T