二模13day1解题报告

二模13day1解题报告

T1.发射站(station)

N个发射站,每个发射站有高度hi,发射信号强度vi,每个发射站的信号只会被左和右第一个比他高的收到。现在求收到信号最强的发射站。

我用了时间复杂度比较高(nlogn)的算法。首先按h排序(从高到低),作为算法的一个“输入”序列(记为A)(标记原来位置)。

在保存这个序列的基础上,记录rank=1~n,然后按pos排序。排完记为B序列。这时会生成一个关于pos对应h的rank序列,对应B中的每个元素在A中的位置。

用next[i]保存A[i]在B中第一个比它大的pos对应的A中的序号,用pre[i]保存比它小的序号。

然后对A从尾到头解决,因为保证高的在前,所以对一个A[i],对应的pre[i]和next[i]在原序列中的位置就是收到信号的信号塔位置。处理完后更新pre[next[i]]=pre[i];next[pre[i]]=next[i].最后找到最大值即可。【参考了noip2016提高组初赛完善程序1的算法】

T2.物品选取(pack)

给出n个物品和m的体积,做一个多重背包。

甲类物品:每个物品有参数A,B,分配体积不定,价值随体积变化,A*V^2+B*V。

乙类物品:每个物品价值A体积B有C个。

丙类物品:每个物品价值A体积B无限个。

求最大价值。

显然,乙丙很水,下面直接说甲类。

把每个体积的甲分成不同的物品,01背包能过。

That’s all.

T3.正则表达式(regexp)

N个点m条有向带权边(可能有环),规定同一强连通分量内距离均为0,求1到n的最短路。

首先tarjan缩点(这算法还得练啊),然后SPFA,爆栈。

主要是tarjan爆栈了(不然呢???),所以肯定要改成非递归,手打栈(手动泪奔~~o(>_<)o ~~)。不管怎样还是过了,时间也没多少。

上一篇:习题:codevs 1035 火车停留解题报告


下一篇:1. Two Sum【easy】