【非官方题解】2022牛客寒假算法基础集训营5

2023-11-01 22:20
文章标签 算法 基础 牛客 2022 题解 寒假 集训营 非官方

本文主要是介绍【非官方题解】2022牛客寒假算法基础集训营5，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2022牛客寒假算法基础集训营5_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

目录

A-疫苗小孩

B-乒乓小孩

C-战棋小孩

D-数位小孩

E-复苏小孩

F-飞车小孩

G-163小孩

H-一六三小孩

I-兔崽小孩

J-三国小孩

K-造梦小孩

A-疫苗小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/A

解题思路：考虑每一针对答案的贡献，可以发现第一针对手速提升没有贡献，只有第二针和第三针对手速提升有贡献，并且贡献值分别与第一二针的间隔、第二三针的间隔有关。可以考虑枚举第二针，这样确定第二针的情况下左右二分第一针和第三针找可以打针的最佳位置，最后再取个最大值即可。下面代码是先预处理出了所有可以打针的位置，然后进行二分查找最佳位置。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005;
char s[N];
int pos[N];int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int n, cnt = 0;scanf("%d%s", &n, s + 1);for(int i = 1; i <= n; i++){if(s[i] == '0') pos[cnt++] = i;}pos[0] = -0x3f3f3f3f, pos[cnt] = 0x3f3f3f3f;ll k, w, q;scanf("%lld%lld%lld", &k, &w, &q);ll ans = 0;for(int i = 1; i <= n; i++){ll res = 0, t1 = 0, t2 = 0;if(s[i] == '0'){int p = lower_bound(pos, pos + cnt, i - k) - pos;t1 = w - abs(i - k - pos[p]) * q;t2 = w - abs(i - k - pos[p - 1]) * q;res += max(max(t1, t2), (ll)0);p = lower_bound(pos, pos + cnt, i + k) - pos;t1 = w - abs(i + k - pos[p]) * q;t2 = w - abs(i + k - pos[p - 1]) * q;res += max(max(t1, t2), (ll)0);}ans = max(ans, res);}printf("%lld\n", ans);return 0;
}

B-乒乓小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/B

解题思路：根据题目的要求进行简单的（不是）分类讨论即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
#include <vector>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
vector<pair<int, int> > ans;int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int t;scanf("%d", &t);while(t--){ans.clear();int x, y, flag = 0;scanf("%d%d", &x, &y);if(x < y){swap(x, y);flag = 1;}if(x < 11){printf("NO\n");continue;}int q = y;while(q >= 11 && (x - q + 2) % 11) q--;if(q >= 11){ans.push_back({q - 2, q});x -= q - 2;y -= q;}while(y >= 11){if(x % 11 == 10){ans.push_back({9, 11});x -= 9;y -= 10;}else{ans.push_back({x % 11, 11});x -= x % 11;y -= 11;}}if(10 * x == 11 * y){printf("NO\n");continue;}q = y;while((x - (q + 2)) % 11 && q + 2 >= 11) q--;if(q + 2 >= 11){ans.push_back({q + 2, q});x -= q + 2;y -= q;}if(x % 11){printf("NO\n");continue;}printf("YES\n");while(x){ans.push_back({11, y});y = 0;x -= 11;}printf("%d\n", ans.size());if(flag){for(auto i : ans){printf("%d %d\n", i.second, i.first);}}else{for(auto i : ans){printf("%d %d\n", i.first, i.second);}}}return 0;
}

C-战棋小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/C

