第二期

基础算法(二)

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

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

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

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

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

考点秘籍

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

蓝桥杯必背第一期

蓝桥杯必背第二期

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

填空题

双指针算法

双指针是一种算法思想，没有固定的模板

所以，我们结合例题去理解记忆这种思想效果 比较好！

双指针算法 蓝桥杯必背第二期

前缀和

顺序:
先求一遍所有的前缀和
再作差求自己想要的区间前缀和

模板题

核心

s[i]=s[i-1]+a[i]
s[r]-s[l-1]

写法1

import java.util.*;
public class Main{
    static int N=100010;
    static int a[]=new int[N];
    static int s[]=new int[N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        int m=sc.nextInt();
        for(int i=1;i<=n;i++)a[i]=sc.nextInt();
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+a[i];
        }
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            System.out.println(s[r]-s[l-1]);
        }
    }
}

写法2

import java.util.*;
public class Main{
    static int N=100010;
    static int s[]=new int[N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        int m=sc.nextInt();
        for(int i=1;i<=n;i++)s[i]=sc.nextInt();
        for(int i=1;i<=n;i++)s[i]+=s[i-1];
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            System.out.println(s[r]-s[l-1]);
        }
    }
}

二维前缀和

顺序:
先求一遍所有的前缀和
再作差求自己想要的区间前缀和

实际上是将一维看作二维处理

通常用于求矩阵内所有数的和,像炸弹、爆炸范围等等

模板题

import java.util.*;
public class Main{
    static int N=1010;
    static int a[][]=new int[N][N];
    static int s[][]=new int[N][N];    
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=sc.nextInt();
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
            }
        }
        while(q-->0){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            System.out.println(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
        }

    }
}

背完模板后，下面让我们小试牛刀

激光炸弹

Accode

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 k=sc.nextInt();
        for(int i=1;i<=n;i++)a[i]=sc.nextInt();
        int res=0;
        for(int R=1;R<=n;R++){
            for(int L=1;L<=R;L++){
                int sum=0;
               for(int i=L;i<=R;i++){
                 sum+=a[i];  
               }
               if(sum%k==0)res++;
            }
        }
        System.out.println(res);
    }
}

K倍区间：

Accode

//同余定理
import java.util.*;
public class Main{
    static int N=100010;
    static long s[]=new long[N];
    static long cnt[]=new long[N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        long k=sc.nextLong();
        for(int i=1;i<=n;i++)s[i]=sc.nextInt();
        for(int i=1;i<=n;i++){
        s[i]+=s[i-1];
        }
        long res=0;
        cnt[0]=1;
        for(int i=1;i<=n;i++){
            res+=cnt[(int)(s[i]%k)];
            cnt[(int)(s[i]%k)]++;
        }
        System.out.println(res);        
    }
}

四平方和

Accode

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        Map<Integer,int []>map=new HashMap<>();
        int n=sc.nextInt();
        for(int c=0;c*c<=n;c++){
            for(int d=0;d*d+c*c<=n;d++){
                int sum=c*c+d*d;
                if(!map.containsKey(sum))map.put(sum,new int[]{c,d});
            }
        }
        for(int a=0;a*a<=n;a++){
            for(int b=0;a*a+b*b<=n;b++){
                int sum=a*a+b*b;
                if(map.containsKey(n-sum)){
            System.out.println(a+" "+b+" "+map.get(n-sum)[0]+" "+map.get(n-sum)[1]);
                return ;
                }
            }
        }
    }
}

差分

差分由于直接插入输入的元素比较难插
所以一般是通过差分插入元素即insert(i,j,i,j,a[i][j])

核心

a[]:前缀和数组
b[]:差分数组
b[l]+=c;
b[r+1]-=c;
顺序：先差分再求一遍前缀和

模板题

import java.util.*;
public class Main{
    static int N=100010;
    static int a[]=new int[N];
    static int b[]=new int[N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=1;i<=n;i++)a[i]=sc.nextInt();
        for(int i=1;i<=n;i++){
            insert(i,i,a[i]);
        }
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int c=sc.nextInt();
            insert(l,r,c);
        }
        for(int i=1;i<=n;i++){
            a[i]=a[i-1]+b[i];
        }
        for(int i=1;i<=n;i++)System.out.print(a[i]+" ");
    }
    public static void insert(int l,int r,int c ){
        b[l]+=c;
        b[r+1]-=c;
    }
}

二维差分

关键点：

二维差分和以往的处理顺序不同！

像前缀和是从右下到左上
而差分是从左上到右下去处理差分
即(x1,y1)-->(x2,y2)这块区域内加上C
顺序：先差分再求一遍前缀和

模板题

