跃迁引擎启动

发表于 分类于 阅读次数：

给定带权图 $G$，求让 $k$ 个关键点联通的权值最小的子图（$1 \le k \le 10$）。

关键点的个数很少，考虑状压 $dp$。

设 $dp[mask][i]$ 表示关键点的点集 $mask$ 连到顶点 $i$ 最小权值和。

转移的时候有两种情况：

  1. 固定顶点 $i$，合并 $mask$ 的子集 $T$ 和 $T$ 的补集两个 $dp$ 状态，相当于顶点分叉。

  2. 固定点集 $mask$，顶点 $i$ 向周围的点用最短路进行转移，相当于节点向外生长。

时间复杂度：$O(3^k \cdot n+2^k \cdot m \log n)$。

阅读全文 »

发表于 更新于 分类于 阅读次数：

A Got Any Grapes?

B Yet Another Array Partitioning Task

给一个序列，分成恰好 $k$ 个连续段，每个连续段至少有 $m$ 个，每个段的贡献是其前 $m$ 大之和，求所有段贡献之和的最大值。

所有值拖进去排序，取前 $mk$ 大之和就是答案。

构造只需要维护哪些位置是前 $mk$ 大即可。

证明的话，考虑把除了前 $mk$ 大的元素都删除，他们的有无对于答案没有影响。

全场最难。

C Trailing Loves (or L’oeufs?)

求十进制数 $n!$ 在 $b$ 进制下有多少个尾 $0$。

题目等价于求最大的 $x$，使得 $n! =k \cdot b^x$ 成立，等价于对 $b$ 质因数分解后的每一个素因子，$n!$ 中对应素因子的幂次与其幂次之比的最小值。

于是，我们需要计算出 $n!$ 对于一个素因子 $p$ 的幂次。

显然，$1$ 到 $n$ 中 $p$ 的倍数有 $n \over p$ 个，$p^2$ 的倍数有 $n \over p^2$ 个，又由于 $p^2$ 的倍数在前面一次已经计算过一个了，只需要加上 $n \over p^2$ 即可。以此类推，于是有

注意别爆掉 $long long$。

D Flood Fill

给一个序列，一串连续的相同数字视作一个联通块，你需要先选择一个联通块，然后每次将这个联通块颜色变成另外一个以此扩大一开始的联通块，直到所有颜色都相同，求最小操作次数。

考虑 $dp[l][r][0/1]$，表示将 $[l,r]$ 区间全部变成 $l$ 处或者 $r$ 处的颜色所需要的最小操作次数。

因为只有一个起点，每次操作只需要考虑扩大一个位置即可，即 $dp[l][r][0/1]$ 只会从 $dp[l+1][r][0/1]$ 和 $dp[l][r-1][0/1]$ 转移过来。

不妨令第三个维度为 $0$，只有三种情况：

  1. $[l+1,r]$ 全部变成 $l+1$ 处的颜色，如果 $l+1$ 和 $l$ 处颜色不同，那么需要多操作一次；

  2. $[l+1,r]$ 全部变成 $r$ 处颜色，也是类似；

  3. $[l,r-1]$ 全部变成 $l$ 处颜色，如果 $l$ 和 $r$ 处颜色不同，我们需要一次操作将 $[l,r-1]$ 先变成 $r$ 处的颜色，再一次操作变回 $l$ 处的颜色。

第三种情况考虑错了 T^T。

E Arithmetic Progression

交互题，给定长度 $n$，$60$ 次询问，猜一个打乱过位置的等差数列的首项和公差，有两种询问方式：

  1. ? i：询问位置 $i$ 上的数字；

  2. > x：询问是否有大于 $x$ 的数字。

先用 $30$ 次询问二分出最大值，然后随机取 $30$ 个位置，做差后全部 $gcd$ 起来就是公差。

随机别用 rand()， 用 mt19937。

F Please, another Queries on Array?

给一个序列 $a$，其中 $1 \le a_i \le 300$，维护区间乘，询问区间乘的欧拉函数。

线段树裸题（误。

由于小于 $300$ 的素数只有 $62$ 个，欧拉函数算的时候只和乘积后的值以及这个值有哪些素因子有关。

因此只需要用 bitset 维护有哪些素因子，线段树维护乘法即可。

阅读全文 »

发表于 分类于 阅读次数：

题面

