牛客编程巅峰赛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;
}
}; 
