注意到\(\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}$
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}$
由于一次比赛被虐得太惨，，生发开始写blog的想法，于是便有了这篇随笔（找了个近期的cf比赛练练手(bushi)）第一次写blog，多多包涵。第二场cf比赛，第一场打的Div2，被虐太惨，所以第二场挑了个Div4...比赛链接：https://codeforces.com/contest/1669A.Division 翻译（参考）： t组样例，每组样例给出一个正整数，判断该整数所在的范围 题解： 签到题，分类讨论下即可B.Trip 翻译（参考）： t组样例，每组给出一个长度为n的数组，对每组样例输出一个在该数组中出现三次及三次以上的数字（可能有多个，输出任意一个就好），若不存在
