貳壹肆の博客

【算法】分治算法分治算法通过递归分解大问题为若干个子问题, 解决每个子问题后合并各个子问题, 直到合并为原来的大问题. 归并排序归并排序是经典的分治解决问题的算法, 通过分解数组, 递归求解, 合并排序这三个步骤对数组排序. 先分析归并排序的复杂度, 由于每次合并需要遍历所有数组, 共 $n$ 次, 然后需要遍历每一层, 一共有 $log_2n$ 层, 所以归并排序的复杂度为 $O(nlogn)$ , 是稳定的排序算法. 由于归并过程允许我们对每一个子问题操作, 所以归并排序可以解决很多问题, 以一道题目为例: 这道题在合并过程中, 可以通过合并右边那部分数组的移位差来获得逆序对的个数, 比如 5 和 4 合并时, 4 从第 1 位移到了第 0 位, 所以逆序对个数+1, 同理 45 和 26 合并时, 2 从第 2 位移到了第 0 位, 逆序对+2… 这里由于只有右半部分会产生逆序对, 需要定义一个 mid 变量去获取归并时的中间值,确保只对左半部分求移位差, 如下图: 代码为: 1234567891011121314151617181920212223242526272829 ...

【算法】暴力求解法简单枚举简单枚举的基本思路就是, 枚举起点, 枚举终点, 然后里面再去做运算, 例题: 对于这道题, 如果使用暴力枚举法的话, 就要枚举每一个元素作为起点, 再枚举每个元素前面的元素作为终点的情况, 代码如下: 12345678910111213141516171819202122232425262728293031#include<iostream>using namespace std;int main(){ int n; int ncase=0; while(cin>>n){ // 注意会溢出 long long ans = 0; long long num[100]; for(int i=0;i<n;i++){ cin>>num[i]; } for(int i=0;i<n;i++){ for(int j=0; i+j& ...

【算法】基础数据结构的使用单调栈通过维护一个单调递增或者单调递减的栈, 来求解元素左右大小边界的问题. 尝试思考下面这个问题, 对于第 1 个元素, 他往右边看, 除了比他高的, 都会被挡住(如第 3 个和第 4 个元素), 而这个就是单调栈的核心思想, 在这里被挡住的元素对当前节点来说是没用的信息, 所以单调栈维护的是当前节点往右边看, 不会被挡住的元素. 来看一道例题 这道例题中, 需要我们找到第一个大于当前元素的元素的下标, 那就是一个大小边界的问题, 我们直接从这个序列的最右边开始遍历, 然后为每一个节点维护一个单调栈. 即当前栈中如果存在比他小的, 就直接 pop 出去即可, 因为对于当前元素后面的元素, 这些都是被挡住的元素. 代码为: 1234567891011121314151617181920212223242526#include<iostream>#include<stack>using namespace std;const int MAXN = 3e6+2;int n, num[MAXN], ans[MAXN];stack<i ...

