【牛客】牛客小白月赛97 题解 A - E

A - 三角形

map存一下每个数出现了多少次，再遍历map

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;map<int, int> mp;for (int i = 0; i < n; i ++ ){int x; cin >> x;mp[x] ++ ;}for (auto t : mp){if (t.second >= 3){cout << "YES\n";return;}}cout << "NO\n";return;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;
// 	cin >> t;while (t--){solve();}
}

B - 好数组

数组没有 0 就是好数组

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ ){if (a[i] == 0){cout << "NO\n";return;}}cout << "YES\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

C - 前缀平方和序列

对 x 开方，得到的就是能存在数组里的所有数的个数，我们要取 n 个，也就是 C(sqrt(x), n)

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int Jc[maxn + 1];void calJc()	//求 maxn 以内的数的阶乘 不知道开多少就1e6吧爆不了
{Jc[0] = Jc[1] = 1;for(int i = 2; i < maxn; i++) Jc[i] = Jc[i - 1] * i % mod;
}int pow(int a, int n, int p) // 快速幂取模
{int ans = 1;while (n){if (n & 1) ans = ans * a % p;a = a * a % p;n >>= 1;}return ans;
}int niYuan(int a, int b)	//费马小定理求逆元
{return pow(a, b - 2, b);
}int C(int a, int b) // 组合数
{if(a < b) return 0;return Jc[a] * niYuan(Jc[b], mod) % mod * niYuan(Jc[a - b], mod) % mod;
}void solve()
{calJc();int n, x;cin >> n >> x;int cnt = sqrt(x);int ans = C(cnt, n);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

D - 走一个大整数迷宫

首先需要注意到 c 的值和 b 一点关系都没有，因为 b 不可能对 (p - 1) 有任何贡献

明确这一点之后只需要 bfs 就可以了，注意需要判断 st[x][y][k] 不重复，(x, y) 就是点坐标，k 就是到达该点的余数

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};struct node {int dist, res, x, y;
};void solve()
{int n, m, p;cin >> n >> m >> p;vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )cin >> a[i][j];for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )cin >> b[i][j];int ans = INF;queue<struct node> q;q.push({0, a[1][1] % (p - 1), 1, 1});vector<vector<vector<bool>>> st(n + 1, vector<vector<bool>>(m + 1, vector<bool>(p + 1)));while (q.size()){auto t = q.front();q.pop();if (st[t.x][t.y][t.res]) continue;st[t.x][t.y][t.res] = true;if (t.x == n && t.y == m && t.res % (p - 1) == 0){cout << t.dist << '\n';return;}if (t.dist >= 1e6){cout << -1 << '\n';return;}for (int i = 0; i < 4; i ++ ){int nx = t.x + dx[i], ny = t.y + dy[i];if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;q.push({t.dist + 1, (t.res + a[nx][ny]) % (p - 1), nx, ny});}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

E - 前缀和前缀最大值

a 的前缀最大值数量最多的情况就是把正数全都排在前面的时候，此时数量为 正数个数+1，加的 1 代表最前面的前缀和 0

数量最少的情况就是把负数全都排在正数前面，且正数从小到大排列，这种情况怎么计算呢，因为 b 的值域最大只有100，所以用 cnt_pos[i][j] 表示前 i 个元素中 j 出现的次数，之后计算最多需要多少个正数可以把负数都抵消即可

答案就是最大值-最小值+1

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<int> a(n + 1), pre_neg(n + 1);vector<vector<int>> cnt_pos(n + 1, vector<int>(110));for (int i = 1; i <= n; i ++ ){cin >> a[i];pre_neg[i] = pre_neg[i - 1] - min(a[i], (i64)0);for (int j = 1; j <= 100; j ++ ){cnt_pos[i][j] = cnt_pos[i - 1][j] + (a[i] == j);}} int q;cin >> q;while (q -- ){int l, r;cin >> l >> r;int cnt_plus = 0; // 正数个数for (int i = 1; i <= 100; i ++ ) cnt_plus += cnt_pos[r][i] - cnt_pos[l - 1][i];int sum_tmp = 0; // 当前正数之和int cnt_need = 0; // 需要多少正数和负数抵消for (int i = 1; i <= 100; i ++ ){int cnt = cnt_pos[r][i] - cnt_pos[l - 1][i];if (sum_tmp + i * cnt >= (pre_neg[r] - pre_neg[l - 1])){cnt_need += (pre_neg[r] - pre_neg[l - 1] - sum_tmp) / i;break;}else{cnt_need += cnt;sum_tmp += cnt * i;}}cout << cnt_plus + 1 - (cnt_plus - cnt_need + 1) + 1  << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}