算法学习
这里更新主要更新一些 模板 / 数据结构 /… 的题目吧
# 图
# 并查集
【定义】:用来管理元素分组情况的数据结构。并查集可以高效的进行如下操作:
查询元素 a 和元素 b 是否属于同一组
合并元素 a 和 b 所在的组
需要注意并查集只能进行合并操作,但是无法进行分割操作
【结构】:并查集是利用树形结构实现的。不过不是二叉树。
(1)初始化:
首先准备 n 个节点代表 n 个元素。最开始没有边。
(2)合并:
如图,从一个组的根向另一个组的根连边,这样两棵树变成一颗树,也就把两个组合合并为一个组。
(3)查询:
为了查询两个节点是否属于同一组,需要沿着树向上走,来查询包含这个元素的根是谁。两个节点走到同一个根,则说明他们属于同一组。下图 5,2 走到 1,7 走到 6,所以 7 和 2,5 不是同一组。
并查集实现中注意的点:
避免退化!
对于每颗树,记录这棵树的高度(rank)
合并时如果两棵树的 rank 不同,则 rank 小的向 rank 大的连边。
此外,通过路径压缩,可以使并查集更高效。对每个节点,一旦走到了一次根节点,就把这个点到父亲的边改为直连连向根。如图 ...
DFS--复习
先上题目:
# [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins
# 题目描述
农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛,以保持它们的健康,使喂给牛的饲料的种数最少。
给出牛所需的最低的维他命量,输出喂给牛需要哪些种类的饲料,且所需的饲料剂量最少。
维他命量以整数表示,每种饲料最多只能对牛使用一次,数据保证存在解。
# 输入格式
第一行一个整数 vvv,表示需要的维他命的种类数。
第二行 vvv 个整数,表示牛每天需要的每种维他命的最小量。
第三行一个整数 ggg,表示可用来喂牛的饲料的种数。
下面 ggg 行,第 nnn 行表示编号为 nnn 饲料包含的各种维他命的量的多少。
# 输出格式
输出文件只有一行,包括牛必需的最小的饲料种数 ppp;后面有 ppp 个数,表示所选择的饲料编号(按从小到大排列)。
如果有多个解,输出饲料序号最小的(即字典序最小)。
# 样例 #1
# 样例输入 #1
4100 200 300 400350 50 50 50200 300 200 ...
反序列化
# PHP 序列化问题 -> 主要是找链 分析代码
# 反序列化魔术方法
123456789__construct()//当一个对象创建时被调用__destruct() //当一个对象销毁时被调用__toString() //当一个对象被当作一个字符串使用__sleep()//在对象在被序列化之前运行__wakeup()//将在反序列化之后立即被调用(通过序列化对象元素个数不符来绕过)__get()//获得一个类的成员变量时调用__set()//设置一个类的成员变量时调用__invoke()//调用函数的方式调用一个对象时的回应方法__call()//当调用一个对象中的不能用的方法的时候就会执行这个函数
1234567891011__wakeup() //执行unserialize()时,先会调用这个函数__sleep() //执行serialize()时,先会调用这个函数__destruct() //对象被销毁时触发__call() //在对象上下文中调用不可访问的方法时触发__callStatic() //在静态上下文中调用不可访问的方法时触发__get() //用于从不可访 ...
正则绕过
# 代码执行函数
首先
eval()
最常见的代码执行函数 把字符串 code 作为 PHP 代码执行
eval ( string $code ) : mixed
assert()
检测一个断言是否为 false
PHP 5assert ( mixed $assertion [, string $description ] ) : bool
PHP 7assert ( mixed $assertion [, Throwable $exception ] ) : bool
assert() 会检查指定的 assertion 并在结果为 false 时采取适当的行动。在 PHP5 或 PHP7 中,如果 assertion 是字符串,它将会被 assert() 当做 PHP 代码来执行。
preg_replace()+/e
执行一个正则表达式的搜索和替换(一般用来)
preg_replace ( mixed $pattern , mixed $replacement , mixed $subject [, int $limit = -1 [, int &$count ...
Hackergame-2023
# Hackergame 启动
利用 burpsuite 拦截发送相似度的报文,对相似度修改为 100 即可。
# 猫咪小测
第一问搜索得值中科大中外书籍存在西区图书馆 12 楼,第二问在 arXiv 上搜索 chick 即可,当然也可以暴力,第三问 gpt 或者 CSDN,第四问 Google 搜索关键词 python typing check,halting problem, 检索 2023 年的文献即可得到 ECOOP 为会议。
# 更深更暗
直接在浏览器 F12 和 ctrl+f 搜索 flag 即可
# 旅行照片
根据图片或奖得主锁定东京大学,google 即可的出东京大学诺贝尔奖得主信息。
再实景地图找公园,锁定活动在 googl 找到相关线上志愿报名,门票钱搜索可知东京大学学生免费。
# 赛博井字棋
burpsuite 抓包发现下的棋子通过 x 和 y 定位,在棋盘本身不能下到电脑下过的地方,试一下修改 x,y 值到电脑下过的地方,发现覆盖,即可获胜。
# 奶奶睡前的 flag
这道题之前做过类似的似乎(虽然我做的题很少很少,但还是想起来最近某次比赛一道没做出来的 M ...
Hello World
This is the start!