好运莲莲_

分类

未归档(1) 题解(36)

/ 注册

全部文章（共68篇）

牛客—— 红球进黑洞（线段树+位运算）

牛客—— 红球进黑洞（线段树+位运算）铭宇巨巨推荐的题！原题链接题意：给定一个序列，两种操作，一是区间求和，二是将区间里的每个数都异或x。思路：一眼就线段树，关键是怎么维护第二个操作。借助最小异或生成树的思想以及异或题的常见套路，我们可以把每个数都进行二进制拆分，用线段树分别维护每一...

2020-08-05

3 678

【牛客】小A的最短路（LCA）

【牛客】小A的最短路（LCA）原题链接题意：给定一棵树，除给定的特殊边边权为0外，其余边权均为1。求两点之间的最短距离。n为3e5 思路：题目是一棵树这个条件有点隐蔽直接进行最短路可能并不可行，考虑树上求两点距离的方法，一般就是LCA。因为存在特殊边，所以节点a和b之间的距离可能有三种...

2020-08-04

0 542

最小异或生成树

最小异或生成树一、前置知识： 1.Trie树：高效的存储和查找字符串集合的数据结构 int son[maxn][26],cnt[maxn],idx; void add(char *str){///将新的字符串插入到字典树里 int p=0,len=strlen(str); ...

2020-07-31

1 1654

牛客——点权和（思维）

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

2020-07-21

1 688

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

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

2020-07-14

1 997

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

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

2020-07-09

0 867

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

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

2020-06-04

1 787

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

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

2020-06-04

0 799

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

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

2020-06-04

0 601

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

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

2020-06-04

0 831