import java.util.*;
public class Main{
    static int N=1010;
    static int a[][]=new int [N][N];
    static int b[][]=new int [N][N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=sc.nextInt();
                insert(i,j,i,j,a[i][j]);
            }
        }
        while(q-->0){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            int c=sc.nextInt();
            insert(x1,y1,x2,y2,c);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }


    }
    public static void insert(int x1,int y1,int x2,int y2,int c){
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
}

位运算(lowbit)

一般不会单独考,lowbit常用于拔高题的进制处理的优化

模板题

可以直接记下来

import java.util.*;
public class Main{

    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while(n-->0){
            int sum=0;
            int x=sc.nextInt();
            while(x!=0){
            x-=lowbit(x);
            sum++;
            }
            System.out.print(sum+" ");
        }
    }
    public static int lowbit(int x){
        return x&-x;
    }
}

离散化

很少看到，时间紧的同学可以跳过,重点还是前几个！

模板题

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        int N = 300010;
        int[] a = new int[N];
        int[] s = new int[N];
        List<Integer> allS = new ArrayList<>();
        List<PIIs> add = new ArrayList<>();
        List<PIIs> query = new ArrayList<>();

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str = reader.readLine().split(" ");
        int n = Integer.parseInt(str[0]); // n次操作
        int m = Integer.parseInt(str[1]); // m次询问
        for (int i = 0; i < n; i++) {
            String[] str1 = reader.readLine().split(" ");
            int x = Integer.parseInt(str1[0]);
            int c = Integer.parseInt(str1[1]);
            add.add(new PIIs(x, c));
            allS.add(x);
        }
        for (int i = 0; i < m; i++) {
            String[] str2 = reader.readLine().split(" ");
            int l = Integer.parseInt(str2[0]);
            int r = Integer.parseInt(str2[1]);
            query.add(new PIIs(l, r));
            allS.add(l);
            allS.add(r);
        }
        reader.close();
        Collections.sort(allS);
        int unique = unique(allS);
        allS = allS.subList(0, unique);
        for (PIIs item : add) {
            int x = find(item.getFirst(), allS);
            a[x] += item.getSecond();
        }
        for (int i = 1; i <= allS.size(); i++) {
            s[i] = s[i - 1] + a[i];
        }
        for (PIIs item : query) {
            int l = find(item.getFirst(), allS);
            int r = find(item.getSecond(), allS);
            System.out.println(s[r] - s[l - 1]);
        }
    }

    public static int unique(List<Integer> list) {
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || list.get(i) != list.get(i - 1)) {
                list.set(j++, list.get(i));
            }
        }
        return j;
    }

    public static int find(int x, List<Integer> allS) {
        int l = 0;
        int r = allS.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (allS.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r + 1;
    }
}

class PIIs implements Comparable<PIIs>{
    private int first;
    private int second;

    public int getFirst() {
        return first;
    }

    public int getSecond() {
        return second;
    }

    public PIIs(int first, int second) {
        this.first = first;
        this.second = second;
    }
    public int compareTo(PIIs o) {
        return Integer.compare(first, o.first);
    }
}

区间合并

(1)按区间的左端点排序

st:左端点、ed:右端点
看下一扫描区间的st与上一扫描区间的位置关系。

(2)扫描整个区间,在这一过程中,把有交集的区间进行合并。

(3)在前面左端点排好序的前提下,分为3种情况：

1.当前扫描区间在上一扫描区间内,无需统计
2.当前扫描区间的st落在上一扫描区间内(含ed),进行统计。
3.当前扫描区间的st大于上一扫描区间的ed
整个是独立区间,进行统计。

模板题

题解

import java.util.*;
public class Main{
    public static void main(String []args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    List<PII>alls = new ArrayList<>();
    for(int i=0;i<n;i++) {
        int l =in.nextInt();
        int r =in.nextInt();
        alls.add(new PII(l,r));
    }
    Collections.sort(alls);
    int res = qu(alls);
    System.out.println(res);            
}
    public static int qu(List<PII> list) {
        List<PII> res = new ArrayList<>();
        int st =(int) -2e9;
        int ed =(int) -2e9;
        for(PII item:list) {
            if(ed<item.x) {
                if(ed!=-2e9)res.add(new PII(st,ed));
                st=item.x;
                ed=item.y;
            }
            else ed=Math.max(ed, item.y);
        }
            if(st!=-2e9)res.add(new PII(st,ed));
        return res.size();
        }
    }
class PII implements Comparable<PII>{
    int x,y;
    public PII(int x,int y) {
        this.x=x;
        this.y=y;
    }
    public int compareTo(PII o) {
        return Integer.compare(x, o.x);
    }

}