- 2024-09-04Checking the Text 文本校对
CheckingtheText文本校对[POJ2758]&&[BZOJ2258]&&[NFLSOJ-文本校对]题面描述为了给Wind买生日礼物,Jiajia不得不找了一份检查文本的工作。这份工作很无聊:给你一段文本要求比对从文本中某两个位置开始能匹配的最大长度是多少。但比无聊更糟糕的是,Jiajia的经理还可
- 2024-09-01【寻迹#3】 哈希与哈希表
哈希和哈希表哈希算法是通过一个哈希函数\(\operatornameH\),将一种数据(包括字符串、较大的数等)转化为能够用变量表示或是直接就可作为数组下标的数,通过哈希函数转化得到的数值我们称之为哈希值。通过哈希值可以实现快速查找和匹配。哈希算法具体应用有:字符串\(\operatorname
- 2024-08-31Hash哈希学习笔记
概念:通过一个hash函数建立值与存储地址的关系原则:开小数组+冲突解决冲突越少,用时越少;可通过调整余数或优质的hash算法尽量使hash值分散,减少碰撞hash算法的构成:hash函数的初始化构造hash函数:典型的函数包括除余法H
- 2024-08-21模拟赛25
模拟赛25最近怎么狂挂不止。博弈考虑策略,首先是优先最小的,但是由于有重复的,所以在最小个数为偶数时会败,以此类推,可以想到当有一个数出现次数时奇数先手必胜,否则必败。考虑将相同的两两相消,发现\(u\tov\)和\(u\to根\tov\)是等价的。于是每个点维护一下当前的数,问题变
- 2024-08-15[lnsyoj2271/luoguP3745/省选联考 2017]期末考试
题意给定长度为\(n\)的序列\(t\)和长度为\(m\)的序列\(b\),以及常数\(A,B,C\),可以进行两种操作:选取任意\(1\lex,y\len\),并使\(b_x+1,b_y-1\),记进行了\(\alpha\)次这种操作;选取任意\(1\lez\len\),并使\(b_z-1\),记进行了\(\beta\)次这种操作。求进
- 2024-08-07CSP15
T1唐了点击查看代码#include<bits/stdc++.h>#defineullunsignedlonglongusingnamespacestd;constintN=1E6+6;constullB=233;intlen;ullh[N],fh[N],p[N];ullget(intl,intr){ returnh[r]-h[l-1]*p[r-l+1];}ullfget(intl,intr){ inttl=len-
- 2024-07-29「模拟赛」暑期集训CSP提高模拟10(7.28)
\(145pts,Rank10\),众数分。数学专题模拟赛%%%总结写前面:1.线性递推式复杂度过大考虑矩阵快速幂优化;2.T1长时间切不了就先跳,先把所有题看一遍,拿分为主。赛时记录正常开T1,期望数学题,大概读懂了,手模下小样例,模了一遍又一遍,“我并不认为样例是对的”,跳了(很正确的决定)。
- 2024-07-25字符串哈希
首先对于知识点会在8月份更新,目前只是单纯的对一道题进行展示题目链接https://ac.nowcoder.com/acm/contest/87255/E题意:题目要求我们找出两个等长的字符串a和b中的“好”字符数量。一个字符被称为“好”字符,如果它在字符串a和b的所有循环同构字符串中出现的位置
- 2024-07-21NOI2024 集合 题解
给个链接:集合。很神秘的题目。基本上看到之后就可以想到哈希。首先想到一个比较神秘的暴力。就是对于每个询问,扫一遍所有\(a\)中的数出现的位置,把它弄成一个哈希值(具体怎么弄随意)存到set里,然后看看是不是和\(b\)中的数出现的位置这样操作后的集合完全相等。事实上就是判断
- 2024-07-19循环位移(2024“钉耙编程”中国大学生算法设计超级联赛(1))
#include<bits/stdc++.h>#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();constintN=4e6+7;constintP=131;ullp[N],an[N],bn[N];intn;voidinit(stringa,stringb){
- 2024-07-19字符串哈希
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefdoubledb;typedeflongdoubleldb;typedefpair<int,int>pii;typedefpair<ll,ll>PII;#definepbemplace_back//#defineint
- 2024-07-10P3993 [BJOI2017] 同构 题解
Description你有\(n\)个点,你可以在这\(n\)个点之间连无向边,两个点之间至多只能连一条边,也不允许连自环,问至多能连多少条边。但这个问题的答案显然是\(\frac{n(n-1)}{2}\)条。所以有一个额外的限制,要求这个图不存在非平凡的自同构。一个图\(G\)有非平凡的自同构定义为存
- 2024-06-03找规律模拟器(1)
点击查看代码#include<bits/stdc++.h>#include<windows.h>#defineptputs("")#defineswpif(a>b)swap(a,b)#defineclsystem("cls")usingnamespacestd;typedefunsignedlonglongull;ullQ1(ullx){ return(x+1)*x/2;}ul
- 2024-05-18Living-Dream 系列笔记 第57期
hashfunction(哈希函数)将一个规模很大的字符串用特定规则转化为特定数值,这种特定规则,我们称之为hashfunction。hashvalue(哈希值)字符串由哈希函数生成的数值。hashcollision(哈希冲突)多个字符串得到了相同的hashvalue。算法竞赛中的hashfunction通常将字符
- 2024-05-04多项式全家桶
还有好一些困难东西没学,现就这样吧。每日一遍:\(167772161,469762049\)除了求逆其他都要预留两倍空间!#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;constllN=(1<<19)+3,H=998244353,g=3,ig=(H+1)/3;intU[N];ull
- 2024-05-03Codeforces 452F Permutation
对于\(a,b,\frac{a+b}{2}\)肯定是需要固定下一些变量来考虑的。考虑固定下\(c=\frac{a+b}{2}\),考虑\(a,b\)。那么这样的\(a,b\)肯定满足\(a-c=b-c,a\not=b\),那么以\(c\)为中心,\(a,b\)就是对称的。用\(s_i=0,1\)来表示\(i\)是在\(c\)的
- 2024-05-02网课-数论学习笔记
埃氏筛P7960[NOIP2021]报数P1835素数密度:区间筛。预处理\(\sqrt{R}\)内的质数,然后用埃氏筛筛[L,R]的质数。线性筛-EOF-欧拉函数P10031「CfzRound3」XorwithGcd光速乘用于解决$$llTimes(lla,llb,llc){ ullt=(longdouble)a*b/c+0.5; llans=(u
- 2024-04-24字符串基础:Hash,KMP,trie
Hash把一个字符串映射成一个整数,可以方便的比较两个字符串是否相等,计算\(Hash\)值:\[\displaystyle\sum_{i=0}^{len-1}(s[i]\timesB^{len-1-i})(mod\;M)\]这里的\(B\)是任取的一个大小合适的数,\(M\)就是为了把算出来的值映射到\([0,M-1]\)的范围内,既然是\(mod\),
- 2024-04-24乌力波
佩雷克很可能在下面的比赛中得到高分(当然,也有可能是低分)。在这个比赛中,人们被要求针对一个主题写出甚至是意味深长的文章,并且让一个给定的“单词”出现次数尽量少。我们的任务是给评委会编写一个程序来数单词出现了几次,用以得出参赛者最终的排名。参赛者经常会写一长串废话,例如500
- 2024-03-31树哈希
这种东西看代码比说话好用。#include<bits/stdc++.h>#defineintlonglong#defineullunsigned#defineup(i,l,r)for(inti=l;i<=r;++i)#definedn(i,r,l)for(inti=r;i>=l;--i)#definepbpush_backusingnamespacestd;constintN=111;constullmask=st
- 2024-03-28树哈希学习笔记
1.作用判断一些树是否同构。2.方法2.1.具体操作这类方法需要一个多重集的哈希函数。以某个结点为根的子树的哈希值,就是以它的所有儿子为根的子树的哈希值构成的多重集的哈希值,即:\[h_u=f(\{h_v|v\inson(u)\})\]其中\(h_x\)表示以\(x\)为根的子树的哈希值,\(f\)是多重集的
- 2024-03-23洛谷P3498 [POI2010] KOR-Beads 题解
P3498[POI2010]KOR-Beads对于数列${A_i}$,求$k$使数列被分为$\lfloor\frac{n}{k}\rfloor$个部分后不同子数列种类最多(子串翻转前后为一类子串)很容易想到:枚举$k\\in\[1,n]$,记录每个$k$下不同种类数,然后取最优即可,那么问题来了:如何计算种类数?暴戾算法:一种纯
- 2024-03-20CF817F MEX Queries 题解
题目链接:CF或者洛谷不是很难的题,但在这里提供一个动态开点线段树怎么卡空间卡过去的极致空间处理技巧全局\(mex\)问题,常见的做法就是维护权值树,然后找第一个没有权值的点,可以维护\(\min\),但本题存在第三个操作,所以不能再去传统地维护\(\min或者\max\)去辅助二分了。观
- 2024-03-17【NC23046】华华教月月做数学
题目华华教月月做数学考虑数据溢出的问题思路题目要求很简单,就是算aaa的bb
- 2024-02-29多项式板子
#include<bits/stdc++.h>#defineullunsignedlonglongusingnamespacestd;constintN=262150,mod=998244353,g=3,invg=(mod+1)/3,inv2=(mod+1)/2;intrev[N];ulla[N],b[N],w[N],inv[N];intqpow(inta,intb){ intans=1; while(b){ if(b&1){ an