- 2024-10-2010.19-10.20 练习
其实是复健。上一次碰电脑是期末考试完(7月),上上次是noip(2023年11月)。1.P9752[CSP-S2023]密码锁__record要求:语文没问题,会基础语法,有生活常识。枚状态,判断。几乎没有复杂度要求。Code#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intn,ans;int
- 2024-10-072024/10/07 模拟赛总结
\(20+55+25+0=100\),压线拿到小饼干!#A.A可以发现\(u_i=A,v_i=B,w_i=C\)至少有一个成立,将这些点抽象到三位空间中。则原长方体一定被一个从\((1,1,1)\)出发的长方体打穿,但是似乎重叠部分比较难实现对于从底打到顶的长方体,可以用后缀\(\max\)解决,然后原长方体就变成了阶梯
- 2024-09-26P8475 「GLR-R3」雨水 题解
关于这道题目卡\(O(n\logn)\)但是放\(O(n^2)\)我也是很疑惑。我们发现,题目要求的是字典序最小的序列。但凡涉及了字典序最小,答案或多或少的都会带点贪心思想。那我们也来贪一贪。考虑当前枚举到第\(i\)个点,如果后面有比它更小的数,那显然把它们交换过来是更优的。如果有多
- 2024-09-24关于异或哈希
Re:疑惑异或哈希异或哈希是个很神奇的算法,利用了异或操作的特殊性和哈希降低冲突的原理,可以用于快速找到一个组合是否出现、序列中的数是否出现了\(k\)次算法如其名,异或+哈希。想起某首歌叫PPAP?Ihavea\(\oplus\),Ihavean\(hash\).(Uhh~)\(\oplushash\)!
- 2024-09-232024.8.21 模拟赛 26
模拟赛怎么都找不到原题了?T1博弈trick,容易发现如果有一个数在路径上的出现次数为奇数,那么先手就能赢。问题是如何判断路径上是否有一个数出现奇数次。是一个存在性问题,考虑异或哈希,发现如果两个相同的数异或和为零,并且\(d_{u,v}=d_{root,u}\oplusd_{root,v}\)。如果
- 2024-09-19字符串指南
kmpkmp是模式串匹配的算法,本来最坏时间复杂度可以达到$\operatorname{O}(n\timesm)$,但是kmp可以将复杂度优化到$\operatorname{O}(n+m)$。kmp有个很重要的东西,叫做$nxt$失配数组。比如对于一个字符串$s$,它的失配数组$nxt_n$就是$s$的最大前缀等于后缀的长度。$\op
- 2024-09-18字符串
字符串哈希哈希是什么?把一个串或者字符映射成一串数字,再通过取模的方式来使其可以被存下字符串哈希?把字符串用数字的方式写出具体的,我们可以通过把字符串变成一个k进制数,最后通过取余实现P3370【模板】字符串哈希#include<bits/stdc++.h>#defineintlonglong#defi
- 2024-09-14P10469 后缀数组(Hash+二分)
#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>
- 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