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

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

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

真题千千万万遍，蓝桥省一自然现！

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

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

考点秘籍

第三期

模拟/枚举专题

你不能错过的DP模板

蓝桥杯考前必背！！！

往期回顾

蓝桥杯上岸每日N题第一期(一)！！！

蓝桥杯上岸每日N题第一期(二)！！！

蓝桥杯上岸每日N题第一期(三)！！！

蓝桥杯上岸每日N题第二期(一)！！！

蓝桥杯上岸必刷专题

蓝桥杯上岸必刷！！！(日期专题+保姆级教学)

蓝桥杯上岸必刷！！！(字符串专题)

竞赛干货

算法竞赛字符串常用操作总结！！！

想背纯享模版的伙伴们点点下方

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全（第二期）

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

蓝桥杯必背第一期

蓝桥杯必背第二期

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

填空题

蓝桥杯每年必出各种模拟、枚举的题目,还不熟的小伙伴,下面让我们一起来刷起来吧

真题千千万万遍，蓝桥省一自然现！

蓝桥杯冲冲冲

必刷题目

连号区间数

题解

Accode

import java.util.*;
public class Main{
    static int Inf=0x3f3f3f3f;
    static int N=10010;
    static int a[]=new int[N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int res=0;
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        for(int i=0;i<n;i++){
            //枚举左端点
            //每次枚举每个左端点时
            //从i~j这段区间的max、min需要清空
            int max=-Inf;
            int min=Inf;
            //枚举右端点
            for(int j=i;j<n;j++){
                //每次只会多出一个a[j]，直接比较求最值即可。
                if(max<a[j])max=a[j];
                //当前的最大值是当前区间的最大值
                if(min>a[j])min=a[j];
                //当前的最小值是当前区间的最小值
                if(max-min==j-i)res++;
                //下标等于最大值和最小值时说明可以填满这段区间的所有数。
                //满足区间内数是连续的这一性质
            }
        }
        System.out.println(res);
    }
}

移动距离

曼哈顿距离：

沿着折线或者直线走的距离
|x1-x2|+|y1-y2|

欧几里得距离：

两点之间的距离:
sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

思路

先按顺序将所有数排序好:
再将所有数进行减1处理，以便处理行号、列号。
减一后矩阵内的点的距离是不变的
我们可以得出一些规律：
行号：n/w
列号：n%w
由于是蛇形矩阵
所以奇数行需要进行翻转操作
怎么翻转？
宽度为6(w)
列的下标从0~5编排
相当于：
0<-->5
1<-->4
2<-->3
两两互换位置且下标之和恰好为5(6-1)=(w-1)
每个数的列号为n%w
我们只需要用5-n%w即可
即w-1-n%w

ACcode

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int w=sc.nextInt();
        int m=sc.nextInt();
        int n=sc.nextInt();
        m--;
        n--;
         //减一操作
        //从矩阵为0开始编号
        int x1=m/w;
        int x2=n/w;
        //从0开始编号后
        //对宽度下取整得到行号

        int y1=m%w;
        int y2=n%w;
        //对宽度取模后得到列号

        //蛇形排列
        //出现奇数行时，需要将数字翻转过来
        //翻转的列号之和恰好为w-1
        if(x1%2==1)y1=w-1-m%w;
        if(x2%2==1)y2=w-1-n%w;

        //折线/直线距离
        //曼哈顿距离：|x1-x2|+|y1-y2|
        System.out.print(Math.abs(x1-x2)+Math.abs(y1-y2));
    }
}

逆序对的数量

考点：归并排序

逆序对的数量

Accode

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int a[]=new int[n+10];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
          System.out.println(mergeSort(a,0,n-1));
    }
    public static long mergeSort(int q[],int l,int r){
        if(l>=r)return 0;
        int mid=(l+r)>>1;

        int i=l,j=mid+1,k=0;
        long res=mergeSort(q,l,mid)+mergeSort(q,mid+1,r);
        int temp[]=new int[r-l+1];
        while(i<=mid&&j<=r){
            if(q[i]<=q[j])temp[k++]=q[i++];
            else{
                temp[k++]=q[j++];
                res+=mid-i+1;
            }
        }
        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];
        }
       return res; 
    }
}

外卖店优先级

考点：模拟+离散化

Ac做法

暴力做法

直接根据题目模拟，学好语文很关键！
从1开始按顺序去枚举每个时刻
在每个时刻中依次去枚举每家店的订单数
开一个score[j]去记录每个店的总订单数
该时刻无订单则减1
有订单则将score[j]加上当前时刻订单数的两倍
最后判断一下在当前时刻每个店的总订单数>5/<=3
>5则入队 <=3则出队
给需要入队的id打上标记
最后统计一下队列中的打上标记的id数即可。

