蓝桥杯蓝桥杯大赛集训二 题解（校内）

蓝桥杯蓝桥杯大赛集训二 题解（校内）

|
编程

1694 字
|
34 分钟

蓝桥杯蓝桥杯大赛集训二 题解（校内）

贪心 + 模拟？
NP问题
运算性质

1. Boolean

题目：
1

题解 简单判断，然后填充一个新的字符串即可

#include <stdio.h>
char string[1001];
char res[1001];

int main()
{
    scanf("%s", string);
    int i = 0, j = 0;
    while (string[i] != '\0')
    {
        if (string[i + 2] != '\0' && string[i] == 'b' && string[i + 1] == 'o' && string[i+2] == 'o')
        {
            res[j] = 'h';
            j++;
            res[j] = 'u';
            j++;
            i += 3;
        }
        else
        {
            res[j] = string[i];
            j++;
            i++;
        }
    }
    res[j] = '\0';
    printf("%s\n", res);

    return 0;
}

2. 无趣的数

题目：

题解

2

你需要判断一些数n(i)。对于每个数，你可以选择它的某一位使用他的平方替换这一位数（但是平方后必须是一个个位数）。问：有没有可能的操作使得这个数变换后能被9整除。可以输出“YES”否则“NO”

题解: 数位和

(1) 数位和证明
原来的判断：
$$
N \mod 9 = (a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1} + \dots + a_1 \cdot 10 + a_0) \mod 9

$$
可以化简为：
$$
N \mod 9 = (a_k \cdot 1 + a_{k-1} \cdot 1 + \dots + a_1 \cdot 1 + a_0) \mod 9
$$
(2) 平方化简：
对于某一位的数，只有0,1,2,3的平方不会大于10故变换的的时候只需要改变这几位就行了。

  1. 对于0 ,1的变化不会改变结果。不用管
  2. 对于2导致结果增加4 - 2 = 2
  3. 对于3导致结果增加9 - 3 = 6
    故记录这个数中有多少个2 ,3然后在原始的sum上+对应的增量，没加一次判断是否满足数位和。
#include <bits/stdc++.h>

using namespace std;
int N;

int main()
{

    cin >> N;

    for (size_t i = 0; i < N; i++)
    {
        string s;
        long long int sum = 0;
        int num2 = 0, num3 = 0, temp3 = 0, flag = 0;
        cin >> s;
        for (auto &&j : s)
        {
            if (j == '2')
                num2++;
            if (j == '3')
                num3++;
            sum += j - '0';
        }

        if (sum % 9 == 0)
        {

            cout << "YES" << endl;
            continue;
        }
        long long int addnum = 0, count2 = 0, count3 = 0;
        // 尝试枚举sum += (0~num2)个2+(0~num3)个3
        
        bool found = false;

        // 枚举所有可能的count2和count3组合
        for (int count2 = 0; count2 <= num2; count2++)
        {
            for (int count3 = 0; count3 <= num3; count3++)
            {
                // 计算当前组合下的增加值
                addnum = count2 * 2 + count3 * 6; // 2变4增加2，3变9增加6

                // 检查当前组合是否使得和能被9整除
                if ((sum + addnum) % 9 == 0)
                {
                    found = true;
                    break;
                }
            }
            if (found)
                break;
        }

        
        cout << (found ? "YES" : "NO") << endl;
    }

    return 0;
}

3. 数字的 字符串 最大化

题目：

3

你有一个字符串s，由从0到9的数字构成。在一次操作过程中，你可以选择字符串中的任意一个数字（除了0或者最左侧的数字），将它减1，然后将它和它左边相邻的数字交换。
例如，在对字符串1023的一次操作过程中，你可以得到1103或者1022。
找到进行任意多次操作后，你能获得的字典序最大的字符串。

题解：贪心

肯定 大的数在更高位 可以最大化结果，但是由于向高位移动会减小数字，所以不能向前移太远，那就一个个比较呗，尽可能走得远。

#include <bits/stdc++.h>

using namespace std;
int n;

