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 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