暴力(过6/10的样例)

import java.util.*;
public class Main{
    static int INF=0x3f3f3f3f;
    static int N=10010,M=2*N;
    static int n,m,t;
    static boolean vis[]=new boolean[N];
    static int score[]=new int[N];  
    static int order[][]=new int[N][N/10];
    public static void main(String []args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        t=sc.nextInt();
        while(m-->0) {
            int ts=sc.nextInt();
            int id=sc.nextInt();
            order[ts][id]++;
            //表示ts时刻编号为id的店有一条订单
            //所以是order[ts][id]++;
        }
        for(int i=1;i<=t;i++) {
            //依次去枚举t个时刻
            for(int j=1;j<=n;j++) {
                //每个时刻去枚举n家店

                if(order[i][j]>0) {
                    //i时刻时这家店有订单
                    //订单数*2
                    score[j]+=order[i][j]*2;
                }
                else 
                //这一时刻无订单
                //需要将订单数减1
                    score[j]--;
                //减无可减置为0   
                if(score[j]<0)score[j]=0;
                //i时刻,j店的订单数大于5则入队
                if(score[j]>5)
                    vis[j]=true;
                //i时刻,j店的订单数小于等于3则出队
                if(score[j]<=3)
                    vis[j]=false;
            }
        }
        //最后遍历一遍所有店
        //店入队的则加上1
        //没入队则加上0
        int res=0;
        for(int i=1;i<=n;i++) {
            if(vis[i])res++;
        }
        System.out.println(res);
    }
}

递增三元组

AC题解

暴力枚举

通过了 7/13个数据
O(n^3)

import java.util.*;
public class Main{
    static int N=100010;
    static int a[][]=new int [3][N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<3;i++){
        for(int j=0;j<n;j++){
            a[i][j]=sc.nextInt();
        }    
        }
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    if(a[0][i]<a[1][j]&&a[1][j]<a[2][k]){
                        res++;
                    }
                }
            }
        }
        System.out.println(res);
    }
}

错误票据

题解

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
    static int N=100010;
    static int cnt[]=new int[N];
    static int INF=0x3f3f3f3f;
    public static void main(String []args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bf.readLine());
        //String s[]=bf.readLine().split(" ");
        int max=-INF;
        int min=INF;
        for(int i=0;i<n;i++) {
            String s[]=bf.readLine().split(" ");
            for(int j=0;j<s.length;j++) {
                int num=Integer.parseInt(s[j]);
                cnt[num]++;
                max=Math.max(max,num);
                min=Math.min(min,num);

            }

        }
        int duan=0;
        int chong=0;
        for(int i=min;i<=max;i++) {
             if(cnt[i]==0)duan=i;
             if(cnt[i]>1)chong=i;
        }
        System.out.println(duan+" "+chong); 
    }
}

回文日期

类似题目见 蓝桥杯上岸必刷！！！(日期专题+保姆级教学)

//先枚举回文数再判断日期是否合法
import java.util.*;
public class Main{
    static int d[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    public static boolean check(int date){
        int year=date/10000;
        int month=date%10000/100;
        int day=date%100;
        if(month==0||month>12)return false;
        //边界值要确定
        //先确定月份是否合法
        //再去确定天数是否合法
        //分为是否为2月
        //不是2月的去判断
        //是2月的去判断闰年还是平年
        //天数用leap去甄别
        if(day==0||month!=2&&day>d[month])return false;
        if(month==2){
            int leap=0;
            if(year%100!=0&&year%4==0||year%400==0)leap=1;
            if(day>28+leap)return false;


        }
        return true;




    }
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int date1=sc.nextInt();
        int date2=sc.nextInt();
        int res=0;
        //枚举回文数
        //先枚举前4位
        //再对前4位翻过来
        //怎么翻？
        //先给date*10+x%10;再继续x%10
        //每次date*10+x%10循环4次后
        //得到回文数
        for(int i=1000;i<10000;i++){
            int date=i;
            int x=i;

            for(int j=0;j<4;j++){
                date=date*10+x%10;
                x/=10;
            }

            //首先要在天数date1~date2之内
            //再去检查是否合法
            if(date1<=date&&date<=date2&&check(date))res++;
        }
        System.out.println(res);
    }
}

日期问题

题解

航班时间

题解

特别数的和

题解

Accode(暴力枚举)

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long res=0;
        for(int i=1;i<=n;i++){
        int b=i;
        int c=b;
        //记录b原本的值，满足条件就加上。
        while(b>0){
            int ans=b%10;
            //依次取出来数字的每个位

            //满足以下其中之一即可break
            if(ans==2||ans==0||ans==1||ans==9)
            {
            res+=c;
            break;

            }
            b/=10;
        }
    }
    System.out.println(res);
}
}