BUPT训练随笔(round 3)

技术文章 1年前 (2020) 完美者
1,990 0

标签:图解   一个人   dong   糖果   打表   https   凸包   blog   一个   

BUPT T3:

目前掌握:ABCDEFGHIJ

A:多边形面积并模板题

思路:赛中完全不会这个算法。赛后看到两个算法。链接1 链接2链接2算法中并没图解,图片放在收藏里了.jpg

B:n个圆的凸包。

思路:队友提供的思路,直接暴力把圆拆点,然后凸包(精度玄学)

C:模拟,略

D:模拟,略

E:还是模拟吧。建边暴力什么的。

思路:队友的写法很好,用map<string,int>建边,这样子能大大减少判断量

F:一棵树,问断开一条边使得尽量多的点对不互相连通,增加一条边使断开一条边减少点对联通最少?

思路:队友写的0.0,看上去是个送分DP

G:一个人一开始有m的食量,每一天有ai个糖果,如果一天吃了糖果,第二天食量会变成2/3,如果休息一天,那么第三天能吃的糖果与第一天相同,如果休息两天,那么第四天食量恢复到m,求最多能吃多少糖果

思路:看上去就是非常快乐的DP,f[i][j]->f[i+1][j+1](j表示当前食量阶级)f[i][j]->f[i+2][j],f[i][j]->f[i+3][0]

H:给定一个网格图求联通块个数

思路:略

I:24点,移动相邻两个点有代价1,使用一次括号有代价1,求最小代价

思路:我们考虑用表达式树来模拟式子!这样子的话,括号的使用就非常的容易了,只要判断父亲比儿子的运算级是否高,如果低就要加括号,然后暴力枚举表达式和表达式的形状,预先打表出排列的转移代价(赛中打的2个表的程序都快比主程序长了)。

J:有一个人要用1-10号机器用3轮。每次用机器需要消耗时间ai,休息bi,同时有10个客人分别对应1-10号机器,循环使用该机器,也有消耗时间和休息时间,还有第一次使用的开始时间,如果这个人和客人同时要用机器,他会让客人先用。求3轮所需要用的总时间。

思路:超级大模拟,思路要清楚的话,很快就能写出来、首先考虑当前时间是否客人在用,如果在用的话把总时间去掉客人用的时间+自己用的+等待时间,同时更新客人下一次使用的开始时间,如果不再用也更新客人下一次使用的开始时间。

BUPT训练随笔(round 3)

标签:图解   一个人   dong   糖果   打表   https   凸包   blog   一个   

原文地址:https://www.cnblogs.com/ghostfly233/p/13649245.html

版权声明:完美者 发表于 2020-09-17 21:27:42。
转载请注明:BUPT训练随笔(round 3) | 完美导航

暂无评论

暂无评论...