比赛链接
牛客周赛 Round 65
A题
思路
谁的单价低就全选哪一个。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, a, b;
void solve()
{cin >> n >> a >> b;if (a <= b){cout << n / a << endl;}elsecout << n / b << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
B题
思路
暴力枚举。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e3 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
char s[N][N];
bool rain(int x, int y)
{return (x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] == '*');
}
bool check(int x, int y)
{int cnt = 0;if (rain(x, y))cnt++;if (rain(x, y + 1))cnt++;if (rain(x + 1, y))cnt++;if (rain(x + 1, y + 1))cnt++;return cnt == 4;
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> s[i][j];}}int ans = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (check(i, j))ans++;}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
C题
思路
从大到小排序，之后交换最大值和最小值的位置，遍历一遍比较谁大谁小即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e3 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;int n;
int a[N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}sort(a + 1, a + 1 + n, [&](int x, int y){ return x > y; });swap(a[1], a[n]);int op1 = 0, op2 = 0;for (int i = 1; i <= n; i++){if (i & 1)op1 += a[i];elseop2 += a[i];}if (op1 > op2){cout << "kou" << endl;return;}if (op1 == op2){cout << "draw" << endl;return;}cout << "yukari" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
D题
思路
k k k最大为 10 10 10，我们考虑使用二进制状压。
对于第 i i i个人，我们将第 j j j个药物能够治疗他的症状情况当作一个二进制数（即当病人的第 k k k位为 1 1 1时，才会保留药物的第 k k k位的 1 1 1的值）。
枚举每一个药物选或不选的情况。即二进制数中，第 k k k位为 1 1 1，则代表使用第 k k k个药物，否则代表不使用第 k k k个药物。如果最后的值 o r or or的结果刚好为病人症状的二进制数，则用当前使用药物的数量更新答案。
时间复杂度： O ( 2 k n k ) O(2^{k}nk) O(2knk)。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e4 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int a[N][25], b[15][25];
string s;
int qmi(int a, int b)
{int res = 1;while (b){if (b & 1)res = res * a;b >>= 1;a = a * a;}return res;
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> s;for (int j = 0; j < m; j++){if (s[j] == '1')a[i][j + 1] = 1;elsea[i][j + 1] = 0;}}cin >> k;for (int i = 1; i <= k; i++){cin >> s;for (int j = 0; j < m; j++){if (s[j] == '1')b[i][j + 1] = 1;elseb[i][j + 1] = 0;}}for (int i = 1; i <= n; i++){vector<int> v;for (int j = 1; j <= k; j++){int res = 0;for (int o = 1; o <= m; o++){if (a[i][o] == 1 && b[j][o] == 1){res += (qmi(2, o - 1));}}v.push_back(res);}int sum = 0;for (int j = 1; j <= m; j++){if (a[i][j] == 1)sum += qmi(2, j - 1);}int minn = inf;for (int val = 0; val < qmi(2, k); val++){int res = 0, cnt = 0;for (int j = 0; j < k; j++){int bit = (val >> j) & 1;if (bit){cnt++;res |= v[j];}}if (res == sum){minn = min(minn, cnt);}}if (minn == inf)minn = -1;cout << minn << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
E题
思路
如果要求最小值：如果 a [ i ] a[i] a[i]为未知气温，则令 a [ i ] = a [ i − 1 ] − x + 1 a[i] = a[i-1] - x + 1 a[i]=a[i−1]−x+1，与温度的下限取 m a x max max。
如果要求最大值：如果 a [ i ] a[i] a[i]为未知气温，则令 a [ i ] = a [ i − 1 ] − x a[i] = a[i-1] - x a[i]=a[i−1]−x，与温度的下限取 m a x max max。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e2 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, x;
int a[N], b[N];
void solve()
{cin >> n >> x;for (int i = 1; i <= n; i++){cin >> a[i];b[i] = a[i];}int ans = 0;// 求最大for (int i = 1; i <= n; i++){if (i == 1){if (a[i] == -999)a[i] = 50;continue;}if (a[i] != -999){if (a[i - 1] - a[i] >= x)ans++;}else{if (a[i - 1] - x >= -50){a[i] = a[i - 1] - x;ans++;}else{a[i] = 50;}}}cout << ans << " ";ans = 0;// 求最小for (int i = 1; i <= n; i++){if (i == 1){if (b[i] == -999)b[i] = -50;continue;}if (b[i] != -999){if (b[i - 1] - b[i] >= x)ans++;}else{b[i] = max(-50ll, b[i - 1] - x + 1);}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
F题
思路
原理同 E E E题，只是改一下数据范围即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, x;
int a[N], b[N];
void solve()
{cin >> n >> x;for (int i = 1; i <= n; i++){cin >> a[i];b[i] = a[i];}int ans = 0;// 求最大for (int i = 1; i <= n; i++){if (i == 1){if (a[i] == -999999999)a[i] = 5e8;continue;}if (a[i] != -999999999){if (a[i - 1] - a[i] >= x)ans++;}else{if (a[i - 1] - x >= -5e8){a[i] = a[i - 1] - x;ans++;}else{a[i] = 5e8;}}}cout << ans << " ";ans = 0;// 求最小for (int i = 1; i <= n; i++){if (i == 1){if (b[i] == -999999999)b[i] = -5e8;continue;}if (b[i] != -999999999){if (b[i - 1] - b[i] >= x)ans++;}else{b[i] = max(-500000000ll, b[i - 1] - x + 1);}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
G题
思路
我们考虑构造 010101... 010101... 010101...或 101010... 101010... 101010...的基地。
当 n n n为偶数时：如果 n 2 > m \frac{n}{2} > m 2n>m，则代表连最起码的基地都无法构造，直接输出 − 1 -1 −1。如果 m − n 2 m - \frac{n}{2} m−2n为奇数，则不可能构造成功，因为每一次操作，都要让基地中最小的数加上 2 2 2。
当 n n n为奇数时：如果 m − n 2 m - \frac{n}{2} m−2n为偶数，则构造 010101... 010101... 010101...这样的基地，否则就构造 101010... 101010... 101010...这样的基地。剩下的操作同偶数。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
void solve()
{cin >> n >> m;if (n % 2 == 0){int op = n / 2;if (op > m || abs(m - op) & 1){cout << -1 << endl;return;}vector<int> v(n + 1, 0);for (int i = 1; i <= n; i++){if (i % 2 == 0)v[i] = 1;}m -= (n / 2);int num = m / (n * 2);for (int i = 1; i <= n; i++){v[i] += num * 2;}m = m - num * n * 2;num = m / n;if (num == 0){for (int i = 1; i <= n; i += 2){if (m <= 0)break;v[i] += 2;m -= 2;}}else{for (int i = 1; i <= n; i += 2){v[i] += num * 2;}m = m - num * n;for (int i = 2; i <= n; i += 2){if (m <= 0)break;v[i] += 2;m -= 2;}}for (int i = 1; i <= n; i++){cout << v[i] << " ";}cout << endl;}else{int op = n / 2; // 1的个数if (op > m){cout << -1 << endl;return;}bool ok = false;if ((abs(m - op) & 1)) // 改为1开头{ok = true;}if (ok)op++;if (op > m){cout << -1 << endl;return;}vector<int> v(n + 1, 0);if (!ok){ // 0开头for (int i = 1; i <= n; i++){if (i % 2 == 0)v[i] = 1;}m -= (n / 2);int num = m / (n * 2);for (int i = 1; i <= n; i++){v[i] += num * 2;}m = m - num * n * 2;num = m / (((n / 2) + 1) * 2);if (num == 0){for (int i = 1; i <= n; i += 2){if (m <= 0)break;v[i] += 2;m -= 2;}}else{for (int i = 1; i <= n; i += 2){v[i] += num * 2;}m = m - num * (((n / 2) + 1) * 2);for (int i = 2; i <= n; i += 2){if (m <= 0)break;v[i] += 2;m -= 2;}}}else{for (int i = 1; i <= n; i++){if (i & 1)v[i] = 1;}m -= ((n / 2) + 1);int num = m / (n * 2);for (int i = 1; i <= n; i++){v[i] += num * 2;}m = m - num * n * 2;num = m / n;if (num == 0){for (int i = 2; i <= n; i += 2){if (m <= 0)break;v[i] += 2;m -= 2;}}else{for (int i = 2; i <= n; i += 2){v[i] += num * 2;}m = m - num * n;for (int i = 1; i <= n; i += 2){if (m <= 0)break;v[i] += 2;m -= 2;}}}for (int i = 1; i <= n; i++){cout << v[i] << " ";}cout << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
