（蓝桥杯）1125 第 4 场算法双周赛题解+AC代码（c++/java）

Posted on by hackdl

题目一：验题人的生日【算法赛】

验题人的生日【算法赛】 – 蓝桥云课 (lanqiao.cn)

思路：

1.又是偶数，又是质数，那么只有2喽

AC_Code:C++

#include 
using namespace std;
int main()
{
  cout

AC_Code:java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println(2);
        scan.close();
    }
}

题目二：蓝桥小课堂【算法赛】

蓝桥小课堂【算法赛】 – 蓝桥云课 (lanqiao.cn)

思路：

1.组成三角形的条件，任意两边大于第三边

2.注意不要用sqrt函数，因为输出的是面积的平方，最后直接输出即可，用sqrt函数时可能有的数据不是平方数，开放后会有精度损失，导致一直无法AC

AC_Code:C++

#include 
using namespace std;

typedef long long LL;

int main()
{
  LL a,b,c;   cin>>a>>b>>c;
  if(a+b>c&&a+c>b&&b+c>a){  //任意两边大于第三边
      LL s=(a+b+c)/2;
      LL ans=s*(s-a)*(s-b)*(s-c);
      cout

AC_Code:java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a=sc.nextLong(),b=sc.nextLong(),c=sc.nextLong();

        if(a+b>c&&a+c>b&&b+c>a){ //任意两边大于第三边
          long s=(a+b+c)/2;
          long ans=s*(s-a)*(s-b)*(s-c);
          System.out.println(ans);
        }
        else System.out.println(-1);
        
    }
}

题目三：压缩矩阵【算法赛】

压缩矩阵【算法赛】 – 蓝桥云课 (lanqiao.cn)

思路：找规律/数学

1.第一行和最后一行是两个数，其他行都是三个数

2.先算出行，算出行后让列也等于行，用x模3看余数是几，看是需要偏移，余数为1向右偏移一位，余数为2向左偏移一位，余数为0不需要偏移

3.算行的话就是找规律了，（x+4）/3就是行

AC_Code:C++

#include 
#include 
#include 
#include 
#include 
#include
#include
#include 
#include 
#include
#include 


using namespace std;

typedef long long LL;
typedef pairPII;

#define x first
#define y second
#define ls u>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

AC_Code:java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        int q=sc.nextInt();

        while(q-->0) {
            long x=sc.nextLong();

            long row=(x+4)/3; //算出行
            long col=row;

            //看是否要向左右偏移
            if(x%3==1) 服务器托管网 col++;
            else if(x%3==2)  col--;

            System.out.println(row+" "+col);

        }


    }
}

题目四：恒纪元【算法赛】

恒纪元【算法赛】 – 蓝桥云课 (lanqiao.cn)

思路：

1.乱纪元的增长速度是非常快的，（2^40>1e12）所以乱纪元是非常少的,那么可以预处理出所有的乱纪元

2.对于每一个询问s,暴力找到大于s的第一个恒纪元t，再暴力（二分也可以）找到第一个大于t的乱纪元，用第一个大于t的乱纪元-t就是恒纪元可以持续的天数了

3.这个的预处理其实是一个谜（预处理不好很容易只能过25%的测试样例），预处理出小于1e13次方的乱纪元就可以过

AC_Code:C++

#include 
#include 
#include 
#include 
#include 
#include
#include
#include 
#include 
#include
#include 


using namespace std;

typedef long long LL;
typedef pairPII;

#define x first
#define y second
#define ls uvis; //存储乱纪元

LL qpow(int a,int b){
    LL res=1;
    
    for(int i=0;iINF) return -1;  //大于正无穷了
    }
    return res;
}

void solve(){
    scanf("%d%d%d",&x,&y,&z);
    
    for(int i=0;iINF)   break;  //三者相加大于正无穷
                
                vis.insert(s);
            }
        }
    }
    
    
    scanf("%d",&q);
    while(q--){
        LL s;   scanf("%lld",&s);   
        LL t=s+1;
        while(vis.count(t)) t++;    //找到第一个恒纪元
        
        //二分找到第一个大于t的乱纪元,相减求恒纪元持续了多少天
        printf("%lld %lldn",t,*vis.upper_bound(t)-t);
    }
} 

