牛客寒假训练营(二)题解(持续更新中)
A
思路:模拟题
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i ++ ) {
int level = 0;
int a, b, c;
cin >> a >> b >> c;
if (a == 100) level += 0;
if (a == 150) level += 1;
if (a == 200) level += 2;
if (b == 29 || b == 30 || b == 31 || b == 32)
level += 0;
if (b == 34 || b == 36 || b == 38 || b == 40)
level += 1;
if (b == 45) level += 2;
if (c == 29 || c == 30 || c == 31 || c == 32)
level += 0;
if (c == 34 || c == 36 || c == 38 || c == 40)
level += 1;
if (c == 45) level += 2;
cout << level << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t -- ) {
solve();
}
return 0;
}
B题
思路:
标记小猫所在位置,如果小猫所在位置上下左右没有加猫网,sum ++。
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using i64 = long long;
const int N = 310;
bool st[N][N];
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<pair<int, int>> a(k);
int sum = 0;
for (int i = 0; i < k; i ++ ) {
int x, y;
cin >> x >> y;
a[i] = {x, y};
}
for (int i = 0; i < k; i ++ ) {
int x = a[i].x;
int y = a[i].y;
if (!st[x - 1][y]) sum ++;
if (!st[x + 1][y]) sum ++;
if (!st[x][y - 1]) sum ++;
if (!st[x][y + 1]) sum ++;
st[x][y] = true;
}
cout << sum << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
I题
思路:
$$w_i=\begin{cases}
0 & u = v \\
|a_u + a_v| + |a_u - a_v| & u \neq v\\
\end{cases}$$
结合上图和$w_i$的公式可推出
共有两种选择:
1, 不绕路:1 -> 2, 2 -> 3, 1 -> 3
2, 绕路: 1 -> 2, 2 -> 3, 1 -> 2 -> 3
由于1 -> 2 + 2 -> 3 $>$ 1 -> 3,所以最短路一定是不绕路
$w_i = 2max(a_v, a_u)$
因此排序后计算当前的最短路即可
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
}
sort(a.begin(), a.end());
i64 sum = 0;
for (int i = 0; i < n; i ++ ) {
sum += a[i] * i;
}
cout << sum * 4 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
J题
思路:
$$w_i=\begin{cases}
0 & u = v \\
|a_u + a_v| - |a_u - a_v| & u \neq v\\
\end{cases}$$
由上图可知最短路一定是选择绕路
结合$w_i$的公式可得$w_i = min(a_0, 2a_i)$
如何计算呢?
只需要将上面的环形图换成下面的矩阵图:
$$
\begin{bmatrix}
0 & 0 & 0 \\
2 & 0 & 0 \\
2 & 4 & 0 \\
\end{bmatrix}
$$
由此可发现排序后同一列的数字都是一样的
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<i64> a(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
}
sort(a.begin(), a.end());
i64 sum = 0;
for (int i = 0; i < n; i ++ ) {
sum += 1LL * (n - i - 1) * min(a[i], 2 * a[0]);
}
cout << 4 * sum << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
E
思路:
比如1 1 1 2 2 第一次消除 1 2 2 第二次消除 1 第三次消除 1
因此只需要消除3次就可全部消除
算法:双指针
倒着循环一遍,碰到跟最后一个不一样的就让ans + 1,
1 1 1 2 2 最后 i 指向 a[1] now = -1; 此时 ans += i, 因为是从0开始的 ans 需要加1
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
}
int res = 0;
for (int i = n - 1; i >= 0; i -- ) {
int now = i;
while (now >= 0 && a[now] == a[i]) {
now --;
// cout << now << '\n';
}
if (now < 0) {
res += i;
}
res ++;
i = now;
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
K题
本题数据范围小 考虑dfs即可
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
int n;
vector<int> st(10), cur(10), pre(10);
string s,t;
i64 res, tmp;
void dfs(int i, i64 sum) {
if(i == n) {
if(sum <= tmp && sum % 8 == 0) {
res = (res + 1) % mod;
}
return;
}
if(isdigit(s[i])) {
dfs(i + 1, sum * 10 + s[i] - '0');
}
else if(s[i] == '_') {
for(int j = 0; j <= 9; j++) {
if(n > 1 && i == 0 && j == 0) continue;
dfs(i + 1, sum * 10 + j);
}
}
else {
if(pre[s[i] - 'a'] == i) {
for(int j = 0; j <= 9; j++) {
if(n > 1 && i == 0 && j == 0) continue;
bool flag =false;
for(int k = 0; k < 4; k++)
if(k != s[i] - 'a' && cur[k] == j) {
flag = true;
}
if(flag) continue;
cur[s[i] - 'a'] = j;
dfs(i + 1, sum * 10 + j);
cur[s[i] - 'a'] = -1;
}
}
else {
dfs(i + 1, sum * 10 + cur[s[i] - 'a']);
}
}
}
void solve() {
cin >> n;
cin >> s >> t;
if(n > 1 && s[0] == '0') {
cout << "0\n";
return ;
}
for(int i = 0; i < 4; i++) {
st[i] = 9;
pre[i] = -1;
cur[i] = -1;
}
tmp = 0;
for(int i = 0; i < n; i++) {
tmp = tmp * 10 + t[i] - '0';
if(s[i] == '_') continue;
if(isdigit(s[i])) {
continue;
}
if(pre[s[i] -'a'] == -1) pre[s[i] - 'a'] = i;
st[s[i]-'a'] = min(st[s[i]-'a'], t[i] - '0');
}
res = 0;
dfs(0, 0);
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while(T--) {
solve();
}
return 0;
}