第一期

基础算法(一)

冲刺蓝桥杯省一模板大全来啦~

蓝桥杯4月8号就要开始了~

还没背熟模板的伙伴们背起来！！！

祝大家4月8号蓝桥杯上岸~

不清楚蓝桥杯考什么的点点下方

考点秘籍

想背注释版的伙伴们点点下方

注释版

想看JavaB组填空题的伙伴们点点下方

填空题

快速排序

模板题

题解

不快读快写版

import java.util.*;
public class Main {
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt();
    int q[] = new int[n];
    for(int i=0;i<n;i++) {
        q[i]=sc.nextInt();
    }
    quickSort(q,0,n-1);
    for(int i=0;i<n;i++) {
        System.out.print(q[i]+" ");

    }   
}

public static void quickSort(int[] q, int l, int r) {
if(l>=r)return;
int x =q[(l+r)/2],i=l-1,j=r+1;
while(i<j) {
    while(q[++i]<x);
    while(q[--j]>x);
    if(i<j) {
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
    }

}
    quickSort(q,l,j);
    quickSort(q,j+1,r);
}
}

快读快写版

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] q = new int[n];
        String[] strs = br.readLine().split(" ");
        for(int i=0;i<q.length;i++)q[i]=Integer.parseInt(strs[i]);
        quickSort(q,0,q.length-1);
        for(int i=0;i<q.length;i++){
            if(i==q.length-1)System.out.print(q[i]);
            else System.out.print(q[i]+" ");
        }

    }

public static void quickSort(int[] q, int l, int r) {
if(l>=r)return;
int x =q[(l+r)/2],i=l-1,j=r+1;
while(i<j) {
    while(q[++i]<x);
    while(q[--j]>x);
    if(i<j) {
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
    }
}

    quickSort(q,l,j);
    quickSort(q,j+1,r);
}
} 

归并排序

模板题

题解

import java.util.*;
public class Main{
    public static void merge_Sort(int q[],int l,int r){
        if(l>=r)return;
        int mid=(l+r)>>1;
        merge_Sort(q,l,mid);
        merge_Sort(q,mid+1,r);
         int k=0,i=l,j=mid+1;
         int temp[]=new int[r-l+1];
        while(i<=mid&&j<=r){
            if(q[i]<=q[j]&&j<=r)temp[k++]=q[i++];
            else temp[k++]=q[j++];
        }
        while(i<=mid)temp[k++]=q[i++];
        while(j<=r)temp[k++]=q[j++];
        for(int a=0,b=l;b<=r;a++,b++){
            q[b]=temp[a];
        }
    }
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int q[]=new int[n];
        for(int i=0;i<n;i++)q[i]=sc.nextInt();
        merge_Sort(q,0,n-1);
        for(int i=0;i<n;i++){
            System.out.print(q[i]+" ");
        }
    }
}

二分

模板题

import java.util.*;
public class Main{
    static int N=100010;
    static int a[]=new int[N];

    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int q=sc.nextInt();
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        while(q-->0){
            int x=sc.nextInt();
            int l=0,r=n-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[mid]>=x)r=mid;
                else l=mid+1;
            }
            if(a[l]!=x)System.out.println("-1 -1");
            else{
                System.out.print(l+" ");
               l=0;
               r=n-1;
               while (l<r){
                  int mid=l+r+1>>1;
                  if(a[mid]<=x)l=mid;
                  else r=mid-1;
            }
            System.out.println(l);
        }
    }
    } 
}