First AK Div3…

A Repeating Cipher

模拟。

B Array Stabilization

序列删掉一个数后最小极差。

显然要么删除最后一个，要么删除第一个。

C Powers Of Two

构造，将 $n$ 划分成恰好 $k$ 个 $2$ 的幂次数之和。

我的构造方法：将 $n$ 二进制分解，从最高位往最低位拆，看能不能拆成 $k$ 个。

D Circular Dance

$n$ 个人围成一个环，每个人知道自己前面的两个人是谁，要求恢复出原来的环，保证有解。

实际上是已知了图上的 $n$ 条边，建图 dfs，把环跑出来，特判一下绕行的正反方向。

E Almost Regular Bracket Sequence

给定一个括号序列，数一下有多少个位置翻转后可以使括号序列平衡。

一个括号序列平衡的条件是，对于其每个前缀，左括号数量都大于等于右括号数量，并且最终括号总数相同。

那么可以将左括号设置 $+1$，右括号设置为 $-1$，跑一下序列的前后缀和，然后判断这个位置和其前后缀和加起来是否能够等于 $0$ 即可。

但是这里实际上不能保证满足第一个条件，可以再维护一下前后缀到多少满足这个条件，如果当前位置的子串包含这些非法的前后缀，则跳过。

注意一个细节：左括号变成右括号时，前缀和不能为 $0$。（因为要匹配新加入的括号，不过我的写法好像不需要特判？）

F Make It Connected

给定 $n$ 个点的点权，两个点连边的代价是两个点的点权之和，给定 $m$ 条边，这条边可以选择使用点权和或者这条边权，求最小生成树。

不考虑 $m$ 条边，实际上只需要从点权最小的点连向每一个点即可。

考虑 $m$ 条边，和点权最小的点连出的边一起加到最小堆内，跑一遍 Kruskal。

A Find Divisible

在 $[l,r]$ 内找到 $(x,y)$，满足 $x|y$ ，保证有解。

输出 $(l,2l)$。

B Substring Removal

在母串中删除一个子串，使得只剩下一种字母，求方案数。

分类讨论：

1. 所有字母都相同：${n+1}\choose{2}$；
2. 第一个和最后一个字母相同：(第一个字母连续区间长度+1)$\times$ (最后一个字母的连续区间长度+1)；
3. 第一个和最后一个字母不同：第一个字母连续区间长度+最后一个字母连续区间长度+1。

C Polygon for the Angle

在正 $n$ 边形内取三个顶点连成大小为 $ang$ 的角。给定 $ang$，找最少正多少边形。

做出外接圆，圆周角对应的弧跨过 $k$ 条边，$ang=\frac{180k}{n}$，即找到最小的 $k$ 使得 $ang|180k$，并且 $k \le n-2$ （最多只能跨过 $n-2$ 条边）。

枚举一下 $k$ ，注意 $k$ 最大为 $360$。

D Easy Problem

在字符串 $s$ 中删掉一些字符，使得 $s$ 中不含有子序列 “hard”，删掉第 $i$ 个字符的代价是 $a_i$ ，求最小代价。

考虑 $dp[n][4]$，第一维表示使得前 $n$ 个字符不含 ‘h’ 的最小代价，第二维表示使得前 $n$ 个字符不含 ‘ha’ 的最小代价，第三维表示使得前 $n$ 个字符不含 ‘har’ 的最小代价，第四维表示使得前 $n$ 个字符不含 ‘hard’ 的最小代价。

转移方程：

当 $s[i]=$”$hard$”$[j]$ 时，

否则：$dp[i][j]=dp[i-1][j]$。

F Inversion Expectation

$1$ 到 $n$ 的排列中有一些位置未知，求逆序数的期望。

好题！

分析

排列中没有位置已知，那么期望是 $n(n-1)\over 4$ ，因为对排列中的任何一对数他们对逆序数贡献的期望为 $1\over 2$。

排列中所有位置已知，树状数组维护，倒着数一遍。

因此，我们只需要知道已知数和未知数之间的逆序数对期望的贡献。

记未知数有 $m$ 个，对于每个未知位置，他取到任何一个未知数的概率均为 $1 \over m$。

对于一个已知位置，其右边有 $k$ 个未知位置，那么如果这个数和后面任何一个未知位置对期望有贡献，则未知位置需要取一个小于当前数的未知数，每个位置之间是相互独立的，全部加起来即可。

