联合省选2021共8题口胡题解

联合省选2021

终于有一天 我也成为了退役场外口胡选手

终于有一天 我写的题解也变成了没有排版和LaTeX的模样

纯口胡,不知道对不对,有错请指

#### D1 B卷T1 P7517

统计每个数出现次数,O(aloga)枚举倍数关系计算。

#### D1 B卷T2/A卷T1 P7514

从小到大枚举选到的最小值,a小于该值的必选b,b小于该值的必选a。剩余的可以变成b的次数中,优先考虑a最大且b<a的。
强制选b的一定是a<b的,强制选a的一定是b<a的,所以这部分相当于一个集合,支持删元素,查询第k大的值,k是递减的。可以按a排序然后用双向链表维护。总复杂度nlogn,log来自按b排一次序,常数小

#### D1 A卷T2 P7515

注意了确定a_i0,a_0j这n+m-1个数之后,每个数都能用它们和b表示出来:
a_ij = (-1)^(i+j+1)a_00 + (-1)^(j)a_i0 + (-1)^(i)a_0j + Σ{x=1 to i}Σ{y=1 to j}(-1)^(x+y+i+j)b_x-1y-1
两边同乘(-1)^(i+j)得
(-1)^(i+j)a_ij = -a_00 + (-1)^(i)a_i0 + (-1)^(j)a_0j + Σ{x=1 to i}Σ{y=1 to j}(-1)^(x+y)b_x-1y-1
建立n+m个点,一个代表0,一个代表a_00,n-1个代表a_00-(-1)^(i)a_i0,m-1个代表(-1)^(j)a_0j,则任意一个a_ij(i>=0,j>=0)都能表示成两个点的差加用b表示的常数
建立差分约束,那么是n+m个点,2nm条有向边的图跑最短路,nm同级时复杂度O(n^3)

#### D1 A卷T3/B卷T3 P7516

可以对原题中的算法进行修改:计算f(u,G)时枚举到v时,无论如何都删掉v。由于不与u强连通的v对后面的点与u是否强连通不会有影响,所以这样不影响答案。那么,u对v有贡献等价于只考虑>=v的点,u和v强连通。
记F(x,y)表示只考虑>=x的点(要求y>=x),max_{枚举x到y的路径}{min 这条路径上的边编号},G(x,y)类似,改成枚举y到x的路径。如果没有路径则为0,x=y则为+∞。这个可以用类似最短路的算法O(nm)计算。
那么,在逐渐删边的过程中,y对x有贡献(y>=x)的时间就应该是删掉min(F(x,y),G(x,y))之前。总复杂度O(nm)

#### D2 B卷T1 P7521

一个朴素的骗分暴力:先把所有数排序,从大到小枚举a_k,然后把剩下的都%=a_k再排序,然后双指针a_i递增a_j递减计算答案。直到枚举的a_k<=ans时就可以停止了。
这个暴力的复杂度是正确的,因为枚举最多执行了logA次(A是值域,1e8)。不妨考虑ans'=max_{a_i<a_j<a_k} a_i+a_j-a_k。一定有ans'<=ans。所以枚举的次数不超过大于ans'的不同的a_i的数量。
考虑怎么让>ans'的a_i最多。显然不会有a_i<=ans'。然后设a是已经去重然后按从小到大排序的,那么有:
a_{i-1}+a_{i-2}-a_i <= ans'
移项得
a_i-ans' >= a_{i-1}-ans' + a_{i-2}-ans'
这是个斐波那契级别增长,所以不同的a最多logA个,所以枚举最多执行logA次。具体实现的时候把大于a_k的取模排序再和前面已经有序的归并进去就行。总复杂度O(nlogn+nlogA)

#### D2 A卷T1/B卷T2 P7518

对于一个序列A,定义f(x)为:想要经过A后匹配到P的第x个元素,需要在进入A之前匹配到第f(x)个元素。A为空时f(x)=x
当A追加一个元素q时,由于P的元素是不重复的,设q在P中出现的位置是k,那么转移为f(k)←f(k-1)。若q未出现则不转移。这个转移是O(1)的。
现在考虑树上一条链x->y经过一个点r,r->x的序列为A(包括r),r->y的序列为B(不包括r)。在序列A上维护一个类似f(x)的函数g,只不过是反向匹配(相当于反转整个P)
那么从x走到r能匹配到的P中的位置就是g(1),继续走到y能匹配到的点在B的f上二分一下,即满足f(k)<=g(1)的最大的k。这样就能处理经过一点r的询问。
在树上点分治一下,这样每条链都转化为过中心的,然后用两次dfs第一次求g第二次求f,dfs回溯的时候回滚。总复杂度O(nlogn+qlogm)

#### D2 A卷T3 P7520

如果加了u->v边后x不再支配y,那么新图有一条1->u->v->y不经过x的路径。反证法可得x在lca(u,v)到v不包括两端点的链上
(之前看错题了,如果询问的是支配集发生改变的x的数量,那就是这条链上的点)
这时如果fa(x)不是lca(u,v),因为fa(x)到y一定经过x,所以这条路径也一定不经过fa(x)。那么fa(x)一定也不再支配y
记h为从lca(u,v)到v方向第一个点,那支配y的点集改变等价于h不再支配y。如果h不存在那么x也不存在,答案就是0
而1->u->v那部分路径不会受h影响,所以就是v不回到h可达的点,h子树内的点
dfs一下就好了 总复杂度O(nq)

#### D2 A卷T2/B卷T3 P7519

这里的最终排名就是滚榜公布顺序的逆序,所以最终排名的数量=滚榜公布顺序的数量。
我们按照滚榜公布顺序选点。可以每次选可行且最小的b,这样最终代价小于m就是可行的
记dp(S,c,x)表示选了集合S,总代价为c,上一个选的是x的方案数。这里“总代价”表示:
Σ((这个点的b_i减上一个点的b_i) × 它和它后面还有几个点)
也就是每个点只需要考虑b_i的增量,并把后面的点用的也预先计算出来。
转移是dp(S,c,x)←Σ_{y∈(S-x)} dp(S-x,c-H(x,y)×(n+1-|S|),y)
这里H(x,y)表示x再加多少题能超过y,也就是max(0,a_y-a_x+[y<x])
总复杂度O(2^n mn^2)