首页 > 其他分享 >CF1045J Moonwalk challenge

CF1045J Moonwalk challenge

时间:2023-11-06 19:46:24浏览次数:39  
标签:log challenge Moonwalk len 哈希 mathcal CF1045J 重链 复杂度

这题怎么才 \(\color{red}*2600\) 啊,我觉得有 $\color{maroon} *3000+ $,太菜了 /ll。

明天期中考试了,来一个官方题解做法涨涨 rp,复杂度稍劣还要离线,被爆了 /ll。题解区大佬说哈希狗都不写。

洛谷 CF

  • 给出一棵 \(n\) 个点的树,边上有字母。\(q\) 次询问,每次给出一条路径 \(u\rightsquigarrow v\) 和一个字符串 \(s_i\),询问 \(s_i\) 在 \(u\rightsquigarrow v\) 的路径边上字母顺次拼接构成的字符串中出现了几次。

  • \(n,q\le 10^5\),记 \(S=\max\limits_{i=1}^q|s_i|\),\(\color{red}\boldsymbol{S\le 100}\)。

看到这题,我的第一反应是 CF1608G Alphabetic Tree,两题难度虽然差的有点多,做法的相似之处也不是很大,但是都是十分恐怖的重工业题。

进入正题,我们发现询问串的长度很小,考虑分别处理每一种长度的询问,记当前正在处理的长度为 \(len\)。

先对树进行重链剖分、边转点,则路径由 \(\mathcal{O}(\log n)\) 条重链组成。对于每一个询问,可以将字符串的出现位置分为完全在重链内以及跨越重链两类。

  • 对于完全在重链内的位置:

先处理出每条重链自上而下以及自下而上前缀哈希值,这样就可以求出重链内任意一条子路径、任意一种方向的哈希值。

求出每个点向上走 \(len\) 条边,向上、向下的哈希值 \(vu_i,vd_i\),并将它们离散化。对于每一种离散化值维护一个 std::vector 按顺序从小到大存放哈希值离散化后为该值的点的 \(dfn\)。

则跳链的时候,设当前的链底的点为 \(x\),则问题可以变成:

查询在区间 \([dfn_{top_x}+len-1,dfn_x]\) 内,有多少点的权值为给定的值。

类似 P5838 一样,在 std::vector 上二分得到左右端点求区间长度即可。

若当前重链在 \(u\rightsquigarrow \text{LCA}\) 的链上,则查询向上的哈希值,否则查询向下的哈希值。

  • 对于跨越重链的位置:

在处理“完全在重链内的位置”时,用 std::vector 存下每一条重链的顶部、\(dfn\) 区间和方向。

枚举起始的重链,则出现位置一定是起始重链长度为 \(len\) 的后缀(若不足则全部选,下同),以及该重链结尾位置再往后走 \(len\) 条边构成的字符串中(不然出现的起始位置要么没有跨越重链,要么不在起始重链内)。

暴力找出这条路径并记录其构成的字符串,进行哈希 / KMP 与询问串进行匹配。注意要保证跨越重链及起始位置在起始重链内。

做法大概就这样,好像也不是 too hard。接下来算复杂度。

  • 输入以及重链剖分的预处理部分时间复杂度为 \(\mathcal{O}(n+qS)\)。

  • 对于枚举 \(len\),预处理每个点向上 / 向下的哈希值并离散化的部分,一个点计算一次时间复杂度为 \(\mathcal{O}(\log n)\),要排序的元素一共有 \(\mathcal{O}(nS+q)\) 个,总时间复杂度是 \(\mathcal{O}((nS+q)\log (n+q))\)。

  • 对于一个询问,处理“完全在重链内”的位置的时间复杂度为 \(\mathcal{O}(\log^2 n)\);处理“跨越重链的位置”时,枚举重链的时间复杂度为 \(\mathcal{O}(\log n)\),找出路径以及字符串匹配的时间复杂度为 \(\mathcal{O}(S)\)。所以一次询问的时间复杂度为 \(\mathcal{O}(\log n(\log n+S))\),总时间复杂度是 \(\mathcal{O}(q\log n(\log n +S))\)。

  • 综上,该算法的时间复杂度为 \(\mathcal{O}((nS+q)\log (n+q)+q\log n(\log n+S))\)。配合 \(6\text{ s}\)

  • 空间复杂度显然为 \(\mathcal{O}(n+qS)\)。

