第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-3 算法训练 K好数

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-3 算法训练 K好数

前言

算法训练 K好数

C语言

C 语言

Java语言

Python语言

总结

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

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

前言

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

算法训练 K好数

资源限制

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

问题描述

如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入格式

输入包含两个正整数，K和L。输出格式输出一个整数，表示答案对1000000007取模后的值。

样例输入

4 2

样例输出

7

数据规模与约定

对于30%的数据，KL <= 106；对于50%的数据，K <= 16， L <= 10；对于100%的数据，1 <= K,L <= 100。

题解，题意的核心就是第一句话：如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。我们好好理解这句话就可以。

C语言

话说，参加C组比赛的孩子们，不累吗？

代码语言：javascript复制

#include<stdio.h>
int main()
{
	int i;
	int k;		//进制数
	int l;		//位数
	long long ka[100];		//前
	long long kb[100];		//当前
	long long cont=0;		//计数
	scanf("%d%d",&k,&l);
	kb[0]=ka[0]=0;
	for(i=1;i<k;i  )
	{
		kb[i]=ka[i]=1;
	}
	for(i=2;i<=l;i  )
	{
		int j;
		for(j=0;j<k;j  )
		{
			int m=0;
			for(m=0;m<k;m  )
			{
				if(m<j-1 || m>j 1)
					kb[j] =ka[m];
			}
			
		}
		for(j=0;j<k;j  )
		{
			ka[j]=kb[j];
			ka[j]=kb[j]00000007;
		}
	}
	while(k--)
	{
		cont =ka[k];
		cont=cont00000007;
	}
	printf("%I64dn",cont);
	return 0;
}

C 语言

C 语言也没有什么简便的方法，但是咱们可以相信Python，但是这次可能会失望，其实除了DP没啥好方法。

代码语言：javascript复制

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	int k,l;
	cin>>k>>l;
	long long table[100][100];
	for(int i=0;i<k;i  )
	{
		table[0][i]=1ll;
	}
	table[0][0]=0ll;
	for(int i=1;i<l;i  )
	{
		for(int j=0;j<k;j  )
		{
			long long  x=0;
			for(int y=0;y<k;y  )
			{
				if(y!=j 1 && y!=j-1)
				{
					x =table[i-1][y];
				}
			}
			table[i][j]=x00000007ll;
		}
	}
	long long count=0;
	for(int i=0;i<k;i  )
	{
		count =table[l-1][i];
	}
	cout<<(count00000007ll);
	return 0;
}

Java语言

Java的DP处理，复杂度小一些优先。

代码语言：javascript复制

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int l = sc.nextInt();
        sc.close();
		int[][] dp = new int[l][k];
        /*0不能作为首位*/
        for (int i=1; i<k; i  ){    //第一行后(k-1)个元素都为1
            dp[0][i] = 1;
        }
        for (int i=1; i<l; i  ){
            for (int j=0; j<k; j  ){
                dp[i][j] = otherCount(dp[i-1], j);
            }
        }
        int result = 0;
        for (int i : dp[l-1])
            result =(result   i) % 1000000007;
        System.out.println(result);
    }
    public static int otherCount(int[] dp_row, int n){
        int sum = 0;
        for (int i=0; i<dp_row.length; i  ){
            if (i 1 == n || i-1 ==n){
                continue;
            }
            sum = (sum   dp_row[i]) % 1000000007;
        }
        return sum;
    }
}

Python语言

还是动态规划处理的，因为有列表推导式，代码相对还简约一些。

代码语言：javascript复制

k,l = map(int,input().split())
sum = [[0 for _ in range(l)]for _ in range(k)]
for i in range(k):
    sum[i][0] = 1 
for i in range(1,l):
    z = 0
    for g in range(k):
        z = z sum[g][i-1]
    for j in range(k):
        sum[j][i]=z
        if j-1 != -1:
            sum[j][i]=sum[j][i]-sum[j-1][i-1]
        if j 1 != k:
            sum[j][i]=sum[j][i]-sum[j 1][i-1]
z = 0
for i in range(1,k):
    z = z sum[i][l-1]
print(z00000007)

总结

动态规划在于过程中规律的寻找，我们找到规律后再去解决问题还是比较容易的，就是很多时候没法判断是否是最优解，毕竟我们的脑力还是优先的。但是题目都能搞出来就非常棒了呢。

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

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

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

第六届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123284163
第七届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123285783
第八届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123302677
第九届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123303285
第十届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123319090
第十一届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123320205
第十二届Java省赛C组第一套	https://laoshifu.blog.csdn.net/article/details/123413141
第十二届Java省赛C组第二套	https://laoshifu.blog.csdn.net/article/details/123413271
第十三届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/128891276

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

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

第六届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123440705
第七届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123442982
第八届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123443626
第九届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123443908
第十届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123444946
第十一届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123445601
第十二届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123446589

java https 网络安全 c语言 python

0 人点赞