十一杂题选讲-VirtualJudge(vjudge.net)/mnt/e/codes/contests/20241008/sol.md目录[AGC004F]Namori[1406E]DeletingNumbers[1081G]MergesortStrikesBack[1033E]HiddenBipartiteGraph[1254E]SendTreetoCharlie[1012E]Cyclesort[1284F]NewYearandSocialN

P2476[SCOI2008]着色方案很好的绿dp，场上卡我2h，场上只考虑了二进制状压，然后组合数填数，最后发现没法去除重复情况。说一下简单的正解，这题组合数也是能搞的，只是需要多开一维记录当前存在多少相邻的同色位置。考虑到\(c_i\leq5\)，我们记录每种颜色个数的个数，然后按照个数记忆

树的直径模板题。定义树的任意两点之间的最长简单路径。求法dfs做法从任意一个节点dfs到和其距离最远的节点，可以证明其为树的直径的一端。然后再以直径的一端dfs走到和其距离最远的节点即可得出答案。若要记录直径路径的话只需在第二次dfs上记录每个节点的前驱即可

新高一矩阵选讲「陶治霖」https://www.becoder.com.cn/contest/5348「CF1970E3」Trails(Hard)考虑DP。定义\(f_{i,j}\)表示，第\(i\)天走到\(j\)的方案数。有转移：\[f_{i,j}=\sum_{k=1}^mf_{i-1,k}\times(s_jl_k+s_kl_j+s_js_k)\]https://www.luogu.com.cn/article/i

