平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共8篇）

牛客算法周周练4

闲话A、B看了这位大佬的博客看懂的传送门，B题我想化简，结果出了问题求助这位大佬，然后同学发现我多算了一个，大佬也很快发现了，我自己找了半天，QAQ。戳我传送 [SDOI2016]齿轮题意： n个齿轮m条链，链上两点u、v的转述比为x：y，若不同链条的传动比不相容，则有些齿轮无法转动，就...

思维博弈唯一分解定理并查集 DFS 异或

2020-04-29

2 698

【每日一题】边的染色来自专栏

戳我传送思路： 1.链式向前星存图后，dfs跑一遍判读是否自身矛盾。2.dfs再跑一遍，对每个联通块的元素个数sum-1求和k。3.dfs再跑一遍，对每个涂了颜色的边组成的连通块的元素个数sum-1求和，再用k减去总和，ans=2^k。原理 1.边的值可以看作两个端点的异或值。2.对每个...

DFS 并查集思维

2020-04-28

0 737

牛客小白月赛20

戳我传送 A、最短路思路： Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define dis(a,b,c,d) sqrt((a-...

贪心模拟前缀和暴力枚举并查集离散化树状数组线段树 dfs序二维差分 Dijkstra DFS 思维 BFS 计算几何

2020-04-18

2 1024

【每日一题】Treepath 来自专栏

戳我传送思路：方法一：因为每条边的权值都是一样，所以可以用LCA求得每个结点想对于根结点1的深度，在这里深度就是距离。从偶数层到偶数层和从奇数层到奇数层的路径都是偶数。这里可以用链式向前星存图，然后dfs统计有多少个奇数层a和偶数层b，不必要区分偶数层和奇数层，答案就是 + 。如果1e5...

树状数组 DFS LCA dp 树状dp

2020-04-16

0 599

牛客算法周周练2

前面的碎碎念菜鸡被碾压的一场比赛，就会一题。比赛传送门 A、相反数思路：签到题，直接枚举每一位， (n)能过，我写这一题的时候居然慌了。 Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);ci...

dp 打表贪心 DFS 模拟树状dp 二分

2020-04-15

1 650

牛客练习赛61

前面的碎碎念：菜鸡差点爆0，题目有点不对胃口传送门 A、打怪签到题，差点没签到成功思路：计算勇士砍死一个怪需要的次数，从而得到砍死一个怪需要消耗的血量，于是能砍死的怪物数量就等于自身血量除于需要消耗的血量，如果能整除则答案数减一，特判自身血量为0；复杂度： (1)。 Code： #inclu...

DFS 模拟贪心 dp Dijkstra 字符串哈希二分答案

2020-04-12

1 677

【每日一题】黑白树来自专栏

黑白树思路： 1.当一个点没有被下方已经选了的点覆盖到的时候，我们选择一个它或者它下方的能向上覆盖的最远的点。2.另外，其实我们也并不关心这个点选的哪个，只需要知道往上能覆盖多远就行了，这个值其实可以直接维护到k数组里面，实际操作就是：首先处理的一定是叶子结点y，它的k值就是题目输入的值，它父亲结...

DFS 贪心树状dp

2020-04-08

0 578

【每日一题】Shortest Path 来自专栏

Shortest Path 思路：由题意可知是一个树形结构。若要使两两之间边权最小，尽量不能选重边，也就是说尽可能在节点所在子树里寻找答案。显然与叶子节点相连的边必须选。假设当前结点为x，如果tot[x]&1==1也就是x的子树的结点数(包括x自己)为奇数时，x和父亲的边就一定要选，即答案...

DFS 树状结构

2020-04-08

1 507