Gsss丶

牛客入门班

板子(4) 每日一题(3) 题解(2)

/ 注册

全部文章 / 牛客入门班（共26篇）

7.3 滑雪与时间胶囊

题目链接滑雪与时间胶囊题目思路要先用dfs把从1能到的点筛选出来, 加边的时候不要else if 因为当H[a] == H[b]的时候, 是双向边然后用Kruskal算法求解代码实现 #include <bits/stdc++.h> using namespace std; ...

2021-02-26

0 553

7.2 挖沟

题目链接挖沟代码实现 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, M = 5e5 + 10; struct Edge { int u, v, w; bool oper...

2021-02-25

0 534

7.1 追债之旅

题目链接追债之旅题目思路用 dist[N][K] 来记录第几天到达第几个点, 用dijkstra算法来求值最后遍历 dist[n][i] 求最小值代码实现 #include <bits/stdc++.h> using namespace std; typedef pair&l...

2021-02-25

0 475

6.3 拦截导弹(dilworth定理 dp经典题)

题目链接拦截导弹题目思路第一问dp求解第二问dilworth定理Dilworth定理简单来说：一个序列的最长递增子序列的长度等于这个序列的最长不递增（包含递减和相等）子序列的个数和；相反，一个序列的最长递减子序列的长度等于这个序列的最长不递减（包含递增和相等）子序列的个数和；代...

2021-02-03

0 618

6.2 开心的金明

题目链接开心的金明题目思路 01背包问题，把+v[i]换成了+v[i]*w[i] 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=30; int v[Max],w[Max]; int dp[Max][30...

2021-01-31

0 451

6.1 马拦过河卒

题目链接过河卒题目思路动态规划，把原问题分解成子问题，找动态方程代码实现 #include<bits/stdc++.h> #define int long long using namespace std; int dr[8][2]={{2,1},{2,-1},{-1,2},{1...

2021-01-31

0 572

5.2 maze

题目链接 maze 题目思路优先队列排列时间，bfs找最短时间代码实现 #include<bits/stdc++.h> using namespace std; const int Max=301; int n,m,q,sx,sy,ex,ey; int mp[Max][Max],vi...

2021-01-27

0 488

5.1 小木棍(搜索剪枝)

题目链接小木棍题目思路 dfs的思想需要学习，努力剪枝减小时间复杂度当第一个木棍尝试dfs无法拼成后，直接break当最后一个尝试dfs无法拼成后，直接breaka[i]不行的话，等于a[i]的也不行代码实现 #include<bits/stdc++.h> using namesp...

2021-01-25

0 563

4.4 建筑抢修(利用堆维护的贪心)

题目链接建筑抢修题目思路和会议问题相似，先把结束时间从小到大排序，再用最大堆维护，比较前面维修所需时间与后面所需维修时间，从而实现贪心最大化代码实现 #include<bits/stdc++.h> using namespace std; const int Max=1e6; s...

2021-01-23

0 506

4.3 任意点

题目链接任意点加边的无向图题目思路都是通过用并查集来寻找是否各点是否关联，通过merge处理之后寻找是否fa[i]==i，从而确定有几个未关联的点集代码实现 //任意点 #include<bits/stdc++.h> using namespace std; const i...

2021-01-22

0 349