如果您是搜索引擎搜进来的。很抱歉，没有您需要搜索的题目的题解。典题\(n\)个物品的背包，重量在\(1\sim4\)之间，价值在\(1\sim10^9\)之间。\(n\leq10^5\)。Minkowski和会遇到不连续的问题。不妨按照\(i\bmod12\)划分dp数组，每个剩余系都是凸的。枚举拿了\(

今天写的很乱。[HEOI2013]SAO容斥。因为我们已经知道父亲\(<\)儿子时的情况（\(n!/\prod_isiz_i\)，也适用于森林），那么儿子\(<\)父亲的情况就容斥掉，无限制的就当作那条边不存在。树上背包，记录当前节点为根的连通块大小和容斥系数的积。*[ECFinal23A]DFSOrder4转写为：统计多

[AGC018F]TwoTrees[AGC018F]TwoTrees-洛谷|计算机科学教育新生态(luogu.com.cn)先判一下奇偶性。考虑做一个很强的钦定，奇数都填\(\pm1\)，偶数都填\(0\)。对于同一棵树的一棵子树，考虑对子树内两个奇数点做匹配，要求匹配上的点一个\(+1\)一个\(-1\)，这样就能在子树的根

[COCI2015-2016#5]OOP（Trie）P6727[COCI2015-2016#5]OOP-洛谷|计算机科学教育新生态(luogu.com.cn)正反串分别建Trie，可以搞出两个dfn区间，加之长度限制，三维数点。有\(O(n\logn)\)做法。将字典串\(S[1..m]\)，对所有\(1\leqi\leqm\)，将\(S[i+1,m]\)的hash值插入

[AGC059C]GuessingPermutationforasLongasPossible（2-sat）这个东西十分智障，只需要对于所有\(a,b,c\)，如果询问顺序是\((a,b),(b,c),(a,c)\)，那么不能\(a<b<c\)或\(a>b>c\)。其它的情况（一条链）你一看发现肯定需要出现上述情况，那么这就是充要条件。你一看你直接对所

DP选讲P5074EattheTrees最简单的插头DP，轮廓线和插头可以很轻松存储状态和转移。P4719【模板】"动态DP"&动态树分治P5024[NOIP2018提高组]保卫王国动态DP一般就是简单的DP带单点修改，而且给你放到树上，这样你就不得不写树剖，写树剖就需要维护重链，我们就要写出也就是

\(TXX\)讲课。\(2024\7\23.\)\(T1.\)首先你可以考虑用\(dp.\)先记棋子脚下的位置为\(v\)，动态规划方程：\(f_i=\max\{\dfrac{1}{2}(f_{i-1}+f_{i+1}),v_i\}\)利用这个方程，我们可以把他用\((i,f_i)\)的画在平面上。然后观察这个平面，发现\(i\)位置上面的答案也就是凸

树状数组维护区间哈希值重点,区间长度=\(lowbit(x)\)#include<bits/stdc++.h>usingnamespacestd;usingint128=__int128;usingLL=longlong;constintN=1e6+6;LLc[4][N],sum,bpow[N],b=100591,mod=1e18+31,u;intn,q,op,l,r,x;char

https://files.cnblogs.com/files/blogs/697234/slide.zip?t=1720184804&download=true110.【PR5】双向奔赴111.AT_agc043_dMergeTriplets112.【JOIOpen2020】黑白点113.apio2022游戏114.UOJ749【UNR#6】稳健型选手115.P5327[ZJOI2019]语言116.UOJ814鸽子收费站

前情提要：题解尽可能的写详细了，但是有些证明写着太费时间就没写了喵本来\(pyb\)想让我弄一个数据结构专题，结果发现我前阵子做的那些列表里的题，每一个的提交记录里都有\(jsy\)，很多题里有\(xcy\)。。。实在整不出什么花活了，太菜了没做啥大家都没做过的题qwq，完全的水题选讲关注Luo

Vizing定理定义考虑如下的问题：对一个无向图的边进行着色，要求相邻的边染不同种颜色。问需要的最少的颜色数是多少。解决上述问题需要借助Vizing定理（又称维金定理）。在开始之前，我们先进行一些符号的规定。\(\Delta(G)\)：无向图\(G=(V,E)\)的最大度数，即\(\Delta(G)=\max_

CF1666KKingdomPartition我们首先钦定\(A\)点选了A，\(B\)点选了B，其它点选了C，这样会有一个代价。然后我们尝试将每个C点改成A或者改成B。我们将其看成一个物品，其代价为其所有向外的连边之和。而同时，对于每条边，如果其两端是不同的颜色，其会使代价减少\(2l\)。我们将

240503好题选讲：概率和期望期望的计算公式：\[E(X)=\sum_ii\timesP(x=i)\]期望的线性性：\[E(X+Y)=E(X)+E(Y),E(kX)=kE(x)\]A百事世界杯之旅B收集邮票一句话题意：\(n\)种邮票，每次等概率选取一张，第\(i\)张的价格是\(i\),问：标准版：集齐\(n\)种邮票所需要购买的期望

CliqueConnectAT_abc352_e朴素的想法是按题意暴力建边跑最小生成树，发现一个联通块内的很多边是冗余的，可以相邻两点建边跑最小生成树即可。//author:yhy#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;usingPii=pair<LL,LL>;constLLkMaxN

MUHandCubeWallsCF471D由于序列同时加\(x\)，该序列的差分数组不变，所以求出\(a,b\)的差分数组跑kmp或哈希。书柜题目描述：有\(A,B\)两种书排成的序列，序列长度为\(n\)，两种书高度分别为\(h_A,h_B\)，\(q\)次询问每次给定一段区间，你需要移除一些书使得剩下的书严格递增

NOI2024数据结构选讲「广铁一中张冀飞」（20240427）多校NOI2024国赛模拟赛8（20240429）多校NOI2024国赛模拟赛9（20240430）NOI2024简单杂题选讲「金华一中毛艺婷」（20240501）多校NOI2024国赛模拟赛10（20240503）NOI2024网络流问题及其简单应用「重庆八中谢自均」（20240506）剩余7题。最小割

染色给定一棵\(n\)个节点的无根树，共有\(m\)个操作，操作分为两种：将节点\(a\)到节点\(b\)的路径上的所有点（包括\(a\)和\(b\)）都染成颜色\(c\)。询问节点\(a\)到节点\(b\)的路径上的颜色段数量。颜色段的定义是极长的连续相同颜色被认为是一段。例如112221由

CF1329DDreamoonLikesStrings将原序列中\(s_i=s_{i+1}\)的位置拿出来，记这些位置的集合为\(S\)。考虑我们选择\(S\)相邻两个数，并且删除中间这一段会产生什么影响。如果两边的数不同，那么这两个位置都会在\(S\)中消失，否则，会在\(S\)中新加入一个为这个数的位置。我们总

不等式选讲一、均值不等式1.1定义这是我们一般说的均值不等式：对非负实数\(a,b\)，有\[a+b\geqslant2\sqrt{ab}\]等号成立当且仅当\(a=b\)。事实上，这个不等式来自于\[(x-y)^2\geqslant0\]即\[x^2+y^2\geqslant2xy\]再令\[x^2=a\\[10pt]y^2=b\\[10pt]\]其中\(a,b

杂题选记写一点比较神奇的杂题。觉得出的都很有心意啊。抽屉原理抽屉原理通常不会在程序中出现，但是这是一个评价复杂度，人肉计算阈值的有时不错的方法。如果你要学习一些十分厉害的抽屉原理，可以翻高中奥林匹克小丛书·组合数学的第二章，上面写着一些比较复杂的抽屉。\(Rams

凸性CF1428ECarrotsforRabbits给\(n\)个胡萝卜,再\(n-k\)次选出一个胡萝卜切一刀成俩,最小化最后所有胡萝卜平方和.CF1661FTeleporters给定数轴上\(n\)个点和\(m\),要再建立若干点,使得存在一条路径\(a_1\ldotsa_n\)的\(\sum{(a_i-a_{i-1})}^2\lem\)