解题思路：由于每场使用礼遇和不使用礼遇对答案的贡献是不同的，而对于不同的情况，使用礼遇和不使用礼遇对答案的贡献无法很好的判断出来，因此需要枚举每一种使用礼遇的组合，最后再将每种的上榜次数取最大值。这里枚举组合用到了状压枚举的方法，即可以令 1 代表使用礼遇，0 代表不使用礼遇，将 n 局游戏抽象成 n 位的二进制数，枚举一遍则是 2^n，然后对于每种组合，将每场的最大值记录下来，进行排序，贪心从大到小进行游戏，每次结束后判断是否上榜，然后对当前组合的答案进行统计即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 25;
int p[N], v[N], w[N], h[N];    // v[]存储每场不使用礼遇的最大值// w[]存储每场使用礼遇的最大值// h[]存储每种使用礼遇的组合中每场的最大值
int n, k, s;int check(int x){int res = 0;while(x){if(x & 1) res++;x >>= 1;}return res;
}int cal(int x){for(int i = 0; i < n; i++){h[i + 1] = ((x >> i) & 1) ? w[i + 1] : v[i + 1];    // ((x>>1)&1)判断第i场是否使用礼遇}sort(h + 1, h + n + 1);int sum = s, res = 0;for(int i = 1; i <= n; i++){sum += h[n - i + 1];if(sum >= p[i]) res++;}return res;
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin >> n >> k >> s;for(int i = 1; i <= n; i++) cin >> p[i];for(int i = 1; i <= n; i++){int a, b, c, d;cin >> a >> b >> c >> d;v[i] = max(a, b);w[i] = max(v[i], max(c, d));}int ans = 0;for(int i = 0; i < (1 << n); i++){    // 状压枚举，二进制中有1则代表使用礼遇if(check(i) == k) ans = max(ans, cal(i));}cout << ans << endl;return 0;
}

D-数位小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/D

解题思路：从一位数开始暴搜每一个符合条件的数，每一次在当前数的末尾加上新的数，判断是否符合题目条件，符合则继续搜，否则就返回，然后只要得到的数落在所给的区间 [l, r] 中并且该数中有 1，就说明该数符合所有条件，答案就可以加一，如果超出 r 则说明没有必要继续搜下去了，则返回，进行下一个搜索，最后直接输出每次搜索累加后的答案即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
ll l, r, ans;bool isprime(ll x){if(x == 0 || x == 1) return false;for(ll i = 2; i * i <= x; i++){if(x % i == 0) return false;}return true;
}void dfs(ll x, int last, int flag){if(x > r) return;if(x >= l && flag) ans++;for(int i = 0; i <= 9; i++){if(isprime(i + last)){dfs(x * 10 + i, i, flag || (i == 1));}}
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin >> l >> r;for(int i = 1; i <= 9; i++){dfs(i, i, i == 1);}cout << ans << endl;return 0;
}

E-复苏小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/E

题目大意：给定一个只含 1，2，3 的字符串，三个鬼的初始能量均为 1，每次遇到 1 时，鬼一吸收鬼二和鬼三各一半能量；遇到 2 时，鬼二吸收鬼一和鬼三各一半的能量；遇到 3 时，鬼三吸收鬼一和鬼二各一半的能量。然后每次询问有两种操作，一种是将字符串某点进行修改，另一种是询问进行字符串某个区间后三者的能量。

解题思路：对于每种情况，如果遇到 1，那么三者能量的变化为(x, y, z)\rightarrow (x + \frac{y}{2} + \frac{z}{2}, \frac{y}{2}, \frac{z}{2})，那么可以考虑矩阵相乘是否能造成这样的变化。可以发现只要将三者能量的矩阵乘上\begin{bmatrix} 1 & 0 & 0\\ \frac{1}{2} & \frac{1}{2} & 0\\ \frac{1}{2} & 0 & \frac{1}{2} \end{bmatrix}就可以得到如上的变化。同理可以构造遇到 2 和 3 情况的矩阵。这样就可以用线段树维护一个能量变化矩阵，然后区间合并即为矩阵相乘。每次询问的答案即为(1, 1, 1)乘上查询得到的变化矩阵。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>#define mid (l + r >> 1)using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 100005;
char c;ll quick_pow(ll a, ll b){ll res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}ll inv(ll x){return quick_pow(x, mod - 2);
}struct Matrix{    // 矩阵ll c[3][3] = {{0, 0, 0},{0, 0, 0},{0, 0, 0}};
}ans;Matrix operator * (Matrix A, Matrix B){    // 矩阵乘法重载Matrix C;for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){for(int k = 0; k < 3; k++){C.c[i][j] = (C.c[i][j] + A.c[i][k] * B.c[k][j] % mod) % mod;}}}return C;
}void init(Matrix &m){ll t = 1 * inv(2) % mod;Matrix emp;m = emp;if(c == '1'){m.c[0][0] = 1;m.c[1][0] = t;m.c[1][1] = t;m.c[2][0] = t;m.c[2][2] = t;}if(c == '2'){m.c[0][0] = t;m.c[0][1] = t;m.c[1][1] = 1;m.c[2][1] = t;m.c[2][2] = t;}if(c == '3'){m.c[0][0] = t;m.c[0][2] = t;m.c[1][1] = t;m.c[1][2] = t;m.c[2][2] = 1;}
}struct node{int l, r;Matrix val;
}tree[N << 2];void sgt_build(int i, int l, int r){    // 建线段树tree[i].l = l;tree[i].r = r;if(l == r){c = getchar();init(tree[i].val);return;}sgt_build(i << 1, l, mid);sgt_build(i << 1 | 1, mid + 1, r);tree[i].val = tree[i << 1].val * tree[i << 1 | 1].val;
}void sgt_modify(int i, int x, int y){  // 单点修改int l = tree[i].l, r = tree[i].r;if(l == r){c = (char)y + '0';init(tree[i].val);return;}if(x <= mid) sgt_modify(i << 1, x, y);else sgt_modify(i << 1 | 1, x, y);tree[i].val = tree[i << 1].val * tree[i << 1 | 1].val;
}void sgt_query(int i, int x, int y){   // 区间查询int l = tree[i].l, r = tree[i].r;if(l >= x && r <= y){ans = ans * tree[i].val;return;}if(x <= mid) sgt_query(i << 1, x, y);if(y > mid) sgt_query(i << 1 | 1, x, y);
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int n, m;scanf("%d%d", &n, &m);getchar();sgt_build(1, 1, n);for(int i = 1; i <= m; i++){int op, x, y;scanf("%d%d%d", &op, &x, &y);if(op == 1){sgt_modify(1, x, y);}if(op == 2){for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){ans.c[i][j] = (i == j) ? 1 : 0;}}sgt_query(1, x, y);Matrix p;p.c[0][0] = p.c[0][1] = p.c[0][2] = 1;p = p * ans;cout << p.c[0][0] << ' ' << p.c[0][1] << ' ' << p.c[0][2] << endl;}}return 0;
}

