第十二届蓝桥杯省赛总结

为能更好的为比赛做准备，作出总结！

关于蓝桥杯比赛知识点，网上已有人做出总结，也有其中的知识点讲解：https://blog.csdn.net/GD_ONE/article/details/104061907

此总结给出练习题目的建议。

一、洛谷题单

洛谷推荐提单包含了从基础至进阶的题目，很有新手练至高手的价值。在这些提单中，重要的便是找到自己所不会的、不懂的进而练习，将各个知识点掌握。毕竟蓝桥杯比赛不是靠赌去猜题，同考试一样，唯有绝对的实力才能让自己游刃有余，我也建议每个学生做到这些，包括我自身。因此，建议通读上面链接的知识点，以此排查自己不会的或需加强锻炼的方面。以下以java为例子给出经验。

二、练习方向

首先，是最基础的语法问题，这是必要的，不需多说，看知识点即可。个人觉得java语法方面可注意自定义类的空值问题，即便是数组new出了数组的大小，此时每个元素也仍然是空值，因此数组需注意每个元素需要new出对象进行赋值。

学完了语法，我们仍然需要了解java各个常用实用的类，因为自己不可能还会将这些数据结构写一遍，在了解这些类之前，建议先了解数据结构的链表。因为很多数据结构都以链表基础发展过来，打个比喻，编程语言的语法是数学中的点，链表是线，通过线又能画出各种平面图形，其实很多其他数据结构都是链表的另外一种形式，个人认为树还处于一个复杂的平面结构，则图达到了立体的效果。

在了解了链表的基础上，可以通过刷相应的题来熟悉库中的类了，并在练习过程中会了解到其使用到的数据结构和算法，以此综合学习，我会根据上面链接的知识点慢慢~~（摸鱼）~~更新这方面的题目。可能会创个博客，又或直接挂洛谷的个人博客。

学完以上，便需要将其学精，能灵活运用各种算法和数据结构，这就需要刷更多的题了（你已经是个成熟的刷题人了，要学会自己找题）。

蓝桥杯C组省赛着重基础，因此参加省赛前基础是要学精的，不然估计省一无了，国赛未参加，不议。

通过这次的省赛，二叉树、图论是我的薄弱环节~~（烂透，一题没做成）~~，着重加强这两个数据结构的学习，其他算法和数据结构也不精，学完数据结构~~（怪我寒假不认真，该补的还是要补回来）~~，再各方面学精。

三、学习建议

练题目，不应是为AC而AC，而是从中掌握其知识点。学习时不能逞强，不会便是不会，直奔题解，还不懂直接问人，切忌硬刚题目，30分钟没思路直奔题解或问人，敲出自己的想法还不行也同样。记住，并非人人都是天才，我们是在学习，该不会的就去寻求帮助，学习他人，拓展自己的思路，闭门造车不可行。

题目练习篇(例子)

一、加速幂

由于加速幂是我学的最精的了，又在协会做过讲解，第一篇文章就来讲加速幂。
这里加速幂分为三个部分：基础加速幂，矩阵加速幂和数列加速幂。

基础加速幂

首先来看一个2的19次幂的加速。

这是一个不断给总幂数二分，底数平方的过程。不多说，上代码讲解。

洛谷P1226 【模板】快速幂||取余运算

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long n = sc.nextInt();
        long k = sc.nextInt();
        long ans = 1%k;
        
        String end = (a + "^" + n + " mod " + k +"=");
        //下面循环是核心算法
        while(n!=0)    //幂数分完了即可退出循环
        {

            if((n&1)==1)//判断所剩幂数是否为奇数，是奇数就得乘以一次底数，不能丢失这个奇数幂。
            {
                ans = ans*a%k;
            }
            n>>=1;    //幂数二分并底数平方
            a=(a*a)%k;
        }
        if(ans<0)
            ans=-ans;
        System.out.println(end+ans);
    }
    
}

先以不会出现奇数次幂的16次幂为例，我们可以把16次幂分为2个8次幂，而后4个4次幂，接着8个2次幂，最后才是16个1次幂，简单的无奇数次幂的至此结束。

