这是一篇没什么意义的题解

babyec 2019-11-29 12:28:03 2019-11-29 14:08:57

T1

众所周知,T1是一道签到题。

n的范围友好,时间复杂度O(n)都不用过脑子。

每个整数的范围也友好,直接标明了 long long就可以 ( 毒瘤又白想卡ull被无情拒绝。

要点一: 有减法, 所以结果中可能出现负数,负数计算位数的时候要当心一点。

要点二: 可能会有0,0也是一个一位数。

请做错的同学自行检讨,写一篇不少于1000字的检讨书发至 white.dai@all-dream.com

期望分100

T2

关键点1:贤者模式

关键点2:每个人最多可以战胜n个人(包括了自己)

推论:如果 i 同学能够战胜 j 同学,那么i 同学的三项和> j 同学的最小的两项和+1 一定不是>就可以。例如三项和是50,两项和是49,那么无法战胜。

那么暴力做法显然是一个二重循环,复杂度O(n2)

那么对于100%数据,有两种做法:

  1. 预处理好每个人的最小两项和,a[i]。将其从小到大排序。那么原暴力程序的第二重循环,就可以用二分查找优化。复杂度O(nlogn)

  2. 预处理好每个人的最小两项和,a[i]。预处理好每个人的三项和,b[i]。将a数组和b数组分别从小到大排序。然后对于每个b[i]来说,如果他能战胜前k个人,那么b[i+1]一定也至少能战胜k个人。所以考虑b[i+1]时,只要从b[i]的能战胜的前k个人的后一个,也就是a[k+1]开始判断即可。但是这里有个关键点,b因为是排序后的三项和,所以他的下标i并不是第i个人的意思,所以b数组要个结构体,存一下b[i]对应的原顺序id,每次算完结果后存在ans[b[i].id]。全部算完之后再输出ans。复杂度O(nlogn)。查找这里是O(n),但是需要排序O(nlogn),所以总复杂度是O(nlogn)

期望分100

本题的原意是“能够战胜多少个其他同学”,也就是不包含自己的人数。思考上更难一些。

T3

根据题意分析,显然是一个01背包问题。

挑出不一样的部分:

  1. 本题的背包容积V其实是V/(a*b)。虽然卡可以斜着放,但是显然正着放能放得下,更省空间。
  2. 相同的d会出现消磁的情况,那么也就是对于同一个d,最多只能放一张,那么显然肯定是选最大的。

对其进行处理:

输入n张工资卡,将其进行去重(相同的d只保留最大的w的那张)后还剩k张工资卡。

一样的部分:

裸的01背包,k就是物品数,V/(a*b)是对应的背包空间。每个工资卡的d是物品占用的空间,w是价值。

就算不会处理消磁情况也有50分。

注意数组只能开一维的。

复杂度O(nV)

期望分100

T4

根据题意分析,显然是一个最小生成树。

挑出不一样的部分:

  1. t 次询问
  2. 每天会有 k 条拦路狗

处理:

  1. t的范围<=10,所以不是要预处理节省时间,只是为了防止-1被蒙对
  2. k条拦路狗可能会站在生成树的边上,会造成影响。所以只要在本次生成树的时候,不考虑这k条边就行了

所以显然是一个t次循环,套一个Kruskal,对于每天读进来的k条边进行vis。在算法模板中,处理并查集判断,再加一个vis判断即可。

注意点:

  1. vis每次要清空
  2. 并查集数组p也要初始化
  3. 有-1
  4. 排序之后边的编号就变了,结构体里得有个原编号id吧

复杂度O(t·mlogm)

期望分100

总体期望分400分

AMAZE UI
Hello world!