威风镰鼬

分类

题解(153)

/ 注册

全部文章（共14篇）

题解 | #[NOIP2017]棋盘#

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

搜索 NOIP 普及组 bfs 最短路

2021-08-06

2 424

题解 | #道路铺设#

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

dfs 普及组贪心 NOIP

2021-07-06

6 379

题解 | #xinjun与阴阳师#

思路这是一个分组背包的模板题，套一下下面的板吧！for 所有的组 ----for k=体力 k>0 -------- for 这个组的操作 ------------ dp递推式代码 #include<bits/stdc++.h> using...

分组背包普及组背包动态规划 dp

2021-06-30

0 512

题解 | #[USACO 2009 Ope S]Cow Line#

思路可以使用vector，也可以使用双向队列（deque）去做，幸好数据能过D操作，不然就要手打了。代码 #include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; deque&l...

deque 普及组队列

2021-06-30

1 437

题解 | #[NOIP2011]铺地毯#

思路感觉是入门题，没用到算法。我们从下往上叠地毯，那么我们从上往下数第一个覆盖这个坐标的地毯的编号就是答案了。如果没有找到就输出-1；代码 #include<bits/stdc++.h> using namespace std; struct X{ int a,b,g,k;...

普及组

2021-06-24

3 630

题解 | #[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

题解 | #[USACO 2009 Oct G]Heat Wave#

思路这道题很开放，spfa能过、Dijkstra能过，普通求法（见代码）也能过。这边供上一个Dijkstra堆优化板子求最短路。坑点：注意优先队列默认是从大到小的，重载运算符要写a.dis>b.dis，别把堆优化做成堆劣化。 Dijkstral代码 #include<bits/stdc...

最短路普及组图论

2021-06-13

1 658

题解 | #字符串逆序#

发个最短题解吧。 #include<bits/stdc++.h> using namespace std; char ch[105]; int main(){ cin>>ch; for(int i=strlen(ch)-1;i>=0;i--) ...

普及组字符串

2021-06-12

2 457

题解 | #挖沟#

思路与<15108道路建设>同解，Kruskal硬过就行了。代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005,maxm=1000005; struct E{ int fro...

普及组最短路 Kruskal 图论

2021-06-12

1 477