3 KsCla

尚未进行身份认证

OI退役选手,广东某强校的菜鸡一只。

等级
TA的排名 2w+

BZOJ4538:[Hnoi2016]网络 (整体二分+Lca+树状数组/线段树+路径交/树链剖分+Heap)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4538题目分析:这题网上好多人写树剖啊,都是把一条路径的区间搞出来之后取反更新,删除的话就套个Heap或者写线段树CDQ分治blablabla,时间复杂度O(nlog3(n))O(nlog^3(n)),好像因为树剖和Heap的常数特别小所以根本不虚。网上某大神用这种方法8200ms就过了,而

2017-08-28 16:49:53

手动友链

没有摘要

2019-12-27 17:50:31

CSP2019Day2T3 洛谷P5666:树的重心 (树上倍增)

题目传送门:https://www.luogu.org/problem/P5666很早以前就觉得,凡是考树的重心相关的题,到最后都变成一道模拟题。树的重心有许多优秀的性质,比如:结论一:记f(node)表示以node为根的最大子树的大小。从无根树上的任意一个点x出发,向相邻的点走一步。假设某个点y的f值比x的小,那么x向y走就相当于向树的重心移动了一步。假设不存在这样的y,那么x就是重心。...

2019-11-24 00:59:31

咕咕咕

没有摘要

2019-07-09 23:24:08

BZOJ5495:[2019省队联测]异或粽子 (Trie+贪心)

题目传送门BZOJ(没题面)洛谷(有题面)题目大意给出一个长为n的序列,选择k个不完全重合的区间使得每个区间的异或值的总和最大。题解作为高三退役狗康复训练的第一题,我发现我的做法有点特立独行……4月份Ghastlcon跟我说这题的时候,我在想为什么要用可持久化Trie。而现在我YY出了一个既不用可持久化也不用堆的方法。首先把所有的异或前缀和扔进Trie,接下来目标就是找最大的k...

2019-06-17 18:03:24

UOJ#348:【WC2018】州区划分 (FMT优化DP)

题目传送门:http://uoj.ac/problem/348题目分析:题面就是要求将n个点划分为若干个集合,使得刚好包含某个集合的点以及它们之间的边的子图不存在欧拉回路。然后题面给出了一种方法计算某种方案的贡献。由于n很小,不妨先用h[s]表示s中的点能不能刚好划分为一个集合。算出h[]的时间是O(n22n)O(n22n)O(n^22^n)的。对于题面给出的式子,我们发现每个集合的贡...

2018-04-17 22:06:42

CodeChef Counting D-sets (容斥原理+组合数学)

vjudge题面传送门:https://cn.vjudge.net/problem/CodeChef-CNTDSETS(PS:vjudge上中文版的题面有误,一个点集的直径应该定义为其中点对的切比雪夫距离的最大值。切比雪夫距离是两个点各个维度之差的绝对值取max。这一点看回英文版题面就能知道)题目分析:一道思维难度较大,代码量极少的题。直径=d的点集数 = 直径<=d的点集数...

2018-03-29 21:40:41

BZOJ4767:两双手 (组合数学+DP+容斥原理)

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=4767题目分析:一开始看题目名还以为是两只手,后来感觉有些不对劲……题面保证了给出的两个向量叉积为0,就是说它们不平行。不平行的两个向量可以作为一组基底,这样原先平面上的所有点就获得了一个新坐标。于是问题变成了:从(0,0)走到(n,m),中间不能经过指定的k个点,求方案数。...

2018-03-29 16:28:10

circle (容斥原理+数据结构)

题目大意:在一条直线上有2*n个点,点与点之间两两配对成n组。现在要你选出三组点对,使得这三组点对满足112233,122331,123123的其中一种形式,问方案数。n≤105n≤105n\leq 10^5。题目分析:多年前的老坑,昨天晚上想填一下,发现还是不会做,而且我还是看不懂题解。懵逼了一整晚,最后翻出标程来看,终于看懂了做法。从n个点对中选取3个点对,有C3nCn3C_n^3...

2018-03-29 10:56:47

