蓝桥杯算法训练

暂时不更新了，，，，

1. 区间k大数查询

easy

package suanfa_train;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class k {
	static List<Integer> list = new ArrayList<Integer>();
	static List<Integer> list2 = new ArrayList<Integer>();
	static int i,j;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();//序列长度
		
		for(i=0;i<n;i++) {
			list.add(scan.nextInt());//给定的序列
		}
		
		int m = scan.nextInt();//询问个数
		int start, end, seq;
		String result = "";
		
		for(i=0;i<m;i++) {
			start = scan.nextInt();
			end = scan.nextInt();
			seq = scan.nextInt();
			
			list2.clear();//清空
			for(j=start-1;j<end;j++) {
				list2.add(list.get(j));//拷贝
			}
			Collections.sort(list2);//排序
			result += list2.get(list2.size()-seq) + "\n";
		}
		System.out.println(result);
	}
}

2. 最大最小公倍数

看着表示不会，，，难搞，发现有诀窍

数学知识：如果三个数互为质数,那么这三个数的乘积便为它们的最小公倍数。

有以下二种情况。

1. 当N为奇数时,那么N,N-1,N-2互为质数,很明显N*N-1*N-2是1到N最小公倍数的最大值。
2. • 当N为偶数时,且能被3整除时,N-1,N-2,N-3互质,此时N-1*N-2*N-3是1到N最小公倍数的最大值；
   • 当N为偶数时,但不能被3整除时,N,N-1,N-3互质,此时N*N-1*N-3是1到N最小公倍数的最大值。

package suanfa_train;

import java.util.Scanner;

public class Gongbeishu {
	public static void main(String[] args) {
		long n = new Scanner(System.in).nextLong();
		long result = 0;
		if(n==1) {
			result =  1;
		}else if(n==2) {
			result = 2;
		}else if(n==3) {
			result = 2 * 3;
		}else if(n%2==1) {
			result = n*(n-1)*(n-2);
		}else if(n%2==0) {
			if(n%3==0) {
				result = (n-1)*(n-2)*(n-3);
			}else {
				result = n*(n-1)*(n-3);
			}
		}
		System.out.println(result);
	}
}

3. K好数

使用动态规划，将运算过程用二维数组保存起来

动态规划学习（参考视频）：https://www.bilibili.com/video/BV1xb411e7ww?from=search&seid=18026845084239363645

思路：

• 若k=4，l=3（3位4进制）
• 假设求3开头，即3XX的个数，只需要求XX中0X，1X，3X的个数即可。
• 对于0X，明显，X只要不为1，有0，2，3.同理，1X有1，3，3X有0，1，3
• 3XX中XX的个数=0X+1X+3X=3+2+3=8

所以状态方程是

dp[i][j] = dp[i][j] + dp[i-1][x]（x与j不相邻的变量。）

package suanfa_train;

import java.util.Scanner;

public class Khaoshu {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int k = scan.nextInt();//进制
		int l = scan.nextInt();//位数
		int [][]dp = new int[101][101];//存放结果
		int mod = 1000000007;
		
		int i,j,x;//循环的变量
		for(i=0;i<k;i++) {//长度为1,数量也为1
			dp[1][i] = 1;
		}

		for(i=2;i<=l;i++) {//长度从2开始的
			for(j=0;j<k;j++) {//k进制(0~k-1)
				for(x=0;x<k;x++) {//k进制(0~k-1)
					if(x!=j-1 && x!=j+1) {//x与j不相邻的情况
						dp[i][j] += dp[i-1][x];//固定开头为j，则加上位数-1且开头与j不相邻的情况
						dp[i][j] %= mod;
					}
				}
			}
		}
		int ans =0;
		for(i=1;i<k;i++) {
			ans += dp[l][i];//结果是将所有l位的不同开头加起来
			ans %= mod;
		}
		System.out.println(ans);
	}
}

参考：https://blog.csdn.net/selaotou11/article/details/104716314

4. 结点选择

java有bug，，，很难100分，所以就用c++来做了。

思路：动态规划。

• dp[cur][0]：不选当前结点所能选出的结点最大值。
• dp[cur][1]：选当前结点的能选出的最大值。

初始化

非常重要

v.resize(n+1);

没有这句话，后面v.pushback就会报错。

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> >v;//存储图的二维数组
int dp[100005][2]={0};//动态规划的数组
void dfs(int cur,int pre)//dfs，带的参数为当前结点和上一个结点
{
    for (int i = 0; i < v[cur].size(); ++i) {//循环当前结点的所有结点
        int sub = v[cur][i];//循环中的一个子节点
        if(sub != pre)//子节点和父结点不通
        {
            dfs(sub,cur);//向下递归，当前结点时sub，上一个结点时cur
            //两种情况
            dp[cur][0]+=max(dp[sub][1],dp[sub][0]);
            dp[cur][1]+=dp[sub][0];
        }

    }
}
int main()
{
    int n,a,b;
    cin>>n;
    v.resize(n+1);//初始化
    for (int i = 1; i <= n; ++i) {
        cin>>dp[i][1];
    }
    for (int i = 0; i < n-1; ++i) {
        cin>>a>>b;
        v[a].push_back(b);//存储图
        v[b].push_back(a);
    }
    dfs(1,0);//当前根结点1，没有上一个结点
    cout<<max(dp[1][0],dp[1][1])<<endl;//输出结果
    return 0;
}