Skywang14
Skywang14
全部文章
题解
归档
标签
去牛客网
登录
/
注册
Skywang14的博客
全部文章
/ 题解
(共15篇)
菜肴制作
题目大意 有N道菜,M个限制条件(第I道菜在第J道菜前做)。 求编号小的菜先做的最优解。 算法 拓扑 我们可以发现求字典序最小不一定是最优解。 所以我们可以建一个反图然后求字典序最大(大的往后了小的就往前了) 代码 #include <cstdio> #include <memor...
2020-09-29
0
414
矿工配餐
题目大意有两个矿井及N辆矿车,每个矿工的产煤量与其最后三顿饭的种类数有关。求最大产煤量。 算法DP,f[i][j1][j2][j3][j4][j5]表示处理到第i辆,第一个矿井前两天吃的是j1,j2,第二个矿井前两天吃的是j3,j4。 但是空间只有18MB,所以我们采用滚动数组 代码 #includ...
2020-09-29
0
471
统计单词个数
题目将一个字符串切K刀后求字典中的词语出现的次数 两个词语不能第一个字母在字符串中出现的位置相同 算法DP,f[i][j]表示枚举到第i个,前面切了j刀 调试记录本来用Hash,调了一个下午没过 然后直接用string,然后就过了 代码 #include <iostream> #incl...
2020-09-29
0
373
蚯蚓
题目大意 有一些蚯蚓,每次取最长的切成两段,其余增长q,求每次切掉的蚯蚓的长度以及最后所有蚯蚓的长度 算法 由于先切掉的一定比后切掉的长,所以我们不需要堆,直接队列即可 所以我们可以使用三个队列,一个存原来的,另外两个存切开的 然后每次从三个队列的队首取最大值切开 然后我们用sum存所有蚯蚓的增长量...
2020-09-29
0
358
引水入城
题目大意有一个N*M的城市,可以在第一行建蓄水池,水可以往低处流。求能否覆盖最后一行。 若能覆盖,求最小蓄水池数;若不能,求有几个不能覆盖 算法DFS,求第一行每个点可以覆盖的最下面一行的左右端点,然后做线段覆盖。 代码 #include <cstdio> #include <me...
2020-09-29
0
465
传染病控制
题目大意 一棵树,每次可以删掉一个节点及其子节点,同时从第一层节点开始,每次每层节点会被打上标记,求最小打上标记的个数 算法 由数据范围<=300得知,此题可以爆搜 然后就开始爆搜 #include <cstdio> #include <vector> #define ...
2020-09-29
0
395
过河
题目大意一条长度为L的河,某些地方有石头,每次可以跳S~T的长度。求最少踩到几块石头。 算法DP,f[i]=f[i-j]+flag[i]。但是河的长度有1e9,所以我们要压缩路径。 若两个石子之间的距离大于t(t-1),我们就可以把它改成t(t-1)。 然后DP就好了 代码 #include <...
2020-09-29
0
383
[ICPC-Beijing 2006]狼抓兔子
题意 求最小割 题解 Dinic+当前弧优化 #include <iostream> #include <cstring> #include <queue> using namespace std; int n,m,S,T,cnt=-1,depth[6000001...
网络流
2020-09-29
0
501
洛谷 #1073. 最优贸易
题目大意 有一些城市,每个城市的水晶球的售价不同。在一条从1到n的路径中,我们可以在其中一个城市买入,另一个城市卖出。 求最大收获。 算法 SPFA 先构造一个分层图,层内的边权值为0,表示随便走不需要钱。 然后第一层往第二层可以到达的点连边,权值为售价的相反数,表示买入需要花钱。 第二层往第三层可...
2020-09-29
0
472
最短路计数
从起点出发,BFS遍历,每到一个点,若之前未访问过,就标记,当前到它的最短路径条数即为该路径上他的父节点的条数;否则比较从当前路径走所得到的与起点的距离和最短路径大小,(此时最短路径大小已知,见上文)若相等,它的最短路径条数加上该路径上它父节点路径数 。 起点到某一点最短路路径条数等于起点到它所有父...
最短路
2019-09-06
0
562
首页
上一页
1
2
下一页
末页