威风镰鼬

题解

/ 注册

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

题解 | #太鼓达人#

题意其实就是求字典序最小的长度为2^k的01串使得子串不重复出现。思路第一个答案很直观可以得到2^k，然后第二个答案爆搜就行了。优先选择0，如果前面以及出现过相应子串就回退填1. 这是一道欧拉回路的题，如何理解呢？就是每个状态都可以连0或者1，都有两个入边和出边。那么必然存在一条路径可以使得走...

dfs 欧拉回路

2022-04-18

0 519

题解 | #[HAOI2016]食物链#

思路记忆化搜索、拓扑排序的题目。对于一个已经走过一次的点，后面能走的情况都是确定的，只要能把情况数记录下来，后面的结点就不需要再走一遍了，就可以很大程度上节省时间。代码 #include <bits/stdc++.h> using namespace std; const int...

搜索记忆化图论 dfs 拓扑排序

2021-07-16

1 493

题解 | #道路铺设#

思路贪心可过，首先我们要把第一个坑填上，如果下一坑比较浅，那么我们肯定会顺便把它也填上，如果比较深的话，需要填的深度就减去了前面坑的深度。代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,a[...

dfs 普及组贪心 NOIP

2021-07-06

6 379

题解 | #xinjun与阴阳师#

思路对于每个选择的点，其周围的点都是不能选的，我们从根结点出发深搜+DP，就能求出答案了。可以参考没有上司的舞会，这道题就是退化版。代码 #include<bits/stdc++.h> using namespace std; const int maxn=500005; str...

dfs 树形dp 搜索动态规划 2星

2021-07-06

0 443

题解 | #[NOIP2015]信息传递#

思路这道题的大意就是要我们求最小环的长度。我们知道这是一个n个顶点n条边的图，所以每一块最多只有一个环，并保证图中有环。我们可以从任意一个点开始搜索，如果碰到了原来记录过的顶点，那么就记录答案并跳出。如果下一个点已经被记录过了并且不是同一次搜索，那么直接跳出就好了。这个是一个O(n)的做法。代码...

dfs 普及组图论环

2021-06-22

1 523

题解 | #没有上司的舞会#

思路树形dp基础题型，dp[i][0]表示i不选中时的最大快乐指数，dp[i][1]表示i选中时的最大快乐指数，所以我们只要先找到一个根节点，然后向下dfs，dp[root][0]和dp[root][1]的较大值就是答案。从下往上状态转移，我们先搜索到叶子节点，然后求出父节点的dp[i][0]和d...

dfs 树普及组图论树形dp

2021-06-16

1 430

题解 | #小G有一个大树#

思路题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的...

dfs 树图论

2021-06-16

1 703

题解 | #树上子链#

思路对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。代码 #include<bits/stdc++.h> ...

dfs 树图论树形dp

2021-06-16

1 481

题解 | #[NOIP2001]数的划分#

[NOIP2001]数的划分思路 dfs的简单题，数据很弱，注意每次减的数都比上一次当要大，分的方式就不会重复了；方案数+1的条件是n减k个数后刚好等于零（也可以理解为k个非递减的数之和等于n）代码 #include<bits/stdc++.h> using namespace st...

dfs 普及组搜索 NOIP 2星

2021-06-09

8 643