CTF Web 原创题三道

为不存在的校内赛出了三道（可能会被采用）的 CTF 题，主要是 Web 方向。

题一：easy_calc ，涉及 Node.js、SQL；

题二：easy_template，涉及 PHP；

题三：easy_pickle，涉及 Python。

提供各题 docker 环境，设计思路及具体 write-up；基于 Apache 2.0 License。

 …

OpenWrt 打通 IPv6 校园网

搞到了个校内 PT 站的邀请码，结果发现那站只有用 CERNET2 IPv6（≈校园网）才能访问……在宿舍里放个 NAS 显然不是那么现实，于是只能想个办法打通校园网，将主要数据存放在云服务器上。（就先不追求延迟和速度了，毕竟那个破烂路由器的 CPU 和宿舍里的百兆网口不是很允许……）这里采用的就是 OpenWrt 当中转的方案。

 …

Wireguard Network, Chaining and Routing

最近自刀了一个深港 IPLC（吃不起饭啦），分有深圳端和香港端两公网 IP 和两内网 IP，内网走的是 IPLC。如果只用 NAT / Port Forwarding 的话未免也太逊了点，对不起我这个钱啊（不x）！于是就尝试通过一些奇妙的操作想把它们 “串” 起来，然而过程可想而知并不是那么的顺利……（

 …

栈溢出 —— 初级 ROP 学习记录

首发 CTF 后再次深刻体会到了自己以前对栈溢出的理解是如此的不深刻，故趁着剩下这没几天的时间（不是应该拿来补作业吗？）学习了一下初级 ROP 的原理及应用。

同样因为是初级学习经验，故神犇请自觉绕路（（

 

 …

菜鸡首发 CTF || 部分 WriteUp & 学习经验

靠着神通广大的群友关系（）混进了 HIT 的 CTF 队招新比赛，学到了很多姿势和 pwn 经验，故在此记录一下。

萌新菜鸡首发 CTF，题目比较简单，而且还没有 AK，神犇请自觉绕步（

还有 %%%%%% rxz mcfx

 

 …

[研学] 质因数分解及素性判定

[研学] 质因数分解及素性判定

时间：2018.10 ~ 2019.3

参加成员：Modem_  Lagoon   _Qijia   mnihyc

感觉这个是人生巅峰了， Lagoon 上清华，剩下我们三也退役了，摆在这留作纪念ww  拿濑户口的话来说，就是萌新那会才是最辉煌的时期www

  • 【序言】

质数的研究一直是数学与信息学领域中的重要课题，质数的判定与质因数分解在现代通讯保密领域中更是发挥着重要的作用，本课题小组将通过此次研学机会对不同规模下自然数素性判定及质因数分解的有效算法进行探究，加深对该领域的了解和理解。

 

  • 【1.0】素数的定义

素数，又称质数。一个数 \(n\) 是素数当且仅当它是大于 \(1\) 的自然数且它的因数有且仅有 \(1\) 与 \(n\) 。

 

  • 【1.1】记号与规定

    1. 记 \(\displaystyle\mathbb{R}\) 表示实数集，\(\displaystyle\mathbb{N}\) 表示自然数集，\(P\) 表示素数集。
    2. 勒让德符号 \(\displaystyle\left( {\frac{n}{p}} \right)\)。设 \(\displaystyle p \in P,n \in \mathbb{N}\)。

 

  • 【1.2】素数的一些性质

    • \(P\) 是无限集。
    • 对于任意大于 \(1\) 的自然数，它要么是个素数，要么可以分解为若干素数之积，并且在忽略顺序的情况下，这样的分解是唯一的。
    • 小于 \(n\) 的质数大约有 \(\ln n\) 个。
    • 一个合数 \(n\) 最小的素因数因数一定小于 \(\sqrt n \)。
    • 费马小定理：设 \(p\) 是大于 \(2\) 的素数，则对于任意正整数 \(n\) 均有 \(\displaystyle \begin{array}{*{20}{c}}{{n^{p – 1}} \equiv 1}&{(\bmod p)}\end{array}\)。
    • Mertens’ second theorem。

 

  • 【2.0】素性判定

