shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共329篇）

Shortest Path题解来自专栏

这个题还是好心的群友教我的...加群的好处..我不会一点图论知识,子树都不会求.群友给我讲的.其实思路我还是懂=-=就是不会写.下面先给大家看看两幅图:算下两幅图的满足题意边权,第一幅图边权是1+2+3,第二幅图的边权是1+3.我们很容易发现假如子树个数为奇数这条边就需要+,假如为偶数这条边就不用加...

2020-04-10

1 934

Rinne Loves Edges题解来自专栏

一个点连几条边就是度为几?所以度为1就是树最外边的那个点..还有题目并不要考虑删完后的情况.先插个图题目就是要让4 5 6 8 9这些点道不了1.让你删除一些边,使得删除的边权最小.那么怎么做呢..这个题目还是很简单的..设立dp[i]为底面的点都到不了i点的最小代价.那么dp[i]= min(vu...

2020-04-09

2 980

数码题解来自专栏

题目要求区间[l,r]的每个数的因数,然后计算每个因数最高的数是出现多少次？那咋写呢?考虑朴素算法..就是枚举[l,r]每个数的因子再对最高位进行统计..但是这样算法的复杂度就到了大于O(r-l)的级别.具体我也不会算.这样肯定不行,考虑优化.怎么优化呢?首先求[l,r]中区间每个因数最高的数是出现...

2020-04-09

2 954

幸运数字Ⅱ 来自专栏

之前航电有道不要62.这个是幸运数字.那么我们可以进行打表处理.打表用个dfs就好了.(1 <= l <= r <= 1000,000,000)说句实话..可能是数据水了.为啥那种r-l的算法能过..先贴一下r-l算法的代码: #include<bits/stdc++.h&g...

2020-04-08

4 1135

树来自专栏

题目意思是用k个点把一个有n个节点的树染色,然后的地方必须联通,求有多少方案数?下面给大家介绍两种做法..做法1:切边表示染色用的颜色个数,比如我要用3种颜色染色,那么我就只要考虑切2条边,比如切2-4,和3和7这是一种方案,那么,考虑树,一共n个点,一共n-1条边,我可以用k种颜色染色,那么就是切...

2020-04-06

10 1392

区间加来自专栏

出题人的题解还是讲的挺清晰的,emm,为了方便大家理解出题人的题解我解说一下..思路大概就是线性dp+差分,做这个题目的时候没有思路大概就是dp的魅力吧!下面讲讲怎么做?题目要求起点和终点同时不能出现两次,用差分思想就是分配括号，相同的括号不能出现两次在同一个地方出现两次,并且括号一定要合法..什么...

2020-04-05

4 798

三角形题解来自专栏

大水题..先介绍下第一种做法dp观察数据易知..每个数大概就是0~100之间,然后最多100组,所以建立一个dp数组dp[i][j]表示到第i组,价值为j的数量是多少?然后转移就更简单了,思想就是桶,你这个转态肯定是有上一个转态+a[i][j]组成a[i][j]表示第i组位于j的价值..然后注意把第...

2020-04-04

5 916

题解(今晚div2 A~D) 来自专栏

昨晚太困了..就没写了..A题..题意:就是t组数据,然后给你一个n代表你可以操作的数字,然后你可以操作m次,就是可以把ai变成任意数字，结果要你求一段从1开始连续最长的数列..思路:代码很简单..先出现过的地方肯定不要花费了,就是补下没出现过的地方就好了..然后判断下最后能连到哪个数就是答案 #i...

2020-04-04

5 1005

每日题解六(六)--咪咪游戏来自专栏

题目问你是不是mqmqmq这种类型的字符串..方法很简单..输入下这个字符串然后判断下位数..奇数位必须是m,偶数位必须是q..然后还要判断下最后一个字符是不是q..代码如下: #include<bits/stdc++.h> #define ios ios_base::sync_with...

2020-04-03

1 687

每日六题解（五）--珂朵莉与宇宙来自专栏

首先看数据..n是1e5,而ai只有10..且暴力枚举的话它也告诉你了..有(n+1)n/2种,直接暴力肯定超时..那么我们换种思路..1.考虑平方数..因为平方数数据肯定是(0~1000^2)那么枚举的复杂度最多n1000当然不会这么大..而且就算这么大,强大的牛客测评机也是过的去的..2.接下说...

2020-04-03

12 854