【蓝桥杯模板】-爱代码爱编程
笔记仅供个人参考
蓝桥杯算法模板
(1)杂题。不需要算法和数据结构,只需要逻辑、推理的题目,难度可难可易。考察思维能力和编码能力,只能通过大量做题来提高。
(2)BFS搜索和DFS搜索,也就是暴力搜索。这是非常基本的算法,是基础中的基础。
(3)动态规划。线性DP,以及一些DP应用,例如状态压缩DP、树形DP等。
(4)简单数学和简单数论。
(5)简单的字符串处理、输入输出,简单图论。
(6)基本算法,例如排序、排列、二分、倍增、差分、贪心。
(7)基本数据结构。队列、栈、链表、二叉树等。
模拟题
不需要什么算法的题目 >只要学过编程语言就能做 >考核思维、逻辑、编码能力 (脑筋急转弯) >这种题有“模拟题、构造题、思维题、 找规律题”,统称“杂题” >每次蓝桥杯都会出现,而且可能有好几题,是重要的得分点 >杂题:可能比较简单,也可能比较难
acwing
ACwing算法基础课全程笔记(2021年8月12日开始重写+优化)_云算法的博客-CSDN博客_acwing算法基础课网盘
快排
void quickSort(int l, int r, int[] a) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1, i = l - 1, j = r + 1, x = a[mid];
while (i < j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
quickSort(l, j, a);
quickSort(j + 1, r, a);
}
二分
①要求红色区间的最右端点
if(check(mid)) l=mid;//区间变为[mid,r]
else r=mid-1;//区间变为[l,mid-1]
int bsearch_2(int l,int r){
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
return l;
}
②要求绿色区间的最左端点
if(check(mid)) r=mid;//区间变为[l,mid]
else l=mid+1;//区间变为[mid+1,r]
int bsearch_1(int l,int r){
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
return l;
}
前缀和
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int a[N],s[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",s[r]-s[l-1]);
}
}
二维:
差分
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],b[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
b[l]+=c;
b[r+1]-=c;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];
printf("%d ",a[i]);
}
}
双指针
for(int i=0,j=0;i<n;i++){
while(j<=i&&check(j,i)) j++;
res=max(res,i-j+1);
}
位运算
1、n的二进制表示中第k位是几
方法:①先把第k位移到最后一位 n > > = k n>>=kn>>=k
②看个位是几n & 1 n&1n&1
最终结果为n > > k & 1 n>>k&1n>>k&1
2、lowbit(x):返回x的最后一位1
操作:x&(-x)=x&(~x+1)
dfs
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int path[N];
bool st[N];
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) printf("%d ",path[i]);
printf("\n");
return;
}
for(int i=0;i<n;i++){
if(!st[i]){
path[u]=i;
st[i]=1;
dfs(u+1);
st[i]=0;
}
}
}
int main(){
cin>>n;
dfs(0);
}
模板
2.优化输入输出时间(快速IO模板):
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
static InputReader in = new InputReader();
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
/**
你的代码写在这里
(输入实例: int a = in.nextInt();)
*/
out.close(); //不关闭输出流的话,控制台会没有输出,所以一定要关,in最好也关,不过实测没有因为不关in出过问题
}
static class InputReader{
private StringTokenizer st;
private BufferedReader bf;
public InputReader() {
bf = new BufferedReader(new InputStreamReader(System.in));
st = null;
}
public String next() throws IOException{
while(st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public String nextLine() throws IOException{
return bf.readLine();
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public BigDecimal nextBigDecimal() throws IOException{
return new BigDecimal(next());
}
}
}
或者
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args) throws Exception {
out.flush();
in.close();
}
}
3.快速幂模板
long long FastPower(long long base, long long power) { //base是底数,power是幂数,result是结果
long long result= 1;
while(power > 0) {
if(power & 1 != 0) {
result*= base;
power -= 1;
}
base *= base;
power >>= 1;
}
return result;
}
4.自定义类排序
例如:
public class Main {
static class Point{
double x;
double y;
public Point() {}
public Point(double x, double y){
this.x = x;
this.y = y;
}
}
public static double INF = 2 << 19;
static InputReader in;
static PrintWriter out;
public static int n;
public static double dist(Point a, Point b) {
double aa = Math.pow(a.x - b.x, 2);
double bb = Math.pow(a.y - b.y, 2);
return Math.sqrt(aa + bb);
}
public static double merge(Point[] point, int left, int right) {
double d = INF;
if(left >= right)
return d;
if(left + 1 == right)
return dist(point[left], point[right]);
int mid = (left + right) >> 1;
double d1 = merge(point, left, mid);
double d2 = merge(point, mid+1, right);
d = Math.min(d1, d2);
int i, j, k = 0;
ArrayList<Point> tem = new ArrayList<>();
for(i = left; i <= right; ++i) {
if(Math.abs(point[mid].x - point[i].x) <= d) {
tem.add(point[i]);
k++;
}
}
Collections.sort(tem, new Comparator<Point>() {
@Override
public final int compare(Point pFirst, Point pSecond) {
if(pFirst.y < pSecond.y)
return -1;
if(pFirst.y > pSecond.y)
return 1;
if(pFirst.x < pSecond.x)
return -1;
if(pFirst.x > pSecond.x)
return 1;
return 0;
}
});
for(i = 0; i < k; i++) {
for(j = i + 1; j < k && (tem.get(j).y - tem.get(i).y) < d; j++) {
double d3 = dist(tem.get(j), tem.get(i));
if(d3 < d) d = d3;
}
}
return d;
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
n = in.nextInt();
Point[] point = new Point[n];
for(int i = 0; i < n; i++) {
double x = in.nextDouble();
double y = in.nextDouble();
point[i] = new Point(x, y);
}
Arrays.sort(point, new Comparator<Point>() {
@Override
public int compare(Point pFirst, Point pSecond) {
if(pFirst.x < pSecond.x)
return -1;
if(pFirst.x > pSecond.x)
return 1;
if(pFirst.y < pSecond.y)
return -1;
if(pFirst.y > pSecond.y)
return 1;
return 0;
}
});
System.out.printf("%.4f", merge(point, 0, n-1));
}
5.归并排序模板
void sort_change(int l,int mid,int r){
//排序部分,把大区间再次分成小区间排序
int k1=l,k2=mid+1,k=l;
//初始化三个指针,一个指左区间左端点,一个指右区间左端点,一个指最终答案区间的左端点
while(k1<=mid&&k2<=r){
if(a[k1]>a[k2]){
temp[k]=a[k2];
k++,k2++;
}
else{
temp[k]=a[k1];
k++,k1++;
}
//每次取两个区间中最小的数字加入答案,指针右移
}
while(k1<=mid){
temp[k]=a[k1];
k++,k1++;
}//如果右区间的数字已经取完了,将左区间剩余数字按照一样从小到大的顺序放入答案
while(k2<=r){
temp[k]=a[k2];
k++,k2++;
}//如果左区间的数字已经取完了,将右区间剩余数字按照一样从小到大的顺序放入答案
for(int i=l;i<=r;i++) a[i]=temp[i];//将储存答案的数组的值赋回原来的数组
}
void sort_re(int l,int r){
if(l>=r) return ;//如果该区间不满足条件,即左边在右边的右边,return
int mid=(l+r)/2;//二分思想
sort_re(l,mid);//给左子区间排序
sort_re(mid+1,r);//给右子区间排序
sort_change(l,mid,r);//保证左右子区间排列得整整齐齐之后,才能并起来
//将大区间化成小区间然后排序
}
6.Int, Integer等数组类型转换
int[] data = {1,2,3};
// int[]转List<Integer>
// Arrays.stream(data): int[] -> IntStream
// IntStream.boxed(): IntStream -> Stream<Integer>
// Stream<Integer>.collect(Collectors.toList()): Stream<Integer> -> List<Integer>
List<Integer> list1 = Arrays.stream(data).boxed().collect(Collectors.toList());
// int[]转Integer[]
Integer[] arr1 = Arrays.stream(data).boxed().toArray(Integer[]::new);
// List<Integer>转int[]
// Collection<Integer>.stream(): Collection<Integer> -> Stream<Integer>
// Stream<Integer>.mapToInt(Integer::intValue): Stream<Integer> -> IntStream
// IntStream.toArray(): IntStream -> int[]
int[] arr2 = list1.stream().mapToInt(Integer::intValue).toArray();
// List<Integer>转Integer[]
Integer[] arr3 = list1.toArray(new Integer[0]);
// Integer[]转List<Integer>
List<Integer> list2 = Arrays.asList(arr3);
// Integer[]转int[]
int[] arr4 = Arrays.stream(arr1).mapToInt(Integer::valueOf).toArray();
7.sort降序排序
Integer[] arr={9,8,7,6,5,4,3,2,1};
Arrays.sort(arr,Collections.reverseOrder());
或
Integer[] arr={9,8,7,6,5,4,3,2,1};
Comparator cmp=new CMP();
Arrays.sort(arr,cmp);
class CMP implements Comparator<Integer>{
@Override //可以去掉。作用是检查下面的方法名是不是父类中所有的
public int compare(Integer a,Integer b){
// 升序排序的话反过来就行
return b-a;
}
或
List<Integer> integersList = Ints.asList(array);
Collections.reverse(integersList);//冒泡交换
System.out.println("Guava降序输出:");
for (int num : integersList) {
System.out.println(num);
}
或利用二维数组的自定义排序,如下:
int[][] arr = new int[3][2];
arr[0][0] = 5;
arr[0][1] = 3;
arr[1][0] = 1;
arr[1][1] = 4;
arr[2][0] = 6;
arr[2][1] = 2;
Arrays.sort(arr, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0]-b[0];
}
});
即按第一列升序排序:
1,4
5,3
6,2
8.高精度运算
1.valueOf(parament); 将参数转换为制定的类型
比如 int a=3;
BigInteger b=BigInteger.valueOf(a);
则b=3;
String s=”12345”;
BigInteger c=BigInteger.valueOf(s);
则c=12345;
2.add(); 大整数相加
BigInteger a=new BigInteger(“23”);
BigInteger b=new BigInteger(“34”);
a.add(b);
3.subtract(); 相减
4.multiply(); 相乘
5.divide(); 相除取整
6.remainder(); 取余
7.pow(); a.pow(b)=a^b
8.gcd(); 最大公约数
9.abs(); 绝对值
10.negate(); 取反数
11.mod(); a.mod(b)=a%b=a.remainder(b);
12.max(); min();
13.public int compareTo();
14.boolean equals(); 是否相等
15.BigInteger构造函数:
一般用到以下两种:
BigInteger(String val);
将指定字符串转换为十进制表示形式;
BigInteger(String val,int radix);
将指定基数的 BigInteger 的字符串表示形式转换为 BigInteger
int n;
BigInteger m;
n=cin.nextInt(); //读入一个int;
m=cin.nextBigInteger();//读入一个BigInteger;
前缀和/差分及其性质
(1)一维前缀和:
预处理:定义一个sum[]数组,sum[i]代表a数组中前i个数的和。
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
查询a数组中第left个数到第right个数的和:
sum[r]-sum[l-1]
(原理:
sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
)
(2)二维前缀和:
预处理:
s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1]
结论:
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]
差分:若a数组为b数组的前缀和数组,则b数组为a的差分数组
例如:a[i] = b[1] + b[2 ]+ b[3] +......+ b[i]
则:b[n] = a[n] - a[n-1];
若求对a数组中 [left,right] 区间每个数加上c,只需:
b[left] += c , b[right+1] -= c
二维差分:
构造差分数组:b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]
求以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中所有元素加c,则:
b[x1,y1] += c;
b[x2+1, y1] -= c;
b[x1, y2+1] -= c;
b[x2+1, y2+1] += c;
10.最大公约数/最小公倍数
最大公约数:
int gcd(int a,int b)
{
return b == 0 ? a : gcd(b,a%b) ;
}
最小公倍数:
两数乘积除以最大公约数
11.二分答案的两个模板:
(1)(最大值最小化):
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
(2)(最小值最大化):
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
12.TreeSet找比某个数大 / 小的数
小于 lower
小于等于 floor
大于等于 ceiling
大于 higher
13、 KMP算法
(2)求next数组:
void GetNext(char T[])
{
int j=0,k=-1;
next[j]=k;
while(T[j]!='\0')
{
if(k==-1||T[j]==T[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
(2)KMP主程序:
```
int KMP(char S[], char T[]) //KMP算法, S为主串,T为字串
{
int next[MaxSize],i=0,j=0;
GetNext(char T[]);
while (i<s.length && j<t.length)
{
if (j==-1 || s.data[i]==t.data[j])
{
i++;j++; //i,j各增1
}
else j=next[j]; //i不变,j后退,现在知道为什么这样让子串回退了吧
}
if (j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
}
```
14.线段树(模板题可至洛谷):
(1)单点修改+区间查询(求区间和)(P3374):
static long search(int i, int l, int r) {
if(tree[i].l >= l && tree[i].r <= r) {
return tree[i].sum;
}
if(tree[i].r < l || tree[i].l > r) {
return 0;
}
int sum = 0;
int mid = (tree[i].l + tree[i].r) >> 1;
if(tree[i].l <= mid) sum += search(i*2, l, r);
if(tree[i].r > mid) sum += search(i*2+1, l, r);
return sum;
}
static void add(int i, int x, long k) {
if(tree[i].l == tree[i].r) {
tree[i].sum += k;
return;
}
int mid = (tree[i].l + tree[i].r) >> 1;
if(x <= mid) add(i*2, x, k);
else add(i*2+1, x, k);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
return;
}
(2).区间修改+单点查询(P3368)(注:涉及区间修改的,要带懒标记(往往能用到))
void push_down(int i)
{
if(tree[i].lazy != 0)
{
tree[i << 1].lazy += tree[i].lazy;
tree[i << 1 | 1].lazy += tree[i].lazy;
int mid = (tree[i].l + tree[i].r) >> 1;
tree[i << 1].sum += tree[i].lazy * (mid - tree[i << 1].l + 1);
tree[i << 1 | 1].sum += tree[i].lazy * (tree[i << 1 | 1].r - mid);
tree[i].lazy = 0;
}
return;
}
void add(int i, int l, int r, int k)
{
if(tree[i].l >= l && tree[i].r <= r)
{
tree[i].sum += k * (tree[i].r - tree[i].l + 1);
tree[i].lazy += k;
return;
}
push_down(i);
int mid = (tree[i].l + tree[i].r) >> 1;
if(l <= mid) add(i*2, l, r, k);
if(r > mid) add(i*2+1, l, r, k);
tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
return;
}
ll search(int i, int x)
{
if(tree[i].l == x && tree[i].r == x)
{
return tree[i].sum;
}
push_down(i);
int mid = (tree[i].l + tree[i].r) >> 1;
if(x <= mid) return search(i*2, x);
else return search(i*2+1, x);
}
(3)区间修改+区间查询(P3372):
static class Tree{
int l, r;
long sum, lazy;
}
static Tree[] tree;
static long[] input;
static void build(int i, int l, int r) {
tree[i] = new Tree();
tree[i].l = l;
tree[i].r = r;
tree[i].lazy = 0;
if(l == r) {
tree[i].sum = input[l];
return;
}
int mid = (l + r) >> 1;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
}
static long search(int i, int l, int r) {
if(tree[i].l >= l && tree[i].r <= r) {
return tree[i].sum;
}
if(tree[i].r < l || tree[i].l > r) {
return 0;
}
push_down(i);
long sum = 0;
if(tree[i*2].r >= l) {
sum += search(i*2, l, r);
}
if(tree[i*2+1].l <= r) {
sum += search(i*2+1, l, r);
}
return sum;
}
static void add(int i, int l, int r, long k) {
if(tree[i].l >= l && tree[i].r <= r) {
tree[i].sum += k*(tree[i].r - tree[i].l + 1);
tree[i].lazy += k;
return;
}
push_down(i);
if(tree[i*2].r >= l) add(i*2, l, r, k);
if(tree[i*2+1].l <= r) add(i*2+1, l, r, k);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
return;
}
static void push_down(int i) {
if(tree[i].lazy != 0) {
tree[i << 1].lazy += tree[i].lazy;
tree[i << 1 | 1].lazy += tree[i].lazy;
int mid = (tree[i].l + tree[i].r) >> 1;
tree[i << 1].sum += tree[i].lazy*(mid - tree[i].l + 1);
tree[i << 1 | 1].sum += tree[i].lazy*(tree[i].r - mid);
tree[i].lazy = 0;
}
return;
}
15.全排列:
static void fullSort(int[] arr, int start, int end) {
// 递归终止条件
if (start == end) {
.........
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);
swap(arr, i, start);
}
}
static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
16.关于求对数
(详解参见以下博客)
1
https://blog.csdn.net/xiaojin21cen/article/details/98944689?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165311820516781683965191%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=165311820516781683965191&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allbaidu_landing_v2~default-3-98944689-null-null.142v10control,157v4control&utm_term=java%E6%B1%82%E5%AF%B9%E6%95%B0&spm=1018.2226.3001.4187
总结:
X^Y = N 转化为 logxN = Y 转化为 logxN = Math.log(N) / Math.log(a)
1
2
17.任意进制转换
// 如果题目要进行转化的进制在2~36之间的话直接调用库函数就行了。
String s = in.readLine();
int a = Integer.parseInt(s, 16) // 将16进制的字符串转化十进制数
//BigInteger a = new BigInteger(s, 16);// 高精度数
out.write(Integer.toString(a, 8)); // 转化为8进制输出
17.匈牙利算法
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //扫描每个目标
if (line[x][j]==true && used[j]==false)
//如果有连接并且还没有标记过
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
girl[j]=x;
return true;
}
}
}
return false;
}
18.邻接矩阵存图(加边方式)
(引申:迪杰斯特拉、floyd、spfa等最短路算法)
static int[] head, to, next, ans, dis;
static int tot = 0;
static void add(int x, int y) {
to[++tot] = y;
next[tot] = head[x];
head[x] = tot;
return;
}
19.大顶堆:
(PriorityQUeue默认小顶堆)
PriorityQueue<Integer>bigHeap=new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});