2020-2021:teams:famerwzyyuki:2020_05_16
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:2020_05_16 [2020/05/22 15:48] yuki |
2020-2021:teams:famerwzyyuki:2020_05_16 [2020/05/22 17:25] (当前版本) yuki |
||
|---|---|---|---|
| 行 28: | 行 28: | ||
| **题解：**贪心，n个点共可以连n*(n-1)/2条边，越短的绳子肯定要对应距离越小的边，找到最短的m条边从小到大与m根绳子比较。\\ | **题解：**贪心，n个点共可以连n*(n-1)/2条边，越短的绳子肯定要对应距离越小的边，找到最短的m条边从小到大与m根绳子比较。\\ | ||
| 找到最短的m条边的方法：二分第m短的边长度L，将点排序后枚举起点就能算出从这个点向后可以链多少长度小于L的边。最后求出L后用同样的方法求出这m条边的具体长度。 | 找到最短的m条边的方法：二分第m短的边长度L，将点排序后枚举起点就能算出从这个点向后可以链多少长度小于L的边。最后求出L后用同样的方法求出这m条边的具体长度。 | ||
| - | |||
| **D：** | **D：** | ||
| 给定N个数，求出使两边数的和差最小的位置，带单点修改\\ | 给定N个数，求出使两边数的和差最小的位置，带单点修改\\ | ||
| 树状数组维护前缀和，二分查找使两边差最接近0的两个位置，比一比就好了\\ | 树状数组维护前缀和，二分查找使两边差最接近0的两个位置，比一比就好了\\ | ||
| + | |||
| + | **E：**\\ | ||
| + | **题意：**给出一个DAG每个点都可以从0到达。在第i次吃到第j个点的贡献是$\frac{val[j]}{2^{i-1}}$，走到的点可以不吃。求最多吃多少。\\ | ||
| + | **题解：**这个题正着想会觉得很迷惑但是如果我们倒过来（从最后一个点往前走），就会变成一个特别显然的dp。\\ | ||
| + | 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.1590133708.txt.gz · 最后更改: 2020/05/22 15:48 由 yuki
