当前位置: 首页 > news >正文

[题解]P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories

P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories

可以想到很 naive 的思路,对于每个 \(x\) 值二分答案 \(m\)check 函数可以 \(O(n)\) 完成。总时间是 \(O(n^2\log n)\) 的。我们发现 check 函数明显还能凹,考虑优化我们对段遍历的过程。

我们可以预处理出 \(a_i\) 之后第一个 \(a_i +1\) 出现的位置,然后就可以使用倍增快速找到 \(x\) 之后第一个合法的 \(x+m-1\) 的位置。寻找 \(x+m-1\) 之后第一个 \(x\) 的位置也不难。如此进行下去,直到进行不下去或者找到 \(k\) 段为止。

这样单次 check 复杂度是 \(O(c\log n)\) 的。其中 \(c\) 是我们总共经过的段数,也即:

\[c=\min(k,\min\limits_{i=x}^{x+m-1} cnt_i) \]

其中 \(cnt_x\)\(x\) 出现的次数。

这样所有查询的 \(c\) 之和一定是 \(O(n)\) 级别的,所以总时间优化到了 \(O(n\log^2 n)\)

继续优化的话,check 函数已经足够优秀了,考虑对外部的二分进行优化。

不难发现对于所有的 \(x\),都有 \(ans_x\ge ans_{x-1}\)

所以其实我们不需要二分,只需要用一个指针,每次从上一个答案 \(-1\) 开始扫描即可。这样 check 的次数是 \(O(n)\) 量级的,于是总时间优化到了 \(O(n\log n)\)

点击查看代码
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=2e6+5;
int n,k,v,a[N],nxt[22][N];
vector<int> p[N];
inline int get_nxt(int x,int v){auto it=upper_bound(p[v].begin(),p[v].end(),x);return (it==p[v].end()?n+1:*it);
}
inline bool check(int x,int m){//基准记忆为x,m是否可行m--;//从x到x+m-1只需要跳m-1次for(int i=1,u=0;i<=k;i++){u=get_nxt(u,x);for(int j=0;j<=21;j++) if((m>>j)&1) u=nxt[j][u];if(u==n+1) return 0;}return 1;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>k>>v;for(int i=1;i<=n;i++) cin>>a[i],p[a[i]].eb(i);for(int i=1;i<=n;i++) nxt[0][i]=get_nxt(i,a[i]+1),nxt[0][n+1]=n+1;for(int i=1;i<=21;i++) for(int j=1;j<=n+1;j++)nxt[i][j]=nxt[i-1][nxt[i-1][j]];for(int i=1,w=0;i<=v;i++){if(w) w--;while(check(i,w+1)) w++;cout<<w<<" ";}return 0;
}
http://www.hskmm.com/?act=detail&tid=25408

相关文章:

  • 线性表的顺序存储和链式存储
  • AWS WebRTC:获取ICE服务地址(part 3):STUN服务和TURN服务的作用 - 实践
  • Python中的对象池与驻留机制:小整数、字符串与大整数
  • 基于ADMM无穷范数检测算法的MIMO通信系统信号检测MATLAB仿真,对比ML,MMSE,ZF以及LAMA
  • 点乘与叉乘的由来:从四元数到公理自洽的启示
  • 【算法深练】分组循环:“分”出条理,化繁为简 - 教程
  • java学习日记10.5
  • 【JNI】JNI基础语法
  • 【EF Core】通过 DbContext 选项扩展框架
  • 从Chrome渲染器代码执行到内核:MSG_OOB漏洞分析与利用
  • assistant-ui
  • 20251006 之所思 - 人生如梦
  • C# Avalonia 16- Animation- RotateButton
  • 2025 十一集训
  • 汇编实验3
  • 20251005 模拟测 总结
  • 基于Python+Vue开发的体育用品商城管理系统源码+运行步骤
  • 完整教程:Microsoft Word使用技巧分享(本科毕业论文版)
  • (转)The Ten Commandments of Digital Cotrol(Part1)
  • ctf逆向常见算法----base64
  • 02020409 EF Core基础09-一对一、多对多、EF Core基于关系的复杂查询
  • 02020503 EF Core高级03-分页查询、IQuerable底层的实现形式、DataReader、DataTable、EF Core中的异步方法
  • 02020502 EF Core高级02-IQuerable会延迟执行、分部和动态构建IQuerable、IQuerable的复用
  • 在 PyCharm 中,环境:bert_env , 执行 import wandb 报错。但是,在CMD窗口,环境:bert_env , 执行 import wandb 正常。
  • Linux_T(Sticky Bit)粘滞位详解 - 详解
  • P2831 [NOIP 2016 提高组] 愤怒的小鸟 题解
  • 库存中心(三层库存模型)
  • Valley靶机渗透实战:从凭证复用到Python库劫持
  • 10.05模拟赛反思
  • MariaDB收购SkySQL增强AI与无服务器能力