2025“钉耙编程”中国大学生算法设计暑期联赛（2）题解报告

Link。
今天打的一坨。(；´д｀)ゞ
1001 筛子

【unkown】
什tm分圆多项式，不会，交个打的表。
1002 数上的图

【分讨，*】
略。
1003 图上的数

【期望，**】
在空序列中均匀随机插入 \(k\) 个数，最终每个数在每个位置的概率均为 \(\frac{1}{k}\)。
得到期望为 \(\frac{\sum{p_i} (2^{k}-1)}{k}\)。朴素地，求出每个长度的最长链取最优。
观察式子， \(k\) 值得影响明显。考虑极端情况，我们需要 \(\frac{\frac{1}{10000} (2^{c1}-1)}{c1} > \frac{c2 (2^{c2}-1)}{c2}\)，发现 \(c1 - c2 \ge 30\) 时一定成立。拓补排序，维护非零最长，最长等。有 tangerine 墨迹半天搞不懂。直接维护即可。
1004

1005

1006 半

【偏序，*】
略。
1007 计数

【DP，多项式，**】
对 \(a\) 做后缀最大值后得到递推式 \(F[x] = \sum_{y=a_{i+1}}^x F[i+1][y]\)，这是一个前缀和形式。那 \(F_i(x)\) 就是一个 \(n-i\) 次多项式，二项式系数基上去化简。（多项式不咋会啊）。
1008 井

【期望，*】
略。
1009 苹果树

【树剖，**】
鸟的做法：对度数分治；
std：暴力做不行，但是反过来，在询问的时候观察贡献的来源，如果修改时只修改 \(\operatorname{Fa}\) 和重儿子，那只有链顶需要单独单点查询，\(O(n \log^2n)\)。
1010

1011 10010

【线段树，树状数组倍增+Hash，***】
从右到左，最远能找出多少个 1，使得相邻 1 之间的间隔，构成一个公差为1 的等差数列。
方法1：线段树维护信息：左右0的个数，最左gap大小，最右gap大小，是否完成等差，1 的个数。
Lovely Code  [code]const int N = 1e6 + 10;int n,m,a[N];struct node{        int len, l0, r0;        int cnt1;        int over, st, ed;        node(){}        node(int x){                len = 1, l0 = r0 = x == 0;                cnt1 = x == 1;                over = 0, st = ed = -1;        }        inline int ans(){                if(!cnt1)return 0;                if(cnt1 == 1)return r0;                if(ed == r0 + 1)return st + 2 * (st - ed + 1);                else return r0;        }};inline node operator +(const node &a, const node &b){        node res;        res.len = a.len + b.len;        res.l0 = a.l0 == a.len ? a.len + b.l0 : a.l0;        res.r0 = b.r0 == b.len ? b.len + a.r0 : b.r0;        res.cnt1 = a.cnt1 + b.cnt1;        if(res.cnt1 < 2){ res.over = 0, res.st = res.ed = -1; return res; }        if(b.cnt1 == 0){ res.over = a.over, res.st = a.st, res.ed = a.ed; return res; }        if(a.cnt1 == 0){ res.over = b.over, res.st = b.st, res.ed = b.ed; return res; }        if(b.over){ res.over = 1, res.st = b.st, res.ed = b.ed; return res; }        int mid = a.r0 + b.l0;        if(a.cnt1 == 1 && b.cnt1 == 1){ res.over = 0, res.st = res.ed = mid; return res; }        if(a.cnt1 == 1){                if(mid == b.st + 1)res.over = 0, res.st = mid, res.ed = b.ed;                else res.over = 1, res.st = b.st, res.ed = b.ed;                return res;        }        if(b.cnt1 == 1){                if(a.ed == mid+1)res.over = a.over, res.st = a.st, res.ed = mid;                else res.over = 1, res.st = res.ed = mid;                return res;        }        if(a.ed == mid+1 && mid == b.st+1)res.over = a.over, res.st = a.st, res.ed = b.ed;        else if(mid == b.st + 1)res.over = 1, res.st = mid, res.ed = b.ed;        else res.over = 1, res.st = b.st, res.ed = b.ed;        return res;}struct Seg{        node tr[N