about 2 years ago

前言

又被LZZ神到了

A

给定个木棍,长度分别为,至多可以选择一根木棍从某个位置(可以不为整数长度)一分为二变成两根木棍,用这些木棍靠墙围成一个矩形,也就是构成三条边,其中两条边相等。问最大能构成的矩形面积是多少。
,时间限制,有多组数据,最多含有个测试点。

首先有几个显而易见的结论,假设有两条横边,一条竖边,“一定存在一种最优方案满足一条横边或者一条竖边仅由原来不劈开的木棍构成”,“当确定了一条横边或竖边后是一定能构造出满足条件的答案的”(注意这里的横边竖边要给其他边留出足够的空余)。
看到这个数据范围可以自然地想到用meet in the middle解决,根据面积公式我们可以知道,假设木棍总长为,那么横边要尽量靠近,竖边要尽量靠近,因此一个朴素的想法就是枚举横边或竖边长度,处理出左边的所有可能性后,做一个two point找到相对应的最接近的点。
现在还有一个问题是会TLE的,因此我们不能排序,可以考虑一个一个把元素插进去,那么我们当前有之前的序列(有序),把之前的序列每个数加上当前元素(有序),直接归并即可保证复杂度。
aria.cpp

B

计算一种维空间中特定点集构成的体积,点形如,满足

考虑如果没有的限制怎么做,下面给出一个我在cmd markdown写的一个解法,超立方体体积
现在有了的限制,我们可以考虑容斥,如果不满足条件的集合是,那么贡献就是:

这个就可以直接算出的个数然后直接计算了,
kara.cpp

C

交互题,维护一种数据结构,支持从末尾插入删除,要求可持久化,并且支持区间“求和”,这里的“求和”是指定义的一种满足交换结合律的二元运算的求和。要求求和的过程中的调用次数不超过一次。
操作次数,交互库会根据你的程序运行情况生成之后的询问。

考虑怎样才能只用一次询问,因为都是末尾插入,所以我们对每个点维护前缀后缀和即可,考虑怎样才能保证不会被卡,我们选用可持久化,因为键值是随机的,无从卡起,注意插入的时候更新前缀后缀和需要暴力重建整棵子树,因为期望子树大小为因此复杂度是对的。
oath.cpp

← WF2015 Tour 2016-7-11 省队集训 →
 
comments powered by Disqus