整体而言偏简单,没有考察高级的算法和数据结构。(当然也许是我不会用...),只能保证样例能过,如果有什么问题欢迎交流。

T1 送分题

15.125GB是多少MB

ans = 15.125 * 1024 = 15488

T2 水题

1200000有多少个约数,只算正的

循环跑一跑就ok了,约数的含义是:如果一个数能够被另一个数整除,另一个数就是这个数的约数。比方说6可以被1,2,3,6整除,那么这四个数就是6的约数。

#include<iostream>
using namespace std;

int cnt = 0;

int main() {
    int a = 1200000;

    for(int i = 1; i <= a ; ++i) {
        if(a % i == 0)
            cnt ++;
    }
    cout << cnt << endl;
    return 0;
}

T3 基本概念

有2019个节点的二叉树,最多有多少个叶子节点

最多的叶子节点,那就是完全二叉树,因为二叉树有一个性质:\(n_0=n_2+1\),如果叶子节点最多说明度为2的节点最多,那就是完全二叉树了,完全二叉树算叶子节点的公式:\(n_0=\left( n+1 \right) /2\)。所以最后的结果是1010。

T4 模拟

1到2019中,统计包含数字9的个数

去年蓝桥杯的原题,直接模拟就行了。

#include<iostream>
using namespace std;

int cnt;

bool is_ans(int i) {
    int x;

    while(i) {
        x = i % 10;  //分别模拟个位百位千位...
        if(x == 9)
            return true;
        i /= 10;
    }
    return false;
}

int main() {
    for(int i = 1; i <= 2019 ; i++) {
        if(is_ans(i)) {   //如果包含9
            cnt ++;         //记录+1
        }
    }
    cout << cnt;
    return 0;
}

T5 模拟

小明对类似于 hello这种单词非常感兴趣,这种单词可以正好分为四段,第一段由一个或多个辅音字母组成,第二段由一个或多个元音字母组成,第三段由一个或多个辅音字母组成,第四段由一个或多个元音字母组成。
给定一个单词,请判断这个单词是否也是这种单词,如果是请输出yes,否则请输出no。
元音字母包括a,e,i,o,u共五个,其他均为辅音字母。

输入:一个单词,只含小写字母
输出:如果满足上述输出yes,不满足输出no

这个题直接模拟,首先用string保存这个单词,然后遍历,将元音字母变成y,辅音字母变成f。第二遍遍历,如果发现前一个字符和后一个字符不同,计数+1。如果第一个字符是y,输出no,如果计数正好为3,输出yes。 talk is cheap, show my code.

#include<iostream>
#include<string>
using namespace std;

char yuanyin[5] = {'a', 'e', 'i', 'o', 'u'};

bool is_yuanyin(char a) {   //判断字符a是否为元音
    for(int i = 0 ; i < 5 ; ++i) {
        if(a == yuanyin[i])
            return true;
    }
    return false;
}

int main() {
    string word;
    cin >> word;
    int num = 0;  //表示次数
    bool state = false; //表示初始状态,为false为辅音
    
    for(int i = 0 ; i < word.length() ; ++i) {
       if(is_yuanyin(word[i])) {
           word[i] = 'y';
       } else 
            word[i] = 'f';
    }

    if(word[0] == 'y') {
        cout << "no" << endl;
        return 0;
    }
    int len = word.length();
    for(int i = 1 ; i < len ; ++i) {
        if(word[i] != word[i - 1]) {
            num ++;
        }
    }

    if(num == 3) //如果恰好转换了三次,输出yes
        cout << "yes";
    else
        cout << "no";
    return 0;
}

时间复杂为\(O\left( n \right) \),常系数估计会有点大,不过单词中的字母个数不超过100肯定应该是没啥问题了。(题目中没给限定时间有点坑,另外我还没见过20个字母以上单词😄)

T6 暴力模拟

在数列\(a\left[ 1 \right] ,a\left[ 2 \right] ,…,a\left[ n \right]\) 中,如果对于下标\(i,j,k\)满足\(0<i<j<k<n+1\)且\(a\left[ i \right] <a\left[ j \right] <a\left[ k \right]\) ,则称\(a\left[ i \right] ,a\left[ j \right] ,a\left[ k \right]\) 为一组递增三元组,\(a\left[ j \right]\) 为递增三元组的中心。给定一个数列,请问数列中有多少个元素可能是递增三元组的中心。

对于 50% 的评测用例,\( 2<=n<=100 \) \( 0<=Num<=1000 \) 。
对于所有评测用例, \( 2<=n<=1000 \) \( 0<=Num<=10000 \) 。

直接三重循环暴力枚举

#include<cstdio>
using namespace std;

int a[1005] , cnt;
bool vis[1005];

int main () {
    int n;
    scanf("%d" , &n);
    for(int i = 0 ; i < n ; ++i) {
        scanf("%d" , a + i);
    }

    for(int i = 0 ; i < n - 2 ; ++i) {
        for(int j = i + 1 ; j < n - 1 ; ++j) {
            for(int k = j + 1 ; k < n  ; ++k) {
                if(!vis[j] && a[i] < a[j] && a[j] < a[k]){
                    cnt ++;
                    vis[j] = true;
                }
            }
        }
    }

    printf("%d" , cnt);
    return 0;
}

这道题估计只能拿一大半的分,时间复杂度为\(O\left( n^3 \right) \),问题规模最大为10的三次方。所以总共运行的次数大概需要10的9次方,计算机一秒可以处理10的8次方到9次方的数,所以有些点可能过不了。

T7 模拟

一个正整数如果任何一个数位不大于右边相邻的数位,则称为一个数位递增的数,例如 1135 是一个数位递增的数,而 1024不是一个数位递增的数。 给定正整数 \( n \),请问在整数 1 至  \( n \)  中有多少个数位递增的数?

输入的第一行包含一个整数  \( n \)
输出一行包含一个整数,表示答案。

对于 40%的评测用例,\( 1<=n<=1000 \)
对于 80% 的评测用例, \( 1<=n<=100000 \)
对于所有评测用例,\(1<=n<=1000000\)

和T4一样,将数字拆分然后比较

#include<iostream>
using namespace std;

bool is_increase(int i) {
    int x = 10;
    while(i) {
        if(x >= i % 10) {
            x = i % 10;
            i /= 10;
        }
        else
            return false;
    }
    return true;
}

