ACM ICPC Asia Nha Trang 2016 Programming Contest

Problem A

Solved by Weaver_zhu. 00:19:21 (+1)

Problem B

Solved by Weaver_zhu. 01:23:57 (+)

Problem C

Solved by Kilo_5723. 01:28:50 (+5)

Problem D

Solved by Xiejiadong && Kilo_5723. 04:19:55 (+1)

题意：求长度为 $n$ 的字符串，包含 $s$ 作为子串的所有方案。

题解：当 $n$ 比较小的时候，这个题目是经典题。

我们令 $f[i][j]$ 表示处理到字符串第 $i$ 位，对于 $s$ 中的第 $j$ 位的方案数，转移的时候，可以利用 kmp 的 next 数组优化，

即如果令 $next[i][j]$ 表示当在 $s$ 的第 $i$ 位的时候，下一位出现字母 $j$ 的时候转移到字符串 $s$ 的第 $next[i][j]$ 位，可以得到 dp 方程是 $f[i+1][next[i][j]]+=f[i][j]$ 。

这部分可以用矩阵乘法优化。

题目里面的乘法可能会爆 long long ，可以用 __int128 来处理一下。

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 01:11:16 (+)

题意：有一些信息站，要求向所有的站点发送信息，有一些路需要被激活，激活需要代价，连通后传输信息每字节传输需要代价 $1$ ，求最小化的代价。

题解：先要使得所有的站点到任意一个信息战是联通的，我们可以通过在信息战直接连接代价为 $0$ 的边，将题目转换为求最小生成树。

于是道路激活所需要的最小花费就是最小生成树的代价。

传输数据所需要的代价，显然，是对于每一个没有信息的站点，都要传入 $l$ 字节的信息，所以总的需要传入的信息，可以直接算出来。

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 04:03:59 (+3)

Problem J

Upsolved by Kilo_5723.

Problem K

Solved by Xiejiadong. 00:15:04 (+1)

题意：将 $3n$ 个数分成 $n$ 组，每一组的价值是这一组的中位数，求最大的所有组的价值之和。

题解：显然，最优配对的方式一定是当前最大的两个搭配当前最小的。

也就是价值之和是总的中第 $2$ 大、第 $4$ 大 、 $\cdots$ 、 第 $2n$ 大。

Problem L

Unsolved.