首页 > 其他分享 >暑假模拟16

暑假模拟16

时间:2024-08-11 21:38:54浏览次数:12  
标签:大样 log 16 复杂度 times 暑假 节点 模拟

暑假模拟16

\(T_A\) 九次九日九重色

最长上升子序列,预处理整除关系,树状数组维护,其中复杂度用到调和级数。

\[O(\sum_{i=1}^n \frac{n}{i} \times \log n) =O(n \times \log ^2 n) \]

\(T_B\) 天色天歌天籁音

挂分最惨的一集。

贪心的策略显然,发现这样题目就变为求区间众数,属于比较典的题。

莫队,分块都有做法,没什么好说的。

讲讲神仙挂分,场上写回滚莫队,然后狂调不止,以前回滚写得少,发现一堆问题,终于调过大样例,还有点不放心,思考要不要写对拍,但我觉得数据应该够强,况且场上没时间也懒得写了。结果挂了 \(90pts\) ,因为最后输出答案,一共 \(m\) 个询问,我输出了 \(n\) 个数?(迷惑行为)

这确实是自己的问题,毕竟人家大样例都开到极限了。对于不同的代码有不同的问题,不要认为过了一组大样例就是AC。样例不一定是水,只是没有撞到各种逆天问题。(悲)我忏悔

\(T_C\) 春色春恋春熙风

dus on tree

树上启发式合并,复杂度达到了神奇的 \(O(n\ \log n)\)

考虑一些字符重排后可以形成回文串,当且仅当出现次数为奇数的字符个数为 \(0\) 或 \(1\)

从根节点出发,求出每个节点到根的异或和,用二进制表示奇偶性,开一个大小为 \(2^{22}\) 的桶维护最大深度(一定初始化为负无穷),具体过程如下:

先处理每个轻儿子,每次处理完都要清空桶(标记为负无穷!),以免对其他节点产生影响。再跑重儿子,不清空,直接继承重儿子的数据。然后再次遍历每个轻儿子,统计答案并不断更新桶,最后把当前节点的贡献统计上就好。

复杂度 \(O(23\times n \log n)\)。所有人都需要控制一下自己的常数

标签:大样,log,16,复杂度,times,暑假,节点,模拟
From: https://www.cnblogs.com/abnormal123/p/18353947

相关文章

  • 暑假集训CSP提高模拟18
    好像还有好多没写的A.Mortis赛时思路是正解,但有一个判断想了但出锅了。。。\(n\)个数的序列\(n-1\)次肯定能换完,一次操作最多贡献2,找出贡献2的操作个数减去即可有一次操作匹配两个,两次操作匹配三个,三个操作匹配四个,三种情况,记个数都跑一遍即可点击查看代码#include<bi......
  • [赛记] 暑假集训CSP提高模拟18
    T2T4不太可做,所以没改Mortis20pts原题:Luogu[ABC302G]Sortfrom1to4赛时用$set$乱搞拿了20pts,事实证明确实是乱搞;考虑交换只有三种情况:a在b上,b在a上,需要一次;a在b上,b在c上,c在a上,需要两次;a在b上,b在c上,c在d上,d在a上,需要三次;这里的在什么什么上是指原数组......
  • 2024暑假集训测试22
    前言比赛链接。今天题好难啊,大多数人T2、T4改不动都不改了,下午miaomiao进来和我们说模拟赛改不动的题可以不改。部分分给的也很少。T1Mortis原题:[ABC302G]Sortfrom1to4。\(O(n)\)桶排序,知道每个数最后应该去哪,那么对于需要交换的只有三种情况:二者错排,交换......
  • 数据恢复软件EasyRecovery16最新破解版本下载安装图文激活教程
    EasyRecovery16作为一款专业的数据电脑恢复软件,除了有着优秀的数据恢复能力外,还有许多便捷的操作技巧。即便是对于计算机很是白目的使用者来说,OntackEasyRecovery也是值得入手的,使用者不必大费周章去备份重要的文件,整日担心文件的丢失问题或者忙碌于文件的实时备份。OntackEa......
  • 2024暑假集训测试21
    前言比赛链接。T1写得和正解差不多但少了个细节炸longlong了;T2只会\(n^3\)的本来只有\(50pts\),但考虑出题人大概率会搞一个\(n\)越大\(T\)越小,所以对于\(n\)很大的直接\(rand\)正确率还是有的,所以获得了\(80pts\);T3不会;T4没有和\(n\)取\(\min\)直接......
  • CF1654E Arithmetic Operations 题解
    CF1654E给定一个长度为\(n\)的序列\(a\)。问至少需要修改几个数才能使得\(a\)变为一个等差数列。\(n\leq10^5\),\(1\leqa_i\leq10^5\)。我们可以发现值域\(\leq10^5\)实属可疑,我们可以就这点进行分析考虑对于序列的公差\(d\),如果\(d\)太大的话经过若干......
  • 5.1模拟赛
    这次,很失败,知识点都学过,打不出来。AABC340CDivideandDivide找规律,很简单,也是我唯一做过的题。每次是2的幂时,它就会加一。复杂度是log⁡\log......
  • 『模拟赛』暑假集训CSP提高模拟18
    Rank致敬传奇不挂分Rank5模拟赛A.Mortis原[ABC302G]Sortfrom1to4签,致敬传奇abc_g作签到题。虽然但是还是想了1h,好在最后成功切了。具体解释看看题解,求个赞。点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintRatio=0;constintN=2......
  • 暑假集训CSP提高模拟18
    \[暑假集训CSP提高模拟\1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1\]Verygoodproblem,thismakemynewsrotate.A.Mortis考虑到应该先写个假的暴力.对于暴力思路,可以想到,假如我们每次都将一个不在它位置上的数字移到它应该在的地方的时候,另一个数字也刚好移到正确的位置,这......
  • 【C++学习笔记 16】构造函数初始化列表
    当编写类并向其中添加成员时,通常需要某种方式对这些成员进行初始化。常见的方法,如写一个构造函数赋初值classEntity{private: std::stringm_Name;public: Entity(){ m_Name="UnKnow"; } Entity(conststd::string&name){ m_Name=name; } constst......