程序员进阶之算法练习（二十四）

前言

已经有三个月未更新算法文章，大厂工作环境是步步紧逼的，使得所有的人越来越忙碌。余下的学习时间，要用于技术预研、知识面开阔、底层原理理解等等，慢慢算法只能占用娱乐时间来耍，这个是非常不稳定的，毕竟还要四排吃鸡、五排王者。
这次更新几个难题，其他题目见算法文集。

正文

1. Vladik and fractions

题目链接

题目大意：
给出一个数字n，求出三个不同的正整数，要求：
2/n = 1/x + 1/y + 1/z。
如果不存在，输出-1。
数据范围：
1<=n<=1e4
x, y and z (1 ≤ x, y, z ≤ 1e9, x ≠ y, x ≠ z, y ≠ z)

Examples
input
3
output
2 7 42
input
7
output
7 8 56

题目解析：
题目属于构造题。
第二个样例给了思路： 2/n = 1/n + 1/(n+1) + 1/n(n+1)
对于这个公式，基本所有的n都能有解；
特别的，n=1的时，存在无解的情况。

2.Chloe and pleasant prizes

题目链接
题目大意：
n个节点的树，1为根；
每个节点有权值a[i]；
现在要求从树中选择两个节点u、v，切断u、v与父亲的边，形成两颗子树，满足条件：
1、两个子树不重叠；
2、两个子树节点的权值和最大；
如果存在，输出权值和；不存在输出-1；

数据范围：
(1<=n<=2e5, -1e9 ≤ a[i] ≤ 1e9)

Examples
input
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8
output
25
input
4
1 -5 1 1
1 2
1 4
2 3
output
2
input
1
-1
output
Impossible

题目解析：
容易知道，只要有一个节点存在两个子树，那么有解；
在有解的情况下，必然存在这样一个点P：两个最优子树T1和T2，都是点P的子树。
那么维护一个最优子树的值：dp[i] 表示i节点为根的子树，子树的权值和；
同时在进行状态转移的时候，维护一个新的数组：top[i] 表示i节点为根的树，其所有子树中，子树权值和的最大值；
那么对于节点u和子节点v，有top[u] = max(dp[u], top[v])；（dp[u]表示以节点u为根的子树权值和，top[v]是u的子树的最大权值和）；
并且对于节点u，如果有多个子节点v，那么只需保留最大的两个top[v]即可。

void dfs(int u, int fat) {
    dp[u] = a[u];
    multiset<lld> childs;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (v != fat) {
            dfs(v, u);
            dp[u] += dp[v];
            tops[u] = max(tops[u], tops[v]);
            childs.insert(tops[v]);
            if (childs.size() == 3) {
                childs.erase(childs.begin());
            }
            if (childs.size() == 2) {
                ans = max(ans, *childs.begin() + *(++childs.begin()));
            }
        }
    }
    tops[u] = max(tops[u], dp[u]);
}

3.Hongcow Builds A Nation

题目链接
题目大意：
给出一个图，n个点，m条边，其中k个点为关键点；
现在在图上加边，要求：
1、关键点之间不能存在路径；
2、不能存在自环、多重边；
问，最多能加多少边。

数据范围：
(1 ≤ n ≤ 1 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n)
先输入n，m，k；
接着是k个数字，表明k个关键点；
接着是m对数字(u,v)，表明u和v之间存在一条边；

Examples
input
4 1 2
1 3
1 2
output
2
input
3 3 1
2
1 2
1 3
2 3
output
0

题目解析：
添加的边不能产生关键点之间的路径，那么可以换一种思路：
对于和关键点已经相连的点，缩成一个关键点；
那么总共会有k个关键点，还有若干个独立点；
sum[i]表示关键点i的点的数量（缩点），假设y=max(sum[i]);
此时能加多的边：
关键点自己内部构建成完全图；
所有的独立点构建成完全图；
独立点集和最大的关键点两两相连；

最后结果，减去所有已有的边。

4.Vladik and cards

题目链接
题目大意：
有若干个卡片排成1行，上面有数字1~8，现在要找到最长的子序列，满足：
1、所有相同数字的卡片数量和c[i]，满足i,j∈[1,8]，|c[i] - c[j]| <= 1;
2、相同的数字卡片必须是连续的；比如说[1,1,2,2]是合法的, [1,2,2,1]是不合法的；
求出最长的子序列。
数据范围：
(1 ≤ n ≤ 1000)

Examples
input
3
1 1 1
output
1
input
8
8 7 6 5 4 3 2 1
output
8

题目解析：
子序列，n又小，状态也少，看起来像动态规划。
问题在于，每个卡片必须选x和x+1张，这个在dp过程中无法控制；
我们只考虑最少的选x张，容易只知道，如果x张可行，那么x-1张可行，具有单调性；
于是，可以用二分来确定x的大小，现在的问题是给出最小长度x，是否能快速求出x的是否有解；
容易知道，每个数字只有x/x+1的状态，可以用0/1来表示，1~8的数字状态压缩后，有255种状态；
dp[i][j] 表示 前i个，状态为j（0101，为1表示对应位数的数字已经选择过）中选择x+1的最大数量；
状态转移：
dp[p[k][t]+1][j|(1<<k)]=max(dp[p[k][t]+1][j|(1<<k)],dp[i][j]); 跳转到新的长度，选择x个
dp[p[k][t]+1][j|(1<<k)]=max(dp[p[k][t]+1][j|(1<<k)],dp[i][j]+1); 选择x+1个
p[k][t] 存的是数字k的第t个的下标；
当len=0特殊处理（出现过的颜色的数量）。

总结

题目的代码在【这里】。
无所事事的时候，尝试解决一道难题，并享受其带来的成就感。