分块入门2
谨以此文,纪念我逝去的这6个小时。原本昨天开开心心学学分块,但是入门2就卡住了,卡到生活都不能自理了。
题目分析
题目意思还是很清晰的。要求区间加法,区间查询符合条件的值。至于加法完全可以照搬前一道题目的方式,但是查询的操作着实有点耐人寻味了,因为区间查询意味着我们得采用分块的思想,不能暴力求解。首先我想到让每一个块变得有序,然后lower_bound查到第一个大于等于某个值的第一个元素的位置。首先对所有块排序的复杂度为√n * √n log_2(√n)也就是nlog_2(n)的复杂度,然后每一次查询最多是√n的复杂度,每一次区间加法是√n的复杂度,区间加法还要对固定两个残缺块进行重新排序(因为两边的残缺块可能会破坏有序结构,而中间的则会保持原来的顺序),这又需要2√nlog_2(√n)的复杂度。查询和加法一起是n√n的复杂度,所以整个算法就是n√n的复杂度,理论可行但是实践可惨死了。
首先,序列排序直接破坏了它的序列结构,这导致我在前一天20点-24点的提交一直不通过。后来我意识到了不能破坏它原有的序列,于是想到每个块用一个vector去保存。更新的时候clear再一个个pus ...
分块入门
最近cf刷的有点难,请教一位大神,大神曰,“汝之惑,分块也”,所以小菜鸡来学分块了。
数列分块分块是我感觉是最优雅的暴力了,适用于同时区间修改和区间查询,而且书写十分方便。对于动态维护序列的题目我们一般会想到树状数组和线段树结构。
树状数组的限制十分明显,不能同时进行区间修改和区间查询地操作,只能支持单点修改+区间查询或者是区间修改和单点查询。虽然此题可以用树状数组做,但是主要还是练习一下分块。
线段树可以说是非常棒的动态维护序列的数据结构了,时间复杂度非常优秀,但是书写起来十分复杂。
分块也并不是万能的,如果同时区间修改和区间查询且数据范围在1e6的范围,那么分块就很可能超时了,此时只能使用线段树结构去维护这个序列。
各有优缺点吧,主要是分块的这个思想得学会,在很多地方都用得到。
下面给出分块算法中的一些特有名词
区间:数列中连续一段的元素
区间操作:将某个区间[a,b]的所有元素进行某种改动的操作
块:我们将数列划分成若干个不相交的区间,每个区间称为一个块
整块:在一个区间操作时,完整包含于区间的块
不完整的块:在一个区间操作时,只有部分包含于区间的块,即区间左右端点所在的两个 ...
AES加密学习
今天来学学AES。
AES简介高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传输就是用这个加密算法的)。对称加密算法也就是加密和解密用相同的密钥,具体的加密流程如下图:
分组问题AES属于分组加密,什么是分组加密呢,顾名思义,分组加密=分组+加密(狗头。分组就是说把它分成一个个组进行加密,可以把它和base64作为一个对比,base64是三个字符一组进行编码,那么既然是要分组那必然也会遇到分组不满的情况,这个时候需要加上填充。这个填充呢,有很多种方案。
零字节填充这个可以说是比较常见的手段了,一般人一般也都能想得到,但是这样的话难以区分末尾的0到底是它的信息本来就存在的还是填充的,信息表达不明确。
填充n位n这个略有点意思。但是假如它本来信息就有n位n呢?那么最后的那n位n还是没办法区分是不是它本来就有的。
那么最终AES采取了哪种填充方式呢?它选择在第二种方案中改进,如果长度刚好不需要填充,那么就填充16位16。这么一来,如果它末尾存在了n位n,但是由于长度满足16的倍数,那么还会填充16位16 ...
启发式搜索算法进阶
继续来学启发式搜索
多的其实没啥好讲了的,因为概念问题在前一篇博文已经讲的很清楚了。主要就是训练寻找估值函数,多点题目练习能应对不通场景下的启发式搜索。
例题洛谷上的p2324骑士精神
题目描述
主要就是说有个空格,然后所有马都走日,没有马脚,只能跳到空格里面去,然后问你是否能在15步以内达到。如果可以则输出最短步数,否则输出-1,因为空格只有一个我们不考虑跳马,考虑跳空格。
递归最大深度15层能确定了,但是任意一个状态可以延伸出最少2中最多八种情况。15作为指数时间上还是遭不住,考虑启发式搜索。那么估值函数需要怎么写呢?
估值函数这里再补充点估值函数的知识。
f(n)=g(n)+h(n)
估值函数一般表达式如上,g(n)为当前状态,h(n)为未来最优状态产生的花费,或者是其它。估值函数为两者和,由于当前状态我们很容易获取,所以算出未来最优状态即可等于获得了估值函数。可能前面讲的有点小问题,但是还是不妨碍的,因为我们平时写也基本是
123if(f(n)+value>ans){ dfs(n+1);}
所以问题不大。
题目分析在本题中,我们的 ...
启发式搜索算法
来快乐学算法了。
启发式搜索启发式搜索(英文:heuristic search)是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数,该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价,进而选择分支。简单来说,启发式搜索就是对取和不取都做分析,从中选取更优解或删去无效解。
在此之前,本蒟蒻一直就只会dfs和bfs,今天来学学新的搜索算法。经过多重资料的 查阅也是大概得知启发式搜索的大概思路,每次搜索会对之后可能的最优状态估值,如果估出来的值不如当前某些状态,那么我就直接舍弃这个状态。就比如经典01背包问题,我对每一个物品的抉择都有选或者不选两种选择,我发现我不选这个物品,选其它物品所产生的最优解不如我当前选这个解的状态好,那么我直接考虑选择这个而不去搜索不选择这个物品的状态。
估值函数这里需要解释一下我如何判断当前状态是否优于之后的最优状态,那么这里需要这么一个估值函数,估值函数不是真的对那个情况做具体分析,那样的话跟暴力没区别了。我这样考虑,如果剩下所有物品全能放进去都不如我一个放进去价值大,那么我肯定得放这个物品(前提是放得进去,放不进去就别讨论了)。那么这个 ...
RoarCTF2019 polyre writeup writeup
buu刷题记录-RoarCTF2019 polyre
初步分析拿到文件ida打开,发现是很绝望的究极无敌的代码混淆——控制流平坦化。
控制流平坦化介绍控制流平坦化(control flow flattening)的基本思想主要是通过一个主分发器来控制程序基本块的执行流程,例如下图是正常的执行流程
在经过控制流平台化的混淆之后,会变成如下的结构
流程图看起来就像是同一级的关系,块之间失去了层次分明,逻辑可读性变得更差。
就好比我们平时做的堆菜单题,选择菜单的时候,逻辑基本就是
1234567891011121314151617181920while(1){ menu(); int num=getnum(); switch(num){ case 1: add(); break; case 2: edit(); break; case 3: delete(); break ...
校园网模拟登录
学校更新了校园网之后,用的宽带就需要每天早上进行一遍网页登录才能有网,非常的麻烦,我就萌生出了想写个模拟登录的脚本的想法。
抓包获得请求方式这里我用wireshark抓包,只抓从登录到登录成功这个时间段的包,这里主要分析我们发送的http的流量包。
可以发现主要有两个流量包出现了username字段,那么主要分析这两个包内容的参数。第一个流量包内容如下
请求api为http://10.110.74.99/cgi-bin/get_challenge
主要有四个参数,callback,username,ip,和_。callback参数不太确定,但是可以确定username是自己登录校园网的账号,ip就是自己本机在这个局域网下的ip,而_很明显就是时间戳。而可以看到call_back后面也有一个类似时间戳的参数。这个暂且不确定,但是后面反复抓包可以发现,这个参数就是固定的。至于本次请求是返回了什么我们可以照着参数打进去看看返回了什么数据,本人很菜,不是打web的,不会用burpsuite只能用这种办法了。
可以发现返回了一串json数据,里面主要有一个challenge字段, ...
RC4加密的学习
最近有点颓废了,想学内核很难进行,逆向光刷题看着也很难,pwn刷题就是处于刷的感觉似曾相识,没有一点提升的感觉,所以我决定先攻一下逆向,把常见加解密算法先学了,今天先来这个RC4
RC4加密我初识RC4是在国赛,记得很清楚的一点就是不停地取模256,那题当时靠着网上资料勉强算过去了。但是还是想系统地学一下,网上教程千篇一律,我决定自己模拟一边它的算法过程然后再理解一遍。
既然是加密,脱离不了三个概念,明文,密文,密钥。RC4是对称加密,我也才知道,一直以为是不可逆的那种hash加密,所以既然它是对称加密,那么对于加密和解密过程,他们所用的密钥相同。它生成密钥的过程如下:
生成密钥需要一个长度不多于256长度的字符串作为种子生成随机密钥,这是我自己的理解,因为它确实给我的感觉就是这样的随机。它初始生成了一个长度为256的S串,初始S[i]=i,后面根据用字符串种子作为一个变换规则T,交换S密钥里的各个值,这样的交换好处在于我们可以保证S串密钥为一个双射(满足单射和满射,这个概念高中应该讲过,不赘述)。然后给的一个字符串种子呢,就会被放进T中,T的长度也为256,如果所给字符 ...
pwnable.kr input
学习Linux输入的五种方式
正则表达式的使用
最近在和战队一起的比赛中又出现了诸多想要学习的知识点,那就是re和QRcode,今天先学一下这个正则吧。
那么我已开始接触正则呢,应该是在学爬虫的时候,因为当时爬虫学的不太好也就没有接着学正则匹配。后来在换了linux系统之后经常会用到一个很有用的东西,那就是|grep。不得不说这个在找东西的时候真的是很有用的,比如
1$ls -l | grep ""
那么本次和Nepnep战队参加xctf分区赛也是有一道修复二维码的题目,当时师傅们可能有些点没注意到,导致最后修复的二维码多达16000的扫描结果。
得到结果之后本以为要经历漫长的人工过滤,可是咱们战队的一位爷爷直接solved,而这位爷爷就是直接用了正则匹配。
正则表达式正则表达式(英语:Regular Expression,常简写为regex、regexp或RE),又称正则表示式、正则表示法、规则表达式、常规表示法,是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里,正则表达式通常被用来检索、替换那些匹配某个模式的文本。
许多程序设计语言都 ...