3 chenxiaoran666

尚未进行身份认证

我要认证

人要有梦想,不然和咸鱼有什么区别!

等级
TA的排名 3w+

博客搬家声明

最近在博客园上注册了一个账号,发现博客园真的是一个很有意思的博客网站,上面也有许多CSDNCSDNCSDN上没有的功能。于是,我决定博客搬家了。我的博客中还有许多空链接,可能永远也不会去补了。一些待修改、标注更新inginging 的地方可能也不会去更新了。希望谅解。下面贴上新博客的链接:http://www.cnblogs.com/chenxiaoran666/...

2018-10-28 12:02:54

BSGS算法初探

前言BSGSBSGSBSGS算法,全称Baby Step Giant StepBaby\ Step\ Giant\ StepBaby Step Giant Step,即大小步算法。某些奆佬也称其为拔(Ba)山(Shan)盖(Gai)世(Shi)算法。它的主要作用是求解形式如xt≡y(mod&

2018-10-28 08:10:27

同余问题(一)——扩展欧几里得exgcd

前言扩展欧几里得算法是一个很好的解决同余问题的算法,非常实用。欧几里得算法简介欧几里得算法,又称辗转相除法。主要用途求最大公因数gcdgcdgcd。公式gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)gcd(a,b)=gcd(b,a%b)公式证明aaa可以表示成a=kb+a%ba=kb+a\%ba=kb+a%b(kkk为自然数)。假设ggg是a...

2018-10-27 17:39:58

【洛谷3759】[TJOI2017] 不勤劳的图书管理员(树套树)