给一个无向图，每个顶点本身有一个颜色 $a_i$，现在要给所有顶点分别染色，满足一个联通块内的顶点染的颜色必须相同。

对于每条边，分别询问删除这条边后，最多有多少顶点染的颜色和其本来的颜色相同。

分析

在一个联通块内，如果这条边在一个环内，删除这条边后，原联通块仍然联通。只有对于桥边，删除后会变成两个联通块，才会对答案有影响。

因此，首先需要用边双联通分量缩点，形成一个森林。

对于，森林内的每棵树，我们需要计算删除每一条树边后，子树内和子树外出现次数最多的次数，加上森林内其他树的答案即可。

对于子树内的众数，这是树上启发式合并，同样对于子树外的众数，反过来维护即可。

修改和查询最大值时，复杂度需要 $O(1)$。这里因为修改都是 $+1$ 或 $-1$，因此维护每种出现次数的个数即可。

注意：树上启发式合并时，缩点大小最好设置为对应块的大小。

阅读全文 »

发表于 更新于 分类于 阅读次数：

场外云选手，全程智障。

A Parity

数据范围小，快速幂随便搞一下。

B Tape

有一段长度为 $m$ 的序列，其中一些位置坏掉了，现在可以用最多 $k$ 个线段覆盖这些坏掉的位置，求最小的覆盖线段总长度。

考虑反面，用 $k$ 段覆盖这些位置，等价于将 $n-k$ 个坏掉位置合并，合并后变成 $k$ 个连续段。

差分一下，拖出来排序，取前 $n-k$ 个。

云选手以为要二分，显然有单调性，但是并不能贪心构造。

C Meaningless Operations

求 $f(a)=\max_{0 < b < a} \gcd(a \oplus b, a \text{&} b)$。

考虑 $a$ 的二进制表示，如果里面有 $0$，那么 $b$ 相应位置设为 $1$，这样 $a \text{&} b$ 为 $0$， $a \oplus b$ 为 $2^k-1$，显然最大。

所有只需要考虑 $a=2^k-1$ 的情况，只有 $25$ 种，打个表即可。

D Jongmah

给定一个序列 $a$，$1 \le a_i \le m$，将序列内元素组成一些三元组，满足三元组三个元素为三个连续整数或三个相同整数，求最大能组成多少三元组。

设 $dp[i][j][k]$ 表示考虑到 $i$ 个位置，以第 $i$ 个位置为首组成 $j$ 个连续三元组，第 $i-1$ 个位置为首组成 $k$ 个连续三元组。

然后，观察到组成 $j+3$ 个连续三元组实际上和组成 $j$ 个连续三元组等价，因为可以把横行变成竖列，数目相同，因此只需要考虑 $0 \le j<3, 0 \le k<3$。

转移方程

云选手没注意到这个结论。

E Magic Stones

给定一个序列 $c$，每次操作可以选择除了首尾的一个位置 $i$，执行

判断一下 $c$ 通过这样的操作变成 $t$。

注意到每次这个操作，实际上是交换了左右的差分值，因此只需要判断 $c,t$ 的差分数组排完序是否相同即可。

注意特判首尾位置。

云选手以为要大讨论。

F Nearest Leaf

顶点编号按照 $dfs$ 序给出一棵带边权的有根树，每次在编号 $[l,r]$ 范围内，询问距离顶点 $v$ 最近的叶子的距离。

离线所有询问，$dfs$ 到一棵子树的时候，相当于子树内所有叶子的距离减去这条边的长度，子树外所有叶子的距离加上这条边的长度，线段树维护即可。

裸题没人做是什么情况？

阅读全文 »

发表于 分类于 阅读次数：

A Superhero Transformation

B Average Superhero Gang Power

给一个序列，你有 $m$ 次操作，每次操作可以选择删除一个数或者给某一个数 $+1$，但是一个数最多被加 $k$ 次，要求序列平均值的最大值。

显然，排个序，枚举删除了多少个，剩下的全部都是加到后面即可。

注意，加到哪个数并不重要，总量不超过上限即可。

Hackforces，插了 $5$ 个，最后又 FST 了上千个2333。

C Creative Snap