F-飞车小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/F

解题思路：按照九峰胜率将每个地图进行排序，如果九峰选图，那么一定是从最右边开始选；如果K0u1e选图，那么一定是从最左边开始选。假设当前是第一条信息，游戏进行到第x局，九峰选了第y张图，那么根据排序后这张图的位置就可以判断之前进行的 x - 1 局中九峰选择的局数，设选择过 t 局，那么 t = n - pos + 1。那么在这之前的选图情况一共就有 C_{x - 1}^{t} 种；K0u1e选图同理。那么到第二条信息的时候就需要找上一局之后到这一局的选图数，因此需要存储上一条信息时候的左右端点。以此类推，当到最后一条信息的时候，需要考虑离总游戏局数还差的局数，剩下的局数每局就都有两种可能，要么九峰选图，要么K0u1e选图，设剩下局数为 res，则剩下的总情况为 2^{res}，与之前得到的总方案数相乘即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 100005;
ll t[N], fac[N], invfac[N];    // t[i]存储第i张地图位于胜率排序后的位置// fac[]存储阶乘,invfac[]存储阶乘的逆元struct graph{    // 地图信息ll id, x, y;bool operator < (const graph &u) const{return x * u.y < u.x * y;}
}g[N];struct message{    // 比赛信息ll op, x, y;bool operator < (const message &u) const{return x < u.x;}
}m[N];ll quick_pow(ll a, ll b){ll res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}ll C(ll a, ll b){return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}void init(){fac[0] = invfac[0] = 1;for(int i = 1; i <= N; i++){fac[i] = fac[i - 1] * i % mod;invfac[i] = invfac[i - 1] * quick_pow(i, mod - 2) % mod;}
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int n, k;cin >> n >> k;init();for(int i = 1; i <= n; i++){cin >> g[i].x >> g[i].y;g[i].id = i;}sort(g + 1, g + n + 1);for(int i = 1; i <= n; i++){t[g[i].id] = i;}for(int i = 1; i <= k; i++) cin >> m[i].op >> m[i].x >> m[i].y;sort(m + 1, m + k + 1);int l = 0, r = n + 1;ll ans = 1;for(int i = 1; i <= k; i++){int lastl = l, lastr = r;if(m[i].op == 1){r = t[m[i].y];l += m[i].x - m[i - 1].x - (lastr - r);ans = ans * C(m[i].x - m[i - 1].x - 1, lastr - r - 1) % mod;}if(m[i].op == 2){l = t[m[i].y];r -= m[i].x - m[i - 1].x - (l - lastl);ans = ans * C(m[i].x - m[i - 1].x - 1, l - lastl - 1) % mod;}}ans = ans * quick_pow(2, r - l - 1) % mod;cout << ans << endl;return 0;
}

G-163小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/G

解题思路：在自己的编译器上暴力枚举出答案即可（当然也可以用排列组合计算答案）。

暴力代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;bool check(int i, int j, int k, int x, int y, int z){if(i == j && i == k && i == x && i == y) return true;if(i == j && i == k && i == x && i == z) return true;if(i == j && i == k && i == y && i == z) return true;if(i == j && i == x && i == y && i == z) return true;if(i == k && i == x && i == y && i == z) return true;if(j == k && j == x && j == y && j == z) return true;return false;
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int cnt = 0;for(int i = 1; i <= 13; i++){for(int j = i; j <= 13; j++){for(int k = j; k <= 13; k++){for(int x = k; x <= 13; x++){for(int y = x; y <= 13; y++){for(int z = y; z <= 13; z++){if(check(i, j, k, x, y, z)) continue;cnt++;}}}}}}cout << cnt << endl;return 0;
}

最终答案：18395

H-一六三小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/H

解题思路：瞎搞题，不想补了OvO

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
#include <vector>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
vector<int> p[14][14][14];
vector<string> s[14][14][14];string CHG(int x){if(x==1) return "A";if(x==10) return "T";if(x==11) return "J";if(x==12) return "Q";if(x==13) return "K";return to_string(x);
}void solve(){vector<int> a(6);for(int i = 0; i < 6; i++){char c;while(c = getchar()){if(c == 'A' || c == 'J' || c == 'Q' || c == 'K' || c == 'T' || c >= '2' && c <= '9') break;}if(c == 'T') a[i] = 10;else if(c == 'A') a[i] = 1;else if(c == 'J') a[i] = 11;else if(c == 'Q') a[i] = 12;else if(c == 'K') a[i] = 13;else a[i] = c - '0';}for(int i = 1; i <= 10; i++){random_shuffle(a.begin(), a.end());for(int j = 0; j < 13; j++)for(int k = 0; k < 13; k++){int x = p[a[0]][a[1]][a[2]][j];int y = p[a[3]][a[4]][a[5]][k];if(x + y == 163){cout << s[a[0]][a[1]][a[2]][j] << '+' << s[a[3]][a[4]][a[5]][k] << endl;return;}if(y - x == 163){cout << s[a[3]][a[4]][a[5]][k] << '-' << s[a[0]][a[1]][a[2]][j] << endl;return;}if(x - y == 163){cout << s[a[0]][a[1]][a[2]][j] << '-' << s[a[3]][a[4]][a[5]][k] << endl;return;}if(x * y == 163){cout << s[a[0]][a[1]][a[2]][j] << '*' << s[a[3]][a[4]][a[5]][k] << endl;return;}}}cout << "OvO" << endl;
}int main(){for(int i = 1; i <= 13; i++)for(int j = 1; j <= 13; j++)for(int k = 1; k <= 13; k++){p[i][j][k].emplace_back(i + j + k); s[i][j][k].emplace_back("(" + CHG(i) + "+" + CHG(j) + "+" + CHG(k) + ")");p[i][j][k].emplace_back(i + j - k); s[i][j][k].emplace_back("(" + CHG(i) + "+" + CHG(j) + "-" + CHG(k) + ")");p[i][j][k].emplace_back(i + j * k); s[i][j][k].emplace_back("(" + CHG(i) + "+" + CHG(j) + "*" + CHG(k) + ")");p[i][j][k].emplace_back(i - j + k); s[i][j][k].emplace_back("(" + CHG(i) + "-" + CHG(j) + "+" + CHG(k) + ")");p[i][j][k].emplace_back(i - j - k); s[i][j][k].emplace_back("(" + CHG(i) + "-" + CHG(j) + "-" + CHG(k) + ")");p[i][j][k].emplace_back(i - j * k); s[i][j][k].emplace_back("(" + CHG(i) + "-" + CHG(j) + "*" + CHG(k) + ")");p[i][j][k].emplace_back(i * j + k); s[i][j][k].emplace_back("(" + CHG(i) + "*" + CHG(j) + "+" + CHG(k) + ")");p[i][j][k].emplace_back(i * j - k); s[i][j][k].emplace_back("(" + CHG(i) + "*" + CHG(j) + "-" + CHG(k) + ")");p[i][j][k].emplace_back(i * j * k); s[i][j][k].emplace_back("(" + CHG(i) + "*" + CHG(j) + "*" + CHG(k) + ")");p[i][j][k].emplace_back((i + j) * k); s[i][j][k].emplace_back("((" + CHG(i) + "+" + CHG(j) + ")" + "*" + CHG(k) + ")");p[i][j][k].emplace_back((i - j) * k); s[i][j][k].emplace_back("((" + CHG(i) + "-" + CHG(j) + ")" + "*" + CHG(k) + ")");p[i][j][k].emplace_back(i * (j + k)); s[i][j][k].emplace_back("(" + CHG(i) + "*" + "(" + CHG(j) + "+" + CHG(k) + "))");p[i][j][k].emplace_back(i * (j - k)); s[i][j][k].emplace_back("(" + CHG(i) + "*" + "(" + CHG(j) + "-" + CHG(k) + "))");}int t;cin >> t;while(t--){solve();}return 0;
}

