第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询

目录

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询

前言

算法训练 区间k大数查询

C语言

C++语言

Java语言

Python语言

第六届——第十三届省赛题解

第六届——第十二届省赛题解

前言

        最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。

算法训练 区间k大数查询

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入

5
1 2 3 4 5
2
1 5 2
2 3 2

样例输出

4
2

数据规模与约定

对于30%的数据，n,m<=100；

对于100%的数据，n,m<=1000；

保证k<=(r-l+1)，序列中的数<=10^6

题解：

C语言

#include <stdio.h>  
 #include <stdlib.h>  
 int Split(int *data,int pre,int rear)  
 {  
     int value=data[pre];  
     while(pre<rear)  
     {  
         while(data[rear]>=value && pre<rear) rear--;  
         data[pre]=data[rear];  
         while(data[pre]<value && pre<rear) pre++;  
         data[rear]=data[pre];  
     }  
     data[pre]=value;  
     return pre;  
 }  
 //快速排序  
 void QuickSort(int *data,int pre,int rear,int k)  
 {  
     if(pre<=rear)  
     {  
         int mid=Split(data,pre,rear);  
         if(mid==k)  
         {  
             printf("%dn",data[mid]);  
         }  
         else if(mid>k)  
         {  
             QuickSort(data,pre,mid-1,k);  
         }  
         else  
         {  
             QuickSort(data,mid+1,rear,k);  
         }  
     }  
 }  
 void Copy(int *data,int n,int *temp)  
 {  
     int i;  
     for(i=0;i<n;i++)  
     {  
         temp[i]=data[i];  
     }  
 }  
 int main()  
 {  
     int i;  
     int n;  
     int m;  
     int *data;  
     scanf("%d",&n);  
     data=(int *)malloc(sizeof(int)*n);  
     for(i=0;i<n;i++)  
     {  
         scanf("%d",&data[i]);  
     }  
     scanf("%d",&m);  
     while(m)  
     {  
         int pre;  
         int rear;  
         int k;  
         int *temp=(int *)malloc(sizeof(int)*n);  
         scanf("%d%d%d",&pre,&rear,&k);  
         Copy(data,n,temp);  
         QuickSort(temp,pre-1,rear-1,rear-k);  
         m--;  
     }  
     return 0;  
 } 

C++语言

#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 10005

int n,m;
int a[N],tree[15][N],sum[15][N];

bool cmp(int x,int y)
{
	return x>y;
}

void build(int x,int L,int R)
{
	if(L==R)	return;
	int i;
	int mid=(L+R)>>1;
	int lp=L,rp=mid+1,l=mid-L+1;
	for(i=L;i<=R;i++)
		if(tree[x][i]>a[mid])
			l--;
	for(i=L;i<=R;i++)
	{
		sum[x][i]=i==L?0:sum[x][i-1];
		if(a[mid]==tree[x][i] && l)
		{
			l--;
			tree[x+1][lp++]=tree[x][i];
			sum[x][i]++;
		}
		else
		if(tree[x][i]>a[mid])
		{
			tree[x+1][lp++]=tree[x][i];
			sum[x][i]++;
		}
		else
			tree[x+1][rp++]=tree[x][i];
	}
	build(x+1,L,mid);
	build(x+1,mid+1,R);
}

int query(int x,int L,int R,int l,int r,int k)
{
	if(l==r)	return tree[x][l];
	int mid=(L+R)>>1;
	int t,tt;
	t=l==L?0:sum[x][l-1];
	tt=sum[x][r]-t;
	if(k<=tt)
		return query(x+1,L,mid,L+t,L+t+tt-1,k);
	else
		return query(x+1,mid+1,R,mid-L+1+l-t,mid-L+1+r-t-tt,k-tt);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		tree[0][i]=a[i];
	}
	sort(a+1,a+1+n,cmp);
	build(0,1,n);
	scanf("%d",&m);
	int l,r,k;
	while(m--)
	{
		scanf("%d%d%d",&l,&r,&k);
		printf("%dn",query(0,1,n,l,r,k));
	}
	return 0;
}

Java语言

这里看好扫描器的使用啊，数据录入不是很方便。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n+1];
			
			String[] s = br.readLine().split(" ");
			for (int i = 1; i < arr.length; i++) {
				arr[i] = Integer.parseInt(s[i-1]);
			}
			int m = Integer.parseInt(br.readLine());
			String[] s1;
			int[][] brr = new int[m][3];
			for (int i = 0; i < m; i++) {
				s1 = br.readLine().split(" ");
				for (int j = 0; j < s1.length; j++) {
					brr[i][j] = Integer.parseInt(s1[j]);
				}
			}
			int a;
			int b;
			int c;
			for (int i = 0; i < m; i++) {
				a = brr[i][0];
				b = brr[i][1];
				c = brr[i][2] - 1;
				int[] brr1 = new int[b - a + 1];
				System.arraycopy(arr, a, brr1, 0, b - a + 1);
				shellSort(brr1);
				System.out.println(brr1[b - a - c]);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
	
	public static void shellSort(int[] arr) {
	    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
	        for (int i = gap; i < arr.length; i++) {
	            int j = i; 
	            int temp = arr[j]; 
	            if (arr[j] < arr[j - gap]) {
	                while (j - gap >= 0 && temp < arr[j - gap]) {
	                    arr[j] = arr[j - gap];
	                    j -= gap; 
	                }
	                arr[j] = temp;
	            }
	        }
	    }
	}
}

Python语言

我们已经不是1次两次看到列表推导式了，应该已经不陌生了，有时间可以专门的捉摸一下列表推导式，很方便好用。

n = input()
n_list = list(map(int,input().split()))
m = int(input())
Ls = []
for i in range(m):
    Ls.append(list(map(int,input().split())))
for j in Ls:
    l=int(j[0])-1
    r=int(j[1])
    k=int(j[2])- 1
    result = sorted(n_list[l:r],reverse=True)
    print(result[k])

 没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第六届——第十三届省赛题解

所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。

第六届——第十二届省赛题解

所有题目均有题解，部分第10题非最优解，至少跑20%数据。

最后

以上就是结实蜻蜓为你收集整理的第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询的全部内容，希望文章能够帮你解决第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。