一排长度为 $2^n$ 的位置，某些位置上有人占领（一个位置可以被多人占领），现在你要毁灭整个区间，你有两种毁灭方式：

  1. 将当前要毁灭的区间分成左右两部分，分别毁灭；
  2. 毁灭当前区间，如果区间内没人占领，费用为 $A$，如果区间内有人占领，费用为 $B \times m \times l$，其中 $A,B$ 为常数，$m$ 为当前区间内的人数，$l$ 为区间长度。

求最小花费。

直接根据题意模拟分治过程即可。

关键是要询问一个区间内的人数，对所有人的位置排序，询问时做两次二分即可。

分治时，注意两个细节：

  1. 区间内没人时，直接返回，无需分治；
  2. 区间长度为 $1$ 时，注意这个位置可能有很多人。

第二点 $wa$ 了一年 T^T。

E Tree

给一棵无根树，现在有 $q$ 次询问，每次询问无根树以 $r$ 为根时，有 $k$ 个关键点，将关键点分为最多 $m$ 块，要求满足每块内没有点对互为这棵有根树上的子孙，求这样的分块方案。

其中 $n, q,\sum k \le 1e5,m\le300$。

首先，考虑根固定为 $1$ 的做法，将关键点按照 $dfs$ 序排序，设 $h[i]$ 表示关键内是 $i$ 的祖先节点的个数，$dp[i][j]$ 表示前 $i$ 个点分成 $j$ 块的方案数，有转移方程

因此，对于每个关键点，我们只需要知道有多少关键点是它的祖先即可，这部分可以搞出 $dfs$ 序，在树状数组上差分即可。

之后，我们考虑这个 $dp$ 的正确性条件，必须满足计算 $i$ 的 $dp$ 状态时，他的祖先必须全部都计算过了。然后，这个条件实际上不需要用 $dfs$ 序来排序，可以考虑用深度或者说祖先的个数来排序，按照这个顺序 $dp$ 即可。

最后，我们考虑换根操作，换根后我们实质上是询问了，某个关键点到根的路径上出现了多少关键点，这个部分用 $LCA​$ 差分即可。

好！

阅读全文 »

发表于 分类于 阅读次数：

题面

给一棵带边权的无根树，维护关键点的增加和删除，询问使得所有关键点联通的最小边集的权值和。

分析

考虑 $dfs$ 遍历一棵树的过程，每一条树边恰好一进一出，走过了两次。

对于树的一个子联通块，遍历的过程也是如此，按照 $dfs$ 序经过了其最小边集中的每条边两次。

于是，我们只需要按照 $dfs$ 序维护一个 $set$，增加和删除时根据前驱和后继更新答案即可。

阅读全文 »

发表于 更新于 分类于 ， 阅读次数：

模板

1
2
3
4
5
6
7
8
9
int ch[maxn][2], val[maxn], tot = 0;
void insert(char* s) {
    int now = 0;
    for (int i = 0; s[i]; i++) {
        if (ch[now][s[i] - '0']) now = ch[now][s[i] - '0'];
        else now = ch[now][s[i] - '0'] = ++tot;
    }
    val[now]++;
}
阅读全文 »

发表于 更新于 分类于 阅读次数：

传送门：Hello 2019 G. Vladislav and a Great Legend

题面

给一棵有根树 $T=(V,E)$，$X$ 是 $V$ 的非空子集，记 $f(X)$ 表示 $T$ 中使得点集 $X$ 联通的最小联通子图中的边数，求

其中，$3 \le |V| \le 10^5,1\le k \le 200$ 。

分析

显然，$k=1$ 直接扫一遍算贡献即可。

考虑 $k>1$ 的情况，由第二类斯特林数展开

前面一部分可以预处理，也就是要求对于 $i (0\le i \le k)​$

设 $E’ \subseteq E$ 且 $|E’|=i$，$E_X$ 为 $f(X)$ 对应联通块的边集，上式可以写成

于是，交换求和顺序

上式含义是枚举边集 $E$ 的大小为 $i$ 的子集 $E’$，计算 $E’$ 出现在多少个点集 $V$ 的非空子集 $X$ 对应的联通块内。

考虑 $dp(i,j)$ 表示以 $i$ 为根的子树内大小为 $j$ 的边集，在子树内对上式的贡献。

设当前计算的根为 $u$，有三种情况：

  1. $u​$ 到子树的边单独构成边集。
  2. $u$ 到子树的边与这棵子树的边集合并。
  3. $u$ 的子树的边集之间合并，子树的边集包含前两种情况。

