牛客周赛Round147总结

这次真的打的不好呀就A了三个半题目这次先写四个题解剩下的以后再更新吧目录A题小红的字符串计数​编辑简单B题小红打舞萌还是简单C题魔物76区间加 1 后的数组权值快速计算核心突破口区间加对相邻差的影响D题小红的子序列线性dp回溯分解质因数筛质数1. 状态设计2. 状态转移推导3. 代码中辅助数组说明4. 整体流程A题小红的字符串计数简单#includebits/stdc.h using namespace std; unordered_mapchar,inta; int main() { string s; cins; for(char c:s)a[c]; int res0; for(auto c:a) { if(c.second1)res; } coutresendl; return 0; }B题小红打舞萌还是简单第一次见B题这么简单没想到后面就难了#includebits/stdc.h using namespace std; typedef long long LL; LL x; int main() { cinx; x/5; LL nx/2x%2; LL resn*4(x-n)*3; coutresendl; return 0; }C题魔物76区间加 1 后的数组权值快速计算核心突破口区间加对相邻差的影响这道题的关键在于观察区间加 1 操作到底会改变哪些相邻元素的差。我们定义相邻差数组s其中 \(s[i] a[i1] - a[i]\)\(1 \leq i \leq n-1\)。那么数组的权值可以简化为 \(\text{权值} \sum_{i1}^{n-1} f(s[i])\) 其中 \(f(x) ((x \bmod 5) 5) \bmod 5\)作用是将任意整数转换为 \(0 \sim 4\) 之间的模 5 非负余数。现在思考当我们给区间 \([l, r]\) 的所有元素加 1 时s 数组会发生什么变化对于任意 i 满足 \(l \leq i \leq r-1\)\(a[i]\) 和 \(a[i1]\) 都在区间内都加了 1。因此 \(s[i] (a[i1]1) - (a[i]1) a[i1] - a[i]\)差不变只有两个位置的差会发生变化左边界左侧\(i l-1\)。此时 \(a[i]\) 不在区间内没加 1\(a[i1]\) 在区间内加了 1。因此 \(s[l-1] (a[i1]1) - a[i] s[l-1] 1\)右边界右侧\(i r\)。此时 \(a[i]\) 在区间内加了 1\(a[i1]\) 不在区间内没加 1。因此 \(s[r] a[i1] - (a[i]1) s[r] - 1\)结论无论区间 \([l, r]\) 有多长每次操作最多只会改变相邻差数组中的 2 个元素#includebits/stdc.h using namespace std; const int N2e510; typedef long long LL; LL a[N]; LL s[N]; int n,q; LL f(int x) { return (x%55)%5; } int main() { cinnq; for(int i1;in;i)cina[i]; LL res0; for(int i1;in-1;i) { s[i]a[i1]-a[i]; resf(s[i]); } while(q--) { int l,r; cinlr; if(l1) { LL ts[l-1]; s[l-1]; resres-f(t)f(s[l-1]); } if(rn) { LL ts[r]; s[r]--; resres-f(t)f(s[r]); } coutresendl; } return 0; }D题小红的子序列线性dp回溯分解质因数筛质数这题真是害苦了我呀搭进去一个小时1. 状态设计设 (f[i]) 表示以数组第 i 个元素结尾的最长好子序列长度。 初始状态每个元素单独成序列故 (f[i] 1)。2. 状态转移推导设当前元素 (xa[i])若 x 接在 y 后合法则 x/ypp 为质数变形得 yx/p也就是说x 的合法前驱只能是 x 除以自身某个质因数得到的数。遍历 x 的所有不同质因数 p若前驱数值 y 已经出现过则更新 f[i]max(f[i],f[pos[y]]1)3. 代码中辅助数组说明st[]埃氏筛标记合数快速判质数flag[]标记某个数值是否在前方出现过pos[v]记录数值 v 上一次出现的下标快速获取前驱位置pre_pos[i]记录第 i 个元素的前驱下标用于后续回溯答案。4. 整体流程预处理用埃氏筛打表预处理 1e6 内所有质数遍历数组对每个元素分解质因数枚举合法前驱更新 DP 值与前驱下标计算完成后再刷新pos和flag构造答案找到最长序列的结尾位置沿着pre_pos向前回溯反转后输出序列。#includebits/stdc.h using namespace std; const int N2e510,M1e610; int n; int a[N]; int f[N]; bitsetM st; bool flag[M]; int pos[M]; int pre_pos[N]; void get_primes() { st[1]1; for(int i2;iM;i) { if(st[i])continue; for(int jii;jM;ji)st[j]1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); get_primes(); cinn; for(int i1;in;i) { cina[i]; } int res0; memset(pre_pos, -1, sizeof pre_pos); for(int i1;in;i) { f[i]1; int ta[i]; for(int j2;jt/j;j) { if(!st[j]t%j0) { int prea[i]/j; if(flag[pre]) { if(f[i]f[pos[pre]]1) { f[i]f[pos[pre]]1; pre_pos[i] pos[pre]; } } while(t%j0)t/j; } } if(t1!st[t]) { int prea[i]/t; if(flag[pre]) { if(f[i]f[pos[pre]]1) { f[i]f[pos[pre]]1; pre_pos[i] pos[pre]; } } } pos[a[i]] i; flag[a[i]] true; resmax(res,f[i]); } coutres\n; vectorintsum; for(int i1;in;i) { if(f[i]res) { int cur i; while(cur ! -1) { sum.push_back(a[cur]); cur pre_pos[cur]; } break; } } reverse(sum.begin(),sum.end()); for(int t:sum)coutt ; return 0; }E题以后会更新未完待续哦~