牛客周赛Round147总结
这次真的打的不好呀，就A了三个半题目
这次先写四个题解，剩下的以后再更新吧
目录
A题：小红的字符串计数编辑
简单
B题：小红打舞萌
还是简单
C题：魔物76
区间加 1 后的数组权值快速计算
核心突破口：区间加对相邻差的影响
D题：小红的子序列
线性dp+回溯+分解质因数+筛质数
1. 状态设计
2. 状态转移推导
3. 代码中辅助数组说明
4. 整体流程
A题：小红的字符串计数
![]()
简单
#include<bits/stdc++.h> using namespace std; unordered_map<char,int>a; int main() { string s; cin>>s; for(char c:s)a[c]++; int res=0; for(auto c:a) { if(c.second==1)res++; } cout<<res<<endl; return 0; }B题：小红打舞萌
还是简单
第一次见B题这么简单，没想到后面就难了
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL x; int main() { cin>>x; x/=5; LL n=x/2+x%2; LL res=n*4+(x-n)*3; cout<<res<<endl; return 0; }C题：魔物76
区间加 1 后的数组权值快速计算
核心突破口：区间加对相邻差的影响
这道题的关键在于观察区间加 1 操作到底会改变哪些相邻元素的差。
我们定义相邻差数组s，其中 \(s[i] = a[i+1] - a[i]\)（\(1 \leq i \leq n-1\)）。那么数组的权值可以简化为： \(\text{权值} = \sum_{i=1}^{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[i+1]\) 都在区间内，都加了 1。因此： \(s[i] = (a[i+1]+1) - (a[i]+1) = a[i+1] - a[i]\)差不变！
只有两个位置的差会发生变化：
左边界左侧：\(i = l-1\)。此时 \(a[i]\) 不在区间内（没加 1），\(a[i+1]\) 在区间内（加了 1）。因此： \(s[l-1] = (a[i+1]+1) - a[i] = s[l-1] + 1\)
- 右边界右侧：\(i = r\)。此时 \(a[i]\) 在区间内（加了 1），\(a[i+1]\) 不在区间内（没加 1）。因此： \(s[r] = a[i+1] - (a[i]+1) = s[r] - 1\)
结论：无论区间 \([l, r]\) 有多长，每次操作最多只会改变相邻差数组中的 2 个元素！
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; typedef long long LL; LL a[N]; LL s[N]; int n,q; LL f(int x) { return (x%5+5)%5; } int main() { cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i]; LL res=0; for(int i=1;i<=n-1;i++) { s[i]=a[i+1]-a[i]; res+=f(s[i]); } while(q--) { int l,r; cin>>l>>r; if(l>1) { LL t=s[l-1]; s[l-1]++; res=res-f(t)+f(s[l-1]); } if(r<n) { LL t=s[r]; s[r]--; res=res-f(t)+f(s[r]); } cout<<res<<endl; } return 0; }D题：小红的子序列
线性dp+回溯+分解质因数+筛质数
这题真是害苦了我呀，搭进去一个小时
1. 状态设计
设 (f[i]) 表示以数组第 i 个元素结尾的最长好子序列长度。 初始状态：每个元素单独成序列，故 (f[i] = 1)。
2. 状态转移推导
设当前元素 (x=a[i])，若 x 接在 y 后合法，则 x/y=p（p 为质数），变形得： y=x/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向前回溯，反转后输出序列。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10,M=1e6+10; int n; int a[N]; int f[N]; bitset<M> st; bool flag[M]; int pos[M]; int pre_pos[N]; void get_primes() { st[1]=1; for(int i=2;i<M;i++) { if(st[i])continue; for(int j=i+i;j<M;j+=i)st[j]=1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); get_primes(); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } int res=0; memset(pre_pos, -1, sizeof pre_pos); for(int i=1;i<=n;i++) { f[i]=1; int t=a[i]; for(int j=2;j<=t/j;j++) { if(!st[j]&&t%j==0) { int pre=a[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%j==0)t/=j; } } if(t>1&&!st[t]) { int pre=a[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; res=max(res,f[i]); } cout<<res<<'\n'; vector<int>sum; for(int i=1;i<=n;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)cout<<t<<' '; return 0; }E题以后会更新，未完待续哦~