【题解】牛客编程巅峰赛S1赛季第1场 - 青铜&白银局

总结

1. 没写过函数式编程，十分不习惯
2. 题的不会用，像傻子一样看着屏幕不知道该咋办
3. 罚时罚了五次，还都是***错误

最后成了一个小小的白银……我真是太菜了！

题解

A 移动字母

链接

题意

给出一个字符串，让你把这个字符串中的小写字母移到字符串的最后

思路

众所周知是具有可加性的，所以可以新建一个字符串储存新的字符串，并用记录的个数，将循环一遍如果就累积到计数器中，否则加入串中，然后循环一遍将个加到串中，最后输出即可

代码

class Solution {
    public:
    string change(string s) {
        // write code here
        int n = s.length();
        int cnt = 0;
        string t;
        for (int i = 0; i < n; i++)
            if (s[i] == 'a') cnt++;
            else t += s[i];
        for (int i = 1; i <= cnt; i++)
            t += 'a';
        return t;
    }
};

B 魔法数字

链接

题意

给出两个数，有三种操作：

1. 当前数加
2. 当前数
3. 当前数平方

问最少操作多少次可以变成

思路

广搜

用一个型的队列，第一维是当前数，第二维是所用的步数

根据题目条件设置三个变量分别为加之后的结果、减之后的结果、平方之后的结果，按照常规广搜思路入队列，根据广搜的性质，最先搜到的次数就是答案，返回即可

代码

class Solution {
    public:
        int solve(int n, int m) {
            queue <pair<int, int> > Q;
            int vis[10001], x, y;
            memset(vis, 0, sizeof(vis));
            Q.push({n, 0}), vis[n] = 1;
            while (Q.size()) {
                x = Q.front().first, y = Q.front().second;
                Q.pop();
                if (x == m) return y;
                //a加之后的结果，b减之后的结果，c平方之后的结果
                int a = x + 1, b = x - 1, c = x * x;
                if (a < 1000 && !vis[a]) Q.push({a, y + 1}), vis[a] = 1;
                if (b >= 0 && !vis[b]) Q.push({b, y + 1}), vis[b] = 1;
                if (c < 1000000 && !vis[c]) Q.push({c, y + 1}), vis[c] = 1;
            }
        }
};

C 牛妹的春游

链接

题意

给出需要的面包数和饮料数

给出个背包，每个背包中有个面包，瓶饮料，花费为

求最小花费

思路

二维费用背包问题

比赛的时候不会用。。。。结束之后发现和数组没啥两样

在题解里看到一个大佬说函数参数是可以改名的……于是改成了

其实背包的数量就是

然后就和背包类似了，选或不选这个背包，优化也一样

但是其实是可以买多的，可能会出现减出负数的情况，这个时候只要对负数体积取即可，表示即使当前需要的饮料/面包小于袋子中的饮料/面包数量依然可以购买

最后返回即可

代码

class Solution {
    public:
        int f[2000][2000];
        int minCost(int a, int b, vector<vector<int> >& v) {
            memset(f, 0x3f, sizeof(f));
            f[0][0] = 0;
            for (int i = 0; i < v.size(); i++)
                for (int j = a; j >= 0; j--)
                    for (int k = b; k >= 0; k--)
                        f[j][k] = min(f[j][k], f[max(j - v[i][0], 0)][max(k - v[i][1], 0)] + v[i][2]);
            return f[a][b];
        }
};