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。

相关文章

Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
使用C#如何创建人名或其他物体随机分组

使用C#如何创建人名或其他物体随机分组

《使用C#如何创建人名或其他物体随机分组》文章描述了一个随机分配人员到多个团队的代码示例,包括将人员列表随机化并根据组数分配到不同组,最后按组号排序显示结果... 目录C#创建人名或其他物体随机分组此示例使用以下代码将人员分配到组代码首先将lstPeople ListBox总结C#创建人名或其他物体随机分组
阅读更多...
vue如何监听对象或者数组某个属性的变化详解

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
Solr 使用Facet分组过程中与分词的矛盾解决办法

Solr 使用Facet分组过程中与分词的矛盾解决办法

对于一般查询而言  ,  分词和存储都是必要的  .  比如  CPU  类型  ”Intel  酷睿  2  双核  P7570”,  拆分成  ”Intel”,”  酷睿  ”,”P7570”  这样一些关键字并分别索引  ,  可能提供更好的搜索体验  .  但是如果将  CPU  作为 Facet  字段  ,  最好不进行分词  .  这样就造成了矛盾  ,  解决方法
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2