阿里嘎多懒羊羊桑_

分类

未归档(1) 题解(36)

/ 注册

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

15天大厂真题带刷Go题解

36篇文章 103人学习

全部文章（共105篇）

牛客——点权和（思维）

牛客——点权和（4个月前好像见过这个题？）思路：考虑每次修改后对答案的贡献，对于一个点来说，考虑这个点会影响到哪些点。考虑只进行一次更新的情况：首先，就是本身，本身的节点值对答案的贡献是度数+1，因为本身的点权会更新，邻接点也会更新；再者，就是他的父节点，父节点对答案的贡献是2，因为在这个过...

2020-07-21

1 683

牛客—— [SCOI2009]生日快乐（dfs）

牛客—— [SCOI2009]生日快乐（dfs）原题链接：https://ac.nowcoder.com/acm/problem/20272题意：给定一个矩形蛋糕，只能平行x轴或y轴切n-1刀得到面积相等的n块蛋糕，求n块蛋糕的长边与短边比值的最大值最小的值。思路：被题意迷惑以为是二分。因...

2020-07-14

1 990

牛客—— 矩阵取数游戏（DP+int128的黑科技）

牛客—— 矩阵取数游戏（DP+int128的黑科技）题意：给定一个n*m的矩阵，矩阵中的每个元素都有自己的值a[i] [j] ，对于每一行，每次都可以取走该行的行首或行尾的元素，其对得分的贡献是被取走的元素值 *2^i，其中i表示第i次取数（从1开始编号）,求取完n行的最大得分。思路： ...

2020-07-09

0 857

牛客—— 漂亮的公园（离散化+LCA+结论）

牛客—— 漂亮的公园（离散化+LCA+结论）原题链接题意：给定一棵树，每个节点都对应有一个颜色，问询问的两个颜色之间的最大距离（可两个颜色可以相同也可以不同）。思路：首先要知道一个结论是对于同一种颜色的直径端点a,b,另一个点c到达这种颜色的最大值，一定是dis(a,c)和dis（b,c...

2020-06-04

1 781

牛客——小A与小B （双向广搜）

牛客——小A与小B （双向广搜）题意：迷宫，小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。思路：双向广搜经典问题将A和B...

2020-06-04

0 816

牛客算法竞赛入门课第四节习题 Part2（并查集扩展）

牛客算法竞赛入门课第四节习题 Part2（并查集扩展） Cube Stacking （带权并查集）题意：有1~n个箱子，把箱子看成栈。进行如下操作：把x放在y的栈顶，计算x所表示的栈里在x下面的箱子数。转化一下就是：连接x和y（有顺序），计算x所在联通块的个数思路：维护两个数组，一个表示x...

2020-06-04

0 602

牛客算法竞赛入门课第四节习题 Part1（并查集基础）

牛客算法竞赛入门课第四节习题 Part1（并查集基础）加边的无向图（思维+并查集）题意：给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达思路：给定的m条边不一定能够联通所有点，只需要计算出联通块个数-1即可。因为3个区域只需要2条边就可以...

2020-06-04

0 831

牛客——算法周周练9（ABDE）

算法周周练9（ABDE） A.符合条件的整数题意：求[2^n,2^m)区间里有多少个整数x满足x%7==1 思路：考虑周期性。可以求从1 ~ 2^n和1 ~ 2^m里符合条件的数，相减即是答案。计算过程会爆int,应该用long long.(我以为也会爆ll，所以用的ull) 代码： ht...

2020-06-04

0 529

牛客—— [CQOI2010]扑克牌（二分）

牛客—— [CQOI2010]扑克牌（二分）原题链接：https://ac.nowcoder.com/acm/problem/19916##题意：给n种牌，每种牌c[i]个，和m张万能牌，问最多能够组成多少套牌（包含所有的种类）思路：考虑二分答案，贪心进行检验。如果最多能够构成x套牌，每种...

2020-06-03

0 774

牛客—— 旅游（树形DP求树的最大独立集）

牛客—— 旅游（树形DP求树的最大独立集）原题链接题意：树的最大独立集定义：对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）；对于任意一个点x，都有选和不选两种情况。我们假设dp[x] [0]表示不选该点的最大值，dp[x] [1] 表示选...

2020-06-02

0 675