平凡的小白

分类

未归档(48) 题解(64)

/ 注册

TA的专栏 69篇文章 0人订阅

38篇文章 1224人学习

牛客算法竞赛入门课第一节例题、习题

17篇文章 1119人学习

牛客算法竞赛入门课第三节例题、习题

4篇文章 845人学习

牛客算法竞赛入门课第二节例题、习题

2篇文章 981人学习

牛客算法竞赛入门课第八节例题、习题

3篇文章 969人学习

牛客算法竞赛入门课第六节列题、习题

2篇文章 676人学习

2篇文章 1153人学习

1篇文章 617人学习

全部文章（共10篇）

Tree with Small Distances 来自专栏

题意：个点条边的无向连通图，问最少加多少条边才能使顶点到任意一个点不超过两条边。思路：一种贪心的策略是如果某个点到根结点的边数超过二就把该节点的父结点和根结点连条边检验刚开始的策略：连了这条边后，的边数都变成了因为没有考虑到结点和根结点连边对父结点的影响，导致多连了一条边正确的方案...

DFS

2020-11-19

3 714

华东交通大学2020年ACM“双基”程序设计竞赛来自专栏

C、欧涛的生日聚会思路：画个图就比较清楚要求什么了（补题的时候比较懒，没画完图就在写了，没考虑全）1.当给的关系图没有环时，显然最大可能的服装类就是每个连通块的最长链之和，最小值就是3（如果最大值小于3的话，最小值和最大值都是-1）2.当给的关系图有一个环时，显然最大值就是环的长度，最小值就是最大...

DFS 图论建图思维数学记忆化搜索

2020-11-17

3 1153

牛客算法周周练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