shyyhs

题解

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

/ 注册

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

Generating Sets 来自专栏

思路: 我也不知道为什么写这个代码调了一会.思路其实比较简单,就是维护一个,从大的能消则消,不能消则加入答案,这样一次一次的变小,最后集合肯定是一个最小的,因为我是从最大的开始消的.每次操作是次,维护一个,然后时间复杂度应该是具体实现过程见代码. 代码: #include <bits/stdc...

贪心

2021-02-06

2 550

Dima and Salad 来自专栏

思路: 一道很不错的01背包问题,比那些普及-的模板题好太多了. 首先假如你不往背包的方向想,那么我们肯定有个贼简单的想法,表示到了第个,第一个的权值为,第二个的权值为的是否存在,个人觉得内存是没问题的,分析下时间复杂度是的,显然不可取. 那么我们往背包考虑,把每个物品的体积看成,权值为.然后做一次...

dp

2021-02-03

3 635

Subsequences (hard version) 来自专栏

思路: 我们令表示到了第i个位子,长度为j且不同的字符串有多少.很显然,到了第i个位子,长度为j,第j个位子可以选,然后前面选取j-1个长度,或者第j个位子不选,前面选取j的长度.但是这样会有重复的,这时就要容斥一下了,所包含的重复状态一定是.然后第i个选长度为0的方案数都是1.这个题就解决了.当然...

dp

2021-02-03

3 753

Train Hard, Win Easy 来自专栏

题意: 题意有点难懂,这里解释一下.题意:给你n组数,每组都可以和其他组配对,然后你只能选这个组的a类,那个组的b类/这个组的b类,那个组的a类.然后要求总和最小,当然还给了m组不能配对的点,然后输出每组配对所获得的值. 思路: 暴力的思路十分简单,就是一一配对,然后一一比较即可.但是这样做的时间复...

贪心

2021-02-01

1 779

匈牙利算法来自专栏

匈牙利算法是二分图匹配的一个简单算法. 算法的实现方式: 1.遍历左部点,观察是不是存在这个点所连的增广路劲,假如存在ans++.2.找增广路径,判断其是否为自己相连的点,假如是假如这个点还没被连接或是这个点可以让原来连接它的点寻找新的连接点的话,我们就连接它.然后找到即结束. 证明: 采用反证法,...

匈牙利算法

2021-02-01

3 641

Vanya and Scales 来自专栏

思路: 做这种题,第一步就是搞清楚题目要干什么,其实这个题目就是判断一个式子是否成立：我们观察可以发现,每次都只有第一项不一定是的倍数,其他一定是的倍数.那么每次我们都判断下,然后将.然后一直处理到即可,假如中途不成立,那么输出,否则就是.当然还有个值得注意的地方就是你代码应该先检测-1,再检测1...

题解

2021-01-31

4 660

Beautiful Array 来自专栏

思路: 首先我们知道最大连续子序列的和的dp方程是:.这题要我们求使得某一度乘以,然后求.一个显然的暴力是左边求一次最大连续子序列,右边求一次最大连续子序列,然后中间乘以.但是这样的时间复杂度是的,显然不可取.那我们换种思路直接线性dp.令表示到了第几个数,状态是哪个.这里我们设立三个状态::表示以...

dp

2021-01-31

3 617

牛客IOI周赛22-提高组来自专栏

打atcoder去了,这里留坑,会补完的(好像都是会的算法)!

题解

2021-01-30

2 761

Tree Constructer 来自专栏

不会构造... 思路: 我们先将图进行黑白染色,然后将白点的最高位和第id位设置为0,其余为1,保证白点相互之间不连通,然后黑色点将其最高位设置为1,其它和白色相邻的点设置成1.然后因为中间缺了些1,黑色点也是不连通的,然后这样构造就保证了黑色点只与相邻的白色点相连. 代码: #include &l...

构造

2021-01-30

1 816

边的染色来自专栏

前言: 思维不够,看到这种陌生的题目无从下手. 思路: 这题应该做过一次的人会觉得它其实并不难.主要思想:把边权->点权.这样做的好处是,无论你怎么分配点权,在环内的异或值一定为(前提是环内的一定合法.)做题步骤也是围绕这些性质来的.1.首先判断给定的点是否有矛盾,就是你给一个点赋值,它假如是...

dfs 图论

2021-01-28

2 688