【HITCTF2023】 Network in network 神经网络图片恢复题目描述拿到题目后, 有三个文件, 一个是模型源码, 一个是跑模型编码后的图片, 还有模型的 pt 参数文件. 源码为: 12345678910111213141516171819202122232425262728293031323334import torchimport torch.nn as nnimport torchvision.transforms as transformsimport torchvisionfrom PIL import Imageimport matplotlib.pyplot as pltimport numpy as npfile = Image.open('origin.jpg')trans = transforms.Compose([ transforms.ToTensor(),])m = trans(file)torch.manual_seed(0x2daa1a1)net = nn.Sequential( nn.Conv2d(3, ...

【算法】算法基础与 STL时间复杂度时间复杂度是算法中基本操作执行次数的数量 时间复杂度排序为 在一般的算法测评机中, 大约 1 秒钟能够执行 $510^8$ 条指令, 也就是说对于 $O(n^2)$ 时间复杂度的算法, 假设 $n$ 最大为 $10^5$, 那么需要的时间最大为 ${(10^{5})}^2/510^8$ 约为 20 秒运行完毕. 在做题的过程中要提前计算运行时间来选择合适复杂度的算法. 空间复杂度空间复杂度是运行时所需空间的度量 对于空间复杂度, 除了要计算所给限制以外, 还需要记忆各个类型最大值, 如下 避免在写代码时发生类型上溢导致判题不通过. 常见的 STL 容器Vector12345678910#include<vector>vector<int> vec; //定义vec.push_back(a); //往后添加元素vec.insert(vec.begin()+1,2); //在下标[1]处插入 2 vec.pop_back(); //移除末尾元素vec.erase(vec.begin()+1); ...

【NewStarCTF2023】Final thinkphp 漏洞与提权题目描述打开靶机后, 是一个 thinkphp 的默认页面, 所以很有可能就是挖掘 thinkphp 的漏洞, 先在路径上输入一些默认参数查看其版本号. 可以看到是 ThinkPHP V5.0.23. 解题过程去谷歌搜索 ThinkPHP V5.0.23 漏洞, 发现有 RCE 漏洞,用 POST 构造请求参数为 /?s=captcha 构造的 payload 为 1_method=__construct&filter[]=system&method=get&server[REQUEST_METHOD]=whoami 这边的用法是 filter[] 参数中输入要执行的命令类型,server[REQUEST_METHOD] 里输入要执行命令的参数. 构造 payload 发送后没有回显, 说明很有可能把 system 给禁止了, 所以构造下面这个 payload 看看他的 phpinfo 1_method=__construct&filter[]=phpinfo&meth ...

【API安全漏洞学习】Paypal IDOR 漏洞 - 2019-7-30漏洞描述Paypal 平台中存在企业账号与对应的子账号, 企业账号通过委托授权子账号来管理账号上的资金, 对于不同的子账号拥有不同的权限和功能.用一张图来理解就是: 攻击者发现在这个 Paypal 的这个功能中存在 IDOR 漏洞, 能够通过实现子账号间越权访问. 漏洞成因IDOR (Insecure Direct Object Reference), 又对象级授权问题, 它涉及到对Web应用程序或API中对象的不安全引用。这些对象通常是数据库记录、文件、目录等。当应用程序提供对这些对象的直接访问，并且没有适当地实施访问控制时，就会产生IDOR漏洞。 常见的 IDOR 漏洞有: 用户数据泄露: 通过修改 URL 中的 ID 获取其他用户的隐私信息, 更严重的包括更改, 删除他人的信息. 文件访问和泄露: 对于本没有权限访问的文件, 通过修改 URL 中文件的编号来越权访问. 在本次漏洞中, 攻击这发现“查看子账号”功能中有一个 URL 为 https://www.paypal.com/businessman ...

【隐私计算】 秘密共享方案Shamir 秘密共享方案Shamir’s Secret Sharing Scheme is based on Lagrange Interception. Now suppose there are $n$ people, and $t$ is the threshold for secret recovery Construct a polynimal at first, the form like: $$ P(x) = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + \cdots + a_2x^2 + a_1x + a_0 $$ Setting $a_0$ as the secret. Each person is allocated a secret share represented as $(i, a_{i}x^{i})$. For the secret recovery, we need to construct a Lagrange Interception to compute the coefficients ...

【AWD】Linux 提权 - 信息枚举大部分攻防场景, 在维持权限获取 shell 后, 很可能会分配到一个低权限用户, 提权到 root 级别的管理员用户才有 getshell 的意义. 权限体系SUID SGIDSUID(Set User ID) 和 SGID(Set Group ID) 统称为 S 位, 被设置在可执行文件上, 当这些位被设置时，文件或程序将以文件所有者或组的权限运行，而不是以运行它的用户的权限运行。 SUID: 当 SUID 位被设置, 无论谁运行这个文件，该文件都会以文件所有者的权限执行, SUID位通常表示为文件权限字符串中的一个s字符，如果权限是可执行的话，否则它是一个大写的S。 SGID: 当 SGID 位被设置, 该文件会以文件组的权限执行。当SGID设置在目录上时，创建在该目录下的任何新文件都会继承该目录的组ID，而不是继承创建它的用户的主组ID。SGID位在文件权限字符串中也表示为s或S，取决于组权限是否可执行。 AppArmor SElinux AppArmor 是一种主要基于路径的强制访问控制（MAC）系统，它允许系统管理员为每个程序定义 ...

【NewStarCTF2023】 Include🍐 pearcmd 文件包含题目进入靶机, 看到代码: 12345678910111213141516<?php error_reporting(0); if(isset($_GET['file'])) { $file = $_GET['file']; if(preg_match('/flag|log|session|filter|input|data/i', $file)) { die('hacker!'); } include($file.".php"); # Something in phpinfo.php! } else { highlight_file(__FILE__); }?> 注释提示 ...