Timeline

07:40-08:10 通看一遍题目，A 甚至都看不出来是什么算法，后面都没头绪，先把 A 暴力写了。

08:10-08:30 把 B 暴力写了。

08:30-09:30 把 C 链的部分分写了。

09:30-09:40 怎么 D 连最低档暴力都没法写 /jk，开始罚坐。

Result

20+20+0+0=4020+20+0+0=40

C 部分分写挂了，众生平等场。

Problem

T1

问长度为 nn 的排列中分别形成深度为 1∼n1\sim n 的笛卡尔树的方案数。

1≤n≤9001\leq n\leq 900

Solution

设 fi,jf_{i,j} 为用 nn 个数构造深度为 jj 的笛卡尔树的方案数。

枚举切割点，设左右两边多的一边用了 kk 个点，少的一边用了 i−k−1i-k-1 个点。

fi,j=∑k=i2i−1{2Ci−1k(sumk,j−2fi−k−1,j−1+sumi−k−1,j−1fk,j−1),k≠i−k−1Ci−1k(sumk,j−2fi−k−1,j−1+sumi−k−1,j−1fk,j−1),k=i−k−1f_{i,j}=\sum_{k=\frac{i}{2}}^{i-1} \begin{cases} 2C_{i-1}^{k}(sum_{k,j-2}f_{i-k-1,j-1}+sum_{i-k-1,j-1}f_{k,j-1}),k\neq i-k-1\\ C_{i-1}^{k}(sum_{k,j-2}f_{i-k-1,j-1}+sum_{i-k-1,j-1}f_{k,j-1}),k=i-k-1 \end{cases}

sumi,jsum_{i,j} 为前缀和。

时间复杂度 O(n2log⁡n)\mathcal{O}(n^2\log n)。

T2

从 1∼n1\sim n 中选 1∼k1\sim k 个数，设其乘积为 kk，则要求 ∄i≥2,i2∣k\not \exists i\geq 2, i^2|k，求方案数。

1≤n,k≤5001\leq n,k\leq 500

Solution

随便 DP 即可。

500500 以内的质因子只有 9595 个，而且后 8787 个质因子一定至多出现一次，考虑根号分治，将每个数按照最大质因子分类，grpigrp_i 表示第 ii 类数的集合，将前 88 个质因子分成同一组并对于每个数统计其出现状态 staista_i。

设 fi,j,kf_{i,j,k} 为考虑到后 8787 个质因子的前 ii 个，特殊分组的前 88 个质因子的选择状态为 jj，选了 kk 个数时的方案数。

fi−1,j,k→fi,jOR⁡stagrpip,k,jAND⁡stai=0f_{i-1,j,k}\rightarrow f_{i,j\operatorname{OR} sta_{grp_{i_p},k}},j\operatorname{AND} sta_i=0

时间复杂度 O(29nk)\mathcal{O}(2^9nk)。

T3

给出一棵有 nn 个点的有权树，两个人轮流占领树上的边，已经被对面占领过的边无法经过，多次询问给定两人的起点，最大化先手边权和。

n,q≤105n,q\leq 10^5

Solution

最优策略都为往对方的方向走，求出会在哪个点相遇后分讨占哪个子树。

时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。

T4

有一头牛，每天吃一份草料，第 ii 天会收到 aia_i 份草料，初始时 ai=0a_i=0，给出 qq 个操作将 axa_x 改为 yy，每次操作后输出有草吃的天的编号和。

1≤q≤105,1≤x≤1014,0≤y≤1091\leq q\leq 10^5,1\leq x\leq 10^14,0\leq y\leq 10^9

Solution

考虑在线段树上存这一段区间内的草一共有多少，一共有多少牛吃到了，吃到草的牛的答案是多少，这样就可以算出来还有多少草可以贡献给右边的区间，对于每次修改，正常修改，查询 pushup 的时候二分一下右子树即可。

时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。