点此看题面大致题意: 给定一个序列,每个元素有两个属性aia_iai​和viv_ivi​,每次操作改变两个元素的位置,求每次操作后∑vi+vj[i<j,ai>aj]\sum{v_i+v_j}[i<j,a_i>a_j]∑vi​+vj​[i<j,ai​>aj​]。关于题意的解读其实,题目差不多就是让我们求逆序对(只不过每个逆序...

2018-10-27 15:49:41

【BZOJ3123】[SDOI2013] 森林(启发式合并主席树)

点此看题面大致题意: 给你一片森林,有两种操作:询问两点之间的第kkk小点权和在两棵树之间连一条边。前置技能:树上主席树做这道题目,我们首先要会树上主席树。关于树上主席树,这有一道很好的例题:【洛谷2633】Count on a tree(只包含此题的询问操作)。LinkLinkLink【洛谷2633】Count on a tree 的题解 详见博客 【洛谷2633】Count o...

2018-10-27 15:25:26

【洛谷2633】Count on a tree(树上主席树)

点此看题面大致题意: 给你一棵树,每次问你两点之间第kkk小的点权,强制在线。主席树这种题目强制在线一般就是数据结构了。而看到区间第kkk小,很容易就能想到主席树。至少不会有人想到树套树。LinkLinkLink主席树 详见博客 可持久化专题(一)——浅谈主席树:可持久化线段树树上主席树与一般的主席树不同,这题的主席树是树上主席树(不过许多奆佬称其为主席树上树)。维护数...

2018-10-27 14:58:11

【BZOJ1925】 [SDOI2010] 地精部落(带有一堆性质的动态规划)

点此看题面大致题意: 问你有多少长度为nnn的数列,它当中每个数字要么比旁边两个数字都小,要么比旁边两个数字都大。性质这题应该比较显然是一道动态规划题,但刚看到这题时我却无从下手。其实,了解了关于这种合法数列的几个性质,这题就不难了。它具有对称性。即如果a1a2...ana_1a_2...a_na1​a2​...an​为合法数列,则anan−1...a1a_na_{n-1}......

2018-10-27 13:26:52

【洛谷2468】[SDOI2010] 粟粟的书架(二合一)

点此看题面大致题意: 问你选取一个矩形区间内至少几个数,才能使它们的和≥Hi\ge H_i≥Hi​。二合一根据数据范围,比较显然能看出它是一道二合一的题目。对于第一种情况,R,C≤200R,C\le 200R,C≤200,我们可以用前缀和+二分去做。而对于另一种情况,R=1,C≤500000R=1,C\le500000R=1,C≤500000,就需要使用主席树了。LinkLinkL...

2018-10-27 12:04:41

2018.10.26 NOIP2018模拟赛 解题报告

得分: 0+10+100+10+100+10+10(T1T1T1死于假题面,T3T3T3死于细节… …)P.S.P.S.P.S.由于原题是图片,所以我没有上传题目描述,只有数据。T1T1T1:颜料大乱斗(点此看题面)由于颜色种类数很少,因此比较容易想到将颜色状压后用线段树去维护。但是,题目中没有提及初始颜色为111,害得我以为初始颜色为000。结果爆000。现将改后的代码贴出来:#...

2018-10-27 11:19:58

NOIP2018初赛 解题报告

前言NOIP2018NOIP2018NOIP2018初赛已经结束了,接下来就要准备复赛了。不过,在此之前,还是先为初赛写一篇解题报告吧。单项选择题送分题。(虽然我还是做错了)可以考虑将它们全部转化为101010进制,则(269)16=(617)10=(1151)8(269)_{16}=(617)_{10}=(1151)_8(269)16​=(617)10​=(1151)8​,而(100...

2018-10-27 09:43:22

【洛谷3157】[CQOI2011] 动态逆序对(CDQ分治)

点此看题面大致题意: 给你一个从111到nnn的排列,问你每次删去一个元素后剩余的逆序对个数。关于808080分的树套树为了练树套树,我找到了这道题目。但悲剧的是,我的**线段树套TreapTreapTreap**被卡了!只得了808080分。LinkLinkLink线段树套TreapTreapTreap 详见博客 初学树套树:线段树套Treap其实这个做法思路还是比较简单的,...

2018-10-26 22:43:12

CDQ分治入门

前言CDQCDQCDQ分治是一个神奇的算法。它有着广泛的用途,甚至在某些题目中还能取代KD−TreeKD-TreeKD−Tree、树套树等恶心的数据结构成为正解,而且常数还小得多。不过它也有一定的缺点,如必须离线操作,遇到强制在线的题目还是老老实实打树套树吧… …核心思想CDQCDQCDQ分治的核心思想真的是非常简单,也就是分与治二字(其实所有分治算法都是这样)。分: 与常见的二分...

2018-10-26 21:52:06

初学莫比乌斯反演

前言莫比乌斯反演应该是比较难的一类数论题了。关于它的许多性质,我也不怎么会证明(毕竟我数学差得要命)。学习这个算法时,在别人的博客中看到一句十分经典的话,在此特将其摘录如下:ExcerptExcerptExcerpt那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。莫比乌斯函数μ\muμ莫比乌斯反演中最重要的自然就是**莫比乌斯函数μ\...

2018-10-26 20:03:37

【HHHOJ】NOIP2018 模拟赛(二十四) 解题报告

点此进入比赛得分: 100+60+100100+60+100100+60+100(挺好的,涨了一波RatingRatingRating)排名: Rank 1Rank\ 1Rank 1RatingRatingRating:+115+115+115T1T1T1:【HHHOJ13】金(点此看题面)原题: 【洛谷2152】[SDOI2009] SuperGCDLinkL...

2018-10-26 18:03:17

【BZOJ3994】[SDOI2015] 约数个数和(莫比乌斯反演)

点此看题面大致题意: 设d(x)d(x)d(x)为xxx的约数个数,求∑i=1N∑j=1Md(i⋅j)\sum_{i=1}^N\sum_{j=1}^Md(i·j)∑i=1N​∑j=1M​d(i⋅j)。莫比乌斯反演这是一道莫比乌斯反演题。LinkLinkLink莫比乌斯反演 详见博客 初学莫比乌斯反演一个重要的性质首先我们要先了解d(i⋅j)d(i·j)d(i⋅j)这个函数的性...

2018-10-26 16:03:32

【BZOJ2648】SJY摆棋子(KD-Tree)

点此看题面大致题意: 在一个二维平面上现有NNN个棋子,有两种操作:增加一个棋子;查询离某个坐标最近的棋子离它的曼哈顿距离。KD−TreeKD-TreeKD−Tree这是一道KD−TreeKD-TreeKD−Tree的乱搞题。LinkLinkLinkKD−TreeKD-TreeKD−Tree 详见博客 浅谈KD-Tree如何询问在此题中,建树、插入、重构等过程其实与普通的KD...

2018-10-26 08:06:24

浅谈KD-Tree

前言KD−TreeKD-TreeKD−Tree是一个十分神奇的东西,其实本质上类似于一个KKK维的二叉搜索树。LinkLinkLink二叉搜索树 详见博客 二叉搜索树(BST)学习笔记核心思想KD−TreeKD-TreeKD−Tree的核心思想与BSTBSTBST是差不多的(插入等操作也都基本上一样)。唯一的区别就在于,它每次比较的是某一维度上的值。但是,与BSTBSTBST一...

2018-10-26 07:47:58

【洛谷2664】树上游戏(点分治)

点此看题面大致题意: 给定一棵树,每个节点有一个颜色,定义s(i,j)s(i,j)s(i,j)为iii到jjj路径上颜色数量,请你对于每一个iii求出∑i=1ns(i,j)\sum_{i=1}^n s(i,j)∑i=1n​s(i,j)。点分治这种题目比较显然是点分治吧… …LinkLinkLink点分治 详见博客 初学点分治大致思路首先,按照点分治的基本套路,对于一棵子树内的...

2018-10-25 22:25:10

【BZOJ1101】[POI2007] Zap(莫比乌斯反演)

点此看题面大致题意: 求∑x=1N∑y=1M[gcd(x,y)==d]\sum_{x=1}^N\sum_{y=1}^M[gcd(x,y)==d]∑x=1N​∑y=1M​[gcd(x,y)==d]。一道类似的题目推荐先去做一下这道题:【洛谷2257】YY的GCD。再来看这题,就非常简单了。LinkLinkLink【洛谷2257】YY的GCD 的题解 详见博客 【洛谷2257】YY的G...

2018-10-25 20:06:21

【洛谷2257】YY的GCD(莫比乌斯反演)

点此看题面大致题意: 求∑x=1N∑y=1MIsPrime(gcd(x,y))\sum_{x=1}^N\sum_{y=1}^MIsPrime(gcd(x,y))∑x=1N​∑y=1M​IsPrime(gcd(x,y))。莫比乌斯反演听说此题是莫比乌斯反演入门题?LinkLinkLink莫比乌斯反演 详见博客 初学莫比乌斯反演一些定义首先,我们可以定义f(d)f(d)f(d)和...

2018-10-25 19:40:33

查看更多

勋章 我的勋章
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得