I-兔崽小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/I

解题思路：由于每次睡着需要 k 分钟，因此需要处理出每两条说说的间隔时间，才能判断这期间是否睡着，将间隔时间排序，每次询问二分查找第一个大于 k 时间的间隔，将该点之后的间隔时间累加减去这若干次入睡时间即为总睡眠时间，可以用前缀和进行处理，每次询问O(log\;n)查找，O(1)计算。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005;
ll t[N], dif[N], sum[N];
int n, q;void init(){for(int i = 1; i < n; i++){dif[i] = t[i + 1] - t[i];}sort(dif + 1, dif + n);for(int i = 1; i < n; i++){sum[i] = sum[i - 1] + dif[i];}
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);scanf("%d%d", &n, &q);for(int i = 1; i <= n; i++) scanf("%lld", &t[i]);init();while(q--){ll k, p, ans = 0;scanf("%lld%lld", &k, &p);int pos = upper_bound(dif + 1, dif + n, k) - dif;ans = sum[n - 1] - sum[pos - 1] - k * (n - pos);if(ans >= p) puts("Yes");else puts("No");}return 0;
}

J-三国小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/J

解题思路：对方为了存活，无论我发出杀还是决斗，对方必定要出一张牌（可以是闪、桃、决斗），因此在不知道手牌的情况下，对方可能存活的条件就是他的手牌数大于等于我方杀加决斗的数量，反之对手必败。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);ll n, m, k;cin >> n >> m >> k;if(k >= n + m) cout << "NO" << endl;else cout << "YES" << endl;return 0;
}

K-造梦小孩

原题链接：https://ac.nowcoder.com/acm/contest/23480/K

解题思路：对于水魔爆技能单点操作，可以直接用树状数组存储伤害值；对于玄冰阵技能，多个单点操作，如果 len 很大，那么也可以看作是几个单点操作，和水魔爆操作相同；如果 len 很小，操作很密集，那就不好直接操作了，这时候就需要用到分块操作。记block[i][j]表示最左端点为 j 的块的长度为 i 的伤害量，注意 x 位置不受伤害，故需要进行特判，或者直接单独对 x 点进行伤害减少的操作。对于查询，那些单点操作的查询可直接用树状数组的前缀和查询完成；对于分块的查询，枚举 len，对 x 来说，不满整块的贡献有 x / len + 1，整块的贡献有 x / len，令 k = x % len，则前缀和的贡献为block[len][k] * (x / len + 1) + (block[len][len] - block[len][k]) * (x / len)。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>#define lowbit(x) (x & -x)using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 100005, M = 500;
ll tree[N];
ll block[M + 5][M + 5];
int n, m;void add(int x, int y){while(x <= n){tree[x] += y;x += lowbit(x);}
}ll ask(int x){ll res = 0;while(x > 0){res += tree[x];x -= lowbit(x);}return res;
}ll query(int x){ll res = 0;for(int i = 1; i <= M; i++){if(x % i == 0) res += block[i][i] * (x / i);else res += block[i][x % i] * (x / i + 1) + (block[i][i] - block[i][x % i]) * (x / i);}return res;
}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin >> n >> m;while(m--){int op, x, y, len, l, r;cin >> op;if(op == 1){cin >> x >> y;add(x, y);}if(op == 2){cin >> x >> y >> len;if(len > M){for(int i = x % len == 0 ? len : x % len; i <= n; i += len){add(i, y);}}else{for(int i = x % len == 0 ? len : x % len; i <= len; i++){block[len][i] += y;}}add(x, -y);}if(op == 3){cin >> l >> r;cout << query(r) - query(l - 1) + ask(r) - ask(l - 1) << endl;}}return 0;
}

这篇关于【非官方题解】2022牛客寒假算法基础集训营5的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/326153。

相关文章

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型，3步搞定一个应
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2