void fucknum(string s)
{
    // 从各位向高位遍历
    // 由于需要比较所以从倒二位开始
    for (int i = s.size() - 2; i >= 0; i--)
    {
        if (i + 1 < s.size() &&s[i] < s[i + 1] - 1)// 判断两个相邻的数是否满足交换条件
        {
            s[i + 1]--;// 交换的代价
            swap(s[i], s[i + 1]);// 执行交换
            i += 2;// 交换后要考虑更小的数会不会比它前面的数更小，因此开始回溯
        }
    }
    cout << s << endl;
}

int main()
{
    cin >> n;

    for (size_t i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        fucknum(s);
    }

    return 0;
}

4. 袜子 其二

题目：

题解：

4

偶数对肯定邻近配对，奇数则需找到那个i；

感觉是对的：（错误思路）

偶数个落单袜子 就邻近配对
奇数个落单袜子 就先找到最大间距的那一对。删除下标为偶的那个袜子（保证左右两边都是偶数个，从而避免使用这个最大的间距），然后调用处理偶数的函数

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

long long int n, k;

void ou(vector<long long int> &diu)
{
    long long int ans = 0;
    for (size_t i = 1; i < k; i += 2)
    {
        ans += diu[i] - diu[i - 1];
    }
    cout << ans << endl;
}



void ji(vector<long long int> &diu)
{
    size_t index1 = 0, index2 = 1;
    // 找到最大间隔的两个数的下标
    for (size_t i = 1; i < k; i++)
    {
        if (diu[i] - diu[i - 1] > diu[index2] - diu[index1])
        {
            index1 = i - 1;
            index2 = i;
        }
    }
    // 删除下标为偶数的那个数
    size_t removeIndex = index1 % 2 == 0 ? index1 : index2;
    diu.erase(diu.begin() + removeIndex);
    k--; // 删除一个元素后k要减1
    ou(diu);
}

int main()
{
    cin >> n >> k;
    vector<long long int> diu(2e5, 0); // 固定大小为2e5
    for (long long int i = 0; i < k; i++)
    {
        cin >> diu[i];
    }
    sort(diu.begin(), diu.begin() + k); // 只对前k个元素排序
   
    
    
    long long int isji = (2 * n - k) % 2;
    if (isji)
    {
        ji(diu);
    }
    else
    {
        ou(diu);
    }

    return 0;
}
`
#### 正解：
偶数邻近配对，奇数的话先遍历的时候记录（记录i左边奇怪值）i(记录i右边奇怪值)。    
然后找到这个`i`使`左 + 右`最小。
代码：
``` c++
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 200009;

inline int read()
{
    int x = 0;
    cin >> x;
    return x;
    
}

int n, k, a[N];
int f[N][2];

int main()
{
    ios::sync_with_stdio(false);
    n = read(), k = read();
    
    
    for (int i = 1; i <= k; i++) {
        a[i] = read();
    }

    if (k & 1)  // 判断 k 是否是奇数
    {
        
        for (int i = 2; i <= k; i++) {
            f[i][0] = f[i - 2][0] + a[i] - a[i - 1];
        }

        
        for (int i = k - 1; i >= 1; i--) {
            f[i][1] = f[i + 2][1] + a[i + 1] - a[i];
        }

        int ans = INT_MAX;
        
        for (int i = 1; i <= k; i++) {
            if (i & 1) {  // 判断 i 是否是奇数
                ans = min(ans, f[i - 1][0] + f[i + 1][1]);
            }
        }
        printf("%d\n", ans);
    }
    else
    {
        int ans = 0;
        
        for (int i = 1; i <= k; i++) {
            ans += a[i + 1] - a[i];
            i++;  // 增加 i 来跳过下一个元素
        }
        printf("%d\n", ans);
    }

    return 0;
}

5. 同构化

题目：
5

题解： DFS 枚举所有可能的映射。

感觉是对的：（错误思路）

直接找出两个图不一样的地方，然后不一样就花费cost修改H。

错误原因在于，没有搞清楚图同构的定义。
图同构要求有一样的图形，但是顶点的编号并不重要，也就是说如果把两个图的节点编号去掉，然后图形一样即可。这些是题目中费用会不一样的原因，因为从H到G可能有很多种点的对应关系

正解：

