为不存在的校内赛出了三道(可能会被采用)的 CTF 题,主要是 Web 方向。
题一:easy_calc ,涉及 Node.js、SQL;
题二:easy_template,涉及 PHP;
题三:easy_pickle,涉及 Python。
提供各题 docker 环境,设计思路及具体 write-up;基于 Apache 2.0 License。
时间:2018.10 ~ 2019.3
参加成员:Modem_ Lagoon _Qijia mnihyc
感觉这个是人生巅峰了, Lagoon 上清华,剩下我们三也退役了,摆在这留作纪念ww 拿濑户口的话来说,就是萌新那会才是最辉煌的时期www
质数的研究一直是数学与信息学领域中的重要课题,质数的判定与质因数分解在现代通讯保密领域中更是发挥着重要的作用,本课题小组将通过此次研学机会对不同规模下自然数素性判定及质因数分解的有效算法进行探究,加深对该领域的了解和理解。
素数,又称质数。一个数 \(n\) 是素数当且仅当它是大于 \(1\) 的自然数且它的因数有且仅有 \(1\) 与 \(n\) 。
因为素数集为无限集,并且素数的分布没有规律,所以我们需要实现一个算法来判定一个数是否为素数。而素性判定算法正是这样一类算法:输入一个整数,返回这个数是“素数”还是“合数”。…
时间: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)\) 。
时间限制: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\)(询问)。