- 2024.7.5杂题选讲
前情提要：题解尽可能的写详细了，但是有些证明写着太费时间就没写了喵本来\(pyb\)想让我弄一个数据结构专题，结果发现我前阵子做的那些列表里的题，每一个的提交记录里都有\(jsy\)，很多题里有\(xcy\)。。。实在整不出什么花活了，太菜了没做啥大家都没做过的题qwq，完全的水题选讲关注Luo......
- 杂题选讲 #1：二分图边着色
Vizing定理定义考虑如下的问题：对一个无向图的边进行着色，要求相邻的边染不同种颜色。问需要的最少的颜色数是多少。解决上述问题需要借助Vizing定理（又称维金定理）。在开始之前，我们先进行一些符号的规定。\(\Delta(G)\)：无向图\(G=(V,E)\)的最大度数，即\(\Delta(G)=\max_......
- 杂题选讲 cy
CF1666KKingdomPartition我们首先钦定\(A\)点选了A，\(B\)点选了B，其它点选了C，这样会有一个代价。然后我们尝试将每个C点改成A或者改成B。我们将其看成一个物品，其代价为其所有向外的连边之和。而同时，对于每条边，如果其两端是不同的颜色，其会使代价减少\(2l\)。我们将......
- 240503好题选讲：概率和期望
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\)种邮票所需要购买的期望......
- 杂题选讲II
CliqueConnectAT_abc352_e朴素的想法是按题意暴力建边跑最小生成树，发现一个联通块内的很多边是冗余的，可以相邻两点建边跑最小生成树即可。//author:yhy#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;usingPii=pair<LL,LL>;constLLkMaxN......
- 杂题选讲I
MUHandCubeWallsCF471D由于序列同时加\(x\)，该序列的差分数组不变，所以求出\(a,b\)的差分数组跑kmp或哈希。书柜题目描述：有\(A,B\)两种书排成的序列，序列长度为\(n\)，两种书高度分别为\(h_A,h_B\)，\(q\)次询问每次给定一段区间，你需要移除一些书使得剩下的书严格递增......
- 重链剖分题目选讲
染色给定一棵\(n\)个节点的无根树，共有\(m\)个操作，操作分为两种：将节点\(a\)到节点\(b\)的路径上的所有点（包括\(a\)和\(b\)）都染成颜色\(c\)。询问节点\(a\)到节点\(b\)的路径上的颜色段数量。颜色段的定义是极长的连续相同颜色被认为是一段。例如112221由......
- 构造题选讲 by_chance
不知道会不会有方法论，先咕了。upd：有的捏，但是好像没啥用/qdARC145DNonArithmeticProgressionSet首先考虑如何构造\(n\)个数满足不存在\(2y=x+z\)。考虑一个分治：将值域均匀分成三部分，并且让所有数平分在第一部分和第三部分，直至为\(1\)就可以在值域内选一个位置扔进去。......
- ATCF 杂题选讲 LHF
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......