蓝桥杯Java组省赛备考经验分享_java蓝桥杯如何学习

获奖情况：

• 第11届蓝桥杯javaB组省一，国三
• 第12届蓝桥杯javaB组省一，国二

考前准备

省赛常考知识点(复习 + 背熟模板)

知识点

思维、模拟、图论(最小生成树、并查集、最短路径(spfa、floyd))、数论(最大公约数/最小公倍数、分解质因子、约数定理、欧拉筛)、搜索(暴力、dfs、bfs)、动态规划(背包类、最长上升/下降子序列、最长公共子序列)->(通过暴力求解)、二分(二分查找、二分答案)

常用对象/方法

String类、Set类、Map类、Queue类、Stack类、Math类、Arrays类Sort方法(熟记)、自定义类(排序优先级)

C++组同学可以对应到C++的这些函数
数论
1.最大公约数/最小公倍数(省赛/国赛 化简3/9-> 1/3) 熟记

static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
}
1
2
3

2.分解质因子(省赛/国赛)
国赛C题
3.约数定理(省赛/国赛)

算术基本定理 求一个数的约数个数

算术基本定理：

唯一分解定理 分解素因数：n=(p1^k1)* (p2^k2)…(pn*kn).（分解方式唯一）

n的约数个数为cnt(n)=(1+k1)(1+k2)…*(1+kn).
1
2
3
4
5
6
7

4.欧拉筛（O(nlogn)级别快速求质数）（常用）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
int prime[maxn];
bool vis[maxn];
void sieve(int n)
{
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i]) //不是目前找到的素数的倍数
            prime[cnt++] = i; //找到素数
        for(int j = 0; j < cnt && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = true; //找到的素数的倍数不访问
            if(i % prime[j] == 0) break; //关键！！！！
        }
    }
}
int main()
{
    memset(vis, false, sizeof vis);
    int n;
    cin >> n;
    sieve(n);
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            cnt++;
            cout << i << " ";
            if(cnt % 10 == 0)
                cout << endl;

        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

注意事项

拿分技巧

因为蓝桥杯是按点得分的，所以我们即使不能AC,也要尽可能的去暴力拿分。

• 不要空题，先考虑最优算法，再考虑模拟题意暴力拿分，最后不会暴力的话可以直接printf出样例。
• 借助excel、windows自带计算器，以前省赛的很多填空题都是可以用这两者来做的。
• 由于蓝桥杯不是即时反馈答案的，所以一定要多测几组样例再提交。
• 使用快读\快输模板。
• 较难的算法短时间内不好攻克，建议训练一下暴力思维。