滑动窗口求极值。

1
2
3
4
5
6
7
8
9
10
11

int l = 0, r = 0;
for (int i = 1; i < k; i++){
    while (l <= r && a[q[r]] <= a[i]) r--;
    q[++r] = i;
}
for (int i = k; i <= n; i++){
    while (l <= r && a[q[r]] <= a[i]) r--;
    q[++r] = i;
    while (i - q[l] >= k) l++;
    ans[i] = a[q[l]];
}

有长度限制的最大连续子序列和

单调队列维护前缀和的不减单调队列，队首元素为最小值标号，则此时的答案最大。

1
2
3
4
5
6
7
8
9
10
11

for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
int l = 1, r = 0, ansl = 0, ansr = 0; ll ans = -inf;
for (int i = 1; i <= n; i++) {
    while (l <= r && pre[i - 1] < pre[q[r]]) r--;
    q[++r] = i - 1;
    while (i - q[l] > k) l++;
    if (pre[i] - pre[q[l]] > ans){
        ans = pre[i] - pre[q[l]];
        ansl = q[l] + 1; ansr = i;
    }
}

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

struct complex{
    double x, y;
    complex(double a = 0, double b = 0):x(a), y(b){}
    complex operator+(const complex& b){return complex{x + b.x, y + b.y};}
    complex operator-(const complex& b){return complex{x - b.x, y - b.y};}
    complex operator*(const complex& b){return complex{x * b.x - y * b.y, x * b.y + y * b.x};}
}a[maxn], b[maxn]; int rev[maxn];
void fft(int n, complex a[], int op = 1){
    for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1){
        complex t(cos(pi / i), op * sin(pi / i));
        for (int j = 0; j < n; j += (i << 1)){
            complex w(1, 0);
            for (int k = 0; k < i; k++, w = w * t){
                complex x = a[j + k], y = w * a[j + k + i];
                a[j + k] = x + y; a[j + k + i] = x - y;
            }
        }
    } 
    if (op == -1) for (int i = 0; i < n; i++) a[i].x /= n, a[i].y /= n;
}
void mul(int n, complex a[], int m, complex b[], int ans[]){
    int l = 0, lim = 1; while (lim <= n + m) l++, lim <<= 1; 
    for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    fft(lim, a); fft(lim, b);
    for (int i = 0; i <= lim; i++) a[i] = a[i] * b[i];
    fft(lim, a, -1);
    for (int i = 0; i <= n + m; i++) ans[i] = (int)(a[i].x + 0.5);
}

A Coins

B Views Matter

最开始想肯定是维护一个递增的序列，后面的只保留一个即可，但是测一测并不对，然后发现前面维护递增的高度的同时可以在维护每列多用了了多少块，这些多用的块可以放在后面，让一列实际上可以全部清空。

C Multiplicity

拆出每个数的因子然后dp。

时间复杂度： $O(n\sqrt{n})$

F Lost Root

交互题，有一棵 $n$ 个节点的满 $k$ 叉树，标号 $1-n$，现在你需要找到树的根。

每次你可以询问两个点 $a,c$ 之间的路径上是否含有 $b$。

首先想到必须要任取两个点，然后枚举其他点看是否在这条路径上，然后我们注意到任取两个点之后，我们很能够不断调整将这两个点移动到叶子上去。

因此，我们可以在 $O(n)$ 次询问内得到一条叶子结点之间的路径，然后我们又可以知道如果这条路径的长度为 $2*dep-1$，那么他必定经过根节点，然后对于根节点，恰好有 $dep-2$ 个节点在分别在两个叶子结点中间，因此如果我们能获得一条经过叶子结点的路径，就能很快计算出他的根节点。

这里我一开始考虑是不断调整，但是这个复杂度很玄学？

实际上，根据其他人提交的代码我们可以注意到一个事实，在树上任取两个点，这两个点 lca 不是根节点的概率实际上是 $\frac{k-1}{k}$，所以直接随机即可。

题面

给一棵带权有根树，$m$ 次询问两个点之间的路径，要求将一条树边置 $0$ 后，最小化所有询问路径长度的最大值。

分析

显然二分答案。

考虑 $check(x)$ 函数，判断是否能构造出最大值为 $x$，我们可以考虑所有长度大于 $x$ 的路径，记录下来，然后记录下来的重合路径是否有满足条件方案。

关键是如何获取重合的边，考虑在树上差分，在询问点打上 $+1$ 的标记，在 lca 上打上 $-2$ 的标记，然后将标记从叶子推上去即可。

