199 字
1 分钟
11月刷题记录
无忧旋律 - 题目 - QOJ.ac
int n,k;
void solve(){ cin>>n>>k; vector<int> arr(n),tj(k); for(int i=0;i<n;i++){ cin>>arr[i]; } for(int i=0;i*k<n;i++){ for(int j=0;j<k&&i*k+j<n;j++){ if(arr[j+i*k]<=k){ tj[(arr[j+i*k]+(k-j-1))%k]++; } } } int ans=0; for(int i=0;i<k;i++){ ans=max(ans,tj[i]); } cout<<n-ans<<"\n";}P16236 [蓝桥杯 2026 省 B] LQ 聚合 - 洛谷
有限时间内自己写出的最好的答案50pt,不过没过样例
void solve(){ cin>>n>>s; int cntl=0,cntq=0; for(int i=0;i<n;i++){ if(s[i]=='Q')cntq++; } ll ans=0; for(int i=0;i<n;i++){ if(s[i]=='L'){ cntl++; ans+=cntq; } else if(s[i]=='Q'){ cntq--; } if(s[i]=='?'){ if(cntl>cntq){ ans+=cntl; } else{ ans+=cntq; cntl++; } } } cout<<ans;}具体贪心思路是断断续续的LQ序列没有相对完整的LQ序列的贡献高,可以做出一些小牺牲(左边的一些Q可能没有用),需要找到一个分界点,满足最少牺牲换取最大收益,逻辑上找分界线,实际上用前缀和,后缀和预处理L和Q简化计算,先将? 全部假设成Q得到最初答案,再逐一替换为L(相当于枚举分界线)更新最大值(逐步贪心的过程)
void solve(){ cin>>n>>s; s='0'+s+'0'; vector<ll> pre(n+2,0),suf(n+2,0); for(int i=1;i<=n;i++){ if(s[i]=='L'||s[i]=='?'){ pre[i]++; } pre[i]+=pre[i-1]; } for(int i=n;i>0;i--){ if(s[i]=='Q'||s[i]=='?'){ suf[i]++; } suf[i]+=suf[i+1]; } ll cur=0,cntl=0; for(int i=1;i<=n;i++){ if(s[i]=='L'){ cntl++; } else{ cur+=cntl; } } ll ans=cur; for(int i=1;i<=n;i++){ if(s[i]=='?'){ ll c=suf[i+1]-pre[i-1]; cur+=c; ans=max(ans,cur); } } cout<<ans;} 分享
如果这篇文章对你有帮助,欢迎分享给更多人!
部分信息可能已经过时
相关文章 智能推荐








