shyyhs

题解

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

/ 注册

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

兔子的排列来自专栏

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

DP

2020-08-02

3 884

随风飘来自专栏

是一个组合数学问题,朴素的对于每个都不取k,那就是两个for的事.但是对于取k,我们应该如何分析呢?总的是n,我们拿走k个.在拿走的过程中,我们考虑始终保留两个特殊的,假设说我不存在取的过程,那么这两个产生的贡献必定是一次lcp.但是我们考虑拿走,这个它会多几次呢?其实也挺显然的,C(n-2,k)考...

组合数学

2020-08-01

4 864

网格填数来自专栏

不努力永远都只能是菜鸡,菜鸡..这题咋一眼看会觉得很难,但是呢.首先的矩阵大小是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

杭电1009题解来自专栏

http://acm.hdu.edu.cn/showproblem.php?pid=6759题意:是说给你很多个初始位置和加速度的机器人.然后问你有多少个机器人曾经拿过rk1,并列不算.怎么写呢?首先我们应该知道,假如两条线重合.那么显然是不能作为答案的,我们要标记一下.对于每个机器人来说他们的运动...

单调栈计算几何

2020-07-23

2 2222

磁力块来自专栏

重点是bfs,分块只是优化bfs. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e5+6e4; const ll M=500;//块的大小 struct vv{ l...

分块 BFS

2020-07-22

2 793