void init(){                     
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

AC_Code:java


import com.sun.source.tree.Tree;

import java.util.*;

public class Main {
    static final long INF=(long)1e13;
    static long qpow(int a,int b){
        long res=1;
        for(int i=0;iINF) return -1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        TreeSet vis=new TreeSet();
        List list=new ArrayList();
        int x=sc.nextInt(),y=sc.nextInt(),z=sc.nextInt();

        //预处理乱纪元
        for(int i=0;iINF)   break;  //三者相加大于正无穷

                    if(!vis.contains(s)){
                      list.add(s);
                      vis.add(s);
                    }    
                    
                }
            }
        }

        Collections.sort(list); //集合排序

        int q=sc.nextInt();
        while(q-->0){
            long s=sc.nextLong();
            long t=s+1;
            //找到第一个恒纪元
            while(vis.contains(t))  t++;

            //找到大于第一个横纪元的乱纪元
            int idx=-1;
            for (int i = 0; i t){
                    idx=i;
                    break;
                }
            }

            //第一个大于t的乱纪元-减去恒纪元
            System.out.println(t+" "+(list.get(idx)-t));
            // System.out.println(t+" "+(vis.ceiling(t+1)-t));   //二分
        }                   //ceiling相当于lower_bound
    }
}

题目五：充能计划【算法赛】

充能计划【算法赛】 – 蓝桥云课 (lanqiao.cn)

思路：

简述题意：n个引擎，m种宝石，q个询问，每个询问选出一种宝石p,放到第k个引擎上，此时区间[k,min(n,k+s[p]-1)]都会放入p这个宝石，s数组为每个宝石的充能范围,最后问n种引擎宝石的数量

1.对n个引擎开n个set,对每个询问的合法区间都加入宝石p，最后对每个引擎输出set的大小，时间复杂度o(n^2),会tle的，怎么优化呢？

2.可以对每种宝石分组，对每一个询问记录区间，最后对每种宝石合并区间（注意合并区间前要对左端点排序），合并区间后用差分记录左右端点位置

3.最后累加差分，计算答案

AC_Code:C++

#include 
#include 
#include 
#include 
#include 
#include
#include
#include 
#include 
#include
#include 


using namespace std;

typedef long long LL;
typedef pairPII;

#define x first
#define y second
#define ls uline[N]; //line[i]:存储宝石i的所有区间
int diff[N];

void solve(){
    scanf("%d%d%d", &n, &m,服务器托管网&q);
    for(int i=1;i=p.x)  r=max(r,p.y);
            else{
                diff[l]++;
                diff[r+1]--;
                l=p.x;
                r=p.y;
            }
        }
        diff[l]++;  diff[r+1]--;
    }
    
    int ans=0;  //累加查分计算答案
    for(int i=1;i>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

AC_Code:java

import com.sun.source.tree.Tree;

import java.util.*;

public class Main {

    static int N=(int)1e5+7;
    static int[] s=new int[N];
    static List[] line=new ArrayList[N];
    static int[] diff=new int[N];

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),q=sc.nextInt();
        for(int i=1;i();
        }

        while(q-->0){
            int p=sc.nextInt(),k=sc.nextInt();
            line[p].add(new Line(k,Math.min(n,k+s[p]-1)));  //按宝石种类分组
        }

        for(int i=1;i= p.l) r = Math.max(r, p.r);
                else {
                    diff[l]++;
                    diff[r + 1]--;
                    l = p.l;
                    r = p.r;
                }
            }
            diff[l]++;
            diff[r + 1]--;
        }

        int ans=0;  //计算答案
        for(int i=1;i{
    int l,r;

    public Line(int l, int r) {
        this.l = l;
        this.r = r;
    }

  
    public int compareTo(Line o) {
        return l-o.l;
    }
}

题目六：大风起兮【算法赛】

大风起兮【算法赛】 – 蓝桥云课 (lanqiao.cn)

思路：

1.动态求平均数，可以用两个multiset,一个存放一半较小的数，一个存放一半较大的数

2.对于每一个询问，先删除一个数，再计算中位数

AC_Code:C++

#include 
#include 
#include 
#include 
#include 
#include
#include
#include 
#include 
#include
#include 


using namespace std;

typedef long long LL;
typedef pairPII;

#define x first
#define y second
#define ls ub;
    for(int i=1;imx,mi; //n为奇数，mi多放一个数
    for(int i=0;imi.size()){
                int temp=*mx.begin();
                mi.insert(temp);
                mx.erase(mx.find(temp));
            }
        }
        else{ //删除大的数那一堆
            mx.erase(mx.find(a[x]));
            if(mi.size()-mx.size()>1){
                int temp=*mi.rbegin();
                mx.insert(temp);
                mi.erase(mi.find(temp));
            }
        }
        
        //输出答案
        if(mi.size()>mx.size()) printf("%.1lf ",*mi.rbegin()*1.0);
        else printf("%.1lf ",(*mi.rbegin()+*mx.begin())/2.0);
    }
    
} 

void init(){                     
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

AC_Code:java

题目七：时空追捕【算法赛】

不会写，占时更新，

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: springboot参数汇总

multipart multipart.enabled 开启上传支持（默认：true） multipart.file-size-threshold: 大于该值的文件会被写到磁盘上 multipart.location 上传文件存放位置 multipart.ma…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: