1 刘成

学生身份

我要认证

大一菜鸡

等级
TA的排名 5k+

HDU多校7 - 6853 Jogging(bfs+结论)

题目链接:点击查看题目大意:在二维平面中有一个点 ( x , y ) ,规定 “ 好点 ” 的定义是,gcd( x , y ) > 1 ,现在从点 ( x , y ) 开始,每一次都能等概率的选择:去周围八个方向中的“好点” 停留在原地不动现在问在走无穷多次步数后,能够从点 ( x , y ) 出发再回到点 ( x , y ) 的概率是多少题目分析:比赛时稍微打了个表,感觉是暴力bfs出所有点然后计算答案,主要是答案不会计算,就放掉了,因为 1e12 以内的相邻两个素数之差最大也不过几

2020-08-12 03:23:15

牛客多校10 - Identical Trees(dp+二分图最小权匹配)

题目链接:点击查看题目大意:给出两个同构树 tree1 和 tree2 ,问最少需要改变多少个结点的标号,可以使得这两棵树相同题目分析:直接 dfs 维护 dp 就好了,dp[ i ][ j ] 表示 tree1 中点 i 的子树与 tree2 中点 j 的子树相同所需要的最小代价,如果点 i 的子树和点 j 的子树不同构的话,那么答案设置为无穷大,最后答案就是 dp[ rt1 ][ rt2 ] 了二分图权匹配我用的是KM算法,随机数据的话时间复杂度为 n^3 ,极限数据会被卡到 n^4,不过这

2020-08-11 02:55:06

牛客多校10 - Decrement on the Tree(边权转点权+思维)

题目链接:点击查看题目大意:给出一棵 n 个点组成的树,每条边上都有边权,现在可以进行数次操作,每次操作可以选择一条路径,使得路径上的权值减一,问最少需要进行多少次操作才能使得所有的边权变为 0 ,输出这个操作次数,再给出 m 次询问,每次询问会修改一条边权,每次需要回答修改边权后的答案题目分析:读完题的第一感觉是树形dp然后用树剖+线段树优化,事实证明确实可以写,但我不会写讲一下官方题解的做法吧,非常需要思维,首先需要将边权转换为点权,对于每次操作选取一条路径然后将其路径上的边权减一,对应过来

2020-08-11 01:16:35

牛客多校10 - Tournament(找规律)

题目链接:点击查看题目大意:现在有 n 个队伍参加比赛,任意两个队伍之间都要进行一次比赛,也就是共需要进行 n * ( n - 1 ) / 2 次比赛,对于每个队伍来说,必须要在第一场比赛的时候到达赛场,在最后一场比赛结束后离开赛场,在赛场上呆的时间即为贡献,现在求出一种比赛的安排顺序,使得每个队伍的贡献之和最小题目分析:可以自己手玩一下找找规律,这里以 n = 6 为例,画个图:上图中表示了 n * ( n - 1 ) / 2 场比赛按照升序排列后,也就是按照红色箭头的方向依次比赛,相信肯

2020-08-11 00:03:54

牛客多校9 - Groundhog Chasing Death(质因子分解+思维)

题目链接:点击查看题目大意:给出 a , b , c , d , x , y ,求题目分析:因为涉及到了 gcd 的乘积运算,那么易知不同质因子的贡献是相互独立的,首先我们就可以先将 x 和 y 进行质因子分解,那么对于质因子 p 来说,设 cntx[ p ] 为 p 在 x 中出现的次数,cnty[ p ] 为 p 在 y 中出现的次数,不难看出,需要这两个数同时大于 0 才有贡献,如果其中一者为 0 的话,那么其表示的质因子就是 p^0 = 1 ,gcd 求出来显然也就是 1 了,对答案没有贡献

2020-08-09 01:22:39

牛客多校9 - Groundhog Looking Dowdy(尺取)

题目链接:点击查看题目大意:给出 n 天,每天可以有数件衣服可以选择,但每天只能选择一件衣服穿,每件衣服都有权值,现在需要挑出 m 天的衣服,使得最大值与最小值之差最小题目分析:比赛时为了恰烂分用了群友不小心说漏嘴的假算法过的(我有罪)赛后看了题解才恍然大悟,这不就是一个裸的尺取,将所有的衣服权值排序,然后枚举左端点,尺取右端点就好了,尺取的目标是使得区间内存在着恰好 m 件衣服(因为已经排过序了,显然右端点越小越好),那么答案就是维护一下 node[ r ] - node[ l ] 的最小值了

2020-08-09 01:05:14

HDU - 4417 Super Mario(主席树/线段树+离线)

题目链接:点击查看题目大意:给出由 n 个数的数列,再给出 m 次查询,每次查询需要输出 [ l , r ] 内小于等于 h 的数有多少个题目分析:大晚上睡不着觉随便做做题,发现这个题目原来可以用主席树来做,又发现这个题目去年暑假竟然没写博客,于是补上一发线段树离线的做法就是对数列和询问的高度排序,遍历每个询问,双指针将小于等于当前询问高度的位置都扔到线段树中,记录当前询问的区间内有多少个数即可主席树在线做法,有两种,先说一下网上最常见的,就是遍历每个位置作为下标,对于下标维护可持久化线段树

2020-08-08 03:12:31

HDU多校5 - 6822 Paperfolding(组合数学)

题目链接:点击查看题目大意:给出一张纸,每次对折可以向上,下,左,右四个方向对折,都是等概率的,现在问对折n 次后,在中心画一个十字切开后能切成几份题目分析:模拟一下可以看出水平对折和垂直对折相互独立,因为总的对折次数为 n ,所以设水平对折的次数为 x,那么垂直对折的次数就是 y 次,且满足 x + y = n ,答案就是 ( 2^x + 1 ) * ( 2^y + 1 )这样期望就是,写这篇博客重点是记录一下化简的过程,需要用到的前置知识就是:C(n,m)表示组合数学n个数中选m个的..

2020-08-08 01:55:41

洛谷 - P6178 【模板】Matrix-Tree 定理(矩阵树定理模板题)

题目链接:点击查看题目大意:给出一张 n 个点 m 条边组成的图,可能是有向图也可能是无向图,定义生成树的权值为所有边权的乘积:如果是无向图,求所有生成树的权值之和 如果是有向图,求所有以点 1 为根的外向树的生成树权值之和题目分析:在有向图中是要求以点 1 为根的外向树,所有可以直接删掉第一行和第一列求解,有向图的外向树是需要维护入度,这个别弄混了代码:#include<iostream>#include<cstdio>#include<stri.

2020-08-07 04:06:34

HDU多校6 - 6836 Expectation(矩阵树定理+高斯消元求行列式)

题目链接:点击查看题目大意:给出一张由 n 个点和 m 条边组成的无向图,对于任意一个生成树,其权值为 n - 1 条边的边权进行二进制的 and 运算,现在需要在图中任意选择一个生成树,问期望权值是多少题目分析:需要对题意进行转换,根据期望的公式 E( aX + bY ) = aE( X ) + bE( Y ) ,又因为 and 运算对于每一位都是相互独立的,所以拆位然后单独讨论首先求出来 sum 为原图中有多少个生成树,对于二进制的每一位 i 来说,令所有第 i 位为 1 的边建图,对于这张

2020-08-07 03:55:49

矩阵树 Matrix-Tree 定理实现模板(高斯消元求解行列式)

大佬1博客:https://www.cnblogs.com/zj75211/p/8039443.html大佬2博客:https://www.cnblogs.com/yangsongyi/p/10697176.html三个定理:给出无向图,求这个图的生成树个数 给出有向图和其中的一个点,求以这个点为根的生成外向树个数 给出有向图和其中一个点,求以这个点为根的生成内向树个数对于上述三个定理,首先都是需要构造基尔霍夫Kirchhoff矩阵,构造方法如下:基尔霍夫Kirchhoff矩阵 K=.

2020-08-07 03:29:12

HDU多校6 - 6831 Fragrant numbers(dfs爆搜+打表)

题目链接:点击查看题目大意:给出一个以 " 1145141919 " 无限循环的字符串,现在可以在合适的位置添加 ' + ' , ' * ' 和 ' ( ' , ' ) ' 将其转换为表达式,现在给出一个 n ,问表达出 n 所需要的最短长度是多少题目分析:比赛时想到了可以状压 3 进制来枚举每个位置的符号:空格,+,*,然后利用递归分治暴力求解,写完之后因为复杂度不太好把控,循序渐进跑,发现当字符串长度为 10 的时候就有 4968 个数了,再想跑 n = 11 的时候就发现本地跑不出来了,硬着头

2020-08-07 02:03:49

CodeForces - 892E Envy(可撤销并查集)

题目链接:点击查看题目大意:给出一张由 n 个点 m 条边组成的连通图,有 q 次询问,每次询问给出一个边集,需要判断这些边是否可以同时出现在最小生成树上题目分析:需要用到的一个性质是,对于同一个询问来说,不同权值的选择是相互独立的,但是相同权值之间会相互影响,所以我们可以对每个询问的每条边单独拿出来讨论在进行正常的最小生成树的操作时,对于每次操作的当前边 i ,需要处理所有询问中边权与当前边权相等的边,因为当前处理的这些询问的边权都相等,所以我们按照询问的 id 分组单独讨论,对于每个 id

2020-08-06 03:56:27

牛客多校8 - All-Star Game(线段树分治+并查集按秩合并的撤销操作)

题目链接:点击查看题目大意:有 n 个球员和 m 个球迷,一个球员可能是多个球迷的粉丝,需要选择最少的球员进行比赛,使得所有的球迷都愿意观看(对于每个球迷来说,都有至少一个其喜欢的球员入选比赛)对于球迷与球员之间的关系,如果球迷a 喜欢球员 b ,且球迷 c 喜欢球迷 b ,那么球迷 a 也会喜欢球迷 c 所喜欢的其他球员,对于球迷 c 同理现在有 q 次粉丝关系的修改(增加或删除),对于每次修改后回答询问题目分析:画画图不难看出,球迷与球员连边,设 cnt 为总的连通块的个数,设 cnt.

2020-08-06 02:47:33

HDU多校5 - 6816 Boring Game(模拟)

题目链接:点击查看题目大意:给出 n 张叠在一起的纸,现在将其连续从左向右折叠 k 次,再从上到下标上序号,问展开后的序号是怎么样的题目分析:比赛时一直在找规律,确实是有规律,但是我找不到。。去请教了一下zx学长,zx学长和我说vector暴力模拟即可这里放一张比赛时画的一张纸折叠四阶的图,提供给想找规律的朋友用吧,有点丑:如果模拟的话,借用题解给出的示意图:稍微提一下模拟的实现,上图中红色序号表示的是层的编号,初始时为 1 ~ limit ,limit = 2 * n *

2020-08-05 00:10:38

牛客多校8 - Enigmatic Partition(二阶差分)

题目链接:点击查看题目大意:首先定义 “ n 的拆分 ” 是 n = a[ 1 ] + a[ 2 ] + ... + a[ m ] ,在本题中,n 的拆分需要满足几个条件:a[ i ] <= a[ i + 1 ] <= a[ i ] + 1 ,i ∈ [ 1 , m ] 1 <= a[ i ] <= n , i ∈ [ 1 , m ] a[ m ] = a[ 1 ] + 2设 f( n ) 为满足上述所有条件下,n 的拆分有多少种,现在给出 t 组查询,每组查询给...

2020-08-04 02:22:50

牛客多校8 - Interesting Computer Game(并查集)

题目链接:点击查看题目大意:给出两个数组 a[ i ] 和 b[ i],每次可以从 a[ i ] 和 b[ i ] 中选择一个数,求最后选出的数中,不同的数的个数最多题目分析:比赛时用网络流乱搞水过去了,但是现在都不知道为什么那样建图能过正解是并查集,将每对 a[ i ] 和 b[ i ] 视为一条边后,n 条边连接之后,会出现数个连通块,对于每个连通块我们分两种情况讨论:连通块是个树:有 n 个点和 n - 1 条边,因为每条边最多选一个点,所以 n - 1 条边最多只能选 n -..

2020-08-03 23:48:20

牛客多校7 - A National Pandemic(树链剖分+线段树)

题目链接:点击查看题目大意:给出一棵树,再给出 m 次操作,每次操作分为三种类型,dist( x , y ) 代表点 x 和点 y 之间的距离:1 pos val:将点 pos 位置的值增加 val ,将其余所有点 x的值,增加 val - dist( pos , x ) 2 pos:点 pos 位置的值与 0 取 min 3 pos:查询点 pos 位置的值题目分析:参考博客:https://blog.csdn.net/tianyizhicheng/article/details/1077.

2020-08-03 03:19:14

牛客多校7 - Pointer Analysis(模拟)

题目链接:点击查看题目大意:给出指针与对象之间的赋值关系,求最后每个指针可能指向哪些对象,为了方便理解四种操作,提前在这里说一下,每个对象中是有 26 个变量的,这 26 个变量分别是 “对象指针” ,也是可以指向对象的,那么四种操作解释如下:A = x:A 指针指向对象 x A = B:A 指针指向指针 B 所指向的对象 A.f = B:A 指针所指向的对象的 f 指针指向 B 指针所指向的对象 A = B.f:A 指针指向 B 指针所指向的对象的 f 指针所指向的对象题目分析:看懂题后直

2020-08-03 00:46:47

HDU多校4 - 6813 Last Problem(构造)

题目链接:点击查看题目大意:给出一个无限大的二维平面,需要在平面内进行染色,每次可以选择一个点 ( x , y ) 将其染色为 n 的前提是,相邻四个格子必须分别已经染了 n - 1 , n - 2 , n - 3 , n - 4 四种颜色,染色可以覆盖,构造出一种合理的染色方案,使得可以在平面上出现颜色 n题目分析:参考博客:https://www.cnblogs.com/graytido/p/13406750.html本来看题解觉得好难的一道构造题,搜到了上面大佬的博客,构造题嘛,就别问那.

2020-07-31 02:27:49

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。