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

前言

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

正文

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特殊处理（出现过的颜色的数量）。

总结

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