做微网站的第三方登录,加国无忧51工作网,网站建设评分,微信视频号推广价格目录
1、【二分】
#xff08;1#xff09;rmid —— 大于等于某数的最小值
#xff08;2#xff09;lmid —— 小于等于某数的最大值
2、【前缀和】
#xff08;1#xff09;一维前缀和
#xff08;2#xff09;二维前缀和
3、【差分】
#xff08;1#x…目录
1、【二分】
1rmid —— 大于等于某数的最小值
2lmid —— 小于等于某数的最大值
2、【前缀和】
1一维前缀和
2二维前缀和
3、【差分】
1一维差分
2二维差分
4、【单调栈】
1单调递增栈
2单调递减栈
5、【并查集】
6、【BFS 求最短路】
为什么BFS可以求最短路
7、【Dijkstra】
8、【spfa】
9、【floyd】
10、【kruskal】
11、【质数】
12、【约数】 1、【二分】
【蓝桥杯集训3】二分专题3 / 5-CSDN博客 l r 1 —— 先 r mid 后 l mid1 —— 寻找左边界 —— 找大于等于某数的最小值lr11 —— 先 l mid 后 r mid-1 —— 寻找右边界 —— 找小于等于某数的最大值 1rmid —— 大于等于某数的最小值
1 2 3 3 3 3 4 5
int l0,rn-1;while(lr)
{int midlr1;if(a[mid]x) rmid;else lmid1;
}
2lmid —— 小于等于某数的最大值
1 2 3 3 3 3 4 5
int l0,rn-1;{int midlr11;if(a[mid]x) lmid;else rmid-1;
} 2、【前缀和】
【蓝桥杯集训1】前缀和专题4 / 5-CSDN博客
1一维前缀和 a数组下标从1开始Si Si-1 ai 则 [ AlAr ]段的和 s[r] - s[l-1] for(int i1;in;i)
{a[i]sc.nextInt();s[i]s[i-1]a[i];
}[Al,Ar]的和 s[r]-s[l-1]2二维前缀和 static int N1010;
static int[][] anew int[N][N],snew int[N][N];for(int i1;in;i)for(int j1;jm;j){a[i][j]sc.nextInt();s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j];} while(q--0)
{int x1sc.nextInt(),y1sc.nextInt(),x2sc.nextInt(),y2sc.nextInt();int ress[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1];System.out.println(res);
} 3、【差分】
【蓝桥杯集训2】差分专题3 / 4-CSDN博客
1一维差分 给a数组 [l,r] 区间的每个数c只需要给其差分数组b做如下操作即可 b[l]c;
b[r1]-c; 构造差分数组 int[] anew int[N];
int[] bnew int[N];for(int i1;in;i)
{a[i]sc.nextInt();b[i]a[i]-a[i-1]; //构造差分数组
}差分数组进行 操作 int l,r,c;
while(k--0)
{b[l]c;b[r1]-c;
} 最后求差分数组b的前缀和即为原数组在【lr】段c的数组 for(int i1;in;i)
{a[i]a[i-1]b[i]; //b的前缀和是aSystem.out.print(a[i] );
} 2二维差分 初始化 static int N1010;
static int[][] anew int[N][N],bnew int[N][N];public static void work(int x1,int y1,int x2,int y2,int c)
{b[x1][y1]c;b[x21][y1]-c;b[x1][y21]-c;b[x21][y21]c;
}for(int i1;in;i)for(int j1;jm;j){a[i][j]sc.nextInt();work(i,j,i,j,a[i][j]);} 求前缀和 work(x1,y1,x2,y2,c);for(int i1;in;i)
{for(int j1;jm;j){b[i][j]b[i-1][j]b[i][j-1]-b[i-1][j-1];System.out.print(b[i][j] );}System.out.println();
} 4、【单调栈】
【蓝桥杯集训9】单调栈、单调队列模拟栈、模拟队列专题3 / 3_Roye_ack的博客-CSDN博客 1单调递增栈 在保持栈内元素单调递增前提下如果栈顶元素大于待入栈元素弹出栈顶新元素入栈对于要入栈的元素在对栈进行更新后栈顶元素就是数组中左侧第一个比自己小的元素 2单调递减栈 在保持栈内元素单调递减前提下如果栈顶元素小于要待入栈元素弹出栈顶新元素入栈 对于要入栈的元素在对栈进行更新后栈顶元素就是数组中左侧第一个比自己大的元素 题目输出每个数左边第一个比自己小的数如果不存在则输出-1
class Main
{public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt();DequeInteger stknew LinkedList();while(n--0){int xsc.nextInt();while(!stk.isEmpty()stk.peek()x) stk.pop();if(stk.isEmpty()) System.out.print(-1 );else System.out.print(stk.peek() );stk.push(x);}}
} 5、【并查集】
【蓝桥杯集训7】并查集专题3 / 5-CSDN博客 int find(int x) //返回x的祖宗结点状态压缩
{if(p[x]!x) p[x]find(p[x]);return p[x];
}p[find(a)]find(b); //合并操作 给a认个祖宗bif(find(a)find(b)) //a和b元素在同一个集合for(int i1;in;i) p[i]i; import java.util.*;class Main
{static int N100010;static int[] pnew int[N];public static int find(int x){if(p[x]!x) p[x]find(p[x]); //如果不是祖宗则向上查找return p[x];}public static void unite(int a,int b){p[find(a)]find(b); //给a认个祖宗b}public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt(),msc.nextInt();for(int i1;in;i) p[i]i;while(m--0){String ssc.next();int asc.nextInt(),bsc.nextInt();if(s.equals(M)){if(find(a)!find(b)) unite(a,b);}else {if(find(a)find(b)) System.out.println(Yes);else System.out.println(No);}}}
} 6、【BFS 求最短路】
【蓝桥杯集训11】BFS4 / 4_Roye_ack的博客-CSDN博客 为什么BFS可以求最短路 为什么就算有多条通路它总能输出最小距离 因为当第一个点到达终点时它一定是最短距离并且会将终点标记那么其他点再也无法到达终点也更新不了初始点到终点的距离 将起点00入队上下左右走只要在合法的范围内且不碰到墙且没有走过则入队 BFS就是将所有能走的路都走第一条能走通的路一定是最短路 static int[][] gnew int[110][110];static int[][] dnew int[110][110]; //记录该点到起点的最短距离static int[][] stnew int[110][110]; //标记走过的点static int[] dx{-1,1,0,0};static int[] dy{0,0,-1,1}; //方向数组 public static int bfs(){d[0][0]0;QueuePII qnew LinkedList();q.offer(new PII(0,0));while(!q.isEmpty()){PII tq.poll();for(int i0;i4;i){int nxt.xdx[i];int nyt.ydy[i];if(nx0nxnny0nymg[nx][ny]0st[nx][ny]0){q.offer(new PII(nx,ny));d[nx][ny]d[t.x][t.y]1;st[nx][ny]1;}}}return d[n-1][m-1];}7、【Dijkstra】
8、【spfa】
9、【floyd】
10、【kruskal】
11、【质数】
12、【约数】