其实错误的思路也不是没用。
如果我们能遍历到一种H图中的点到G图中的点的映射，那么在用之前的“错误思路”就行了。
代码：

#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> G, H, mycost;
vector<int> perm;
int result = INT_MAX;

void dfs(int idx, vector<bool> &used)
{
    if (idx == N)// 如果映射数目已经达到点的数目，说明已经构建了一种映射。计算这种映射下的费用。
    {
        // 计算当前排列下的修改费用
        int total_cost = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                int u = i, v = j;
                int x = perm[u], y = perm[v];// u,v是H未经映射的点，x,y是H映射后的点。
                if (G[u][v] != H[x][y])
                {
                    total_cost += mycost[x][y];
                    if (total_cost >= result)
                        return; // 剪枝
                }
            }
        }
        result = min(result, total_cost);
        return;
    }

    for (int i = 0; i < N; i++)// 排列组合 构建各种可能的映射
    {
        if (!used[i])
        {
            used[i] = true;
            perm[idx] = i;
            dfs(idx + 1, used);
            used[i] = false;
        }
    }
}

int main()
{
    cin >> N;
    G.assign(N, vector<int>(N, 0));
    H.assign(N, vector<int>(N, 0));
    mycost.assign(N, vector<int>(N, 0));

    int MG;
    cin >> MG;
    for (int i = 0; i < MG; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a - 1][b - 1] = G[b - 1][a - 1] = 1;
    }

    int MH;
    cin >> MH;
    for (int i = 0; i < MH; i++)
    {
        int a, b;
        cin >> a >> b;
        H[a - 1][b - 1] = H[b - 1][a - 1] = 1;
    }

    // 读取每对边的修改代价
    for (int a = 1; a <= N; a++)
    {
        for (int b = a + 1; b <= N; b++)
        {
            int tmp;
            cin >> tmp;
            mycost[a - 1][b - 1] = mycost[b - 1][a - 1] = tmp; // 无向图，代价是双向的
        }
    }

    perm.resize(N);
    vector<bool> used(N, false);
    dfs(0, used);

    cout << result << endl;

    return 0;
}

6. 我什么事情都愿意做

题目：
6

题解

就是一个搜索的题目。但是题解说用的（DP或者贪心，反正我看不懂）

  1. BFS 会有两个超时的测试点（想想觉得也很正常，毕竟先搜索的局部所有的可能，在探索下一个）
    即使优化了搜索路径，然后剪枝了，还是会有俩超时，所以不推荐。
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring> // 用于 memset
using namespace std;

// 定义状态：当前位置和剩余的游泳距离
struct State
{
    int pos;      // 当前所在的位置
    int swimLeft; // 剩余的游泳距离
};

bool canCross(int n, int m, int k, const string &river)
{
    if (m >= n + 1)
    {
        return true; // 如果跳跃距离大于等于河流长度，直接返回 true
    }

    // 队列用于BFS
    queue<State> q;
    // visited[pos][swimLeft]: 记录某位置和剩余游泳距离的访问情况
    vector<vector<bool>> visited(n+2, vector<bool>(k + 2, false));

    // 初始化起点
    q.push({0, k});
    visited[0][k] = true;

    while (!q.empty())
    {
        State current = q.front();
        q.pop();
        int pos = current.pos;
        int swimLeft = current.swimLeft;

        // 如果到达终点，返回 true
        if (pos == n + 1)
            return true;

        // 1. 尝试跳跃
        if (river[pos] != 'W'||pos==0)
        { // 只有在路面（L）或水岸（W）时才能跳跃
            for (int jump = m; jump >= 1; --jump)
            {
                int nextPos = pos + jump;
                if (nextPos >= n+1)
                    return true; // 如果跳跃后超出河流长度，直接返回 true
                if (river[nextPos] != 'C' && !visited[nextPos][swimLeft])
                { // 非死亡地板
                    visited[nextPos][swimLeft] = true;
                    q.push({nextPos, swimLeft});
                }
            }
        }

        // 2. 尝试游泳
        if (river[pos] == 'W' && swimLeft > 0)
        { // 当前是水面并且还可以游泳
            int nextPos = pos + 1;
            if (nextPos >= n+1)
                return true; // 如果游泳后超出河流长度，直接返回 true

            if (nextPos < n && river[nextPos] != 'C' && !visited[nextPos][swimLeft - 1])
            {
                visited[nextPos][swimLeft - 1] = true;
                q.push({nextPos, swimLeft - 1});
            }
        }
    }

    // 如果队列空了还没有到达终点，返回 false
    return false;
}

