shyyhs

题解

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

/ 注册

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

二分图染色

邓老师题解写的十分的好.首先把完全二分图转化成一个二维的棋盘,因为完全二分图的连边可以把左边看成横坐标和右边看成纵坐标.如此题目就变成了,棋盘中同一横纵坐标不能存在相同颜色,且绿色根本不影响结果,我们不妨假设棋盘原本都是绿色,然后涂上红蓝两色...orz我们不妨设f[n]是一种颜色满足要求的所有涂法...

数学 DP 组合数学

2020-08-21

2 802

兔子的排列来自专栏

题目的意思就是一个序列本来是0,1,2...n-1.然后要你变成p[0],p[1],p[2]...p[n-1],通过交换相邻的两个数每两个相邻的数都可以交换一次,你可以选择交换的顺序.问你有多少种交换顺序?很有意思的一道记忆化搜索题目,emm,大佬教我做的...具体怎么做呢?就是一个典型的分治,加记...

DP

2020-08-02

3 884

网格填数来自专栏

不努力永远都只能是菜鸡,菜鸡..这题咋一眼看会觉得很难,但是呢.首先的矩阵大小是hw的,但是他只要求nm的任意加起来为奇数.当然题目似乎没讲只能填1~9的数..你会发现假如第一个nm的矩阵确认,那么符合条件的填法也是确认了..因为为了维护奇数,我平移一个数,移进来的数和移出去的数奇偶性一定是一样的,...

DP

2020-08-01

7 728

网格游戏

期望dp哎,虽然以前也写过,但是不系统..虽然看到还是很迷茫的.题目描述: 有一个游戏平板上面有n×m个格子，一开始每个格子都是关闭的，每个格子里面都有一个标记已知每种标记恰好出现两次，也就是一共有n*m/2种标记规定一次移动为依次(one by one不是同时)打开一对格子查看里面的标记，如果...

DP

2020-08-01

12 1174

牛牛的回文串来自专栏

牛客dp虽然对于入门学dp的...很不开心,但是感觉题目还是很好的...这题大概利用了Floyd和最长公共子序列的思想吧..题目描述: 牛牛喜欢回文串，牛妹给了牛牛一个字符串S，牛牛想把S变成回文串牛牛可以做如下三种操作 1：在任意位置增加一个字符 2：删除一个字符 3：改变一个字符每种操作都有...

DP

2020-07-31

10 828

和与或来自专栏

..对于刚学dp的萌新十分不友好..题目描述:你一个数组R,包含N个元素,求有多少满足条件的序列A使得0≤A[i]≤R[i].A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模.首先知道等式成立的条件是对于每一位分配的A[i],不可能...

DP

2020-07-30

12 888

codeforces 来自专栏

这题貌似写过= - =...我们考虑取每个的价值,假设说我们取了第i个,其他个没有取.取第i个,其他不选,对于在取i的时间内是一种什么情况呢?假设我们有两种选择,第一个时间是ti.另外一个时间是tj.第一个每分钟减少w[i],另外一个减少w[j].第一个完成的价值是val[i],另外一个完成的价值是...

DP

2020-07-29

3 893

DP

https://blog.nowcoder.net/n/82f28d6e3af24c7f97dab5f9d5e8afd6

dp

2020-07-29

6 573

换教室来自专栏

简要的证明一下floyd算法的正确性.想必大家都做过旅行商问题(状态压缩).floyd就是暴力枚举了每个点的对整幅图的贡献.然后就是讲下这个题,这个题是个概率dp,因为要求最小.首先得明确dp所表示的含义.我们令f[i][j][0/1]表示我们学到了第i门课,我们用了j次机会,第j次的时候用了/没用...

floyd dp

2020-07-13

3 622

守卫者的挑战来自专栏

今天更完这题结束吧,明天多校爆零ε唉.(这题和前面3个题目.然后打多校的时候,每天更一篇就好了...4天结束数论.这题是个概率题,很简单的maybe.题目意思啥的都不解释了.直接上代码: #include <bits/stdc++.h> using namespace std; cons...

dp

2020-07-11

2 737