程序员进阶之算法练习(二十四)

前言

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

正文

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

总结

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据派THU

手把手教你由TensorFlow上手PyTorch(附代码)

来源:机器之心 作者:Illarion Khlestov 本文为你解读PyTorch 的易用性。 当我第一次尝试学习 PyTorch 时,没几天就放弃了。和 ...

98140
来自专栏用户2442861的专栏

kaggle-2美国人口普查年收入50K分类

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

38830
来自专栏互联网大杂烩

机器学习面试

线性回归的因变量是连续变量,自变量可以是连续变量,也可以是分类变量。如果只有一个自变量,且只有两类,那这个回归就等同于t检验。如果只有一个自变量,且有三类或更多...

11240
来自专栏程序员宝库

码农也要学算法

当“人工智能”、“AlphaGo”、“无人驾驶”、“智能投顾”等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算机通过提供给人类每天要面临的...

501100
来自专栏来自地球男人的部落格

机器人的运动范围

【原题】 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和...

24060
来自专栏趣学算法

算法之美——算法复杂性

《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

29410
来自专栏Python数据科学

机器学习“特征编码”的经验分享:鱼还是熊掌?

我们拿到的数据通常比较脏乱,可能会带有各种非数字特殊符号,比如中文。下面这个表中显示了我们最原始的数据集。而实际上机器学习模型需要的数据是数字型的,因为只有数字...

42110
来自专栏小鹏的专栏

tf27: Deep Dream—应用到视频

本帖就基于前一贴的代码在视频上应用Deep Dream,应该能生成比较抽的视频。 代码逻辑: 使用ffmpeg从视频中提取帧 为每一帧图像应用Deep ...

21970
来自专栏ATYUN订阅号

数据清理的简要介绍

清理数据应该是数据科学(DS)或者机器学习(ML)工作流程的第一步。如果数据没有清理干净,你将很难在探索中的看到实际重要的部分。一旦你去训练你的ML模型,他们也...

15230
来自专栏AI研习社

问答 | 如何理解 NVIDIA 新 GPU 架构 Turing 的 Tensor Core?

问:如何理解 NVIDIA 新 GPU 架构 Turing 的 Tensor Core?

20740

扫码关注云+社区

领取腾讯云代金券