首页 > itarticle > 蓝桥杯及天梯赛查漏补缺与模拟题分析（此文长期更新）

蓝桥杯及天梯赛查漏补缺与模拟题分析（此文长期更新）

admin 11月 14, 2020 0

此文用来整理通过刷题发现的暂时没有学到的但很有用的知识点
另外从本文开始引入播放器，放个歌不容易，下载下来格式一般都不支持，转成mp3才能用。专辑封面也要必须下载或者截图，所以先放近期超喜欢的一首吧！好听不火的宿舍蹦迪神曲：

双向队列

先不说双向队列的事，学习双向队列是因为一道烦人的题：

例题：2019蓝桥杯B组模拟(一)：蒜厂年会

avatar

我的错误代码

用我的话来说：那就是这个程序明明天衣无缝!为什么就是过不了？？以至于我的舍友说我已经具有了程序员的一条必备素质：

对自己的程序极度自信

看我的代码：

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
 

#include <cstdio>
using namespace std;
long long a[200010];
long long ans;
int (){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        scanf("%ld", &a[i]);
        a[i + n] = a[i];
    }
    long long sum = 0;
    int k = 1;
    for(int i = 1; i < k + n; i++){
        if(k > n){
            break;
        }
        if(sum + a[i] < 0){
            sum = 0;
            k = i + 1;
        }
        else{
            sum += a[i];
            if(ans < sum){
                ans = sum;
            }
        }
    }
    cout << ans << endl;
}

首先把环式转成链式
设个k用来记录当前状态下的得到数值是从第几个数字开始计算的，这样就限定了整个循环计算的区间
然而用例过了80%，强迫症，这个代码到底哪里有错不看出来我浑身难受

3月21日更新：
今天重做了这道题，一下就想到了没有考虑到的一种情况：
当k为一定值得时候，sum一直加到k + n也没有小于0，此时获得的最大值并不一定就是最大，只是在当前k值下的最大
所以在得到这段序列之后，可以用双向队列再把剩下的情况遍历一下！

过还是要过的，这就引入了双向队列
除了双向队列之外，还会再介绍一种非常巧妙的方法

双向队列介绍：

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <deque>
deque <int> q;
q.size() 
q.front() //返回队头元素
q.back() //返回队尾元素
q.push_back() //队尾入队
q.pop_back() //队尾出队
q.push_front() //队头队
q.pop_front() //队头出队
q.begin() //返回正向队头迭代器
q.end() //返回正向队尾迭代器
q.rbegin() //返回正向队尾迭代器
q.rend() //返回反向队尾迭代器

双向队列解法源码

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
 

#include <deque>
using namespace std;
int cp[200001];
long long sum[200001];
int (){
    int n;
    cin>>n;
    for(int i = 1; i <= n ;i++){
        cin>>cp[i];
        cp[i + n] = cp[i]; //将环队列变成链式队列
    }
    for(int i = 1; i <= 2 * n; i++){ // 类似于数学中的前n项和的求法
        sum[i] = sum[i - 1] + cp[i];
    }
    deque<int > que; //双向队列 对头保存i前面的sum最小的下标值
    que.push_back(0);
    long long ans = cp[1];
    for(int i = 1; i <= 2 * n; i++){
        if(!que.empty() && que.front() < i - n){
            que.pop_front();
        }
        ans = max(ans, sum[i] - sum[que.front()]);
        while (!que.empty() && sum[que.back()] >= sum[i]) { //维护一个单调队列
            que.pop_back();
        }
        que.push_back(i);
    }
    cout << ans;
    return 0 ;
}

巧妙解法

这个方法的思路是在不循环的数组中找到最小连续和，和最大连续和。
组成两个连续和的所有数字即是构成了整个数组，可能理解起来会有一些困难
所以：如果某一个连续和的区间[l, r]包含了整个数组的第一位和最后一位数字l > r，那么另一个连续和的区间[l, r]就必定没有构成循环l < r
所以最后的结果直接可以写成下面这样：

1
 
max(sum-Mi,Mx);  //sum 为整个数组和，Mi为最小连续和 Mx为最大连续和

下面给出这个思路的源码：

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
 

# define MAXN 200005
# define INFI 0x3f3f3f3f
using namespace std;
long long sum, mx, mi, Mx, Mi;
long long num[MAXN],n;
int (){
    ios::sync_with_stdio(false);
    cin >> n;
    memset(num,0,sizeof(num));
    Mx = -INFI;
    Mi = INFI;
    mx = mi = sum = 0;
    long long tmp = 0;
    for(int i=0; i<n; ++i){
        cin >> num[i];
        sum += num[i];
        mx += num[i];
        mi += num[i];
        Mx = max(Mx, mx);
        Mi = min(Mi, mi);
        if(mi > 0){
          mi = 0;
        }
        if(mx < 0){
          mx = 0;
        }
    }
    cout << max(sum - Mi, Mx) << endl;
    return 0;

贪心

贪心可不是一个社会主义好青年应有的品质！

贪心与动态规划不同，动态规划是完美的，科学的，贪心也不是不科学…需要具体情况具体分析，有点投机取巧的感觉

例题：2019蓝桥杯B组模拟(一)：轻重搭配

avatar
这题我还真不是故意想用贪心，想了半天也不知道该怎么写，就想着用过觉得能过最多组的写法能得多少分是多少分
但在思考的过程中我的思路和贪心的基本思路达到了一致：

  • 只看当前情况下的最优解

其实使用贪心还要满足一条原则：

  • 各个情况的最优能够达到互相不影响

对于此题的贪心，排序后，对于每个后一半的数，在前一半中找到比它小2倍以上的数

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
 

#include <algorithm>
using namespace std;
int a[1000005];
int ans;
bool cmp(int x, int y){
    return x < y;
}
int (){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    sort(a, a + n, cmp);
    int k = 0;
    for(int i = n / 2; i < n; i++){
        if(a[i] >= 2 * a[k]){
            a[i] = 0;
            k++;
            while(a[k] == 0 && k < n){
                k++;
            }
            ans++;
        }
    }
    cout << n - ans << endl;
}

模运算运算法则

基本性质
若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)
(a % p)=(b % p)意味a≡b (% p)
对称性：a≡b (% p)等价于b≡a (% p)
传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)
运算规则
模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a b) % p = (a % p b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）
结合律：
((a + b) % p + c) % p = (a + (b + c) % p) % p （5）
((a b) % p c)% p = (a (b c) % p) % p （6）
交换律：
(a + b) % p = (b + a) % p （7）
(a b) % p = (b a) % p （8）
分配律：
(a + b) % p = ( a % p + b % p ) % p （9）
((a + b) % p c) % p = ((a c) % p + (b c) % p) % p （10）
重要定理
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（11）
若a≡b (% p)，则对于任意的c，都有(a c) ≡ (b c) (%p)；（12）
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a c) ≡ (b * d) (%p)； （13）

为什么要贴出模运算的法则呢，第一：以前看模运算没有仔细学习这里，导致做题做模运算的时候偶尔会心里打鼓
另外：下面的快速幂需要模运算法则，请看：

快速幂

先看题：

例题：2019蓝桥杯B组模拟(二)：充话费

avatar
不会快速幂这道题可以说是完全没法做了
以求a的b次方来介绍
把b转换成2进制数
该2进制数第i位的权为a^（2^(i-1)）
例如
a^11=a^(2^0+2^1+2^3)

1
2
 
11的二进制是   1         0         1         1
11    =    2^3*1  +  2^2*0  +  2^1*1  +  2^0*1

a^11转化为算a^(2^0)a^(2^1)a^(2^3)
用一种东西叫做位运算，正好可以实现这个事情：
结合下面的函数实现来看
（转载，原作者）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//计算快速幂的函数：
// x为底数  p为指数
// & 为逻辑与运算，运算规则：
/*
0 & 0=0
0 & 1=0
1 & 0=0
1 & 1=1
*/
//即当p二进制最后一位为1时，执行res = res * x;
//进行位运算，将指数p位右移一位为1位置并增大x的权值
long long pow_mod(long long x, long long p) {
    long long res = 1;
    while (p){
        if (p & 1){
            res = res * x;
        }
        p >>= 1;
        x = x * x;
    }
    return res;
}

这个函数完美实现了将 a^11转化为算a^(2^0)a^(2^1)a^(2^3)

另外，上面贴出的模运算运算法则：(a b) % p = (a % p b % p) % p （3）
实现了计算过程中数字过大无法存储的问题

下面给出例题的源码

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
 
