题解 P3940 分组
2021/6/22 23:30:01
本文主要是介绍题解 P3940 分组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
有些梦想虽然遥不可及,但不是不可能实现。只要我足够的强。
前言
调了挺长时间的,并查集合并的时候需要 find 一下,不然会炸内存。。。。
解题思路
参考了题解区一篇思路非常好的题解,在这里讲一下自己的见解。
首先明确一下 K 的取值只有 1 或者 2 这里看数据范围非常重要!,对于 \(K=1\),\(K=2\) 的情况要分开来做。
K=1
对于 \(K=1\) 的情况,为了保证字典序最小,我们需要倒着枚举序列了。
然后再次观察数据范围,发现\(131072 \times2=512^2\),因此我们可以枚举 \(1 \sim 512\) ,令 vis[i] 表示在当前扫到的组里颜色为 i 的是否存在,查看是否访问过 \(x^2-s_i\) 。
-
如果访问过,表示和第 i 只兔子发生矛盾的已经在这个组里了,因此需要再次分一个组,并且记录下分组的边界,清空 vis 数组。
-
如果没有访问过,把该种颜色的标记成 true 记录就好了。
K=2
几乎同样的思路,我们仍然需要倒着枚举序列。
对于同一组的兔子,状态之可能有两种:同一小团体或者在敌对小团体,因此我们用并查集维护。
-
\(\operatorname{find}(1 \sim n)\) 表示 \(1\sim n\)的兔子所在的小团体。
-
\(\operatorname{find}(n+1 \sim 2 \times n)\) 表示 \(1\sim n\)的兔子所在的小团体的敌对小团体。
然后开一个 vector 数组记录同一颜色的序号,然后分别对于发生矛盾的兔子进行判断,同时更新该兔子所在组以及小团体和敌对小团体。
同样的,如果矛盾无法避免,那就重新开一个组,并清空标记,记录分割点就好了。
code
#include<bits/stdc++.h> using namespace std; const int M=131080; int n,m,K,las,s[M],fa[M<<1]; vector<int> ans,v[M<<1]; bool vis[M]; int find(int x) { if(fa[x]==x) return x; return fa[x]=find(fa[x]); } void work_1() { for(int i=n;i>=1;i--) { bool flag=true; for(int j=1;j<=512;j++) if(j*j>=s[i]) if(vis[j*j-s[i]]) { flag=false; break; } if(!flag) { for(int j=i+1;j<las;j++) vis[s[j]]=false; ans.push_back(i); las=i+1; } vis[s[i]]=true; } printf("%d\n",ans.size()+1); for(int i=ans.size()-1;i>=0;i--) printf("%d ",ans[i]); } int update(int l,int r) { for(int i=l+1;i<r;i++) vector <int>().swap(v[s[i]]); ans.push_back(l); return l+1; } void work_2() { for(int i=1;i<=(n<<1);i++) fa[i]=i; for(int i=n;i>=1;i--) { for(int j=1;j<=512;j++) if(j*j>=s[i]) if(v[j*j-s[i]].size()) for(int k=0;k<v[j*j-s[i]].size();k++) { int temp=v[j*j-s[i]][k]; if(find(temp)==find(i)) { las=update(i,las); break; } else { fa[find(i+n)]=find(temp); fa[find(temp+n)]=find(i); } } v[s[i]].push_back(i); } printf("%d\n",ans.size()+1); for(int i=ans.size()-1;i>=0;i--) printf("%d ",ans[i]); } int main() { scanf("%d%d",&n,&K); las=n+1; for(int i=1;i<=n;i++) scanf("%d",&s[i]); if(K==1) work_1(); else work_2(); return 0; }
这篇关于题解 P3940 分组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)