shyyhs

分类

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

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3897人学习

AtCoder思维大提升

6篇文章 750人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 840人学习

全部文章（共105篇）

Stars Drawing (Hard Edition) 来自专栏

思路: 这题思路还是比较好的,对于这种十字形状的图形,我们可以设置一个表示这个点上下左右四个方向可以延续的长度是多少.然后转移十分简单,这里就不写了.然后我们贪心的把每个可以取的位子全部取了,都取.最后再前缀记录一下是否被全部覆盖,假如存在没有被覆盖的,那么答案就输出.否则就是所有存在里的答案了. ...

贪心 dp

2021-02-07

4 598

Classy Numbers 来自专栏

思路: 了解过数位的,这题一定是可以写出来的.我们用表示到了第i位无限制的条件下填了个~的方案数.然后对于限制和非限制进行一个讨论即可.就是一个简单的递归,最后答案是.但是有个细节值得注意,了我一会,就是你应该放到返回答案的前面,不然就会出..数组越界.(因为我只开了.) 代码: #include ...

dp

2021-02-07

6 617

Dima and Salad 来自专栏

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

dp

2021-02-03

3 627

Subsequences (hard version) 来自专栏

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

dp

2021-02-03

3 745

Beautiful Array 来自专栏

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

dp

2021-01-31

3 606

贝壳找房2021届校招算法卷3[编程题]世界杯来自专栏

直接dp即可. #include <bits/stdc++.h> using namespace std; const int N=2e3,M=12; double f[N][M];//第i个人在第j轮生出的概率. double F[N][N];//第i名战胜第j名的概率. int ...

dp

2021-01-27

3 779

魔改森林来自专栏

前言: 很久很久以前就看到这个题目.记得这题应该是小乔出的.当时我队友来问我,我跟他讲了一下35分的做法.因为那个时候太菜了,不会容斥原理. 思路: 这题前面1000个数据直接dp即可.后面1e5,直接组合数预处理+容斥原理即可. 代码: #include <bits/stdc++.h>...

容斥原理 dp 组合数学

2021-01-27

3 829

加分二叉树来自专栏

前言: 树的遍历,以前学的时候就很懵逼... 今天就来记录下树的四种遍历. 思路: 这题思路比较简单.区间dp一下即可. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N...

dp

2021-01-24

5 714

比赛来自专栏

emmm水题)... #include <bits/stdc++.h> using namespace std; const int N=13; struct ANS{ double a,b,c; }f[N]; int n=12; double ans[N]; void dfs(...

dp

2021-01-23

3 687

Removal 来自专栏

简单的dp就好了,去重的话,就是记录上一个x所在的位子,把它们全部删除就好了.emmm不难吧 #include <bits/stdc++.h> using namespace std; const int N=1e5+50,M=12; const int mod=1e9+7; typed...

dp

2021-01-22

2 721