DUT"华为杯"第八届大工之星编程挑战赛第四周 题解

虽然没参与命题,而且打的很菜,补下题解。

T1

一道帮助大家适应acm英文环境的题目,不断取最大值即可

T2

将所有子弹按照其位移距离排序,然后尽可能先用距离远的就行。注意下除法上取整即可。

T3

这个我们枚举一下,我们由线性代数知识可以知道,三角形面积为叉积/2

T4

如果只有一个奇数,显然需要使用不断异或的方法获得正解。所以我们也联想到使用异或。

al记录异或和。然后ls[i]记录,第i位为1的所有数的异或和。

这样子我们最后遍历ls[i],如果它等与a[i],那么意味这,两个奇数都被异或进去了。如果当前ls[i]不为0,且和a[i]不相等,证明这是一个奇次的数和一堆偶素次的异或和,就是那个奇数次的数,然后我们在用这个数和al异或下,求出另一个数。

 

T5

我么考虑一下使用线段树,因为公式最多200000个 ,所以我们不要被纸面长度10的9次方吓到。线段树开到200000,每个点最初是纸的宽度,维护下节点的max,然后我们每当尝试插入一个公式,就看左右子节点,如果左子节点的max够用,就往左面插,否则往右子节点插入。

T6

这题就是个暴力…….我也不知道为什么就我过了….

我们每次从交换的两个格子,格子朝相反方向不断尝试最大矩形面积。因为不断朝反方向尝试,矩形的长递增,矩形的宽不断取min,从中取一个面积的最大值即可。

T7

是最小直径生成树的裸题,八中有原题…..

而且某种程度上是模板题,而acm比赛众所周知是可以带板子的。然而在周赛中不太好界定什么程度算查板子,什么程度算抄代码,所以出这个题有点狗…..

链接如下

http://oi.self-jqe.win/?p=1019

总结

 

愉快的周赛,最后一题纠结了半天要不要用板子,最后还是没用。与AK失之交臂….然而题目还是很不粗的,出题人是个超级大佬kisado!%%%%%%%

发表评论