子希

题解

ACM动态规划(4) ACM花里胡哨(1) c++(4) Dijkstra(5) javafx开发(1) java学习(1) oj几何(1) oj贪心(7) oj递归(5) stl练习题(6) 动态规划(2) 单调栈(4) 图论最小生成树(6) 图论-网络流(1) 图论最短路(8) 图论（杂）(5) 字典树(2) 字符串(8) 并查集(14) 思维题(23) 数据结构实现(2) 数据结构实验(2) 数论(1) 暴力(1) 暴力搜索(26) 有趣的数学题(1) 未归档(2) 树状数组(6) 模拟(3) 每日一题(1) 离散数学实验(5) 算法设计与分析题库(15) 线段树(10) 网络比赛(6)

/ 注册

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

2021牛客寒假算法基础集训营3 题解来自专栏

前言：第三场比前面两场难度下降了很多，打起来还算比较舒服，这场理论上来说应该可以开7题了，但是场上只写了5题，有两题是思路但是需要再仔细考虑一下的，没开出来有点可惜。D思路：签到题，范围挺小的，没多想，直接一发暴力。代码： #include<bits/stdc++.h> using na...

2021-02-07

1 519

牛客练习赛74(ABCD) 来自专栏

思路：三个for判断一下就好了。但是判断等比数列的时候不能直接除，因为不一定全部整除。a[2] / a[1] = a[i] / a[i - 1]a[2] * a[i - 1] = a[i] * a[1]变成乘法就行了。 #include<iostream> #include<que...

2020-12-21

2 640

牛客小白月赛30 来自专栏

A 思路：看到两两联通就容易想到最小生成树，然后要黑边多，白边少，那只需要最小生成树改一下排序条件就行了。代码： #include<iostream> #include<vector> #include<algorithm> using namespace std...

暴力

2020-12-06

4 603

牛客IOI周赛20-普及组来自专栏

思路：容易发现这个题要求的就是它的所有因子之和，所以唯一分解定理就可以用一个比较不错的复杂度切掉这题。代码： #include<iostream> #include<vector> #include<algorithm> using namespace std; ...

暴力

2020-12-01

4 590

牛客小白月赛29 来自专栏

A思路：这题我感觉写复杂了。我的思路是贪心：尽可能让所有的战机拿到贡献，并且在当前这辆战机在可以拿的贡献中拿最大的。那么，先对自己的战机和敌人的战机按照防御值升序。然后枚举自己的所有战机，因为敌人的战机已经排序了，我们二分出最后一个小于当前这辆战机的位置，然后在区间[1,index]找最大值。这就是...

2020-11-15

3 760

Propagating tree(奇偶性+dfs序+差分线段树) 来自专栏

题目大意：给你一颗树，你可以在树上进行两种操作1 x val,把val加到x节点上面去，然后-val加到x的第一层儿子节点，然后-(-val)加到第二层儿子节点，。。。等2 x,查询x节点的值。思路：这题看了大佬的思路才做出来的。 https://blog.nowcoder.net/n/d8f8d...

2020-11-13

5 750

选点(dfs序+lis) 来自专栏

思路：这个题意我读了半年样例的3是这样的这里为什么不选4号节点呢，因为“如果在左子树选了一个点，在右子树中选的其他点要比它小。”，也就是左子树的值应该比右子树的值大，并且根节点的值最小，那么我们可以知道根节点<右子树<左子树，那么我们可以根-右-左这样遍历这棵树，然后存他的dfs序，要...

2020-11-11

7 652

Military Problem(DFS序) 来自专栏

题目大意：给你一棵树，然后有q个询问(u,k),问以u为根进行深度优先搜索第k个元素是多少？思路：朴素做法：对于q个询问，每个询问dfs一下求第k个元素即可。---超时正解：我们可以先求出以1为根的所有节点的dfs序，然后记录一下第i个dfs序是谁，然后对于q个询问输出第(dfn[u] + k - ...

2020-11-11

6 700

求和(dfs序+树状数组) 来自专栏

思路：最朴素的做法：维护一个dp[i]:以i为子树的所有结点和，然后对于每个节点更新，朴素的更新它父亲节点的值，但是，如果树是一个长链这个就超时了。正解：先dfs求一个dfs序，这样以i节点的子树都是在一段区间内，所以我们可以维护一下i的子树的数量，那么求以i为根的子树和就是[dfs(i) - 1,...

2020-11-09

5 605

小A与欧拉路(树的直径) 来自专栏

思路：直接想怎么去加边可能比较难想。但是虽然欧拉路不太好求，我们可以从欧拉回路着手，因为这是一棵树，如果要找到一条路，必定是每条边都经过两次(因为是一棵树，不存在任何回路，所以回路必须原路返回，即再经过原来的边一次)，那么欧拉回路的权是。欧拉回路必然满足欧拉路，接下来怎么从欧拉回路找一条最小权的欧...

2020-11-05

4 699