牛客编程巅峰赛S1第8场 - 黄金钻石

A.牛牛的分配

Solution

签到题，从大到小排序，多出来的统计，少的看能不能补上，不能补的话就跳出

Code

class Solution {
public:
    /**
     * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
     * @param n int整型 瓶子的数量
     * @param x int整型 牛牛的对瓶中的水量要求
     * @param a int整型vector 每个瓶子中的含水量
     * @return int整型
     */
    int solve(int n, int x, vector<int>& a) {
        sort(a.begin(), a.end(), greater<int>());
        int now = 0, ans = 0;
        for(int i = 0; i < a.size(); i++) {
            if(a[i] >= x) now += a[i] - x;
            else {
                now -= (x - a[i]);
                if(now < 0) break;
            }
            ans++;
        }
        return ans;
    }
};

B.playfair

Solution

模拟题，写得有点长，数据是随机的，不知道写得有没有锅，跟着题意走就行了，注意j全部换成i

Code

class Solution {
public:
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
char maze[10][10];
string Encode(string key, string str) {
    map<char, int> mp;
    for(int i = 0; i < key.size(); i++) {
        if(key[i] == 'j') key[i] = 'i';
    }
    for(int i = 0; i < str.size(); i++) {
        if(str[i] == 'j') str[i] = 'i';
    }
    int l = 0, r = 0;
    for(int i = 0; i < key.size(); i++) {
        if(!mp[key[i]]) {
            mp[key[i]] = 1;
            maze[l][r++] = key[i];
            if(r == 5) r %= 5, l++;
        }
    }
    for(int i = 'a'; i <= 'z'; i++) {
        if(i == 'j') continue;
        if(!mp[i]) {
            mp[i] = 1;
            maze[l][r++] = char(i);
            if(r == 5) r %= 5, l++;
        }
    }
    string p;
    for(int i = 0; i < str.size(); i += 2) {
        if(i + 1 < str.size()) {
            if(str[i] == str[i + 1]) {
                p += str[i], p += str[i + 1];
                continue;
            }
            for(int j = 0; j < 5; j++) {
                vector<pair<int, int> > v(3);
                int cnt = 0;
                for(int k = 0; k < 5; k++) {
                    if(maze[j][k] == str[i]) {
                        v[1] = make_pair(j, k);
                        cnt++;
                    }
                    if(maze[j][k] == str[i + 1]) {
                        v[2] = make_pair(j, k);
                        cnt++;
                    }
                }
                if(cnt == 2) {
                    p += maze[v[1].first][(v[1].second + 1) % 5];  
                    p += maze[v[2].first][(v[2].second + 1) % 5];
                    goto loop;
                }
            }
            for(int j = 0; j < 5; j++) {
                vector<pair<int, int> > v(3);
                int cnt = 0;
                for(int k = 0; k < 5; k++) {
                    if(maze[k][j] == str[i]) {
                        v[1] = make_pair(k, j);
                        cnt++;
                    }
                    if(maze[k][j] == str[i + 1]) {
                        v[2] = make_pair(k, j);
                        cnt++;
                    }
                }
                if(cnt == 2) {
                    p += maze[(v[1].first + 1) % 5][v[1].second];
                    p += maze[(v[2].first + 1) % 5][v[2].second];
                    goto loop;
                }
            }
            vector<pair<int, int> > v(3);
            for(int j = 0; j < 5; j++) {
                for(int k = 0; k < 5; k++) {
                    if(maze[j][k] == str[i]) {
                        v[1] = make_pair(j, k);
                    }
                    if(maze[j][k] == str[i + 1]) {
                        v[2] = make_pair(j, k);
                    }
                }
            }
            p += maze[v[1].first][v[2].second];
            p += maze[v[2].first][v[1].second];
            goto loop;
        } else {
            p += str[i];
        }
        loop:;
    }

    return p;
}
};

C.牛牛摇骰子

Solution

显然范围小的情况下可以bfs，范围大的话肯定是取11最优，那么至少找到一个合适的范围，大的范围用11去做，小的范围bfs暴力找就能得到答案。这里我找的范围是231(3 * 7 * 11)，大于231先处理成231的范围，然后查表。

Code

class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
   int dir[10] = {3, -3, 7, -7, 11, -11};
   int table[505];
    map<int, int> vis;
    int bfs(int x, int ed) {
            vis.clear();
            queue<pair<int, int> > q;
            q.push(make_pair(x, 0));
            while(!q.empty()) {
                    int x = q.front().first;
                    int step = q.front().second;
                    q.pop();
                    if(x == ed) {
                        table[ed] = step;
                        return step;
                    }
                    for(int i = 0; i < 6; i++) {
                            int xx = x + dir[i];
                            if(!vis.count(xx)) {
                                    vis[xx] = 1;
                                    q.push(make_pair(xx, step + 1));
                                    //cout << xx << ' ' << step + 1 << ' ' << ed << "\n";
                            }
                    }
            }
            return 0;
    }
    vector<int> MinimumTimes(vector<int>& arr) {
            vector<int> cons;
            for(int i = 1; i <= 250; i++) {
                bfs(0, i);
            }
            for(int i = 0; i < arr.size(); i++) {
                    if(arr[i] <= 231) {
                        cons.push_back(table[arr[i]]);
                        continue;
                    }
                    int num = (arr[i] - 231) / 11;
                    arr[i] -= 11 * num;
                    cons.push_back(table[arr[i]] + num);
            }
            return cons;
    }
};