- 博客(169)
- 收藏
- 关注
RSS订阅
原创 博客搬家声明
最近在博客园上注册了一个账号，发现博客园真的是一个很有意思的博客网站，上面也有许多CSDNCSDNCSDN上没有的功能。于是，我决定博客搬家了。我的博客中还有许多空链接，可能永远也不会去补了。一些待修改、标注更新inginging 的地方可能也不会去更新了。希望谅解。下面贴上新博客的链接：http://www.cnblogs.com/chenxiaoran666/...
2018-10-28 12:02:54
788
原创 2018暑假绍兴集训小记（7.12~7.21）
前言本次暑假的7.12~7.21，我们的信息团队到绍兴一中进行集训。这一次集训，让我感受到了绍一的强大（一道他们口中的EASY题却可以让我们想上一个甚至两三个小时）。不过，我也在这次集训中收获了许多。 Day1 7.12今天主要是在学习图论。图论包含割边割点，强连通分量等各种玄学的内容。图论与DP之间有着很大的联系，成环DP就是其中很难的一种。例如【POJ3028】Shoot-...
2018-07-18 17:13:46
1147
2
原创 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
512
5
原创 同余问题（一）——扩展欧几里得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
516
原创 【洛谷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
328
原创 【BZOJ3123】[SDOI2013] 森林（启发式合并主席树）
点此看题面大致题意： 给你一片森林，有两种操作：询问两点之间的第kkk小点权和在两棵树之间连一条边。前置技能：树上主席树做这道题目，我们首先要会树上主席树。关于树上主席树，这有一道很好的例题：【洛谷2633】Count on a tree（只包含此题的询问操作）。LinkLinkLink【洛谷2633】Count on a tree 的题解 详见博客 【洛谷2633】Count o...
2018-10-27 15:25:26
265
原创 【洛谷2633】Count on a tree（树上主席树）
点此看题面大致题意： 给你一棵树，每次问你两点之间第kkk小的点权，强制在线。主席树这种题目强制在线一般就是数据结构了。而看到区间第kkk小，很容易就能想到主席树。至少不会有人想到树套树。LinkLinkLink主席树 详见博客 可持久化专题（一）——浅谈主席树：可持久化线段树树上主席树与一般的主席树不同，这题的主席树是树上主席树（不过许多奆佬称其为主席树上树）。维护数...
2018-10-27 14:58:11
323
原创 【BZOJ1925】 [SDOI2010] 地精部落（带有一堆性质的动态规划）
点此看题面大致题意： 问你有多少长度为nnn的数列，它当中每个数字要么比旁边两个数字都小，要么比旁边两个数字都大。性质这题应该比较显然是一道动态规划题，但刚看到这题时我却无从下手。其实，了解了关于这种合法数列的几个性质，这题就不难了。它具有对称性。即如果a1a2...ana_1a_2...a_na1a2...an为合法数列，则anan−1...a1a_na_{n-1}......
2018-10-27 13:26:52
201
原创 【洛谷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
159
原创 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
345
原创 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
829
原创 【洛谷3157】[CQOI2011] 动态逆序对（CDQ分治）
点此看题面大致题意： 给你一个从111到nnn的排列，问你每次删去一个元素后剩余的逆序对个数。关于808080分的树套树为了练树套树，我找到了这道题目。但悲剧的是，我的**线段树套TreapTreapTreap**被卡了！只得了808080分。LinkLinkLink线段树套TreapTreapTreap 详见博客 初学树套树：线段树套Treap其实这个做法思路还是比较简单的，...
2018-10-26 22:43:12
257
原创 CDQ分治入门
前言CDQCDQCDQ分治是一个神奇的算法。它有着广泛的用途，甚至在某些题目中还能取代KD−TreeKD-TreeKD−Tree、树套树等恶心的数据结构成为正解，而且常数还小得多。不过它也有一定的缺点，如必须离线操作，遇到强制在线的题目还是老老实实打树套树吧… …核心思想CDQCDQCDQ分治的核心思想真的是非常简单，也就是分与治二字（其实所有分治算法都是这样）。分： 与常见的二分...
2018-10-26 21:52:06
405
原创 初学莫比乌斯反演
前言莫比乌斯反演应该是比较难的一类数论题了。关于它的许多性质，我也不怎么会证明（毕竟我数学差得要命）。学习这个算法时，在别人的博客中看到一句十分经典的话，在此特将其摘录如下：ExcerptExcerptExcerpt那些各种各样的性质与定理，大多是前人几年甚至几十年才得出来的，哪里是你几天就能理解并证明的。莫比乌斯函数μ\muμ莫比乌斯反演中最重要的自然就是**莫比乌斯函数μ\...
2018-10-26 20:03:37
315
原创 【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
552
原创 【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=1Md(i⋅j)。莫比乌斯反演这是一道莫比乌斯反演题。LinkLinkLink莫比乌斯反演 详见博客 初学莫比乌斯反演一个重要的性质首先我们要先了解d(i⋅j)d(i·j)d(i⋅j)这个函数的性...
2018-10-26 16:03:32
206
原创 【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
231
原创 浅谈KD-Tree
前言KD−TreeKD-TreeKD−Tree是一个十分神奇的东西，其实本质上类似于一个KKK维的二叉搜索树。LinkLinkLink二叉搜索树 详见博客 二叉搜索树（BST）学习笔记核心思想KD−TreeKD-TreeKD−Tree的核心思想与BSTBSTBST是差不多的（插入等操作也都基本上一样）。唯一的区别就在于，它每次比较的是某一维度上的值。但是，与BSTBSTBST一...
2018-10-26 07:47:58
815
原创 【洛谷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=1ns(i,j)。点分治这种题目比较显然是点分治吧… …LinkLinkLink点分治 详见博客 初学点分治大致思路首先，按照点分治的基本套路，对于一棵子树内的...
2018-10-25 22:25:10
239
原创 【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
183
原创 【洛谷2257】YY的GCD（莫比乌斯反演）
点此看题面大致题意： 求∑x=1N∑y=1MIsPrime(gcd(x,y))\sum_{x=1}^N\sum_{y=1}^MIsPrime(gcd(x,y))∑x=1N∑y=1MIsPrime(gcd(x,y))。莫比乌斯反演听说此题是莫比乌斯反演入门题？LinkLinkLink莫比乌斯反演 详见博客 初学莫比乌斯反演一些定义首先，我们可以定义f(d)f(d)f(d)和...
2018-10-25 19:40:33
307
原创 【CF739E】Gosha is hunting（WQS二分套WQS二分）
点此看题面大致题意： 你有两种捕捉球（分别为AAA个和BBB个），要捕捉nnn个神奇宝贝，第iii个神奇宝贝被第一种球捕捉的概率是s1is1_is1i，被第二种球捕捉的概率是s2is2_is2i，问在最优策略下期望捕捉到的神奇宝贝数量。WQSWQSWQS二分这应该是一道比较经典的WQSWQSWQS二分题（毕竟是**WQSWQSWQS二分套WQSWQSWQS二分**）。LinkLin...
2018-10-25 16:50:52
995
原创 WQS二分学习笔记
前言WQSWQSWQS二分听起来是个很难的算法，其实学起来也并不是那么难。适用范围在某些题目中，会对于某个取得越多越优的物品，限定你最多选择kkk个，问你能得到的最优答案。例如这道题目：【CF739E】Gosha is hunting。LinkLinkLink【CF739E】Gosha is hunting 的题解 详见博客 【CF739E】Gosha is hunting（WQS...
2018-10-25 16:27:13
3599
原创 【洛谷2152】[SDOI2009] SuperGCD（Python好题）
点此看题面大致题意： 给你两个长度≤10000\le10000≤10000的正整数，让你求它们的gcdgcdgcd。Python高精请绕道。这题的正解应该是Python。对于这种高精题，肯定是Python最方便了。于是我就默默写了Python。代码n=(int)(input())#读入第一个整数m=(int)(input())#读入第二个整数while n!=m:#辗转相...
2018-10-25 16:08:14
374
2
原创 【洛谷2519】[HAOI2011] problem a（动态规划）
点此看题面大致题意： 一次考试共有nnn个人参加，第iii个人说有aia_iai个人分数比他高，bib_ibi个人分数比他低。求最少有几个人说谎。动态规划刚看完题目可以说是一头雾水。仔细想想，可以把每个人的状态转化为一个区间（[ai+1,n−bi][a_i+1,n-b_i][ai+1,n−bi]），表示这个区间内所有元素都相等。那么我们要求的就是求出最大的区间数MaxMaxMa...
2018-10-25 14:08:50
210
原创 2018.10.24 NOIP2018模拟赛 解题报告
得分： 100+0+100=200100+0+100=200100+0+100=200（T2T2T2悲惨爆000）P.S.P.S.P.S.由于原题是图片，所以我没有上传题目描述，只有数据。T1T1T1：query（点此看题面）熟悉主席树的人都知道，这是一道主席树查询区间排名的模板题。LinkLinkLink主席树 详见博客 可持久化专题（一）——浅谈主席树：可持久化线段树但是，由...
2018-10-25 07:34:50
331
原创 【BZOJ1972】[SDOI2010] 猪国杀（恶心的大模拟）
点此看题面大致题意： 让你模拟一个游戏猪国杀的过程。极大坑点对于这种模拟题，具体思路就不讲了，就说说有哪些坑点。题面有锅，反猪是FPFPFP。数据有锅，牌堆中的牌可能不够用，牌堆为空之后需一直抽最后一张牌。主猪杀死忠猪后猪哥连弩也要清除。无懈可击也可以用无懈可击抵消。使用决斗的猪可能死亡。无懈可击是从使用锦囊牌的猪开始轮流选择是否响应。使用完一张牌...
2018-10-23 20:28:41
431
原创 【洛谷1613】跑路（倍增+最短路）
点此看题面大致题意： 小AAA要从111号节点到nnn号节点，已知他每个单位时间可以跑2k2^k2k千米，求他最少需要多少个单位时间。预处理由于数据范围较小，我们可以先大力预处理。首先，将题目中给出的边边权初始化为000。若从一点出发，到两点皆有一条边权为kkk的边，就将这两点之间连一条边权为k+1k+1k+1的边。这样重复nnn次，就能保证所有该连的边都连好了。SPFASPFA...
2018-10-21 14:07:02
192
原创 【洛谷4149】[IOI2011] Race（点分治）
点此看题面大致题意： 给你一棵树，问长度为KKK的路径至少由几条边构成。点分治这题应该比较显然是点分治。LinkLinkLink点分治 详见博客 初学点分治主要思路与常见的点分治套路一样，由于K≤1000000K≤1000000K≤1000000，因此我们可以考虑开个桶fff数组来记录每种长度的路径至少由几条边构成。但是要注意，每换一个根要将桶清空！呃，暴力清空肯定TTT...
2018-10-21 13:49:58
194
原创 【洛谷2216】[HAOI2007] 理想的正方形（二维RMQ）
点此看题面大致题意： 求出一个矩阵中所有n∗nn*nn∗n正方形中极差的最小值。另一种做法听说这题可以用单调队列去做，但是我写了一个二维RMQRMQRMQ。二维RMQRMQRMQRMQRMQRMQ相信大家都会的，而 二维RMQRMQRMQ 其实与普通RMQRMQRMQ是没什么区别的。我们可以用Maxi,j,kMax_{i,j,k}Maxi,j,k来表示(i,j)∼(i+2k,j+...
2018-10-21 12:40:59
176
原创 【洛谷2577】[ZJOI2005] 午餐（较水DP）
点此看题面大致题意： 有NNN个学生去食堂打饭，每个学生有两个属性：打饭时间aia_iai和吃饭时间bib_ibi。现要求将这些学生分成两队分别打饭，求最早何时所有人吃完饭。贪心首先，依据贪心的思想，肯定是吃饭时间长的先打饭，因此可以将其按吃饭时间先排序预处理一遍。如何DPDPDP贪心完，就是DPDPDP了。个人认为三维DPDPDP还是非常好想的：用fi,j,kf_{i,j,k...
2018-10-21 12:35:34
189
原创 【BZOJ1060】[ZJOI2007] 时态同步（树形DP）
点此看题面大致题意： 给你一棵带权树，每次使用道具可以将某条边的边权加111，问你至少需要使用多少次道具，才能使每个叶子节点到根节点的距离相等。贪心的思想首先，我们应该先有一个贪心的思想。不难发现，如果要将以xxx为根节点的子树内的所有边权加上valvalval，不如直接将xxx到faxfa_xfax的边权加上valvalval更优。这样一来就有一个基本思路：对于以xxx为根节点的子...
2018-10-21 12:33:23
149
原创 【洛谷2051】[AHOI2009] 中国象棋（烦人的动态规划）
点此看题面大致题意： 让你在一张N∗MN*MN∗M的棋盘上摆放炮，使其无法互相攻击，问有多少种摆法。辟谣听某大佬说这是一道**状压DPDPDP**题，于是兴冲冲地去做，看完数据范围彻底懵了：N≤100N≤100N≤100！这么大的数据范围压死你！好吧，其实这就是一道普通的DPDPDP，与状压没有任何关系。其实状压可以用来骗分，能得50。考虑性质对于这种题目，第一步肯定是考虑有没有...
2018-10-20 15:49:13
220
原创 【洛谷4287】[SHOI2011] 双倍回文（Manacher算法经典题）
点此看题面大致题意： 求一个字符串中有多少个长度为偶数的回文串，它的一半也是回文串。ManacherManacherManacher算法这应该是ManacherManacherManacher算法一道比较好的入门题，强烈建议在做这题之前先去学一学ManacherManacherManacher算法。LinkLinkLinkManacherManacherManacher算法 详见博客...
2018-10-20 13:02:52
397
原创 【洛谷2264】情书（字符串水题）
点此看题面大致题意： 给你nnn个关键词和一个文本串。让你求出这些单词在这个文本串中总共出现次数（一句话中同一单词只算一次）。细节这题其实还是比较水的，一道很简单的TrieTrieTrie题（数据范围这么小，貌似暴力照样过），居然还能是一道蓝题。LinkLinkLinkTrieTrieTrie 详见博客 Trie：字典树但是，这题还是有很多细节的，大体如下：关键词在一句话中的...
2018-10-20 13:02:40
284
原创 【洛谷1273】有线电视网（树上背包）
点此看题面大致题意： 给你一棵带权树，已知每连接一条边需要一定花费，如果某个叶节点能到达根，可以获得一定收益。问在不亏本的情况下，最多能使多少个叶节点能到达根。树上背包这是一道比较经典的树上背包题。LinkLinkLink树上背包 详见博客 动态规划专题（二）——树形DP如何记录状态我们可以用fi,jf_{i,j}fi,j表示在以iii为根的子树内选择jjj个叶节点能得到的...
2018-10-20 13:02:23
234
原创 【BZOJ1088】[SCOI2005] 扫雷Mine（分类讨论）
点此看题面大致题意： 给你一个2∗n2*n2∗n的扫雷棋盘，现让你根据第二列的信息确定第一列有多少种摆法。扫雷性质听说这是一道动态规划+数学题。其实，根据扫雷游戏的某个性质，只要确定了第一个格子是否有雷，就可以确定整列雷的分布情况！因此，最多只可能有两种摆法。这样一来，只要对第一个格子是否有雷分类讨论即可，遇到合法的情况就将ansansans加$1。如何确定整列雷的分布情况我们...
2018-10-20 13:02:02
247
原创 2018.10.05 TOPOI提高组模拟赛 解题报告
得分： 100+5+100=205100+5+100=205100+5+100=205（真的是出乎意料）T1T1T1：抵制克苏恩（点此看题面）原题： 【BZOJ4832】[Lydsy1704月赛] 抵制克苏恩应该还是一个比较简单的DPDPDP吧（我是用记忆化搜索实现的）。可以用fn,A,B,Cf_{n,A,B,C}fn,A,B,C来表示还有nnn个回合，三种血量奴隶主个数分别为A,B,...
2018-10-18 18:33:53
179
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人