题目大意有\(3\)个门，有两个门后面会有一个钥匙，你现在手中有一把钥匙，问你能不能打开所有的门。题目分析我们可以一步一步推导，既然给了我们一把钥匙编号为\(x\)，也就是可以打开编号为\(x\)的门，我们用\(a_x\)表示这扇门后面钥匙的编号，将可以打开的门标记起来，然后产生分类讨论：如果是\(a_x\)等于\(0\)的话，就没有钥匙，不用标记，直接输出NO。如果\(a_x\)不等于\(0\)的话，就说明可以打开下一个门，用\(f\)数组标记，然后可以继续讨论，不过讨论时变成了判断\(a_{a_x}\)，以此类推。但是到达最后一次的时候，不管\(a_{a_{a_x}}\)是否等于\(0\)
注意到\(\sum\limits_{i=2}^N|x_{p_i}-x_{p_{i-1}}|+|y_{p_i}-y_{p_{i-1}}|\)。本质上是两个点之间的曼哈顿距离。而曼哈顿最小距离生成树要\(O(n^2\logn)\)，显然过不了。注意到我们写过一个叫莫队的东西。而莫队的复杂度为\(O(n\sqrtn)\)，也就是我们要求的东西。加一点小优化，奇偶排序。就可以过了。怎么证明？可以看一看这一篇博客精简来说就是控制了左右指针跨越块的数量。#includeusingnamespacestd;constintmaxn=1000001;structquery{intl,r,id;}q[maxn]
注意到\(\sum\limits_{i=2}^N|x_{p_i}-x_{p_{i-1}}|+|y_{p_i}-y_{p_{i-1}}|\)。本质上是两个点之间的曼哈顿距离。而曼哈顿最小距离生成树要\(O(n^2\logn)\)，显然过不了。注意到我们写过一个叫莫队的东西。而莫队的复杂度为\(O(n\sqrtn)\)，也就是我们要求的东西。加一点小优化，奇偶排序。就可以过了。怎么证明？可以看一看这一篇博客精简来说就是控制了左右指针跨越块的数量。#includeusingnamespacestd;constintmaxn=1000001;structquery{intl,r,id;}q[maxn]
\(0.\)前言有一天\(Au\)爷讲期望都见到了此题，通过写题解来加深理解。\(1.\)题意将初始为空的序列的末尾给定概率添加\(a\)或\(b\)，当至少有\(k\)对\(ab\)时停止（注意是“对”，中间可以间隔字符），求\(ab\)期望对数。\(2.\)思路通过查看标签通过阅读题面我们容易发现本题是一道期望DP，但是本题的状态并不很容易想到，设\(f[i][j]\)表示前缀中有\(i\)个\(a\)，\(j\)个\(ab\)停止后的期望个数，这样发现转移就容易了很多，不会被\(a\)和\(b\)纠缠不清，设\(A=pa/(pa+pb)\)，\(B=pb/(pa+pb)\)，则有：\[f
\(0.\)前言有一天\(Au\)爷讲期望都见到了此题，通过写题解来加深理解。\(1.\)题意将初始为空的序列的末尾给定概率添加\(a\)或\(b\)，当至少有\(k\)对\(ab\)时停止（注意是“对”，中间可以间隔字符），求\(ab\)期望对数。\(2.\)思路通过查看标签通过阅读题面我们容易发现本题是一道期望DP，但是本题的状态并不很容易想到，设\(f[i][j]\)表示前缀中有\(i\)个\(a\)，\(j\)个\(ab\)停止后的期望个数，这样发现转移就容易了很多，不会被\(a\)和\(b\)纠缠不清，设\(A=pa/(pa+pb)\)，\(B=pb/(pa+pb)\)，则有：\[f
D.SameCountOne(PolynomialRound2022(Div.1+Div.2,Rated,Prizes!))题意给定\(n\)个长度为\(m\)的01序列，每次操作可以选择两个序列a1,a2，并选择一个\(pos\),std::swap(a1[pos],a2[pos]),求是每个序列中的\(1\)的个数都相等所需的最小操作数。思路可以发现(\(1\)的总数)\(\bmod\n\neq0\)时，是无解的。令\(avg=\)(\(1\)的总数)\(/n\),我们可以把这\(n\)个序列分为两类，严格小于\(avg\)的和严格大于\(avg\)的，其他的序列可以丢掉。严格大于\(av
D.SameCountOne(PolynomialRound2022(Div.1+Div.2,Rated,Prizes!))题意给定\(n\)个长度为\(m\)的01序列，每次操作可以选择两个序列a1,a2，并选择一个\(pos\),std::swap(a1[pos],a2[pos]),求是每个序列中的\(1\)的个数都相等所需的最小操作数。思路可以发现(\(1\)的总数)\(\bmod\n\neq0\)时，是无解的。令\(avg=\)(\(1\)的总数)\(/n\),我们可以把这\(n\)个序列分为两类，严格小于\(avg\)的和严格大于\(avg\)的，其他的序列可以丢掉。严格大于\(av
H.HotBlackHotWhite(COMPFEST14-PreliminaryOnlineMirror(Unrated,ICPCRules,TeamsPreferred))题意有\(n\)个石头，每个石头有一个值\(a_i\)，现在需要给这\(n\)个石头染色，要求\(\frac{n}{2}\)为白色，\(\frac{n}{2}\)为黑色(\(n\)为偶数)，并且任何两个颜色不相同的石头\(i\)，\(j\)满足：\[concat(a_i,a_j)\timesconcat(a_j,a_i)+a_i\timesa_j\not\equivZ\bmod3\]求\(Z\)与染色方法。\(conca
H.HotBlackHotWhite(COMPFEST14-PreliminaryOnlineMirror(Unrated,ICPCRules,TeamsPreferred))题意有\(n\)个石头，每个石头有一个值\(a_i\)，现在需要给这\(n\)个石头染色，要求\(\frac{n}{2}\)为白色，\(\frac{n}{2}\)为黑色(\(n\)为偶数)，并且任何两个颜色不相同的石头\(i\)，\(j\)满足：\[concat(a_i,a_j)\timesconcat(a_j,a_i)+a_i\timesa_j\not\equivZ\bmod3\]求\(Z\)与染色方法。\(conca
CF链接：LeastPrefixSumLuogu链接：Least PrefixSum${\scr\color{CornflowerBlue}{\text{Solution}}}$先来解释一下题意：给定一个数组，问最少把多少个数变成相反数，使得$\forall\cal{i}$,$\sum_{k=1}^ia_k$$\le$ $ \sum_{k=1}^ma_k$发现对于所有数据点，$\cal{n}\le2\times10^5$，说明需要$Ο(\cal{n\logn})$或者$O(\cal{n})$的算法。分析一下题目，发现要分成$\cal{i}>\cal{m}$与$\cal{i}当$\cal{i}$
