|Crisp|

分类

题解(8)

/ 注册

全部文章（共8篇）

胖胖的牛牛（dfs）

题意：给你一个迷宫，求出从A到B最少需要多少次90度转弯。思路：这题和普通迷宫的区别在于：普通迷宫求的是最少走的步数，而这题要我们求的是最少的转弯数，这就导致了dfs的方式对于这题是优于bfs的，因为dfs的状态记录更加方便，而bfs还得专门开数组来记录方向和判重。既然确定了解法，就可以开...

胖胖的牛牛

2020-06-30

1 811

小A买彩票题目题解

题目描述： 3元买一张彩票，买一张彩票得到1，2，3，4元的概率相等。问买n次，不亏的概率多少，输出最简分数形式。思路：由题意我们得，这一次买彩票新出现的情况是由上次买彩票的情况分别加上1，2，3，4元得到的。于是我们可以想到使用DP来解决这道题目，状态转移方程是： f[i][j]+=f[i-1...

每日一题小A买彩票

2020-06-30

0 714

Protecting the Flowers(贪心)

题目描述：你是一个牧场主，你放牛吃草后，有出去砍树了。当你回来的时候，你发现你的牛在吃你心爱的小花，为了防止你的小花被吃，你只能把这些可恶的牛赶回他们的窝。。。但是你只有一个人，所以一次只能赶回一只牛，在你赶它们回去的时候，他们还在持续的吃草，而且根据牛个体的不同，赶回他们所需要的时间 t[i]*...

每日一题

2020-05-31

0 722

中位数图（前缀和+思维）

题目描述给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。题解：题目没有给数据范围。。。实测1e5+10能过。由于是 1~n 的一个排列，所以不用担心数字重复的问题。而且，由于是连续子序列，所以满足答案的序列必须是...

中位数图每日一题前缀和

2020-05-29

3 1727

【每日一题】比赛（DP）

题目梗概：搁你面前有十二道题，你们小队有 a[i] 的概率做出来第 i 题，如果做不出来，你分别还有 b[i] 和 c[i] 的概率从你旁边那俩讨论声音贼大的队伍口中听懂怎么做（我怀疑他们是在装逼。。(╬▔皿▔)╯），最后要你输出从一道都不会到全都会做的总共十三种情况的概率。解题思路： ...

每日一题比赛

2020-05-21

0 682

「火」皇家烈焰题解（DP）

题目简述：在一个一维数组中，存放着'0'、'1'、'2'、'*'、'?'这几个字符，数字代表他左右两边存在'*'的个数，'*'的左右两边可以是数字或者'*'，而'?'代表这个地方的东西不确定是什么。题目问的是总共可能的情况有多少种，显而易见，不同的情况是由'?'所在的位置产生的。要我们输出所有的情...

每日一题「火」皇家烈焰

2020-05-09

2 776

子序列（动态规划+数学）

题解：首先，我们把问题拆分。假设这是一道不那么复杂，数据普通的子序列问题。则对于一个数，结果中所有包含它的序列都是从前面的序列中继承过来的。那么到这个数为止，它能产生的新的序列就是1+它之前所有比较结果成立的序列数如果用 f[i] 来记录第i个数产生的新序列，那么转换方程就是1+sum{1,i...

2020-04-30

1 976

华华给月月准备礼物

华华给月月准备的礼物题目：原题链接题解：这是一道纯血的二分搜索题。题目中要求切出k根等长木棍，输出可能的最大长度。于是我们可以使用二分遍历所有可能的木棍长度，判断当前长度是否满足来缩减范围。由于最大的可能长度为1e9，所以时间复杂度并不是很高，加上遍历判断的过程，复杂度只有O(nlog...

2020-04-16

1 839