威风镰鼬

分类

题解(153)

/ 注册

全部文章（共5篇）

题解 | #Graph Coloring I#

思路无非就两种情况：可二涂色或者存在奇环。那么我们在dfs的过程中留意有无涂色不符的情况，没有发现就直接输出一种涂色方案就行了。现在问题就是找到奇环该怎么输出呢？因为我是个笨比所以一开始写了个tarjan记录SCC，然后去输出第一个奇数并大于1个点的SCC的每一个点编号，结果只过了45.45%（所...

搜索二分图 tarjan

2021-08-26

3 567

题解 | #[NOIP2017]棋盘#

思路没啥思考过程，照着题目跑bfs就过了。大概就是跑的时候记格子的花费和是否用过魔法。记录颜色时+1是因为比较方便区分白色。剪枝直接把同一格子花费大的剪掉就行了。正确性的大概考虑：若经过同一格子两次，用魔法的状态肯定是一样的，并且金币只会递增。（不知所云）代码 #include<bits/...

搜索 NOIP 普及组 bfs 最短路

2021-08-06

2 424

题解 | #[HAOI2016]食物链#

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

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

2021-07-16

1 493

题解 | #xinjun与阴阳师#

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

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

2021-07-06

0 443

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

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

dfs 普及组搜索 NOIP 2星

2021-06-09

8 643