2020-2021:teams:famerwzyyuki:2020_05_16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:2020_05_16 [2020/05/22 16:54] yuki |
2020-2021:teams:famerwzyyuki:2020_05_16 [2020/05/22 17:25] (当前版本) yuki |
||
|---|---|---|---|
| 行 36: | 行 36: | ||
| **题意：**给出一个DAG每个点都可以从0到达。在第i次吃到第j个点的贡献是$\frac{val[j]}{2^{i-1}}$，走到的点可以不吃。求最多吃多少。\\ | **题意：**给出一个DAG每个点都可以从0到达。在第i次吃到第j个点的贡献是$\frac{val[j]}{2^{i-1}}$，走到的点可以不吃。求最多吃多少。\\ | ||
| **题解：**这个题正着想会觉得很迷惑但是如果我们倒过来（从最后一个点往前走），就会变成一个特别显然的dp。\\ | **题解：**这个题正着想会觉得很迷惑但是如果我们倒过来（从最后一个点往前走），就会变成一个特别显然的dp。\\ | ||
| - | f[u]=max(f[v],\frac{f[v]}{2}+val[u]) | + | f[u]=max(f[v],$\frac{f[v]}{2}$+val[u]) |
| + | **F：**一个有点麻烦是计算几何题。 | ||
| + | |||
| + | **G：**\\ | ||
| + | **题意：**有一个红绿灯，你知道绿、黄、红持续时间分别为Tg，Ty，Tr，但是不知道初始绿灯亮的时间T，接下来有n次观察，观察到第t秒的时候红绿灯的颜色，最后一行是一次询问，询问在第t秒颜色为c的概率。\\ | ||
| + | **题解：**对于每次观察，合法的初始时间T的范围是一系列连续的区间，在第一次观察时，选择一段区间保存，之后拿每一段区间与当前的区间集合求交集，最终询问的值即为： 最终区间总长度/进行最后一次合并前的区间总长度。\\ | ||
| + | 考场上的最后一道题，虽然思路正确但是时间太紧实现时出了一些细节问题。 | ||
| + | |||
| + | **H:**水题 | ||
| + | |||
| + | **I:**\\ | ||
| + | **题意：**给一串数字串，求问最多能分成多少个区域使得区域回文。\\ | ||
| + | **题解：**贪心，从当前字母，最少分多少字母才能回文匹配。（本来很简单的题，一开始贪心被否决，再贪心又否决，最后就是贪心） | ||
| **J：** | **J：** | ||
| 最小生成树模板题\\ | 最小生成树模板题\\ | ||
| + | **K：**虽然题意特别绕，但就是一个简单的背包问题 | ||
2020-2021/teams/famerwzyyuki/2020_05_16.1590137674.txt.gz · 最后更改: 2020/05/22 16:54 由 yuki
