A simple Blog for wyx I've been down the bottle hoping.
4488: [Jsoi2015]最大公约数 && 4052: [Cerc2013]Magical GCD
发表于: | 分类:Oi | 评论:0 | 阅读:163
当我发现Js出了一道原题的时候我也是……顺便说一下,其实4052也不是原题,原题是一道cf题2333333 现在估计也是把出题人憋坏了 首先你需要明确一个事情,对于一段区间$[L,R]$,他的$gcd$一定是不小于$[L,R+1]$的 进一步我们可以发现,就算是...

阅读全文>>

4542: [Hnoi2016]大数 莫队
发表于: | 分类:Oi | 评论:0 | 阅读:132
傻逼BZ 不给数据范围 毁我青春 这是一道非常简单的题……首先我们可以维护一个模意义下的后缀和。然后一个中间的数字就是两个后缀和的差/10多少次幂 然后就非常好办了,只需要统计一段区间内有多少个相同的数字就行了,显然$k$个相同的数字对答案的贡献就是 $C_k^...

阅读全文>>

4537: [Hnoi2016]最小公倍数 莫队
发表于: | 分类:Oi | 评论:0 | 阅读:131
莫队+数据结构训练,再次手动@HNOI2016 这题还是挺简单的,首先思考一下这个东西由于对路径的要求非常低,而且可以离线,果断是可以离线并查集的 暴力的话就直接把所有$a,b$小于等于他的$a,b$的边用并查集练练,然后判断一下最大值啥的就行了 现在考虑用分块优...

阅读全文>>

2125: 最短路 圆方树 仙人掌 倍增LCA
发表于: | 分类:Oi | 评论:0 | 阅读:165
犯了个智障错误调了半天 还是原来的套路,先把圆方树建出来,然后把每个点连到方点的距离设置成到环最上面的点的最短距离,然后正常倍增lca 注意最后的时候如果落在了一个圆点上就可以直接更新答案啦,如果落在方点上,就找到在lca方向上的最后一个点,然后把他们到lca的距...

阅读全文>>

1023: [SHOI2008]cactus仙人掌图 圆方树 单调队列 仙人掌
发表于: | 分类:Oi | 评论:0 | 阅读:143
开始刷仙人掌问题,主要依靠圆方树来解决问题 圆方树就是找一个环,然后把环上的边都拆掉,然后新建一个点连接所有的换上的点 实现的话依靠深搜,维护一下点在搜索树上的父亲以及深度,如果发现一个点连接的另外一个点的深度比自己的深度还小,那连接的点一定是一个环的上顶点,然后...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP