首页 💻 数据结构,📝 算法学习

某OJ整理的试题(民间数据)


试题A.组队

题目

1.png
2.png

题意

给出20个人担任1-5号位的得分情况,在20人当中选出5个人使得总得分最大

思路

通过看表很容易看出答案

答案

490


试题B.年号字串

题目

3.png

题意

这题就是求2019的26进制表示(1从A开始)

思路

模拟进制转换

代码

#include <bits/stdc++.h>
using namespace std;
string s = "0ABCDEFGHIGKLMNOPQRSTUVWXYZ", ans;
int n = 2019;

int main(){
    while(n){
        ans += s[n % 26];
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    
    return 0;
}

答案

BYQ


试题C.数列求值

题目

4.png

题意

给出一个斐波那契数列,求第20190324项的最后四位

思路

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] (i >= 4)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e7 + 5;
const int mod = 10000;
int n = 20190324, dp[maxn];

int main(){
    dp[1] = dp[2] = dp[3] = 1;
    for(int i = 4; i <= n; i++)
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
    cout << dp[n] << endl;
    
    return 0;
}

答案

4659


试题D.数的分解

题目

5.png

题意

将2019分解成3个各不相同的正整数之和,不包括2和4,问有多少种情况

思路

按照顺序枚举三个数,中间判断一下是否包含2和4即可

代码

#include <bits/stdc++.h>
using namespace std;
int n = 2019, ans;

bool check(int x){
    while(x){
        int t = x % 10;
        x /= 10;
        if(t == 4 || t == 2) return false;
    }
    return true;
}

int main(){
    for(int i = 1; i <= 2019; i++){
        for(int j = i + 1; j <= 2019; j++){
            int k = 2019 - i - j;
            if(k > j) if(check(i) && check(j) && check(k)) ans++;
        }
    }
    cout << ans << endl;
    
    return 0;
}

答案

40785


试题E.迷宫

题目

6.png
7.png

题意

给出一个30行50列的迷宫(0是空地,1是墙),问从左上角走到右下角的最短路径(需要字典序最小DLRU)

思路

蓝桥杯这种问最短路径问题一般都是BFS,这题(字典序)注意一下move数组的先后顺序就行了

代码

/*
0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 
0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 
0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 
0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 
1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 
0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1 
1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 
0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 
1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 
1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 
1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1 
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 
1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1 
0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 
1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1 
0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 
1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 
0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 
1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0 
0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 
1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 
1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 
*/
#include <bits/stdc++.h>
using namespace std;
int mv[4][8] = {1, 0, 0, -1, 0, 1, -1, 0}, vis[105][105]; // vis记录当前位置有没有走过
int mp[105][105];
struct node{
    int x, y;     // 当前位置
    string step;  // 路径
};
queue<node> q;

bool check(int x, int y){
    return x >= 0 && y >= 0 && x < 30 && y < 50 && mp[x][y] == 0 && vis[x][y] == 0;
}

string bfs(){
    q.push({0, 0, ""}); vis[0][0] = 1;
    while(!q.empty()){
        node head = q.front(); q.pop();
        if(head.x == 29 && head.y == 49) return head.step;
        for(int i = 0; i < 4; i++){
            int dx = head.x + mv[i][0];
            int dy = head.y + mv[i][1];
            if(check(dx, dy)){
                vis[dx][dy] = 1;
                if(i == 0) head.step += "D";
                else if(i == 1) head.step += "L";
                else if(i == 2) head.step += "R";
                else head.step += "U";
                q.push({dx, dy, head.step});
            }
        }
    }
}

int main(){
    for(int i = 0; i < 30; i++)
        for(int j = 0; j < 50; j++)
            cin >> mp[i][j];
    cout << bfs() << endl;
    
    return 0;
}

答案

DDDDRRDURRRRRRDRRDRRDDDLDDLRDDDDDDDDDDDDLRDDLRRRDURRUURRDDDDRDDRRRRRRDDRRURRDDDDLRRRRDRUURUULUUULUULULLDLUULRUURRDRRUULLLLUULRUULLDULURULUULRRDURRURURRRDDDLRRDRRRDDLRRDDLLLDDLRRDDLRDDLDDDDLLDDLLLDLDDDLDDDRRRDRRRRDRRDDDDDDRR


试题F.特别数的和

题目

8.png

题意

问1-$n$中,包含2, 0, 1, 9这四个数字的数的和是多少

思路

从前往后枚举判断即可

代码

#include <bits/stdc++.h>
using namespace std;
int n, ans;

bool check(int x){
    while(x){
        int t = x % 10;
        x /= 10;
        if(t == 2 || t == 0 || t == 1 || t == 9) return true;
    }
    return false;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        if(check(i)) ans += i;
    cout << ans << endl;
    
    return 0;
}

试题G.完全二叉树的权值

题目

9.png
10.png

题意

给出一颗二叉树,问相同深度权值之和最小的深度是哪个

思路

第一层个数是1,第二层个数是2,第三层个数是4...依此类推,注意完全二叉树不是满二叉树,所以最后一层可能不满,答案也有可能爆int,所以我们用long long

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, x, sum, maxv = -1e18, maxv_d; // maxv -> 记录权值和最大, maxv_d -> 最大的权值和的层数

int main(){
    cin >> n;
    for(ll i = 0, length = 1, depth = 1; i < n; depth++, length <<= 1){
        sum = 0;    // 每一层的权值和
        for(ll j = 0; j < length && i < n; j++, i++){
            cin >> x; sum += x;
        }
        if(sum > maxv){
            maxv = sum; maxv_d = depth;
        }
    }
    cout << maxv_d << endl;
    
    return 0;
}

试题H.等差数列

题目

11.png
12.png

题意

给出等差数列中的一些项,输出最短的等差数列的长度

思路

公差是排序后差值最小的两项的差值,注意公差是0时直接输出原始长度即可

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x7fffffff;
int gcd[maxn];
 
int main(){
    vector<int>a;
    int n, minn = inf, x;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    if(a.size() == 1){
        printf("%d\n", n);
        return 0;
    }
    for(int i = 1; i < a.size(); i++){
        gcd[i] = a[i] - a[i - 1];
    }
    minn = gcd[1];
    for(int i = 2; i < a.size(); i++){
        minn = __gcd(gcd[i], minn);
    }
    printf("%d\n", (a[a.size() - 1] - a[0]) / minn + 1);
 
    return 0;
}

试题I.后缀表达式

题目

13.png

题意

给出$n$个"+"和$m$个"-"和$n$+$m$+1个数字,问这些数字组成的后缀表达式中,最大的答案是多少

思路

这个题是后缀表达式,所以相当于带括号计算,减法容易掉坑里,其实最大值后缀表达式相当于所有的加号相加,然后再加上剩下的数(除了最小的数以外), 再减掉最小的数

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, tot, x, s1, s2, sa, sb, mi = 1e9;

int main(){
    cin >> n >> m;
    tot = n + m + 1;
    for(ll i = 1; i <= tot; i++){
        cin >> x;
        if(x > 0) s1++, sa += x;
        else s2++, sb -= x;
        mi = min(mi, abs(x));
    }
    if(m == s2) cout << sa + sb << endl;
    else if(m > s2){
        if(s2) cout << sa + sb << endl;
        else cout << sa + sb - 2 * mi << endl;
    }
    else{
        if(m){
            if(s1) cout << sa + sb << endl;
            else cout << sb - 2 * mi << endl;
        }
        else cout << sa - sb << endl;
    }
    
    return 0;
}

试题J.灵能传输

emmmm说实话这题没读懂,附上y总的视频讲解吧!




文章评论