int main()
{
    int t; // 数据组数
    cin >> t;

    while (t--)
    {
        int n, m, k;
        string river;
        cin >> n >> m >> k >> river;

        // 调用函数判断能否过河
        if (canCross(n, m, k, river))
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }

    return 0;
}
  1. DFS 非常快
#include <iostream>
#include <string>
using namespace std;

bool dfs(int pos, int n, int m, int k, int swam, const string& river, bool* visited) {
    // 到达终点
    if (pos == n + 1) return true;
    
    // 超出游泳距离限制
    if (swam > k) return false;
    
    // 已访问过的位置
    if (visited[pos]) return false;
    visited[pos] = true;
    
    // 当前在岸上或木头上
    if (pos == 0  || river[pos-1] == 'L') {
        // 尝试跳跃
        if (pos + m >= n + 1)
        {
            return true;
        }
        
        for (int jump = m; jump >= 1 && pos + jump <= n + 1; jump--) {
            int newPos = pos + jump;
            // 不能跳到鳄鱼处
            if (newPos <= n && river[newPos-1] == 'C') continue;
            
            // 跳到水里需要计算游泳距离
            int newSwam = swam;
            if (newPos <= n && river[newPos-1] == 'W') newSwam++;
            
            if (dfs(newPos, n, m, k, newSwam, river, visited)) return true;
        }
    }
    // 当前在水里
    else if (river[pos-1] == 'W') {
        // 只能游到下一格
        if (pos + 1 <= n && river[pos] != 'C') {
            int newSwam = swam;
            if (pos + 1 <= n && river[pos] == 'W') newSwam++;
            
            if (dfs(pos + 1, n, m, k, newSwam, river, visited)) return true;
        }
    }
    
    return false;
}

void solve() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        string river;
        cin >> river;
        
        bool* visited = new bool[n + 2]();
        bool result = dfs(0, n, m, k, 0, river, visited);
        cout << (result ? "YES" : "NO") << endl;
        
        delete[] visited;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

7. 划分

题目：
7

题解

出现了数组连续和，所有考的是前缀和。
思考：如果把前面某个数移动到后面去，那么前后两部分相差的就是2a(i)。所以这个题目就转化成了，找到一个划分点i使得前后的前缀和相差2a(i)。

#include <bits/stdc++.h>
using namespace std;

int t;

// 建议将函数名更改为有意义且符合编码规范的名称，例如 `checkPartition`。
void checkPartition(vector<int> &num, int &n)
{
    set<int> ai2;
    for (int i = 1; i <= n; i++)
    {
        ai2.insert(num[i] * 2);
    }

    // 求前缀和
    vector<int> pre(n + 1, 0); // 1-based索引，大小为n+1
    pre[1] = num[1];
    for (int i = 2; i <= n; i++)
    {
        pre[i] = pre[i - 1] + num[i];
    }

    // 遍历每个位置i
    for (int i = 1; i <= n; i++)
    {
        int left = pre[i];
        int right = pre[n] - pre[i];
        if (left == right)
        {
            cout << "YES" << endl;
            return;
        }
        // 查找元素
        if (ai2.find(abs(left - right)) != ai2.end())
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> num(n + 1, 0); // 1-based索引，大小为n+1
        for (int i = 1; i <= n; i++)
        {
            cin >> num[i];
        }
        checkPartition(num, n);
    }

    return 0;
}// 不知道为什么 有一个例子过不了 QAQ
C++算法蓝桥杯
暂无评论

发送评论 编辑评论












  















|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!



上一篇


推荐文章
蓝桥杯蓝桥杯大赛集训一 题解（校内）


2024第十五届蓝桥杯 C/C++B组 题解


P1306 斐波那契公约数


Tiny_python（基础数学）


P3397 地毯（差分）