BZOJ4710:[Jsoi2011]分特产 (容斥原理+组合数学+DP)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4710题目分析:一开始看完全没有头绪,后来发现这不就是个和第二类stirling数很像的容斥吗?首先考虑没有“每个人至少要拿一个特产”这个条件怎么做。由于不同的特产之间是独立的,可以记h[i][j]表示前i个人拿了j件特产的方案数。转移方程为h[i][j]=∑jk=0h[i−1...

2018-03-28 10:54:59

BZOJ1042:[HAOI2008]硬币购物 (容斥原理+DP)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1042题目分析:我看某个课件看到这题,一开始还以为每组询问都重新给出四个面值,导致我一直没有思路QAQ。由于四个面值是固定的,可以先做一次完全背包,将价值为1~maxs的答案记下来。每次询问的时候,记f(s)表示 只有 s集合中的硬币超过限制的方案数,记g(s)表示 至少有 s...

2018-03-28 09:23:41

BZOJ4008:[HNOI2015]亚瑟王 (概率DP)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4008题目分析:一道很厉害的DP,做法和背包类似。记g[i][j]表示前i张卡牌,有j张卡牌发动了技能的概率,那么存在如下转移:g[i+1][j]=g[i][j]∗(1−p[i+1])r−jg[i+1][j]=g[i][j]∗(1−p[i+1])r−jg[i+1][j]=g[i...

2018-03-27 15:58:42

BZOJ1444:[Jsoi2009]有趣的游戏 (AC自动机+概率DP+高斯消元)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1444题目分析:首先考虑静态的问题:如果已经生成一个字符串,如何让它跟所有模式串匹配?答案是建出所有模式串的AC自动机,然后让生成串在上面跑,如果跑到某个有endpos的节点就一直停在那里。然后考虑动态的问题:如果生成串无限长,如何求出它停在每个节点的概率?把AC自动机扩展成T...

2018-03-27 11:11:54

BZOJ3143:[Hnoi2013]游走 (高斯消元+概率DP)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3143题目分析:很久之前就对这种高斯消元解DP值的题目有一种莫名的恐惧,因为它明明是DP却没有递推顺序因为我对概率论一窍不通。学了高消之后,我YY了一下这题的DP方程,发现一直过不了样例。最后居然被tututu在旁边随便口胡一句就过了?!本题要让我们自定每条边的权值,所以我们想...

2018-03-26 21:26:43

BZOJ1923:[Sdoi2010]外星千足虫 (高斯消元+二进制压位)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1923题目分析:一开始还很好奇什么是异或高斯消元,后来发现就是用高消解异或方程组。普通的n3n3n^3高消理论上来说是过不了这题的,虽然实际上能过。观察一下,发现高斯消元的主要时间在于选定某一行作为主元后,将后面几行的对应位置变成0。而本题由于是异或操作,可以用bitset或者...

2018-03-26 16:52:50

BZOJ1013:[JSOI2008]球形空间产生器sphere (高斯消元)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1013题目分析:设题面给出的第i个坐标为(ai,1,ai,2……ai,n)(ai,1,ai,2……ai,n)(a_{i,1},a_{i,2}……a_{i,n}),设答案为(b1,b2……bn)(b1,b2……bn)(b_1,b_2……b_n)。经过一番推导,令:pi=2∑j=1...

2018-03-26 15:12:36

洛谷P3389:【模板】高斯消元法

题目传送门:https://www.luogu.org/problemnew/show/P3389题目分析:时隔多年(月),我终于入了高消这个坑。表示挂一发模板就跑,以后复习用。具体细节什么的还是自己YY吧,有益身心健康。CODE:#include<iostream>#include<string>#include<cstring&...

2018-03-26 11:07:46

count (类插头DP+矩阵快速幂)

题目大意:有n个点,编号为1~n。第i个点和第j个点之间有一条无向边当且仅当|i-j|<=k。求这个图的生成树个数。k≤5,n≤1015k≤5,n≤1015k\leq 5,n\leq 10^{15}。题目分析:Coming在他初二时的资料里找到的一道题,是我校上古大神cdc给的。我不得不吐槽:难道前几届的dalao初二就能做这种题了吗?而且题面还很恶意地给出了怎么用矩阵树定理算无向图...

2018-03-22 20:19:00

CodeChef Union on Tree (虚树+点分治)

vjudge题面传送门:https://cn.vjudge.net/problem/CodeChef-BTREE题目分析:sro wjmzbmr这是道码农神题。首先考虑简化版的问题:如果给出一个点x,再给出一个距离d,如何求出距离x不超过d的点的个数?这可以用点分治解决。先用点分治预处理出每个连通块的所有点到其分治中心mid的深度数组f。f[mid][son][dep]=num表示分治...

2018-03-22 14:38:41

洛谷P4067:[SDOI2016]储能表 (数位DP)

题目传送门:https://www.luogu.org/problemnew/show/P4067题目分析:一道令我心态爆炸的数位DP。一调调一天,WA不花一分钱先说一下我理解的数位DP是什么。数位DP本质上还是个DP,它里面有很多重复的子问题。但现在题面给了DP的下标一个上界限制,而我们不能直接枚举下标,所以要贴着这个上界限制来DFS。形象地做个比喻就是走楼梯,DFS的时候要紧贴着楼...

2018-03-22 08:39:20

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。