牛客小白月赛133
这次感觉难度适中吧，A了四个题
看题吧
目录
A题：愿望魔镜：真题的倒影
签到题
B题：桃夭：花树的高度博弈
博弈策略解释
结果推导
C题：魔法少女：愿望卷轴与真名刻印
核心思路
代码执行步骤
D题：魔力共鸣：最小公倍数的融合
分解质因数
A题：愿望魔镜：真题的倒影
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int main() { string s; cin>>s; if(s=="awdec")cout<<"Fantasy_Blue"<<endl; else if(s=="Fantasy_Blue")cout<<"awdec"<<endl; else cout<<"other"<<endl; return 0; }签到题
B题：桃夭：花树的高度博弈
博弈策略解释
先手（最大化 LIS）最优策略：每次将当前最小的未使用数放在最左侧的空位置，逐步构建从左到右的小数序列。
- 后手（最小化 LIS）最优应对：每次将当前最大的未使用数放在先手刚放的数的右侧，用大数隔开先手的小数，尽可能阻止长上升序列形成。
结果推导
以 n=6 为例，双方最优操作后的序列为：[1,6,2,5,3,4]
- 先手依次放：1→2→3（共 3 步，n/2=3）
- 后手依次放：6→5→4（共 3 步）
- 最终 LIS 为
1,2,3,4，长度 = 3+1=4，正好是n/2+1。
后手只能用大数隔开先手的小数，但最后一个小数必然会被放在末尾，与先手的最后一个小数形成上升，因此 LIS 长度固定为n/2+1。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int main() { int t; cin>>t; while(t--) { int n; cin>>n; cout<<n/2+1<<endl; } return 0; }C题：魔法少女：愿望卷轴与真名刻印
这个题真的是细节比较多
尤其是在代码实现上
核心思路
我们的目标是找到两个不重叠的位置，分别修改成 "awdec" 和 "Fantasy_Blue"，使得总修改次数最少，再判断是否≤k。
代码执行步骤
- 边界判断：如果字符串长度小于 17（两个子串总长度），直接输出 No，不可能放下两个不重叠的子串。
- 预处理代价数组：遍历字符串所有可能的起始位置，分别计算每个位置改成 "awdec" 需要的修改次数（存入 cost1），以及改成 "Fantasy_Blue" 需要的修改次数（存入 cost2）。
- 计算 A 在 B 左边的最小代价：从后往前遍历 A 的所有位置，同时维护右边所有合法 B 位置的最小修改代价。这样每个 A 的位置都能直接得到右边最优的 B 位置，总代价就是 A 的代价加这个最小值。
- 计算 B 在 A 左边的最小代价：从前往后遍历 A 的所有位置，同时维护左边所有合法 B 位置的最小修改代价，同样计算总代价。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int cost1[N],cost2[N]; string s1="awdec"; string s2="Fantasy_Blue"; const int l1=5,l2=12; int n,t,k; int main() { cin>>t; while(t--) { memset(cost1,0,sizeof cost1); memset(cost2,0,sizeof cost2); cin>>n>>k; if(n<l1+l2) { cout<<"No"<<endl; continue; } string s; cin>>s; for(int i=0;i<=n-l1;i++) { int cnt=0; for(int j=0;j<l1;j++) { if(s[i+j]!=s1[j])cnt++; } cost1[i]=cnt; } for(int i=0;i<=n-l2;i++) { int cnt=0; for(int j=0;j<l2;j++) { if(s[i+j]!=s2[j])cnt++; } cost2[i]=cnt; } int res=1e9; int mi2=1e9; for(int i=n-l1;i>=0;i--) { int j=i+l1; if(j<=n-l2)mi2=min(mi2,cost2[j]); if(mi2!=1e9)res=min(res,cost1[i]+mi2); } mi2=1e9; for (int i = 0; i <= n - l1; ++i) { int j = i - l2; if (j >= 0) { mi2 = min(mi2, cost2[j]); } if (mi2 != 1e9) { res = min(res, cost1[i] + mi2); } } if(res<=k) { cout<<"Yes"<<endl; } else cout<<"No"<<endl; } return 0; }D题：魔力共鸣：最小公倍数的融合
分解质因数
每次操作将两个数合并为它们的 lcm，本质是：
- lcm (x,y) 被质数 p 整除 ⇨ x 或 y 被 p 整除
- 要让最终所有数的 gcd>1，只需存在一个质数 p，所有数都被 p 整除
- 对于质数 p，已有 c 个数被 p 整除，只需将剩下 n-c 个数分别与任意一个被 p 整除的数合并，共需 n-c 次操作
因此答案就是：n 减去所有质数中出现次数最多的那个质数的出现次数
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; bool st[N]; int primes[N]; int cnt; int t,n; int a[N]; int c[N]; void get_primes() { for(int i=2;i<N;i++) { if(st[i])continue; primes[cnt++]=i; for(int j=i+i;j<N;j+=i)st[j]=true; } } int main() { get_primes(); ios::sync_with_stdio(false); cin.tie(nullptr); cin>>t; while(t--) { memset(c,0,sizeof c); cin>>n; bool flag=true; for(int i=0;i<n;i++) { cin>>a[i]; if(a[i]!=1)flag=false; } if(flag) { cout<<"-1"<<endl; continue; } for(int i=0;i<n;i++) { int x=a[i]; if(x==1)continue; for(int j=0;primes[j]*primes[j]<=x;j++) { if(x%primes[j]==0) { c[primes[j]]++; while(x%primes[j]==0)x/=primes[j]; } } if(x>1)c[x]++; //cout<<x<<endl; } int max_c=0; for(int i=0;i<cnt;i++) { max_c=max(max_c,c[primes[i]]); } cout<<n-max_c<<endl; } return 0; }