#include<iostream>
using  namespace std;
const long long mod = 10086;
long long pow_mod(long long x, long long p)
{
    long long res = 1;
    while (p)
    {
        if (p & 1)
        {
            res = res * x % mod;
        }
        p >>= 1;
        x = x * x % mod;
    }
    return res;
}

int ()
{
    long long ans = 0;
    long long tmp = 1e12;
    for (int i = 1; i <= mod; i++){
        ans = (ans + pow_mod(i, 2019)) % mod;
    }        //10086 以内的取模结果
    ans = ans * (tmp / mod) % mod;  //到1e12共有多少个这样的取模结果（对10086取模相同的数字的最终计算结果也相同，所以直接乘上去即可）
    tmp %= mod;      //最后剩下的那些数字，对10086的取模结果
    cout << tmp << endl;
    for (int i = 1; i <= tmp; i++){
        ans = (ans + pow_mod(i, 2019)) % mod;
    }
    cout << ans << endl;
    return 0;
}

关键位置的解释已经写在注释里，注意看

超快的质数的预处理

例题：2019蓝桥杯B组模拟(一)：找质数

avatar
这题无论用多快的方法算质数，还是会超时
为何不反其道而行之呢？我把范围内所有能靠相乘乘出来的数（非质数）都标记出来，剩下的都是质数
看代码~

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
 

#include <cmath>
#include <cstdio>
using namespace std;
bool num[1000000];
int main(){
    int t, a, b;
    scanf("%d", &t);
    for(int i = 2; i <= 1000000; i++){
        num[i] = true;
    }
    for(int i = 1; i * i <= 1000000; i++){
    	if(num[i]){
            for(int j = i * i; j <= 1000000; j += i){
                num[j] = false;
            }
        }
    }
    while(t--){
        scanf("%d", &a);
        for(int j = 2; ; j++){
            b = a - j;
            if(num[b] && num[j]){
               printf("%d %dn", j, b);
                break;
            }
        }
    }
    return 0;
}

太巧了~♫ ♫♬♪♫

2019蓝桥杯B组模拟(一)补全

这一看基本这一套题基本全整理一个遍了，把最后一个补上，这也是唯一一个想好了一遍A的题：
说明深度优先搜索学的还是稍微像点样子的~
（学习深度优先搜索正好是春节期间，待在家没有任何外部的干扰，椅子上一坐就是一天。好怀念那时的效率~）（好想回家啊！学校真的没有好环境。😶）
avatar
avatar
avatar
avatar
看完了这浩浩荡荡的一大串题没有，字多但是分析简化一下非常非常的简单，只要把所有边框靠边界的黑色像素全部删去就可以啦！
没错就是这么简单，，先找到靠边界的边框，然后深度优先搜索下去，再继续找下一个靠边界的边框……
看代码：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
using namespace std;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int map[505][505];
bool vis[11][505][505];
int H, W, N;
bool in(int x, int y){
    return x > 0 && x <= H && y > 0 && y <= W;
}
bool edge(int x, int y){
    return x != 1 && x != H && y != 1 && y != W;
}
bool jud(int x, int y){
    if(!edge(x, y)){
        return false;
    }
    return true;
}
void dfs(int x, int y){
    map[x][y] = 0;
    int nx, ny;
    for(int i = 0; i < 4; i++){
        nx = x + dir[i][0];
        ny = y + dir[i][1];
        if(map[nx][ny] > 0 && in(nx, ny) && !vis[N][nx][ny]){
            vis[N][nx][ny] = true;
            dfs(nx, ny);
        }
    }
    return;
}
int main(){
    cin >> N;
    while(N--){
        cin >> H >> W;
        for(int i = 1; i <= H; i++){
            for(int j = 1; j <= W; j++){
                cin >> map[i][j];
            }
        }
        for(int i = 1; i <= H; i++){
            for(int j = 1; j <= W; j++){
                if(map[i][j] > 0 && !jud(i, j)) {
                    dfs(i, j);
                }
            }
        }
        for(int i = 1; i <= H; i++){
            for(int j = 1; j < W; j++){
                cout << map[i][j] << " ";
            }
            cout << map[i][W] << endl;
        }
    }
}

延迟标记

并查集

善用映射

二进制枚举

0x3f3f3f3f的妙用

未完待续

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能