首页 > 其他分享 >[科技] 异或哈希

[科技] 异或哈希

时间:2023-06-06 23:12:27浏览次数:40  
标签:字符 10 ll 1048576 科技 异或 哈希

一个小问题

Statement

来源:https://www.luogu.com.cn/problem/T297472?contestId=91205

给定字符串 \(S\),求最长的连续子序列满足其中每个字符都出现了偶数次,求最长长度。

\(T\) 组询问,\(\displaystyle \sum_{}|S| \leq 5\times 10^6\)。

注:本题暂时只需要通过 \(\text{Subtask 4}\) 即可,原题的 hack 数据在时间限制和空间限制上都不太够。

Solution

前置知识:哈希。

这个题要求每个字符都出现偶数次,这种感觉就是异或的值为 \(\textbf{0}\)。

就引入异或哈希这个玩意。

其方法就是,在 \([0,L]\) 的范围内给每个字符都随机生成一个,代码如下:

const ll mod = 1048576;
mt19937_64 maker (time (NULL));
inline void gen () {
	for (ll _ = 0;_ < need; ++ _) {
		for (ll i = 0;i <= 256; ++ i) a[_][i] = maker () % mod;
	}
}

注意 \(L\) 一定要是形如 \(2^N\) 的数,比如 \(2^{20}=1048576\)。

剩下的我们就记录每一个哈希结果最早出现的下标,第二次出现的时候就计入答案即可。

inline ll solve (ll can) { 
	fir[0] = 0;
	lpos[0] = can;
	ll XOR = 0, Result = -1;
	for (ll i = 1;i <= n; ++ i) {
		XOR ^= a[can % need][(ll) s[i]];
		if (lpos[XOR] == can) {
			Result = max (Result, i - fir[XOR]);
		}
		else {
			fir[XOR] = i;
			lpos[XOR] = can;
		}
	}
	return Result;
}

为了保险,我们要做 \(10\) 次 solve() 函数。

标签:字符,10,ll,1048576,科技,异或,哈希
From: https://www.cnblogs.com/RB16B/p/17462019.html

相关文章

  • 网迅科技与浪潮信息KOS完成兼容性认证
    日前,北京网迅科技有限公司多款产品与浪潮信息KOS完成并通过了澎湃技术认证,此次测试的产品包括网迅科技WX1860系列千兆网络控制器、SP1000A/WX1820AL万兆网络控制器,和浪潮信息服务器操作系统KOSV5。经测试,网迅科技两个系列产品在KOS上运行稳定,兼容性良好,满足用户的关键性应用需求,与......
  • 企业出海掘金中东,茄子科技助力出海游戏破局用户增长
    中东已成为游戏企业出海最为看好的地区之一。地处连接亚欧的关键位置,又占据全球石油总储量和六成之高,使得中东长期以来都是全球各国外交与经贸关注的热土。近年来,随着中东数字化产业基础设施建设大力投入,移动互联网参透率突飞猛进,加之年轻化的人口红利,使得游戏、社交、电商、物流等......
  • Amazon电商、音乐、云服务不分家,亚马逊云科技告诉你如何巧用全球业务体系占据80%中国
    花木兰为啥“东市买骏马,西市买鞍鞯”?在半年一度的6.18电商购物节里,大家可能会说:“因为没有跨店满减”……但事实是,如果东市都可以把骏马、鞍鞯买齐是怎样的一种体验?亚马逊云科技就可以做到,作为占据80%中国企业出海市场的亚马逊云科技,其覆盖全球的业务体系,从亚马逊海外购、......
  • 全志科技官方Ubuntu16.04根文件系统镜像的替换和测试方法
     本指导文档主要基于全志A40i开发板——TLA40i-EVM,一款基于全志科技A40i处理器设计的4核ARMCortex-A7高性能低功耗国产评估板,演示Ubuntu根文件系统镜像的替换和测试方法。创龙科技TLA40i-EVM评估板接口资源丰富,引出双路网口、双路CAN、双路USB、双路RS485等通信接口,板载Bluetoo......
  • 西北农林科技大学,我的母校! http://xnxy.43i.net/index.php
          西北农林科技大学,我的母校!曾经在校园里,看着"今天你以学校为荣,明天学校以你为荣"的横幅,心里默默给自己加油,希望真的可以如此;今天毕业了,在茫茫深圳,怀揣梦想努力着,却不忘曾经那份感情,梦中游弋在母校的角角落落,我想身为西农校友的一份......
  • 跨境电商出海东南亚,茄子科技助推出海企业占领海外新兴市场
    随着欧美电商市场日趋饱和,中国跨境电商卖家开始寻找新的蓝海市场,作为全球增速最快、强力最大的海外新兴蓝海市场,东南亚市场吸引了无数巨头相继入局。得益于政策扶持叠加线上需求旺盛,跨境企业在东南亚市场发展势头强劲。 对于中国企业出海东南亚而言,除了庞大的人口及市场红利外,相近......
  • 3D打印助力齿科数字化升级,黑格科技携全链路解决方案亮相北京展
    2023北京国际口腔展,如约而至黑格将携椅旁及技工厂端的数字化新思路、新实践亮相展区与齿科同行共享数字化成功经验共话数字化发展新篇章数字化新玩法,已就位精彩亮点,提前锁定!一:数字化口腔新范式,提升就诊体验黑格从患者角度出发带来“一日戴牙”系列解决方案方案广泛应用于数字......
  • 完整支持Oracle PL/SQL,星环科技KunDB高兼容性实现低成本国产化替代
    从中兴、华为等一系列高新科技企业被美国制裁,到俄乌冲突事件爆发后,西方各国相继宣布制裁俄罗斯,以Oracle、IBM、微软、SAP为代表的科技巨头暂停在俄服务,这一系列动作给我们敲响了加速国产化替代的警钟。数据库作为提供数据存储与处理能力的基础软件,是信息系统的基础、信息安全的基石......
  • UOJ91 最大异或和
    最大异或和把区间进行前缀异或相当于差分,我们知道线性基异或后仍是线性基,那么我们在差分后的数列上进行操作。不难发现修改后需要对线性基进行删除,在线的方法看zxy博客吧。注意差分数列(线性基)和原数列是分开处理的,我们对原数列的修改目的是修改线性基,而线性基的维护用上......
  • 最小哈希 minhash
    最小哈希维基百科,自由的百科全书 在计算机科学领域,最小哈希(或最小哈希式独立排列局部性敏感哈希)方法是一种快速判断两个集合是否相似的技术。这种方法是由AndreiBroder (1997),[1]发明的,最初在AltaVista搜索引擎中用于在搜索结果中检测并消除重复Web页面。[2]它同样也应用于大规模......