F.小红的数组分组

2024-02-26 23:52
文章标签 数组 分组 小红

本文主要是介绍F.小红的数组分组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 解题思路

  • 维护集合，满足集合内一个元素一定存在另一个元素与其有某一个相同的质因子(size>1)
  • 若集合只有一个，则无解
  • 特判存在1，则1单独放一个，其余放一起
  • 预处理出1e6内所有质数的同时，可以处理出每个数的最小质因子
  • 对于任意一个数，while(x/=mifac[x])可以得到该数所有质因子
  • 避免了对于1e6内某一数进行质因数分解时
  • while从2开始++查找 或 利用已经求出的质数for从小到大进行尝试
  • 注意维护集合时，不要通过质因子将其能整除的一块处理，因为会有已经被处理过的，虽然不计，但会访问，重复访问会超时
  • 而自己处理自己的，相互之间通过质因子进行联系，这样每个至多访问一次
  • 注意java不要在循环中建数组，会超时。直接建全局，结束时进行删除即可。

最优解 


import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int find(int x,int[] fa) {if(x==fa[x])return x;else return fa[x]=find(fa[x], fa);}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int N=1000000;int[] prim=new int[1000001];int cnt=0;boolean[] isnotprim=new boolean[1000001];int[] facmi=new int[1000001];for(int i=2;i<=N;++i) {if(!isnotprim[i]) {cnt++;prim[cnt]=i;facmi[i]=i;}for(int j=1;j<=cnt;++j) {int now=prim[j]*i;if(now>N)break;isnotprim[now]=true;facmi[now]=prim[j];if(i%prim[j]==0)break;}}int[] a=new int[200001];int[] b=new int[200001];int[] c=new int[200001];int[] fa=new int[1000001];HashSet<Integer> ol=new HashSet<Integer>();int q=input.nextInt();while(q>0) {int n=input.nextInt();int one=0;int mx=0;for(int i=1;i<=n;++i) {a[i]=input.nextInt();fa[a[i]]=a[i];ol.add(a[i]);mx=Math.max(mx, a[i]);}if(one!=0) {out.println(one+" "+(n-one));for(int i=1;i<=one;++i) {out.print(1+" ");}out.println();for(int i=1;i<=n;++i) {if(a[i]!=1)out.print(a[i]+" ");}out.println();q--;for(int x:ol) {fa[x]=0;}ol.clear();continue;}for(int i=1;i<=cnt;++i) {if(prim[i]>mx)break;fa[prim[i]]=prim[i];ol.add(prim[i]);}
//	    	boolean[] vis=new boolean[mx+1];//其实还可以去个重for(int i=1;i<=n;++i) {
//	    		if(vis[a[i]])continue;
//	    		vis[a[i]]=true;int x=a[i];int fx=find(x, fa);while(x!=1) {int y=facmi[x];int fy=find(y, fa);if(fy!=fx)fa[fy]=fx;x/=y;}}int bb=0;int cc=0;int bf=find(a[1], fa);for(int i=1;i<=n;++i) {int fx=find(a[i], fa);if(fx==bf) {bb++;b[bb]=a[i];}else {cc++;c[cc]=a[i];}}if(bb==n) {out.println("-1 -1");q--;for(int x:ol) {fa[x]=0;}ol.clear();continue;}out.println(bb+" "+cc);for(int i=1;i<=bb;++i) {out.print(b[i]+" ");}out.println();for(int i=1;i<=cc;++i) {out.print(c[i]+" ");}out.println();q--;for(int x:ol) {fa[x]=0;}ol.clear();}out.flush();out.close();}//System.out.println();//out.println();staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

 超时解

  • 会超最后一个点，也是赛时代码
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int find(int x,int[] fa) {if(x==fa[x])return x;else return fa[x]=find(fa[x], fa);}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));HashMap<Integer, HashSet<Integer>> NumhsPrim=new HashMap<Integer, HashSet<Integer>>();//每个数的质因子HashSet<Integer> now=new HashSet<Integer>();int q=input.nextInt();while(q>0) {int n=input.nextInt();int[] a=new int[n+3];for(int i=1;i<=n;++i)a[i]=input.nextInt();Arrays.sort(a,1,n+1);HashMap<Integer, Integer> d=new HashMap<Integer, Integer>();//统计相同个数int o=0;for(int i=1;i<=n+1;++i) {if(a[i]==a[i-1]) {o++;}else {d.put(a[i-1], o);o=1;}}int[] e=new int[n+1];o=0;//去重for(int i=1;i<=n;++i) {if(a[i]==a[i-1])continue;o++;e[o]=a[i];}int[] b=new int[n+1];int bc=0;int[] c=new int[n+1];int cc=0;if(e[1]==1) {//1自己为一组，其它放一组bc=d.get(1);for(int i=2;i<=o;++i) {int p=d.get(e[i]);for(int j=1;j<=p;++j) {cc++;c[cc]=e[i];}}out.println(bc+" "+cc);for(int i=1;i<=bc;++i) {out.print(1+" ");}out.println();for(int i=1;i<=cc;++i) {out.print(c[i]+" ");}out.println();}else {for(int i=1;i<=o;++i) {if(NumhsPrim.get(e[i])==null) {now=new HashSet<Integer>();int x=e[i];int t=2;while(t<=x) {if(t==x) {now.add(t);break;}else if(x%t==0) {now.add(t);while(x%t==0) {x/=t;}}else t++;}NumhsPrim.put(e[i], now);}}Queue<Integer> qu=new LinkedList<Integer>();HashSet<Integer> checkover=new HashSet<Integer>();//被处理过的质数不在重复处理//该质数是哪些数的因子HashMap<Integer, Vector<Integer>> PrimhsNum=new HashMap<Integer, Vector<Integer>>();Vector<Integer> may=new Vector<Integer>();HashSet<Integer> op=new HashSet<Integer>();for(int i=1;i<=o;++i) {op=NumhsPrim.get(e[i]);for(int x:op) {//该数的所有质因子if(PrimhsNum.get(x)==null) {may=new Vector<Integer>();may.add(i);PrimhsNum.put(x, may);}else {may=PrimhsNum.get(x);may.add(i);PrimhsNum.put(x, may);}}}int[] fa=new int[n+1];for(int i=1;i<=o;++i)fa[i]=i;//集合内某一元素一定存在另一个元素与其有相同因子for(int i=1;i<=o;++i) {if(fa[i]!=i)continue;qu=new LinkedList<Integer>();checkover=new HashSet<Integer>();op=NumhsPrim.get(e[i]);for(int x:op) {qu.add(x);}int fx=i;while(!qu.isEmpty()) {int x=qu.peek();qu.poll();if(checkover.contains(x))continue;checkover.add(x);may=PrimhsNum.get(x);for(int y:may) {//会有重复访问，超时！！！！！int fy=find(y, fa);if(fy==fx)continue;//已经处理过了fa[fy]=fx;op=NumhsPrim.get(e[y]);for(int z:op) {//将新的质因子加入if(!checkover.contains(z)) {qu.add(z);}}}}}int m=0;for(int i=1;i<=o;++i) {//有多少个连通块if(fa[i]==i)m++;}if(m==1) {//只有一个连通块，分不开out.println("-1 -1");}else {op=new HashSet<Integer>();now=new HashSet<Integer>();int p=0;for(int i=1;i<=o;++i) {if(fa[i]==i) {//块头决定放在b/cif(p==0) {op.add(i);int l=d.get(e[i]);for(int j=1;j<=l;++j) {bc++;b[bc]=e[i];}p=1;}else {now.add(i);int l=d.get(e[i]);for(int j=1;j<=l;++j) {cc++;c[cc]=e[i];}p=0;}}else {if(op.contains(fa[i])) {//跟着放进去int l=d.get(e[i]);for(int j=1;j<=l;++j) {bc++;b[bc]=e[i];}}else {int l=d.get(e[i]);for(int j=1;j<=l;++j) {cc++;c[cc]=e[i];}}}}out.println(bc+" "+cc);for(int i=1;i<=bc;++i) {//输出out.print(b[i]+" ");}out.println();for(int i=1;i<=cc;++i) {out.print(c[i]+" ");}out.println();}}q--;}out.flush();out.close();}//System.out.println();//out.println();staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}
//想要处理出1e6内所有数分解后的质因数
//对于每次询问的a，进行质因数分解

