27.6.18 考试小记

发布于 2018-06-27  1.01k 次阅读


今天开始换湖南的题了,前几天一直在考山东的省队集训,感觉之前题目非常毒瘤而且不给部分分,没有写题解的欲望。

T1

给出一棵n个点的树,支持换根、子树权值加、求子树权值和,查询LCA,n<=3e5。

如果不涉及LCA,那么只要求出DFS序之后讨论一下即可。

对于换根求LCA,我们只需要先求u和root的lca还有v和root的lca,如果不同,则u和v一定处于root到原来根的路径上的两棵子树,这时候我们只需要找到较深的那个即可。如果相同,则为u和v的lca,之后这道题就做完了。

另外,如果想用LCT求LCA,只需要access(u),然后在access(v)后的那个splay根就是答案。为什么?模拟一下就好了。但是这样因为常数太大而无法通过。

 

T2

题意略。

首先,对于询问(x,y),答案为\(f(x,y)=min_{i}{sum(y)-sum(i)+(x-y)\,S(i)+i\,S(i)}\)。

之后,发现这是个斜率优化的式子,就是令\(b=f - sum(y)\),\(y=i\,S(i) - sum(i)\),\(x=S(i)\),我们想最大化截距。

把每个决策点看成点(x,y),那么对于两个决策点i和j,如果i<j且s(i)>s(j),那么i一定不优,因此我们需要保证点的横坐标单调递增,且需要形成一个下凸包,维护就好了。

计算答案的时候直接在凸包上三分或者二分就好了。因为精度问题,我选择了差积判断凸包以及三分凸包算答案的方法,这样做不设计斜率的计算,精度也就有了保证,虽然三分会慢一些。

 

T3

另序列B表示序列A的前缀按位或和,计算在A中元素小于2^k且B单调递增的情况下的A的个数。

首先如果我们直接令f[i][j]表示i个数用了j位(考虑空位),那么我们就可以通过NTT优化到O(nklogk),获得59分。

之后,可以改一下DP数组的定义,我们不需要考虑没有使用的空位,只需要维护数位之间的相对标号即可,这样转移的话可以倍增进行,转移的式子就是\(f[a+b][x]=\sum_{i=0}^{x-1}f[a][i]*f[b][x-i]*C_{x}^{i}2^{bi}\)。复杂度O(klognlogk)。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974