热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

洛谷P3295萌萌哒[SCOI2016]倍增+并查集

正解:倍增+并查集 解题报告: 传送门! 最近考试考到了一道类似的题然后就想起这道回来看下,发现题解写得奇奇怪怪的我我我重构下$QwQ$ 首先不难想到暴力?就考虑把区间相等转化成对应点对相等
正解:倍增+并查集 解题报告:

传送门!

最近考试考到了一道类似的题然后就想起这道回来看下,发现题解写得奇奇怪怪的我我我重构下$QwQ$

首先不难想到暴力?就考虑把区间相等转化成对应点对相等,然后直接对应点连边,最后求有几个连通块就好辣

然后看下复杂度,修改是$O(n^2)$查询是$O(n)$,就比较容易想到能不能通过一些技巧变成都是$O(nlogn)$的,结合数据范围发现$nlogn$的复杂度似乎是对的,于是就往这个方面想呗.就不难想到倍增和线段树.

考虑倍增,设$f_{i,j}$表示$[i,i+2^j-1]$这一段区间的信息.然后每次赋值操作就可以二进制拆分成$log$个区间,然后直接赋值$f_{l_1,j}=f_{l_2,j}$.

最后回答询问的时候把所有相等关系下放下去,就$f_{i,j}=f_{i,j+1},f_{i,i+2^{j-1}}=f_{i,j+1}$.

最后统计下联通块个数$cnt$,答案就$10^{cnt}$.

其实是有点类似线段树的$lazy\_tag$操作的$QwQ$

#include
using namespace std;
#define il inline
#define ll long long
#define rg register
#define gc getchar()
#define rp(i,x,y) for(rg int i&#61;x;i<&#61;y;&#43;&#43;i)
#define my(i,x,y) for(rg int i&#61;x;i>&#61;y;--i)
const int N&#61;1e5&#43;10,mod&#61;1e9&#43;7;
int n,m,f[N][20],poww[20],cnt;
ll as&#61;9;
il int read()
{
rg char ch&#61;gc;rg int x&#61;0;rg bool y&#61;1;
while(ch!&#61;&#39;-&#39; && (ch>&#39;9&#39; || ch<&#39;0&#39;))ch&#61;gc;
if(ch&#61;&#61;&#39;-&#39;)ch&#61;gc,y&#61;0;
while(ch>&#61;&#39;0&#39; && ch<&#61;&#39;9&#39;)x&#61;(x<<1)&#43;(x<<3)&#43;(ch^&#39;0&#39;),ch&#61;gc;
return y?x:-x;
}
il void pre(){poww[0]&#61;1;rp(i,1,19)poww[i]&#61;poww[i-1]<<1;rp(i,1,n)rp(j,0,20)f[i][j]&#61;i;}
int fd(int x,int lth){return f[x][lth]&#61;&#61;x?x:f[x][lth]&#61;fd(f[x][lth],lth);}
il void merg(int x,int y,int lth){int fax&#61;fd(x,lth),fay&#61;fd(y,lth);if(fax!&#61;fay)f[fax][lth]&#61;fay;}
int main()
{
// freopen("mmd.in","r",stdin);freopen("mmd.out","w",stdout);
n&#61;read();m&#61;read();pre();
while(m--){int l1&#61;read(),r1&#61;read(),l2&#61;read(),r2&#61;read();my(i,19,0)if(l1&#43;poww[i]-1<&#61;r1)merg(l1,l2,i),l1&#43;&#61;poww[i],l2&#43;&#61;poww[i];}
my(j,19,1)rp(i,1,n-poww[j]&#43;1)merg(i,fd(i,j),j-1),merg(i&#43;poww[j-1],fd(i,j)&#43;poww[j-1],j-1);
rp(i,1,n)if(fd(i,0)&#61;&#61;i)&#43;&#43;cnt;rp(i,1,cnt-1)as&#61;as*10,as%&#61;mod;
printf("%lld\n",as);
return 0;
}

放个代码就麻油辣QAQ


推荐阅读
  • 树链问题的优化解法:深度优先搜索与质因数分解
    本文介绍了一种通过深度优先搜索(DFS)和质因数分解来解决最长树链问题的方法。我们通过枚举树链上的最大公约数(GCD),将所有节点按其质因子分类,并计算每个类别的最长链,最终求得全局最长链。 ... [详细]
  • JSOI2010 蔬菜庆典:树结构中的无限大权值问题
    本文探讨了 JSOI2010 的蔬菜庆典问题,主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性,提出了有效的解决方案,并详细解释了算法的实现过程。 ... [详细]
  • 本题来自WC2014,题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系,要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]
  • 本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现,并详细解释了算法的核心思想和具体实现步骤。 ... [详细]
  • 本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符,并提供了多种编程语言的实现示例。 ... [详细]
  • 在高并发需求的C++项目中,我们最初选择了JsonCpp进行JSON解析和序列化。然而,在处理大数据量时,JsonCpp频繁抛出异常,尤其是在多线程环境下问题更为突出。通过分析发现,旧版本的JsonCpp存在多线程安全性和性能瓶颈。经过评估,我们最终选择了RapidJSON作为替代方案,并实现了显著的性能提升。 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • Linux环境下C语言实现定时向文件写入当前时间
    本文介绍如何在Linux系统中使用C语言编程,实现在每秒钟向指定文件中写入当前时间戳。通过此示例,读者可以了解基本的文件操作、时间处理以及循环控制。 ... [详细]
  • 本文介绍了一个经典的算法问题——活动选择问题,来源于牛客网的比赛题目。该问题要求从一系列活动集合中选出最多数量的相容活动,确保这些活动的时间段不重叠。 ... [详细]
  • 本文详细解析了2019年西安邀请赛中的一道树形动态规划题目——J题《And And And》。题目要求计算树中所有子路径异或值为0的集合数量,通过深入分析和算法优化,提供了高效的解决方案。 ... [详细]
  • JavaScript 基础语法指南
    本文详细介绍了 JavaScript 的基础语法,包括变量、数据类型、运算符、语句和函数等内容,旨在为初学者提供全面的入门指导。 ... [详细]
  • Python处理Word文档的高效技巧
    本文详细介绍了如何使用Python处理Word文档,涵盖从基础操作到高级功能的各种技巧。我们将探讨如何生成文档、定义样式、提取表格数据以及处理超链接和图片等内容。 ... [详细]
  • 在尝试使用C# Windows Forms客户端通过SignalR连接到ASP.NET服务器时,遇到了内部服务器错误(500)。本文将详细探讨问题的原因及解决方案。 ... [详细]
  • 探讨ChatGPT在法律和版权方面的潜在风险及影响,分析其作为内容创造工具的合法性和合规性。 ... [详细]
  • 优化SQL Server批量数据插入存储过程的实现
    本文介绍了一种改进的SQL Server存储过程,用于生成批量插入语句。该方法不仅提高了性能,还支持单行和多行模式,适用于SQL Server 2005及以上版本。 ... [详细]
author-avatar
hexin01
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有