2019.10.22 校内CSP%你赛

我太难了

先说好没有代码T1

题目大意:

给定一些形如|ax+b|的式子,求最小的x使得它们的和最小。

算法一:

大家知道零点分段法 对于这n个式子我们有n+1个取值范围 使得展开这n个式子得到的新式子不同

而对于每一个形成的式子,因为我们有这个x的取值范围,所以我们可以在O(1)的复杂度求出它的最小值。

而我们从最左边的取值范围开始,对于相邻的两个取值范围我们可以用O(1)的复杂度转移,即我们可以用O(n)遍历所有可能形成的n个式子,每个算一下答案即可。

需要注意的是,对于所有a[i]=0,我们需要去除这些点,将对应的b[i]加成一个常量,随后加在ans上。

还需要注意的是,当a<0时,我们通过把a和b分别取绝对值得到a>0的等价的式子,这样便于处理。

算法二:

我们容易知道,|ax+b|是一个下凸函数,而这些|ax+b|的和因为是一个新的|ax+b|,所以依然是一个下凸函数。

所以我们考虑三分或者爬山法,得到x的取值即可。

 

T2

题目大意:

给定一个有向图y,求构造一个有向图使得每条边起点编号比终点小,且1号点到n号点恰好有y条路径。子任务满足n越小越分多。

我们先构造一个64个节点的完全图,这样从1-63号节点到64号节点的贡献依次是2^63,2^62,2^61……2^0.

也就是说我们先连1-64,此时1-64有一种方案,再往图里加入63号点,补全完全图,此时加了一种方案,再加62号点,加了2种方案……以此类推。

我们再新建一个0号节点作为起点,将y快速幂分解,从向分解出的2^k1,2^k2……的k1,k2……对应的完全图中的节点连边即可。

 

T3

题目大意:

给定一段序列,旋转其中一段连续子序列后可以得到一个新的序列,设新的序列中有x个数满足a[i]=i(a[i]是序列中是的数),求不同旋转方案下最大的x。

我们旋转一段子序列时有一个旋转中心,对于每个旋转中心可以对应的旋转子段,设其为[l,r],则对于有效的旋转子段,必有a[l]==r&&a[r]==l,否则它没有[l+1,r-1]更优;

所以我们把所有有效的旋转子段按照旋转中心为关键字排序,同时再给每个旋转中心开一个vector存储其所有有效的子段,其中这些子段按照从短到长排序;

对于一个子段,将其分为三部分:

(1)[1,l);

(2)[l,r];

(3)(r,n]。

(1)(3)两部分因为旋转前后不变,所以我们分别利用前缀、后缀数组存储其答案贡献,查询复杂度为O(1);

(2)部分中,因为每个子段距离上一个更新的子段只多出了一个新的答案贡献(a[l]==r&&a[r]==l),所以该子段(2)部分的答案为2*k,其中k是其在该旋转中心的vector内的位置。

所以只需要扫描所有的[l,r]即可在O(1)的复杂度内检查出其答案。总复杂度O(n)。

 

T4

题目大意:

给定一段序列,设好的子序列是一段连续子序列满足其中所有数互质,求该序列中好的子序列的个数。

我们知道互质的本质是不存在相同的质因子,所以我们先用欧拉筛筛出所有质数;

而我们从头扫描所有[l,r],用book数组记录该序列中出现过的质因子,每次加入一个新的数就判断它是否含有这些质因子,若有,则该序列不好。分解一个数的质因子需要的复杂度是O(logn)。

总复杂度O(nlogn)。

 

我。果然。越来越能口hu了。

相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
公众号推荐
   一个历史类的公众号,欢迎关注
一两拨千金