什么是DFS序？ dfs序是指：每个节点在dfs深度优先遍历中的进出栈的时间序列。 比如有一颗普通树，它长这样： 进出栈我们用一个in[i]和out[i]数组来记录，用全局变量dfn从0开始每次进栈就++，出栈就记录下来退出时候的时间，这里在Tarjan算法中也经常有，叫时间戳。 那么上图的进出栈顺序是： 序列中第一次出现的当然就是进栈时候，第二次就是出栈的时候。出栈有两种写法，有的时候写1out[i]=++dfn，也可以写out[i]=dfn，影响不大，如果不写++的话判断的时候就会有<=这样的，因为时间戳…
题意 题目链接：Problem - 1372C - Codeforces 输入 t 表示 t 组数据，每组数据输入一个正整数 $n(1\leq n\leq 2e5)$ 和一个长为 n 的 1~n 的排列 a。 每次操作，你可以选择 a 的一个子数组，将其错排（错排前后，子数组同一位置上的元素不能相同）。 输出将 a 变为升序，至少需要几次操作。 例如如果一个连续序列是2 3 4，如果想要变成4 3 2，因为3的位置没有变，所以3 4 2和4 2 3都是可以的。 思路 大胆猜测！最多只需要两次即可，那么什么时候零次什…
题意 题目链接：Problem - D - Codeforces 输入正整数 $n(2\leq n\leq 2e9)$, $k(1\leq k\leq2e5)$ 和 $s(1\leq s\leq 1e18)$。 在数轴上有 1,2,3,...,n 共 n 个整点（位置），你一开始在 1 上。 每一步你可以移动到任意位置上（但不能原地不动），移动的距离就是两个位置的距离。 问能不能恰好走 k 步，使得移动的距离之和恰好为 s？ 若不能，输出 "NO"；否则输出 "YES" 和 k 个数，表示每一步移动之后的位置。 思…
比赛链接：Dashboard - Codeforces Round #805 (Div. 3) - Codeforces 这波偷偷拿小小号，估计能上400+分吧，没有做出G题...太菜了，我估摸着这回G题得有2000分？ 周中没有几场，这场搞到唯一一天假可累死我了！下午还有robocom... 这场前几题简直是STL专场.. 这场重点在EFG题。 A. Round Down the Price（模拟） 直接按照题意最高位-1即可，也可以用字符串。我这里是写一个函数找有多少位，比如有3位就减去100. 参考代码： i…
在“帮助”里面相应位置输入下段即可 Mifeng User Single User License EA7E-1184812 C0DAA9CD 6BE825B5 FF935692 1750523A EDF59D3F A3BD6C96 F8D33866 3F1CCCEA 1C25BE4D 25B1C4CC 5110C20E 5246CC42 D232C83B C99CCC42 0E32890C B6CBF018 B1D4C178 2F9DDB16 ABAA74E5 95304BEF 9D0CCFA9 8AF8F8E2…
题目 题目来源于北华大学计算机程序设计算法提高训练营个人赛的J题，邀请码:bhu2022。 给出一个$n(1\leq n\leq 10^6)$点$m$边的无向图每条边长为$1$，每个点拥有一个$0/1$的点权，0表示雌性，1表示雄性。一共有$q$次询问，每次询问x，回答距离点x最近的异性的最短距离是。 思路 考虑到数据范围比较大，肯定不能用暴力，所以需要用两遍bfs，一次从所有的0出发，去更新每个1点到0的最短距离；一次从所有的1出发，去更新每个0点到1的最短距离。 令f[i][0/1]，其中f[i][0]表示点i…
比赛链接：牛客小白月赛53 好久没有打小白月赛了，这回算半个四题首吧，E题怎么也写不出，代码又臭又长，结果是一个地方忽略掉了，第二天把F补了。经过上一次牛客练习赛，这回还是没有能升到1500...下次再来。 A.Raining（水题） B.Kissing 打表发现其实就是$1+3+...+2n-1$，根据等差数列公式$\frac{(1+2n-1)\times n}{2}=n^2$，注意取模 C.Missing 这里wa了一发，一味的求快导致没看清题目，如果一个匹配的也没有就全部按字典序输出即可 前三题都太简单了不详…
题意 给你一个字符串$s$，有$q$次询问，每次询问格式有两种： 1) 1 pos c：将字符串中位置为pos的字符改为c 2） 2 x y：询问区间$[x,y]$中有多少个不一样的字符 数据范围： $|s|\leq 10^5,q\leq 10^5$ 思路 我是先会做了另外一道线段树的题（线段树-单点修改+区间求最大连续子段和 - CarryNotKarry）才会秒这个题的。 这个题很明显是单点修改，然后区间查询，这里设置一个结构体，有普通的存当前结点的l,r以及如果是叶子节点的字符ch，也存上一个num[26]数…
