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中的分组和多表连接详解

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数组获取数组的长度读取某下的
阅读更多...
SpringValidation数据校验之约束注解与分组校验方式

SpringValidation数据校验之约束注解与分组校验方式

《SpringValidation数据校验之约束注解与分组校验方式》本文将深入探讨SpringValidation的核心功能,帮助开发者掌握约束注解的使用技巧和分组校验的高级应用,从而构建更加健壮和可... 目录引言一、Spring Validation基础架构1.1 jsR-380标准与Spring整合1
阅读更多...
Mysql如何将数据按照年月分组的统计

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》：本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA
阅读更多...
C++原地删除有序数组重复项的N种方法

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体：最多保留两次五、分析和代码实现5.1、问题分析5.
阅读更多...
Java中数组转换为列表的两种实现方式(超简单)

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架（Arrays.asList）1.1 示例代码1.
阅读更多...
C++一个数组赋值给另一个数组方式

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法：使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2