对于这个已知位置的左边，也可以类似地 $O(1)$ 求出贡献。

实现

儿子兄弟表示法，维护一个多叉树。

1. merge(rootX, rootY) : 将两个树根按照堆的要求连边即可，返回新的树根。

2. pop(root) : 将根节点的所有儿子拿出来从左到右一个接一个合并。

复杂度

• 最值查询 $O(1)$

• 删除最值 $O(\log n)$

• 插入 $O(1)$

• 合并 $O(1)$

链接：xlorpaste.cn

A Right-Left Cipher

模拟。

B Div Times Mod

求解关于 $x$ 的不定方程 $(x / k) * (x \% k) = n$ 的最小解。

对 $n​$ 质因数分解即可。

C Connect Three

平面分成了无数 $1 \times 1$ 的方格，给定 3 个方格的坐标，用最少的方格让这三个联通。

枚举两两之间的 6 个最近点，找这个最近点与第三个点的最短路径。

D Minimum Diameter Tree

给一棵树，给树上每条边加一个非负实数范围上的权值，权值总和为 $S$，最小化树的直径。

显然，对于任意一条直径，都会经过两个度数为 1 的顶点，那么必须要给每个这样的叶子上的边平均分配 $S$。

二分了一个小时是怎么回事啊？

A Definite Game

给一个数字 $n \le 1e9$ ，每次操作可以将 $n$ 减去一个不是其因子的数，求最小的结果。

显然，$gcd(n, n-1)=1$，直接输出 $1$ 即可。

注意特判掉 $n=2$。

B Farewell Party

$n$ 个人都戴了一顶某个颜色的帽子，第 $i$ 人的帽子颜色和 $a_i$ 个人不一样，要求恢复出每个人的帽子颜色。

$a_i$ 可以转化为第 $i$ 个人的帽子颜色一共出现 $n-a_i$ 次，对于这种颜色一共有 $n-a_i$ 倍数数量的人与之颜色相同。

有点难写T^T？

C Colorful Bricks

一行有 $n$ 个位置，用 $m$ 种颜色染色，要求恰好有 $k$ 个位置，满足该位置和其左边位置颜色不同，求方案数。

显然，$dp[i][j]$ 表示前 $i$ 个位置恰好有 $j$ 个位置满足条件：

D Maximum Distance

给一个无向带权有重边自环的连通图，给出 $k$ 个关键点，求每个关键点到最远的关键点的距离（距离是路径最大边的长度的最小值）。

考虑对边权排序，按照 $Kruskal$ 的方式加边，维护每个联通块内关键点的个数，当所有关键点加入到一个联通块时，这里的边权就是相同的 $k$ 个答案。

证明，每次合并两个联通块时，联通块内的路径距离一定小于当前的边，当前边加入后，两个联通块内的答案就是一个块内关键点到另外一个块内的关键点的路径，路径距离即为新加入的边。又由于如果一个联通块内没有关键点，实际上答案并不会更新，实际上由于图的联通性，当关键点恰好加入一个块内时，所有点的答案都被更新了，并且向这个联通块内加入点并不会影响答案。

E Missing Numbers

给一个长度为偶数的序列的所有偶数项 $a[2i]$，满足所有前缀和都是完全平方数。

简单推一推可知前缀和 $s[2i-1]$，$s[2i]$ 仅与给出的 $a[2i]$ 有关，即要求解方程 $p^2-q^2=a[2i]$，即 $(p-q)(p+q)=a[2i]$，质因数分解即可。另外由于前缀和要求严格单调，每次贪心地解出最小的 $s[2i]$ 。

给定一个无向简单图 $G=(V,E)$，$|V|, |E| \le 1e5$。

问有多少个无序三元组 $(i,j,k)$，满足三个点两两有连边。

处理方法

1. 将无向图转化成有向图，对于每条边：

   1. 度数大的点连向度数小的点；
   2. 度数相同，编号小的点连向编号大的点。

2. 枚举每个点 $u$：

   1. 将 $u$ 相邻的每一个点打上标记；
   2. 枚举 $u$ 相邻的每一个点 $v$ 的相邻点 $w$，如果 $w$ 被打上了标记，那么 $(u,v,w)$ 即为一个要求的三元环。

滑动窗口求极值。

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}$，所以直接随机即可。