因此，最简单的就是如此不断将底数平方，平方一次便少一半幂数，直至幂数为零得出答案。

为保证数据通用，那奇数次幂当然得考虑。

以2的19次幂为例，19是一个奇数，直接二分会导致丢失一个幂数，因此在每个奇次幂数的时候由ans乘上一次底数。19÷2=9余1，不能丢失这个奇数幂。注意：并不是2的幂数才除以2，而是因为这是一个二分的过程才将幂数除以2，与开始的底数无关。

奇数与偶数次幂的结合，即得出这里的加速幂。

矩阵加速幂

建立在上面加速幂的基础上，先掌握基础加速幂的情况再看下面，不能理解的建议多多根据代码理解。我没学过矩阵，就根据我的想法理解矩阵。

求矩阵加速幂：设矩阵为A,那么便是快速的求出A的K次幂。

首先，来理解为什么矩阵能加速，基础加速幂是一个数的加速幂，很明显，将一个数看成1X1矩阵就行了。既然一阶矩阵能加速，那么其他阶的自然能行。

先理解两个概念：

单位矩阵：左高右低对角线为1的矩阵，乘以任何矩阵都不变，对应一阶的1。
基础矩阵：所求A的K次幂的A。

上代码讲解。

洛谷P3390 【模板】矩阵快速幂



import java.util.Scanner;

public class Main {
    static int n;
    static long mod = 1000000000+7;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        long m  = sc.nextLong();
        long[][] sq = new long[n][n];    //基础矩阵
        long[][] ans = new long[n][n];//单位矩阵
        for(int i=0;i<n;i++)
        {
            ans[i][i] = 1;    //单位矩阵左高右低对角线为一
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                sq[i][j] = sc.nextInt();
            }
        }
        //加速幂算法
        while(m!=0)//幂数分完停止
        {
            if((m&1)==1)
            {
                ans = mult(ans,sq);//分出一个奇数幂，不能丢失
                m--;
            }
            else
            {
                sq = mult(sq,sq);//基础矩阵平方，对应底数的平方
                m>>=1;
                        
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                System.out.print(ans[i][j]    + " ");
            }
            System.out.println();
        }
        
    }
    //矩阵乘法运算
    private static long[][] mult(long[][] a, long[][] b) {
        long[][] c = new long[n][n];                
        for(int i=0;i<n;i++) //遍历a的行    同时是c的行        
        {
            for(int j=0;j<n;j++)    //遍历b的列  同时是c的列
            {
                for(int k=0;k<n;k++)    //遍历a的列 遍历b的行
                {
                    c[i][j] = (c[i][j]+(a[i][k]*b[k][j]))%mod;
                }
            }
        }
        return c;
    }
}

矩阵加速很简单，只是换成了矩阵的运算方法，相信在基础加速幂的基础上很容易理解。

重要的是弄懂那两个概念，理解不是问题。

数列加速幂

同样先理解上面的点。

此问题为求数列的第几项，如求斐波那契数列的第1883项。

可以从2的19次幂看出，无非是求2的n次幂这个等比数列的第19项，但是基础加速幂只能满足等比数列的求解，因此又有了其他数列的加速求解。

这里的加速是通过矩阵实现的，要矩阵加速便需要得知单位矩阵和基础矩阵，下面是求这两个矩阵的方法。

以斐波那契数列为

上代码。

洛谷P1962 斐波那契数列


import java.util.Scanner;

public class Main {
    static long mod = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long[][] sq = {{1,1},{1,0}};
        long[][] ans = {{1,1},{0,0}};
        if(n<=2)
        {
            System.out.println(1);
            return;
        }
        n-=2;
        while(n!=0){
            if((n&1)==1)
            {
                ans=mutl(ans,sq);
                n--;
            }
            else 
            {
                sq=mutl(sq,sq);
                n>>=1;
                
            }
        }
        System.out.println(ans[0][0]);
    }

    private static long[][] mutl(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    c[i][j] = (c[i][j]+(a[i][k]*b[k][j])%mod)%mod;
                }
            }
        }
        return c;
    }
}