对于以 $v$ 为根的子树，更新 $v$ 的 $dp$ 状态，情况一就是 $dp(v,1)+2^{size(v)}-1$，而情况二是用 $dp(v,i)$ 更新 $dp(u,i+1)$ 。得到每一个子树 $v$ 的 $dp$ 状态，做一个卷积即可得到根 $u$ 的 $dp$ 状态。

考虑卷积的过程，如果 $v_1$ 和 $v_2$ 合并，没有考虑到 $u$ 的其它子树对其的贡献。

为了解决这个问题，卷积过程中对于 $0$ 次项，设置其为 $2^{size(v)}$，这样没有参与合并的子树贡献就被计算进去了，注意这个部分的贡献不需要 $-1$。因为只要参与了合并，那么只有端点的子树才是必须非空，路径上的点都是可取可不取。

但是，状态转移的过程中，实际上已经对最终答案产生贡献，因为 $dp(i,j)$ 考虑的点集都是以 $i$ 为 $LCA$ 的。

对答案的贡献也有类似的三种情况。

情况一和情况二只需要考虑 $u$ 外的节点是否被取，更新答案即可。

情况三需要考虑合并后的边集对答案贡献，注意到卷积后实际上有一些是没有合并的，我们需要从 $u$ 的 $dp$ 状态中减去前两种情况，这有卷积结果就只剩下参与过合并的边集了。这部分边集同样是考虑 $u$ 外的节点是否选取。

于是，我们就得到了一个 $ans$ 数组表示大小为 $i$ 的边集 $E’$ 的贡献，使用第二类斯特林数即可得到最终答案。

时间复杂度 $O(nk^2)$。

最后参考树形依赖背包的优化原理，上面的卷积过程，实际上与子树大小有关，用类似的方法，我们最终得到时间复杂度为 $O(nk)​$ 的解法。

阅读全文 »

发表于 更新于 分类于 阅读次数：

A Lunar New Year and Cross Counting

模拟一下（第一发写错了符号还能过样例是什么鬼？

B Lunar New Year and Food Ordering

C Lunar New Year and Number Division

把 $n$ 个划分成好多个集合（ $n$ 为偶数），记 $S_j$ 表示第 $j$ 个集合内数的和的平方，要求最小化 $\sum S_j$。

显然，排个序，最大的和最小的组成一组即可（容易证明）。

D Lunar New Year and a Wander

一个人在图上走，每次走到一个未经过的点，将其记录下来，求走遍这个图记录下的字典序最小的序列。

显然，直接贪心地 $dfs$ 是不行的。我们可以用优先队列做一个类似 $Prim$ 的过程，维护一下当前可以走到哪些没有走过的点。

E Lunar New Year and Red Envelopes

给一个长度为 $n$ 的时间轴，有 $k$ 个红包，每个红包可以在 $[s,t]$ 的时间内被领取，领取后获得价值 $w$，领取后直到 $d+1$ 时间才能继续领红包。

一个人贪心的领取红包，能领红包的话，就领价值最大且 $d$ 最大的那个。

你现在有 $m$ 次机会阻止他在某一个时间拿红包，你非常聪明，求这个人能获得的最小价值。

首先，线段树（ $set$ + 扫描线）预处理每个位置拿的红包 $a_i$。

考虑 $dp[i][j]$ 表示在前 $i$ 个时间内，被阻止了 $j$ 次获得的最小价值，转移方程

阅读全文 »

发表于 分类于 阅读次数：

题面

求 $n$ 个点 $m$ 条边的带标号图是某个 $n$ 个点的环的子图的个数。

分析

把几个情况特判掉：

  1. $m>n$：图上已经有环。
  2. $m=n$：图本身就是一个 $n$ 个点的环，答案为 ${n!\over2}$。
  3. $m=0$：答案为 $1​$（底下的公式会挂在这个地方）。

题目等价于求将一个带标号的图分成 $n-m$ 条链的方案数（块内有序，块间无序）。

先给块间加一个有序条件，最后乘上 $n! \over (n-m)!​$ 即可去除掉块间的序，因此可以使用指数生成函数先算出块内块间有序的方案数。

考虑一条链的情况，只有一个点时，方案数为 $1$，有 $n$ 个点时 $(n \ge 2)$，方案数为 $n! \over 2$。因此得到对应的指数生成函数

答案为

阅读全文 »