【杂项】2018.4.21题解

前前言:我的博客好不好看2333333333
前言:其实我是想把题目的标题出成“一道二分好题”这种格式的,然后被冷漠义正言辞的拒绝了,说这种暗示不好
1 梅花桩
1.1 解法一
将靠近东岸的所有梅花桩放进队列,对整张图跑一个bfs,即可判断靠近西岸的梅花桩是否能被全部到达。假设全部到达,那么显然,只选择一个点作为起点的话,最后西岸能被到达的点将会连成一片,成一条线段。因为如果中间有断点的话,就存在无法到达的点,与初始条件相违背。这样我们就可以将第二问转化为用尽可能少的线段,令整个区间全部被覆盖。可以贪心,也可以dp。
2 大霸星祭
原题出自sdwc2018 day3 运动会,网上应该找不到。
2.1 解法一
考虑先二分答案。假设当前选择某个运动项目的人数超过了二分值,我们
就必须删掉它,然后再重新计算每个人选择的项目。如果最后所有运动项目都
删光了就说明不合法。删运动项目的时候暴力重算的话每次需要 O(nm) 的复
杂度,我们可以维护一下每个人的前几个喜欢的项目被删掉了,那么删项目的
总复杂度就只需要 O(nm) 了。
时间复杂度 O(nm log m),期望得分 70-100 分。
2.2 解法二
实际上解法二的二分答案是不必要的。我们要想使得答案减小,就必须删
掉当前最多人选择的那个运动项目。一边做一边更新一下答案就可以了。
时间复杂度 O(nm),期望得分 100 分。
3 可爱的阿福
原题出自bzoj(爆炸oj)2763飞行路线
3.1 解法一
考虑没有阿福,答案为朴素的最短路,显然与最短路(这里我们用spfa)有关系。现在阿福可以使某些边边权变为0,那么spfa进行转移的时候有两种方法,一种是将这条边的边权变为0,另一种是不变,那么就可以建出一张分层图。设dis[i][j]表示当前走到第i点,之前使用过j次阿福时的最短路径,看做一个二维的状态,就可以spfa了。
时间复杂度O(玄学),期望得分70分
3.2 解法二
既然数据范围支持spfa,且没有负权边,说明dij也可以做。我们把spfa换成dij即可。
数据范围O(nlogn),期望得分100分
注:此题用spfa可以在bzoj上通过,所以bzoj应该是总时限10s内即可
4 人际关系
原题出自SDOI 2017 Round1 day2 t3 相关分析
现在我们求线性回归方程里带个平均数,令我们难以维护,所以我们试图将这个式子变形

4.1 解法一

发表评论

电子邮件地址不会被公开。 必填项已用*标注