2024牛客寒假算法基础集训营2

2024-02-11 17:36

本文主要是介绍2024牛客寒假算法基础集训营2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

C Tokitsukaze and Min-Max XOR

题目大意

  • 给定一个数组a
  • a任取数构成序列b
  • 序列b满足b_i=min\ b,b_j=max\ b,b_i\ xor\ b_j \leq k,(可以只取一个数)
  • 问能构造出多少个b
  • mod=1e9+7

解题思路

  • maxmin
  • 双枚举时间复杂度到O(n^2),考虑利用01Trie加速统计b_i \ xor\ b_j< k的方案
  • 01Trie,即将数字按二进制位拆分挂在树上
  • 对于一个数,它在树上经过的点,均加上它对答案的贡献
  • 所以树上的某一点存的信息为,以这个点的数位为分界,在它之前(包括它)均为某固定值,而在它后均为任意值的数对答案的贡献
  • 若当前值为a_j,令其为max,则小于a_j的有j-1个,不考虑限制的话,共有2^{j-1}种选取min的方式
  • 若选取了a_i作为min,则1\rightarrow i均确定了是否选取
  • 所以min=a_i,max=a_j,方案数为2^{j-1}/2^i
  • 若在01Trie上,当前为第t位,则前t-1位均与a_j\ xor\ k对应数位相同
  • k的第t位为1,且01Trie存在着与a_j的第t位相同的点
  • a_j与该点往下的所有值异或后,第t位均为0
  • 答案加上该点值,即ans+=\sum_{i} Val(a_i),a_i\ xor\ a_j< k
  • 不必在从该点往下走挨个统计,实现了加速
  • 若能在01Trie上走到最后,则存在a_i\ xor\ a_j=k,答案加上该点值
  • 最后处理完了a_j,在将其加入01Trie
  • 由于b数组长度可以为1,所以初始ans=n
  • 最终复杂度为O(nlogn)
  • 注意Trie上为31\rightarrow 0

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.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)1e9+7L;static long qm(long a,long b) {long res=1;while(b>0) {if((b&1)==1)res=(res*a)%md;a=a*a%md;b>>=1;}return res;}staticclass Trie{long[] cnt;//一个数分成32位,共32层,最后一层最多为nint[][] tr;//01trieint t;public Trie(int n) {cnt=new long[n*32];tr=new int[n*32][2];t=0;}void insert(int x,long y) {int p=0;for (int i = 31; i >= 0; i--) {int j=(x>>i)&1;if(tr[p][j]==0) {t++;tr[p][j]=t;}p=tr[p][j];cnt[p]=(cnt[p]+y)%md;//在沿途放上,便于统计小于k的情况}}long query(int x,int k) {long res=0;int p=0;for (int i = 31; i >= 0; i--) {int xt=(x>>i)&1;int kt=(k>>i)&1;if(kt==1&&tr[p][xt]!=0) {res=(res+cnt[tr[p][xt]])%md;//统计i^j<k}if(tr[p][xt^kt]==0) {return res;//不能满足前t-1位,i^j=k}p=tr[p][xt^kt];}res=(res+cnt[p])%md;//i^j=k的情况return res;}}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int T=input.nextInt();while(T>0) {int n=input.nextInt();int k=input.nextInt();int[] a=new int[n+1];for(int i=1;i<=n;++i)a[i]=input.nextInt();Arrays.sort(a,1,n+1);Trie Tp=new Trie(n+1);long ans=n;//min=i,max=j,i=j的情况for(int i=1;i<=n;++i) {//此时trie上的数均小于a[i]int x=a[i];ans=(ans+Tp.query(x, k)*qm(2, i-1)%md)%md;long inv=qm(qm(2L, i), md-2);Tp.insert(x, inv);}out.println(ans);T--;}out.flush();out.close();}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();}}
}

这篇关于2024牛客寒假算法基础集训营2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/700405

相关文章

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.