Misaka16172's Blog

前言 赛时四发罚时直接葬送 perf，写完还以为是个脑子题，过的人肯定不多。 累了，能不能数据加到 n≤107n\leq 10^7n≤107 把写 nlog⁡kn\log knlogk 的都叉掉（虽然我当时降智地使用了《倍增》来求树上 kkk 级祖先）。 思路 把每个 iii 向 xix_ixi​ 连边，形成一张 nnn 个点 nnn 条边的有向图。 由于每个点出度均为 111，这张图实际上是内向基环树森林。 观察到进行 kkk 次操作对 aia_iai​ 的影响实际上就是以 iii 为起点在图上走 kkk 次。 那么可以分类讨论两种情况：kkk 次操作后，第 iii 个点在环上 / 不在环上。 首先拓扑排序一遍找出所有在环上的点，dfs 出每个环的大小并对每个环上的节点从 000 开始进行标号。设某个环的大小为 sss，手玩发现如果已经走到了该环上的第 iii 个节点，还需要走 xxx 步，则最后一定落在环上的第 (i+x)mod  s(i+x)\mod s(i+x)mods 个节点。于是直接从环上的每个节点出发再 dfs 一遍，预处理出每个不在环上的节点将会到达的环上节点与需要走 ...

思路 不太一样的做法。 直接爆搜每条边的颜色复杂度是 2n2^n2n，我们可以尝试折半搜索然后合并答案。 具体地，把 n−1n-1n−1 条边分成两半，分别搜索每条边染黑还是白，搜索结果是一个二进制数，第 iii 位是否为 111 代表是否满足第 iii 个条件的限制。O(1)\mathcal{O}(1)O(1) 检查是否满足条件可以先预处理每个条件所包含的边集 EiE_iEi​，然后再把搜索出来的边集 SSS 与 EiE_iEi​ 做按位与即可，这部分预处理时间复杂度为 O(nm)\mathcal{O(nm)}O(nm)，搜索时间复杂度为 O(2n2m)\mathcal{O}(2^{\frac{n}{2}}m)O(22n​m)。 搜索完之后我们得到了两个二进制数组成的集合，分别代表前 n−12\frac{n-1}{2}2n−1​ 条边染色后满足条件的情况和后 n−12\frac{n-1}{2}2n−1​ 条边的情况。可以考虑对于第一个集合里的每个元素分别计算可以和多少个第二个集合里的元素配对。两个状态 a,ba,ba,b 可以配对当且仅当 aor⁡b=2m−1a\operatorn ...

前言 ABC 出题人喜欢出板子是吧，像这种出题人就应该好好用乱搞拷打一下。 拜谢 @RailgunZzzz 以及其他 HL 群群友在卡常和卡哈希时给予的若干帮助。 思路 先处理出整串哈希，然后我们考虑根号分治。 设根号分治的阈值为 TTT，则有两种算法可以用来回答询问： 对长度 >T>T>T 的串暴力。求出被询问的串的哈希，从左到右枚举被匹配的子串的右端点，把两个哈希 O(1)\mathcal{O}(1)O(1) 进行比较，单次询问复杂度 O(n)\mathcal{O}(n)O(n)。设 sum=∑∣t∣sum=\sum |t|sum=∑∣t∣（ttt 为被询问的串），长度 >T>T>T 的串最多被询问 O(sumT)\mathcal{O}(\frac{sum}{T})O(Tsum​) 次，所以这部分时间复杂度为 O(nsumT)\mathcal{O}(n\frac{sum}{T})O(nTsum​)。 对长度 ≤T\leq T≤T 的串预处理。预处理原串所有长度 ≤T\leq T≤T 的子串的哈希值，扔到 TTT 个 vector 里进行排序， ...

前言 感觉这个题跟 P7114 [NOIP2020] 字符串匹配 莫名有点联系啊，我如果没写过那题是肯定不会做这个题的。 思路 一开始先特判掉全 a 串，显然此时答案为长度 −1-1−1，以下讨论全部默认给定的串不是全 a 串。 性质 1：一个全 a 串一定不能成为答案，证明显然。 性质 2：一个合法的答案串一定是原串的一段前缀删去前缀的若干个 a。 证明：设原串 sss 中第一个非 a 的位置为 ppp，一个不满足该性质的 sss 的子串 t=slsl+1⋯srt=s_ls_{l+1}\cdots s_rt=sl​sl+1​⋯sr​（不妨设 lll 为 ttt 第一次出现的左端点），则条件等价于 p<lp<lp<l。如果 [1,l)[1,l)[1,l) 能被合法划分，由于 sp≠s_p≠sp​​= a，这段字符串中必然有一段 [l′,r′]=t (1≤l′≤p≤r′<l)[l',r']=t\ (1\leq l'\leq p\leq r'<l)[l′,r′]=t (1≤l′≤p≤r′<l)，否则第 ppp ...

题单 ABC305F 直接 dfs + 回溯一定不会让一个点被遍历超过 222 次，于是直接 dfs 就做完了。 CF1658C 首先转化题意， cic_ici​ 相当于把第 n−i+1n-i+1n−i+1 个元素右边的所有元素全扔到最前面所形成的排列的价值，此时排列开头的元素为 pn−i+2p_{n-i+2}pn−i+2​（c1c_1c1​ 例外，它是原排列）。于是发现当且仅当排列以 nnn 开头的时候才有 c=1c=1c=1，这题就已经做完一半了。 然后考虑以 pn,p1,p2,⋯ ,pn−1p_n,p_1,p_2,\cdots,p_{n-1}pn​,p1​,p2​,⋯,pn−1​ 这个排列为基础，一个一个把最右边的元素扔回第一个，发现这个过程中价值要么减少要么至多增加 111。于是这题就做完了。 如何证明价值无论减少多少都能构造出一个排列？发现当前排列里元素到底是多少并不重要，只需要在乎相对大小即可，故你往前扔的时候想吞掉前面几个元素都可以。 CF1905C 这个题比较考验注意力和手玩能力，你需要注意到我们实际上一直只是在对字符串字典序最大的一个子序列进行右移，然后你找出这个子 ...

前言 这个题真的是太困难了。 思路 考虑从每个人向他想坐的地方建图。 发现 ≤n\leq n≤n 的点出度均为 111，>n>n>n 的点出度为 000，如果联通块里全是 ≤n\leq n≤n 的点那里面就有 nnn 条边，否则就有 n−1n-1n−1 条边（因为构成一个联通块至少需要 n−1n-1n−1 条边），所以这一定是一个内向基环树 + 内向树森林。 然后我们考虑怎么选座位。分类讨论，对于树的情况答案为树上到根节点的最长链长度再 -1（根节点 ≥n\geq n≥n 所以根节点可以随便让人坐），而基环树的情况只能选环上的所有节点，不然就有人没地方坐。 实现上，树的情况可以对于每个 ≥n\geq n≥n 的点 dfs；基环树的情况直接拓扑排序，没有出队过的点一定在环上，求出一共有几个点没有入队即可。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344constexpr int N = 2e5+5;vector<int> tr[N];set ...

前言 怎么题解区全是假做法，这里提供一个和标解思路略微不同的方法。 思路 对于每个 xix_ixi​，设 xi=⌈kα⌉−1x_i=\lceil k\alpha\rceil-1xi​=⌈kα⌉−1，解不等式可得 xi<kα≤xi+1x_i<k\alpha \leq x_i+1xi​<kα≤xi​+1，考虑枚举 kkk 把不等式解集转化成一堆区间（即 [xik+eps,xi+1k][\frac{x_i}{k}+eps,\frac{x_i+1}{k}][kxi​​+eps,kxi​+1​]），同时注意到答案保底为 111，于是可以忽略右端点在 111 左边的区间，这样枚举到 kkk 的上界就不会超过 xix_ixi​。 于是问题就变成了找到最大的、被每个 xix_ixi​ 形成的区间都覆盖过的数，而这个过程可以离散化后用差分解决；具体地，枚举每个 xix_ixi​，将其形成的所有区间都推平为 111，处理完之后将每个当前为 111 的下标的 sumsumsum 值都加上 111，最后 sum=nsum=nsum=n 的下标就是合法的。 容易发现答案一定是某个区间的右端点 ...

