sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

全部文章 / 题解（共372篇）

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

华尔兹来自专栏

题目意思存在格子规定方向，存在格子随意走动，不存在不能走的格子，只需要输出可以到达终点的某一条路径即可。解题思路 BFS，直接对地图剖解，把方向字母用数字代替）其实也可以不换后面明显一点就是了，后面通过BFS记录当前走的方向，走到终点。再一次方向走图，记录每个点是如何过来的。再输出答案就行了！ ...

2020-06-09

1 666

【每日一题】6月10日失衡天平来自专栏

题目意思给你一个天平，你可以使用无数次，每次只要放上去的物品相差绝对值小于等于m就可以把左右两边物品带走，问最大带走的物品质量是多少？解题思路二维dp，首先看到题目范围100以内的数据，除了二进制枚举三次方也可以满足复杂度。那么一个思维模型，使用代表前i个数中差值在j以内的最大重量。可以发现每...

2020-06-09

4 913