sunrise__sunrise

分类

未归档(12) 读书笔记(1) 题解(372)

/ 注册

TA的专栏 306篇文章 2人订阅

147篇文章 1182人学习

牛客算法竞赛入门课

92篇文章 1265人学习

牛客编程巅峰赛S1

6篇文章 795人学习

2020牛客暑期多校训练营

10篇文章 877人学习

7篇文章 1221人学习

2021牛客寒假算法基础集训营

6篇文章 804人学习

2篇文章 695人学习

2021牛客暑期多校训练营

36篇文章 1385人学习

全部文章（共385篇）

道路建设来自专栏

解题思路题目很明确，最少的花费就是最小生成树的权值，我选择prim算法求最小生成树，比较简单，套板子主要理解prim里面的两栖边的意义。prim理解起来就不难了。 //无向图最小生成树 #include <bits/stdc++.h> using namespace std; #de...

2020-07-12

0 508

B-旅行来自专栏

题目意思给出t组数据，每组数据第一行n个节点m条边的无向图给出边权信息，问选其中三个点最短路径之和最大值为多少。解题思路既然要我们最短路可能要用到dijkstra，又因为点可以随意确定，所以只要枚举中间点k，对k求最短路里面最长的两条路之和在return主函数判断最大值即可。如果只有一条路记得...

2020-07-12

1 773

DDoS 来自专栏

题目意思大水题，给出n个顶点的m条边的有向带权图。求从1到n的方法数有多少条？是不是很震惊，边权不同控制发出时间即可同一时间到达，所以边权的信息没什么用。解题思路我写的dfs，回溯法先求道各个入点的路径数，累加就是这个出度点的答案。使用记忆化搜索可以简化计算时间 #pragma GCC tar...

2020-07-12

0 719

挖沟来自专栏

题目意思给出n个点m条边，找出最小生成数的花费解题思路挺简单的最多100000个点，500000条边，可以看到是个稀疏图大概，采用kruskal求最小生成树 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimiz...

2020-07-12

0 682

【每日一题】7月13日Kingdom 来自专栏

题目意思给出n个节点构成的一棵树，根节点权值为0，重儿子权值为父节点的权值，轻儿子为父节点权值+1。问最大的权值之和为多少？注释应该码的比较清楚用个递推算一下。 Code #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC op...

2020-07-10

0 837

【每日一题】7月10日矩阵取数游戏来自专栏

题目描述给出n行m列的矩阵，每次要取出每一行行头或者行位去掉，得到的价值为这个数加上2的第几次取次方。问最大的价值是多少解题思路很容易发现每一行都是同一个处理办法去处理，行与行之间不会相互影响，那么在一行中，可以用上动态规划，要么取队头加上后面的len-1个数，要么取队尾加上len-1个数，这...

2020-07-10

1 623

【每日一题】7月7日题目最短路来自专栏

题目意思给出n个点，最多只会有n+100条边，问给出q次询问，每次询问的两个点最短距离是什么，规模都是1e5 解题思路第一想法：floyd算法，再看下问题规模，1e5，因为floyd基于邻接矩阵存储而且要On^3空间时间都不满足。换个方向，题目给出的数据范围要仔细琢磨，最多的只有n+100条边...

2020-07-10

0 787

【每日一题】7月6日平衡二叉树来自专栏

题目意思题目规定的还是比较正统的BST，那么就左右子树差值不超过给定的第二个数字，高度为第一个数字解题思路直接动态规划是最简单的解法：我们想想假设待求得状态为，代表高度为i的所求节点个数那么就有代表着高度为和得左右子树所求节点个数之和再加上根节点最终就有左子数为满二叉树，右子树为满足题目高度只...

2020-07-09

0 638

【每日一题】7月3日毒瘤xor 来自专栏

题目意思给出的个数，给出次询问，每次询问都会给出两个左右区间，问我们为什么时候异或区间全部数之后答案最大。解题思路异或基本思想，所以统计这个区间中这一位共有几个1，如果大于0的个数那么这一位就取0，否则0个数大于1个数就取1在的这一位。有关区间各个位数统计可以用前缀和预处理，把时间复杂度降为 ...

2020-07-09

0 603

小木棍来自专栏

题目意思乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。解题思路参考秃头大太阳题解深度优先搜索加减枝。首先我们从第一根...

2020-06-09

2 788