前言 第一次场切 G（虽然被 after_contest 叉了），纪念一下。 思路 贪心地，考虑最优秀的操作一定是修改中间的一个元素，把左右两边的 LIS 接在一起。 于是可以预处理每个以每个下标 iii 开头 / 结尾的最长 LIS 长度 RiR_iRi​ 和 LiL_iLi​，然后枚举右边 LIS 开头的下标 rrr，代表修改 ar−1a_{r-1}ar−1​ 的值，则答案为 max⁡r=2n+1{Rr+max⁡l=0r−2{Ll}(al+1<ar)+1}\max^{n+1}_{r=2}\{R_r+\max_{l=0}^{r-2}\{L_l\}(a_l+1<a_r)+1\}maxr=2n+1​{Rr​+maxl=0r−2​{Ll​}(al​+1<ar​)+1}。 预处理和统计答案使用离散化 + 线段树优化 dp 实现即可，时间复杂度为 O(nlog⁡n)\mathcal{O}(n\log n)O(nlogn)。 需要注意的是统计答案时，应先将 a0a_0a0​ 设为极小值，an+1a_{n+1}an+1​ 设为极大值，这样就可以分别覆盖到左边的 LIS 为空和右 ...

思路 一眼看上去像一个 dp，但怎么 dp 不太显然。 先考虑爆搜怎么打：最先爆搜获得了 000 个暗物质时的状态，枚举接下来做哪个实验，再枚举这次实验产生了多少暗物质并继续爆搜，对每个实验的结果取 min⁡\minmin（最坏情况下），再对 nnn 个实验的 min⁡\minmin 值取 max⁡\maxmax（最多能得到多少利润）。 于是我们得到了一个倒着的 dp 式子：fx=max⁡i=1n{min⁡j=x+lix+ri{fj+109×(j−x)}−cj}f_x=\max^n_{i=1}\{\min^{x+r_i}_{j=x+l_i}\{f_j+10^9\times (j-x)\}-c_j\}fx​=maxi=1n​{minj=x+li​x+ri​​{fj​+109×(j−x)}−cj​}，要枚举 x,i,jx,i,jx,i,j 三维，复杂度为 O(a2n)\mathcal{O}(a^2n)O(a2n)，最后答案为 f0f_0f0​。 考虑怎么优化掉一个 aaa，把 min⁡\minmin 里面的式子拆出来，得到 min⁡{fj+109×j}−109×x−cj\min\{f_j ...

前言 这远古题怎么还能交题解。 思路 考虑使用数据结构直接模拟题目操作，这里直接使用线段树。 线段树的下标代表内存空间，每个节点里存两个 int 和一个 pair，两个 int 分别代表当前节点里有几个下标已经有数了，另一个只在叶子节点有用，代表当前节点存储的数是多少；pair 第一维代表访问次数，第二维代表插入时间。同时开一个 map，记录某个数在内存里的下标。 模拟过程如下： 若当前数在 map 里有值，则将线段树上其对应下标处加 111，同时答案加 111，否则继续下一步； 使用线段树上二分找出一个还没有被占用的下标，若能找到这样的下标，则将其修改为当前值，同时更新 map 里的下标，否则继续下一步； 若当前所有下标都被占用，则在线段树上查询访问次数最少、插入时间最早的下标，将该位置之前对应的值在 map 里的下标置为 000，并在线段树上修改为当前值。 细节详见代码。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515 ...