cf1514 D. Cut and Stick
2022/4/28 6:14:14
本文主要是介绍cf1514 D. Cut and Stick,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
给定数组。q 次询问,每次问至少把 \(a[l,r]\) 拆成几个子序列,才能让每个子序列中的众数的出现次数 不大于子序列长度/2上取整
\(n,q\le 3e5, 1\le a_i\le n\)
思路:
绝对众数:出现次数严格大于N/2
如果区间众数不是绝对众数,则答案为1。否则,设绝对众数的出现次数为 x
,把其他所有数(共 n-x 个)和 n-x+1 个绝对众数分一组,剩下的绝对众数每个单独一组,组数是 x-(n-x+1)+1=2x-n。这样就是最优的!(真的)
众数可以用莫队求。但根据绝对众数的性质,还有些其他方法
法一:随机
绝对众数的出现次数大于一半,随便选一个数,它不是绝对众数的概率约 1/2,随机选40次左右就很稳,每次选出来都二分求出现次数
实测随机40次要2秒,30次1.7秒,25次居然wa
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll ran(ll l, ll r) { return uniform_int_distribution<int>(l,r)(rng); } const signed N = 3 + 3e5; int n, q, a[N]; vector<int> pos[N]; int cnt(int l, int r, int x) { //x在区间中的出现次数 return upper_bound(all(pos[x]),r) - lower_bound(all(pos[x]),l); } signed main() { iofast; cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i], pos[a[i]].pb(i); while(q--) { int l, r; cin >> l >> r; int ans = 0; for(int i = 1; i <= 30; i++) ans = max(ans, cnt(l,r,a[ran(l,r)])); cout << max(1, 2*ans-(r-l+1)) << endl; } }
法二:线段树
绝对众数肯定也是至少一个儿子的绝对众数
节点维护区间的绝对众数
查询可谓非常暴力啊。所有走过的区间的绝对众数都作为候选,每个都求(在整个大区间中的)出现次数,取max返回
复杂度俩log,不到一秒
const signed N = 3 + 3e5; int n, q, a[N]; vector<int> pos[N]; int cnt(int l, int r, int x) { //x在区间中的出现次数 return upper_bound(all(pos[x]),r) - lower_bound(all(pos[x]),l); } #define mid ((l+r)/2) #define lson u*2 #define rson u*2+1 #define ls lson,l,mid #define rs rson,mid+1,r int tr[N<<2]; //区间众数 void build(int u, int l, int r) { if(l == r) tr[u] = a[l]; else build(ls), build(rs), tr[u] = cnt(l,r,tr[lson]) > cnt(l,r,tr[rson]) ? tr[lson] : tr[rson]; } int ask(int u, int l, int r, int x, int y) { //返回区间绝对众数的出现次数 if(y < l || x > r || y<x) return 0; //没交集 if(x <= l && r <= y) return cnt(x,y,tr[u]); //包含 return max(ask(ls, x, y), ask(rs, x, y)); } signed main() { iofast; cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i], pos[a[i]].pb(i); build(1, 1, n); while(q--) { int l, r; cin >> l >> r; cout << max(1, 2*ask(1,1,n,l,r)-(r-l+1)) << endl; } }
这篇关于cf1514 D. Cut and Stick的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-25Elevate Your Lead Generation Game with Maps Scraper AI
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能