Gsss丶

分类

板子(4) 每日一题(3) 牛客入门班(26) 题解(2)

/ 注册

全部文章（共35篇）

题解 | #吉吉王国#

题目想法这是Rinne Loves Edges的扩展版, 依然是剪掉一些路径从而达到题目要求, 但多了一重限制, 不过不影响核心思路题目要求要剪去所有叶子结点路径(可以剪去叶子结点, 也可以剪去叶子结点的某个根结点), 并且总权值要小于等于m. 而题目要求的结果为求剪去所有叶子结点且总权值小...

2021-05-03

5 599

题解 | #Most Powerful#

题解思路用状态压缩dp 0表示未消失 1表示已经消失题目代码 #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 12...

2021-04-27

0 532

7.3 滑雪与时间胶囊

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

2021-02-26

0 550

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 528

7.1 追债之旅

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

2021-02-25

0 470

图的存储

伪邻接表 struct ty{ int t,next; }edge[Max]; void insertedge(int x,int y) { edge[++m].t=y; edge[m].next=head[x]; head[x]=m; }

2021-02-06

0 351

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

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

2021-02-03

0 616

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 445

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 570

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 486