fanfansann - 个人主页动态 - 牛客网

发布(176) 刷题

2020-05-01 12:12

C++

P4779 【模板】单源最短路径（标准版）（dijkstra模板）

dijkstra模板 输入： 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 输出： 0 2 4 3 堆优化版本 #include<bits/stdc++.h> using namespace std; #define debug(x) cout<<"# "<<x<<" "<<endl; typedef long long ll; const ll mod=2147483647000; const ll N=500007; struct Edg...

0 点赞评论收藏

转发

2020-05-01 12:12

已编辑

C++

最短路合集（Dijkstra、SPFA、Floyd以及路径还原模板）

目录 一.Dijkstra算法（不能处理存在负权的清况） 1.堆（优先队列）优化版本：（慢，占用内存还大） 2.普通线段树优化版本（一般块） 2.大佬的特殊线段树优化版本：（超快的） 二.SPFA 算法（可以处理存在负权的清况） 三.Floyd算法（可以处理存在负权的清况） 1.P2888 [USACO07NOV]牛栏Cow Hurdles（Floyd算法） 四.路径还原 （1）模板 （2）模板题 一.Dijkstra算法（不能处理存在负权的清况） 4 6 1 1 2 2 2 3 2 2...

0 点赞评论收藏

转发

2020-05-01 12:11

C++

P2888 [USACO07NOV]牛栏Cow Hurdles（Floyd算法）

P2888 [USACO07NOV]牛栏Cow Hurdles 行 1…T: 行 i 为一个整数，表示任务i路径上最高的栏的高度的最小值。如果无法到达，输出 -1。 5 6 3 1 2 12 3 2 8 1 3 5 2 5 3 3 4 4 2 4 8 3 4 1 2 5 1 4 8 -1 注意：memset(dis,0x7f,sizeof dis);dis[0][0]=0x7f7f7f7f 但是dis必须是int型的 #include<bits/stdc++.h> using namespace std; #define debug(x) cout<<&q...

0 点赞评论收藏

转发

2020-05-01 12:11

C++

ACM竞赛技巧总结

目录 1.更快（最快）的读入优化 2.memset用来赋最大值（非0，-1） 3.错排公式 4. 圆周率 5.自然对数 6.浮点数比较时最好控制精度 7.判断是不是2的幂 8.lowbit函数 ： 9.Runtime Error 10.除vector和string以外的STL都不支持*（it+1）的访问形式 11.位运算的妙用 12.运用fill函数给任意容器赋任意值 （1）给二维数组赋值 （2）其他容器 13.哭了， ...

0 点赞评论收藏

转发

2020-05-01 12:11

C++

CF231C To Add or Not to Add（思维，模拟）

CF231C To Add or Not to Add 先排序，每次更新一个i就以a[i]为最终的答案来看当前区间里的这些数能否通过不大于k次的+1（排过序了就不会有-1了）操作实现区间内所有的值都为a[i]，一旦大于k次就把最前面的pop掉（类似滑动窗口） #include<bits/stdc++.h> using namespace std; typedef long long ll; ifstream in("input.txt"); ofstream out("output.txt"); #define debug(x) cerr...

0 点赞评论收藏

转发

2020-05-01 12:10

已编辑

C++

使用MarkDown编辑器做出有意思的柱状图（完整代码）

这是生成的效果 <menclose notation="box"> <mstyle displaystyle="false" scriptlevel="0"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle mathcolor="white"> ...

0 点赞评论收藏

转发

2020-05-01 12:10

已编辑

C++

USACO07DEC道路建设Building Roads（prim算法+堆优化与Kruskal+路径压缩对比）

目录 p r i m prim prim算法 ...

0 点赞评论收藏

转发

2020-05-01 12:10

已编辑

C++

【图论】最小生成树算法（prim和kruskal详解及对比）

目录 一.最小生成树之 p r i m prim prim算法 ...

0 点赞评论收藏

转发

2020-05-01 12:09

已编辑

C++

【图论】用一道题从本质上讲清楚Floyd算法

P1119 【灾后重建】 4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4 -1 -1 5 4 一道非常好的Floyd最短路练习题，从算法本质上出的题目，对于初学Floyd算法的人来说是绝佳的练习题 首先我们从Floyd算法谈起，这是一个看上去很简单的算法-事实上也的确很简单，整个算法一共只有五行，三重循环＋一个判断就能求出图中任意两点之间的最短路径。 很多人都是直接把这个算法背了下来，然后要求最短路时直接默写，没有考虑到这个算法的本质意义，而这个题目，正好考了这个算法的本质，如果只会背的话，...

0 点赞评论收藏

转发

2020-05-01 12:09

已编辑

C++

【数论基础】欧几里德算法及其各种应用

目录： 欧几里德算法（辗转相除法） 1.问题引入：线段上格点的个数 2.输入两个正整数，求最大公约数和最小公倍数 3.P1029 最大公约数和最小公倍数问题 欧几里德算法（辗转相除法） 辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。 1.问题引入：线段上格点的个数 问题描述：给定平面上的两个格点P1=(x1,y1)和P2=(x2,y2)，线段P1P2上，除P1和P2以外一共有几个格点？ 限制条件：-109≤x1,y1,x2,y2≤109 辗转相除法的原理：① ...

0 点赞评论收藏

转发

2020-05-01 12:08

已编辑

C++

【题解】P1029 最大公约数和最小公倍数问题

目录 P1029 最大公约数和最小公倍数问题 方法一 方法二 P1029 最大公约数和最小公倍数问题 方法一 要知道最大公约数和最小公倍数的乘积就是原两个数的积。 换成公式就是： x ∗ y = g c ...

0 点赞评论收藏

转发

2020-05-01 12:08

C++

【题解】P1419 寻找段落（二分+单调队列）难度⭐⭐⭐★

P1419 寻找段落 首先二分答案，即：二分最大平均值。 我们将a全部减去mid，问题转化为判断是否存在一个长度在s~t范围内的区间它的和为正，如果有说明还有更大的平均值。 用前缀和和单调队列维护。 不会单调队列的点这里 然后用单调队列求出sum[i]-min(sum[i-t]~sum[i-s]),然后判断是否大于0即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; ifstream in("input.txt"); ofstream out("output....

0 点赞评论收藏

转发

2020-05-01 12:08

C++

【数论基础】模运算详解及其应用

一.基本理论 1.基本概念： 给定一个正整数p，任意一个整数n，一定存在等式 n = k p + r n = kp + r n=kp+r    其中 ...

0 点赞评论收藏

转发

2020-05-01 12:07

C++

【数论基础】有关素数的基础算法（内含三种筛法，低至O(N^(2/3))！）

目录 1.P3383 【模板】线性筛素数 2.P3912 素数个数 3. O （ n ( 2 ...

0 点赞评论收藏

转发

2020-05-01 12:07

C++

【题解】CF1070E Getting Deals Done（二分+思维）难度⭐⭐⭐

CF1070E Getting Deals Done 题意翻译 题目描述 Polycarp有很多工作要做。最近他学会了一条新的时间管理技巧：“如果任务需要五分钟或更短时间，请立即执行”。Polycarp喜欢新技巧，但他不确定五分钟是最佳值。他认为这个值 d（分钟）应根据现有任务列表选择。 Polycarp有一份长度为 n 的要完成的任务清单。第 i 个任务有一个需要的时间Pi，即它确切地需要 Pi 分钟来完成。Polycarp从第一个到第 n 个逐个浏览任务。如果任务所需时间是 d 或更少，Polycarp立即开始执行任务。如果任务需要时间大于 d ，他不会去完成这个任务。列表中的任务的顺序...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务