int n,  cnt;
int main() {
    
    cin >> n;

    for(int i = 1 ; i <= n ; ++i) {
        if(is_increase(i)) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

时间复杂度为\(O\left( n^2 \right) \),还是只能拿一点分。

T8 dfs

小明想知道,满足以下条件的正整数序列的数量。

1、第一项为\(n\) 2、第二项不超过 \(n\) 3、从第三项开始,每一项小于前两项的差的绝对值。

计算,对于给定的 \(n\) ,有多少种满足条件的序列。

输入:一个整数 \(n\)
输出:一个整数,表示答案,可能很大,输出除以10000的余数

对于 20% 的评测用例,\(1<=n<=5\)
对于 50%的评测用例,\(1<=n<=10\)
对于 80%的评测用例,\(1<=n<=100\)
对于所有评测用例,\(1<=n<=1000\)

这道题应该是用动态规划做,我不会...最后还是用的dfs来搜索,暴力dfs能过50%的数据,如果剪纸应该可以过80%,但是剪枝我学的很菜所以也没用上(tcl),如果剪枝成功的话,可以打表。。。

第一项是题目给的:\(n\),第二项就是从1到\(n\),第三项是从1到abs(前两项的差),abs表示绝对值,递归边界就是这个差小于1。

#include<iostream>
#include<cmath>
using namespace std;

int cnt, a[1005];

void dfs(int x , int y) { //分别表示前一项和当前项
    cnt ++;
    int subtract = abs(x - y);
    
    if(subtract < 1)
        return;
    for(int k = 1; k < subtract ; ++k)
        dfs(y, k);    
}

int main() {
    int n;
    cin >> n;
  
    for(int i = 1 ; i <= n ; ++i)
        dfs(n, i);

    cout << cnt % 10000 << endl;
    return 0;
}

递归的时间复杂度用主定理推,这里推不推都无所谓了。。(要开始好好学剪枝和动规了)

T9 bfs

小明有一块空地,他将 他将这块空地划分为\(n\)行\( m \)列的小块,每行和每列的长度都为 1,小明选了其中的一些小块空地,种上了草,其他小块仍然保持是空地。 这些草长得很快,每个月,草都会向外长出一些,如果一个小块种了草,则它将向自己的上、下、左、右四小块空地扩展,这四小块空地都将变为有草的小块。 请告诉小明,\(k\) 个月后空地上哪些地方有草。

输入:第一行包含\(n\)和 \(m\) ,接下来的 \(n\) 行和 每行\(m\)个字母,表示空地的状态,如果为点表示为空地,如果为g表示长草。接下来的一行包含一个整数\(k\)。
输出:将 \(k\) 个月后的空地输出

对于30%的数据,\(2<=n, m<=20\)。
对于70%的数据,\(2<=n, m<=100\)。
对于所有的额数据,\(2<=n, m <= 1000, 1<=k<=1000\)。

地图题一般用dfs或者bfs,显然这个题是每个月扩散一圈,所以就是bfs了。模板题,唯一需要注意的是,刚开始就需要将所有的起点均加入到队列中,而且标记访问过。(如果你对dfs和bfs不熟悉的可以看看蓝桥杯省赛训练中的内容,讲的很不错)

#include<iostream>
#include<queue>
using namespace std;

char maze[1005][1005];
bool vis[1005][1005];
int dir[4][2] = {{1,0} , {-1,0} , {0,1} , {0,-1}};
int n , m , k;

struct node {
    int x, y , time;
    node (int xx , int yy, int tt) {
        x = xx;
        y = yy;
        time = tt;
    }
};

queue <node> q;

void bfs() {
    int dx, dy;   
   
    while(q.size()) {
        node now = q.front();
        q.pop();

        if(now.time == k)  //如果到达了第k个月,则退出
            break;

        for(int i = 0 ; i < 4; ++i) {    //邻居入队
            dx = now.x + dir[i][0];
            dy = now.y + dir[i][1];

            if(0 <= dx && dx < n && 0 <= dy && dy < m) {
                maze[dx][dy] = 'g';
                if(!vis[dx][dy])
                    q.push(node(dx, dy, now.time + 1));                
            }                
        }
    }
}

int main() {
    cin >> n >> m;

    for(int i = 0 ; i < n ; ++i) {
        for(int j = 0 ; j < m ; ++j) {
            cin >> maze[i][j];
            if(maze[i][j] == 'g') {
                vis[i][j] = true;
                q.push(node(i, j, 0));   //将起点均加入队列
            }
        }
    }
    cin >> k;    
    bfs();
    for(int i = 0 ; i < n ; ++i) {
        for(int j = 0 ; j < m ; ++j) {
            cout << maze[i][j];
        }
        cout << endl;
    }
    return 0;
}

时间复杂度为\(O\left( n*m \right) \),如果细节不出错的话满分应该没啥为题。

T10 贪心?

小明要组织一台晚会,总共准备了 \(n\)个节目。然后晚会的时间有限,他只能最终选择其中的 \(m\) 个节目。 这  \(n\)  个节目是按照小明设想的顺序给定的,顺序不能改变。 小明发现,观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系,他希望选出的第一个节目尽可能好看,在此前提下希望第二个节目尽可能好看,依次类推。 小明给每个节目定义了一个好看值,请你帮助小明选择出  \(m\) 个节目,满足他的要求。

输入:第一行两个整数 \(n\) 和 \(m\)  ,表示节目的数量和要选择的数量。
第二行包含 \(n\) 个整数,依次为每个节目的好看值。
输出:包含 \(m\) 个整数,为选出的节目的好看值。

由于最近几天一直在研究各种背包问题,看这个题的第一眼觉得应该是01背包的变体,物品种数为 \(n\),背包容量为\(m\) ,每个物品的价值就是节目的好看值,物品重量都为1。但是这个和普通01背包不同的是,这道题需要输出具体有哪些物品,而我之前看的基本都是输出最大价值,思考了很久。然后看到了“ 选出的第一个节目尽可能好看,在此前提下希望第二个节目尽可能好看 ”,才意识到应该用贪心的思想,先取最大的、再取第二大的......这样一想之后就很容易了。

我这里使用优先级队列来进行维护:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int a[100005];
bool vis[100005];
priority_queue<int> pq;

int main () {
    int m , n;
    cin >> n >> m;
    for(int i = 0 ; i < n ; ++i) {
        cin >> a[i];
        pq.push(a[i]);
    }

    while(m--) {
        int t = pq.top();
        for(int i = 0 ; i < n ; ++i) {
            if(t == a[i]) {
                vis[i] = true;
                break;
            }                
        }
        pq.pop();        
    }

    for(int i = 0 ; i < n ; ++i) {
        if(vis[i]) {
            cout << a[i] << " ";
        }
    }
    return 0;
}

需要注意的是,输出顺序要按照输入的序列顺序,所以我这里用了一个vis数字来判定这个节目有没有被选。

总结:其实题目难度都不大,最复杂的也就是dfs、bfs。但是主要考察的是优化算法的能力。

立志成为一名攻城狮
最后更新于 2020-03-27