因为素数集为无限集，并且素数的分布没有规律，所以我们需要实现一个算法来判定一个数是否为素数。而素性判定算法正是这样一类算法：输入一个整数，返回这个数是“素数”还是“合数”。…

[研学] 偏序问题的研究

[研学] 偏序问题的研究

时间：2019.04 ~ 2019.09

参加成员：Modem_  Lagoon  _Qijia  mnihyc

备注：第二年就开始混水了啊（笑），只存了自己写的那部分：

  • 高维偏序

至此，\(k \le 3\) 的问题已经被我们解决了。

那 \(k = 4\) 呢？CDQ套CDQ？CDQ套树套树？树套树套树？

如果 \(k\) 更大，达到 \(k = 10\) 呢？十维树状数组？树套树套树套树套………？

很明显 \(O(n{\log ^{k – 1}}n)\) 的复杂度是承受不起的，需要从别的方面下手。

注意到在 \(k\) 变大的同时，\(n\) 也在变小，所以可以考虑复杂度以 \(n\) 为主的算法。

首先考虑的，当然是暴力啦）。

可以暴力枚举所有维度，并且按照这个维度（上的数）排序，这些就可以快速找出一个点控制了其它哪一些点。如果把这个信息用一个长度为 \(n\) 的二进制数表示，那么对于每个询问，只需要把它在所有维度下的二进制数取“与”运算（即能控制的点取交集），这样答案就是二进制位为 \(1\) 的数量了。

维护二进制串？当然是用 std::bitset<>  啦）。

这样复杂度就是 \(\displaystyle O\left( {\frac{{{n^2}k}}{{32}}} \right)\) ，足以通过本题了。

 

代码略。

 

这里其实还有一种在时空复杂度上的优化——分块）。

按照分块的那一套理论，把区间分成 \(\sqrt n \) 个，每块用一个 std::bitset<>  维护前缀，同时维护一个块最大值。查询的时候在块上二分，找到询问点所在的块，然后暴力加块内的点即可。时间复杂度即可缩小至 \(\displaystyle O\left( {\frac{{nk\sqrt n }}{{32}}} \right)\) 。

 

 …

YZOJ P4643 [BJOI2018] 链上二次求和

[BJOI2018] 链上二次求和

时间限制：4000MS     内存限制：131072KB

难度：\(6.2\)

  • 题目描述

YJC 有一棵 \(n\) 个节点的树， \(i\)、\(i+1\) （\(1 \leq i < n\)）节点间有一条边，第 \(i\) 个点的权值为整数 \(a_i\) 。

现在他有 \(m\) 个询问：

操作 \(1\)（修改）：给定树上两个节点 \(u\)、\(v\) 和一个整数 \(d\)，表示将树上 \(u\) 到 \(v\) 唯一的简单路径上每个点权值都加上 \(d\)。

操作 \(2\)（询问）：给定两个正整数 \(l\)、\(r\) ，表示求树上所有节点个数大于等于 \(l\) 且小于等于 \(r\) 的简单路径节点权值和之和。由于答案很大，只用输出对质数 \(1000000007\) 取模的结果即可。

一条节点个数为 \(k\) 的简单路径节点权值和为这条上所有 \(k\) 个节点（包括端点）的权值之和，而本题中要求是对所有满足要求的简单路径，求这一权值和的和。

树边是无向的，所以路径也是无向的，即点 \(1\) 到点 \(2\) 的路径与点 \(2\) 到点 \(1\) 的路径是同一条，不要重复计算。

  • 输入格式

输入第一行包含两个正整数 \(n\)、\(m\)，分别表示节点个数和操作次数。

第二行包含 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 为第 \(i\) 个点的初始权值。

接下来 \(m\) 行，每行为 1 u v d  或 2 l r  的形式，分别表示进行一次操作 \(1\)（修改）或操作 \(2\)（询问）。

  • 输出格式

对于每次询问，输出一行一个整数，表示答案对 \(1000000007\) 取模的余数。…