这篇关于F.小红的数组分组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/750563。

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案（推荐）2. 模糊匹配方案参数化查询示例使用场景建议性能优
阅读更多...
关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...
MySQL JSON 查询中的对象与数组技巧及查询示例

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA
阅读更多...
Java反射实现多属性去重与分组功能

Java反射实现多属性去重与分组功能

《Java反射实现多属性去重与分组功能》在Java开发中,​​List是一种非常常用的数据结构,通常我们会遇到这样的问题：如何处理​​List​​​中的相同字段？无论是去重还是分组,合理的操作可以提高... 目录一、开发环境与基础组件准备1.环境配置：2. 代码结构说明：二、基础反射工具：BeanUtils
阅读更多...
JAVA数组中五种常见排序方法整理汇总

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言：法一：Arrays.sort()法二：冒泡排序法三：选择排序法四：反转排序法五：直接插入排序前言：几种常用的Java数组排序
阅读更多...
Java如何根据文件名前缀自动分组图片文件

Java如何根据文件名前缀自动分组图片文件

《Java如何根据文件名前缀自动分组图片文件》一大堆文件（比如图片）堆在一个目录下,它们的命名规则遵循一定的格式,混在一起很难管理,所以本文小编就和大家介绍一下如何使用Java根据文件名前缀自动分组图... 目录需求背景分析思路实现代码输出结果知识扩展需求一大堆文件（比如图片）堆在一个目录下，它们的命名规
阅读更多...
MySQL中的分组和多表连接详解

MySQL中的分组和多表连接详解

《MySQL中的分组和多表连接详解》：本文主要介绍MySQL中的分组和多表连接的相关操作,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录mysql中的分组和多表连接一、MySQL的分组（group javascriptby ）二、多表连接（表连接会产生大量的数据垃圾）MySQL中的
阅读更多...
Java数组初始化的五种方式

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化：简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化：灵活但需手动管理代
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2