由此我们获取每条边在多少条路径之内，容易判断是否能够构造出来。

这场题怎么这多锅？题面看起来怎么这么麻烦啊，自闭 T^T。

A Minimizing the String

字符串删掉至多一个字符时得到的串中，输出字典序最小的那个。

显然必须删一个，从左往右必须单调不减，找到第一个断开的位置或者删除最后一个位置即可。

B Divisor Subtraction

日常 B 翻车？

一开始觉得找到最小素因子，输出 n / 最小素因子 即可，实际上最小素因子会改变。

在第一次删除最小素因子后，n 变成了一个偶数，这时最小素因子不会再次改变。

$ans=1+\frac{(n-mindivsor)}{2}$。

C Meme Problem

解一元二次方程，这 BC 位置是不是该换一换啊？

D Edge Deletion

给一个无向带权联通图，记 $d_i$ 表示 1 到 i 的最短路长度，将图上的边删到至多 $k$ 条，最大化最短路长度不变的点的数量。

感觉上跑一个 dijkstra，然后把出现次数最多的扣出来？挂了，直接在最短路图上 dfs 输出 k 条边就行了？

E Vasya and a Tree

给一棵树，每个节点初始值为 $0$。

定义 $k-subtree(i)$ 表示 $i$ 的子树中深度不超过 $dep[i] + k$ 的顶点构成的树。

$m$ 次询问将 $d-subtree(v)$ 内所有顶点加上 $x$，输出所有点权。

离线询问，注意到每个顶点的权值只与其祖先有关，所以可以用树状数组，对深度维护的前缀和。

A Extract Numbers

字符串处理。

B Queries about less or equal elements

二分。

C Make Palindrome

特判一下奇数个数字符，对应修改。

D Area of Two Circles’ Intersection

两个圆的面积交。

卡double，毒瘤。

E Lomsat gelral

树上启发式合并。

A Elections

仔细读题。

B Simple Game

给定一个区间 $[1,n]$，两个人分别选定一个数 $a,m$，在范围内随机生成一个数 $x$，距离这个数近的胜利，距离相等对方胜利。

已知区间长度和对方的选择，问自己选择什么获胜概率最大。

计算一下可以得到：$2(a-m)x>(a-m)(a+m)$，对 $a,m$ 大小关系讨论后，发现 $a$ 只会取 $m+1$ 和 $m-1$，分类算一下即可。

注意特判 $n=1$。

C Replacement

给一个字符串，每次将最前面的 “..” 合并为 “.”，询问将某个位置永久修改成另外一个字符时的操作次数。

分类之后进行修改，讨论一下可以 $O(1)$ 更新答案。

D Tree Requests

树上启发式合并。

树上启发式合并是用于解决一类树上无修改的子树信息离线查询问题的一种有力工具。

其时间复杂度由轻重链剖分来保证，轻儿子的大小会小于父亲大小的一半，也就是一条链上最多有 $\log$ 数量级的轻儿子。

树上启发式合并，优化自一个 $O(n^2)$ 的想法，对于一个节点，递归计算这棵子树，更新答案，然后消除其所有子树的贡献，防止儿子之间相互影响。

但是，这样做实际上有些答案的贡献是多删除的，应该保留一些贡献不删除，根据树链剖分选择保留重儿子的信息回溯到父亲节点。

之后我们得到了这样的过程，递归进入一个节点，先计算其轻儿子的答案，最后计算重儿子，之后将重儿子的信息上传到父亲，结合这些信息再递归计算这棵子树的轻儿子位置，得到该节点的答案，最后根据递归参数调整是否要上传子树信息。

题面

给定 $n$ 个人的位置和目标位置坐标的 y 值。

每天所有人朝目标位置上下左右移动一格，优先上下移动。

如果两个或三个人到同一个位置，则两个人都死亡。

目标坐标的 x 在整数范围内取值，要求最多和最少多少人到达目的地。

分析

几个人肯定只能在轴线上撞到，对所有人按 x 轴排序。

分别计算出在轴线上往左走和往右走时，每个位置能够剩余多少人。

搞出前缀和，即表示有多少人人向这个方向走，能够到达当前位置。

答案为当前位置上下的人数加上到左右两格的总人数的最大最小值。

注意要特殊处理 3 人同时相遇的情况，当且仅当轴线上下各有一个距离相同的人，之前也剩余了人没撞到。

银牌！