至此这题基本上解决了。完结撒花!

提交记录(含 \(\boldsymbol{8.9\,\text{KB}}\) 抽象代码)

标签:log,challenge,Moonwalk,len,哈希,mathcal,CF1045J,重链,复杂度
From: https://www.cnblogs.com/MnZnOIerLzy/p/17813543.html

相关文章

  • Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) B. Kuroni an
    Problem-1305B-Codeforces 啦啦啦,这题题目有点长,概括一下就是,希望将所有()匹配的括号去掉问你需要操作多少次 双指针,一个i一个j,从前往后记录匹配的括号如果发现:1.括号匹配2.i<jok,就放入ans (⊙o⊙)…,最后记得sort一遍ans,第一遍因为这个wa了一发 #include......
  • QOJ # 7514. Clique Challenge
    题面传送门为啥我会在想多项式做法啊?首先考虑稠密图怎么做,也即\(n=O(\sqrtm)\)的图。将点分为前一半后一半,然后meetinmiddle,其中一边用高维前缀和即可做到\(O(n2^{\frac{n}{2}})\)的复杂度。然后我们需要将其扩展到可能稀疏的图上。仿照三元环计数的方法,将其按照度数排......
  • A Challenge Dataset and Effective Models for Aspect-Based Sentiment Analysis
    摘要基于方面的情感分析(ABSA)由于其广泛的应用,近年来受到了越来越多的关注。在现有的ABSA数据集中,大多数句子只包含一个或多个具有相同情感极性的方面,这使得ABSA任务退化为句子级情感分析。在本文中,我们提出了一个新的大规模多方面多情感(MAMS)数据集,其中每个句子至少包含两个具有不......
  • challenge1-MFQ
    #challenge1-MFQlab4环境调度部分的challenge:多级反馈队列(MFQ)调度算法chellenge原文:向内核添加一个不那么简单的调度策略,例如一个固定优先级的调度器,使每个环境都有一个优先级,确保优先选择优先级高的环境,而不是优先级低的环境。如果你喜欢冒险,可以尝试实现unix风格的可调......
  • xsschallenge通关(11-15)
    level11老规矩,先查看源码,做代码审计:<?phpini_set("display_errors",0);$str=$_GET["keyword"];$str00=$_GET["t_sort"];$str11=$_SERVER['HTTP_REFERER'];$str22=str_replace(">","",$str11);$str33=st......
  • xsschallenge通关(1-10)
    level1这一关很简单,标准的xss注入,打开hackbar,输入<script>alert(/xss/)</script>点击EXECUTE,通关!level2这一关有一个搜索框,输入<script>alert(/xss/)</script>发现直接将这段JS代码当做HTML实体,即普通字符查看源代码,发现有htmlspecialchars()函数,会转换双引号、单引号和尖角号成H......
  • Enhancing Vehicle Connectivity: Overcoming Challenges of 4G/LTE Connectivity in
    EnhancingVehicleConnectivity:OvercomingChallengesof4G/LTEConnectivityinDenseUrbanAreasInthemodernera,vehicularconnectivityhasbecomeanindispensableaspectofourlives.Fromnavigationtoinfotainmentandremotediagnostics,vehiclesre......
  • 2023 LS-PC Programming Challenge TFT
    2023LS-PCProgrammingChallengeTFT2344ASCIIArea-PCOIOnlineJudge(pcoij8.ddns.net)题目大意求一个封闭区域的面积做法我们考虑一行一行看,第一次遇到斜线时标记一下,接下来每一个点都加入答案,等到下一次遇到斜线时为止,再额外加上一代码#include<bits/stdc++.h>u......
  • P1219 八皇后 Checker Challenge(深度搜索dfs经典问题+回溯)
    题目连接:P1219[USACO1.5]八皇后CheckerChallenge-洛谷|计算机科学教育新生态(luogu.com.cn) 典型的深度优先搜索的问题----》先付代码再来跟新java组代码packagePTACZW;importjava.util.Scanner;importjava.io.*;importjava.util.Set;importjava.util.Has......
  • [Typescript Challenge] 148 Medium - CartesianProduct
    Given2sets(unions),returnitsCartesianproductinasetoftuples,e.g.CartesianProduct<1|2,'a'|'b'>//[1,'a']|[2,'a']|[1,'b']|[2,'b'] Solution:/*____________......