mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
199 字
1 分钟
11月刷题记录
2026-11-01

无忧旋律 - 题目 - 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;
}
分享

如果这篇文章对你有帮助,欢迎分享给更多人!

11月刷题记录
https://blog.hydrodyio.xyz/posts/11月刷题记录/
作者
Hydroiody
发布于
2026-11-01
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

目录