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

相关文章

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.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》:本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt