sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

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

牛客挑战赛48

A、天使果冻给你个数，有次查询，每次查询询问下标之前的第二大数是什么？首先我们要了解如果只有一次查询，如何在的情况下找到整个序列的第二大数，我们使用两个变量方便是，代表从的最大值和次大值，接下来就去看能不能更新最大值或者最小值。那么这题的题目变成了次查询，我们只需要使用两个数组记录答案，接下来...

2021-03-22

2 758

【每日一题】3月22日[HAOI2012]ROAD 最短路图、拓扑排序来自专栏

Solution 首先看数据范围比较有限，所以我们要计算每条路被做为最短路通过的次数，那么我们就可以分各个点进行处理。我们每次都枚举一个源点做为最短路的起点，求解最短路的话使用这样我们就可以求解出去各个点的最短长度，接下来我们就考虑一个最短路图的概念，我们通过求解得到的数组很显然如果是第一次显然这条...

2021-03-19

4 1163

【每日一题】3月19日 Sand Fortress 二分来自专栏

中文题意给出两个整数，现在要你寻找某个序列，保证数组中相邻两个数差值的绝对值不大于，并且，最终使得。要你求解合法的序列最小的长度是多少。 Solution 我们拿到题目，看到数据范围就只能考虑直接计算或者二分解答两种方法。优先考虑能不能把题目转化为二分再去判断是否成立。对于给定长度，并且的序列，...

2021-03-19

0 884

【每日一题】3月18日树上染色数上背包来自专栏

Solution 题目需要我们求解收益的最大值，那么我们就要拆分每一条边都来考虑一下，因为给出的是一棵树，所以对于每条边他会被计算的次数就是在它下方有几个黑节点乘上它上方有几个黑节点，再加上它下方有几个白节点乘上它上方有几个白节点。这样我们通过枚举根节点它的子树会存在几个黑节点进行动态规划处理。我...

2021-03-18

1 885

【每日一题】2021年3月17日Tower of Hay 单调队列优化dp 来自专栏

中文题意第一行输入代表下面会有个草方块，并且给出的是草方块的宽度，给出的草方块高度都是。现在要你不重不漏的从编号小到编号大堆积草方块，你可以把草方块放在新的一层时，首先要满足它堆上上一层之后，宽度小于等于下一层。问这样的前提中你可以堆积的最高的草方块高度是多少？ Solution 对于这样的问题，...

2021-03-16

1 734

【每日一题】3月16日[HNOI2004]打鼹鼠 dp 来自专栏

Solution 枚举每一个鼹鼠出现的位置，并且从前往后转移。看看你要敲打这个鼹鼠的前提下，还可以继续往前敲打几个鼹鼠。这就是一题简单动态规划的题目了。我们使用代表一定敲击这个鼹鼠最多的得分，那么枚举每一个前面的就可以找到答案，取即可。 #include <bits/stdc++.h>...

2021-03-16

2 655

【每日一题】3月15日[HAOI2012]容易题(EASY) 规律题来自专栏

Solution 第一步，我们简化题目，如果的情况下，我们如何求解个位置每个位置可选中的数，全部数乘积的和是多少。那么这里我是一开始没看出来，所以直接暴力枚举以及的情况，根据乘法分配律还是很容易可以提出式子来的。经过提公因子可以发现，这个就会变成。接下来我们考虑限制，如果一个位置存在限制，说明那...

2021-03-14

2 896

牛客练习赛78

A、CCA的词典因为我们可以随意交换相邻两个数，根据冒泡排序规则，所以我们可以得到由这些字母组成的任意字符串。那么我们就对每行字符串进行字典序排序，再使用计数器计数即可。 #include <bits/stdc++.h> using namespace std; #define js ...

2021-03-13

4 923

【每日一题】3月11日[HAOI2016]字符合并区间dp 来自专栏

题目描述给你长度为的一个字符串，你可以选择长度为的一段合并成一个字符，并且会得到一个价值。现在通过二进制中大小在后面的行中依次给出，问你这个字符串在最优的合并情况下，可以得到的最大价值是多少。 Solution 通过题目发现，所以最终得到的字符串一定是一个的字符串，如果存在大于情况，一定可以再合并...

2021-03-11

0 884

【每日一题】3月10日石子搬运线段树优化dp 来自专栏

Solution 首先我们思考一个简化版的问题，如果不支持修改，我们如何找到搬运完全部石头数的最优解。考虑动态规划解题，对于一堆石子来说，我们可以枚举搬运次数，根据求解的消耗是很容易发现数学规律，我们要让每次搬运的石头尽可能相同的多，就算有不同的不同的两次之间绝对值差值只能小于等于。那么我们考虑代表...

2021-03-10

1 833