集训队 题解2019 day

\(d<n\le 2e5,m\le 10,1\le p\le 10^9,0\le a_i\le 1e9\) 每个位运算之间独立，所以我们可以构造一个 \(\{2^{k-1},2^{k-1}.....\}\) 和一个 \(\{0,0,0...\}\) 的数组，让他们倍增去做如上运算，最后用他们把 \( ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

Typo Descreption 求反转一个不合法的括号序列中的一位使其成为一个合法序列的方案数（保证方案一定存在） Solution 其实也就是一道较复杂的模拟题 先判断哪一类括号数量更多，因为一定是将数量多的括号改成数量少的才有可能变为合法序列，这里就先用左括号举例 记录每个位置时没有配对的左括 ......

题目传送门 本题共有两种方法，分别是递归深搜和动态规划 方法一：递归深搜 Solution 从小到大一一枚举每一个划分的数，。只要找到一种方案就记录，具体细节代码中有注释。 Code #include <bits/stdc++.h> using namespace std; int n,k,ans; ......

A Equalize Prices Again 题解 题目大意 \(n\) 个商品，每个商品价格为 \(a_i\)，求一个最小的价格 \(x\)，使得不亏本（即 \(\sum\limits_{i=1}^n{(a_i-x)}\ge0\)）。 解题思路 输出平均数向上取整（即 \(\left\lceil ......

随机化写法很强，但是这里不说。 这里只记录数据结构写法。 枚举右端点，快速找左端点。 首先一种合法的方案中，一种颜色只会有两种情况。全部在区间中及全部在区间外。 对于区间外的情况，也就是最后一次出现的位置 \(p\) 大于右端点 \(r\)，我们可以维护当前枚举右端点之前的所有颜色非最后一次出现的点 ......

T1. 逆序对 给出一个长度为 \(n\) 的排列 \(a\)，你需要交换其中两个元素，使得逆序对尽可能少，输出逆序对变化量。 \(1 \leq n \leq 10^6\) 先推式子，考虑交换 \(x,y(x\leq y)\) 两个位置的逆序对变化量。 容易发现逆序对减少了： \[\sum_{k=x ......

由于太懒了，所以不想（会）写 \(\texttt{A B}\) 和 \(\texttt{F2}\)。 C Common Divisors 题解 题目大意 给定一个长度为 \(n\) 的数列 \(\{a_i\}\)，求 \(\sigma(\gcd\limits_{i\in[1,n]}\{a_i\})\ ......

思路 首先，\(A\) 和 \(B\) 只会移动一个，那么，我们分开来算，我们先假定 \(B\) 会动。 不妨令 \(A\) 与 \(b\) 连边的端点为 \(x,y\)。如果有线段 \(pq\) 能与 \(xy\) 相交，一定满足如下其中一条规律： \(p < x \wedge q > y\) \ ......

首先看到询问有关位运算考虑拆为处理，由于 \(a_i \leq 10^3\) 所以一个数最多有 \(10\) 位。 我们考虑对于一位它的贡献是多少，我们发现第 \(j\) 位一个连续段的异或值为 \(1\) 时会产生 \(2^j\) 的贡献，所以问题转化为快速求所有位上异或和为 \(1\) 的区间个 ......

A Short Sort 题解 题目大意 给定一个长度为 \(3\) 、由 \(a,b,c\) 组成的字符串，问可以不变或交换两个字符是的变为 \(\texttt{abc}\)。 解题思路 由于大小固定，所以预处理可行的字符串（仅包含 \(\texttt{abc acb bac cba}\)）即可。 ......

P2757 [国家集训队] 等差子序列 在线段树存哈希的时候，注意字符长度的改变，否则 query 会崩掉 lol query (int u, int l, int r, int lft, int rht) { if (lft <= l && r <= rht) return tr[u]; else ......

很妙的性质题！全是意识流证明见过吗？ problem 每次选一个非空边集删掉，谓之曰砍树。砍树后需要满足每个连通块的点权和相同。 在一个方案中可以砍很多次树，都要满足砍树后的要求。一共有多少种合法方案呢？ \(n\leq 10^6,1\leq a_i\leq 10^9\)。 solution 假如我 ......

高级语言大体上分为：面向过程和面向对象两大类 C语言是典型面向过程的语言。C++，java是典型的面向对象的语言 Java帝国的诞生（一场旷日持久的战争） 1972年C诞生 贴近硬件，运行极快，效率极高 操作系统，编译器，数据库，网络系统 指针和内存管理 1982年C++诞生 面向对象 兼容C 图形 ......

传奇团子师傅题解（模拟退火） 申明： 本篇题解借鉴了： https://www.luogu.com.cn/blog/SDNetFriend/solution-p7218 这篇博客（主要在bitset部分）。 题意： 给你个矩阵，包含三种颜色，一个美丽串要求你横着或者竖着或者斜着串成一串的三个颜色有特 ......

原理 常规注入 解题过程 进入登录界面，还是使用万能登录试一试 payload:1' or 1=1# 没想到成功了，说明字符型注入使用的'爆出的密码应该是MD5加密，爆破很麻烦，试试常规注入 payload:1' order by 4# payload:1' order by 3# 找出列项 pay ......

原理 抓包工具的使用 解题过程 进入靶场，什么也没看出来，老规矩查看页面源代码，发现个php文件，那就点开试试 又有一个php文件，再点开 却啥也没有，那就抓个包看看 因为肯定发生了跳转，明明请求的是action.php却变成了end.php 果然抓到了。那就继续访问secr3t.php 发现了文件 ......

原理 ||的不同功能，连接字符串和或 堆叠注入 解题过程 进入靶场，按常规进行注入，发现过滤了很多关键字，跑一下fuzz 试试堆叠注入 payload:1;show tables; 得出放flag的表，但flag字段被过滤了。 看wp原代码查询语句是select $_POST['query']||0 ......

题目传送门 思路： 设有两个颜色 \(x_1 x_2\) ，两端分别为 \(l_1\) \(r_1\) ， \(l_2\) \(r_2\)。通过观察可以发现，若满足 \(x_1<x_2\) 且 \(r_1 > l_2\) 则 \(x_1 x_2\) 一定是单调不下降的。 那么我们可以先预处理出一个颜 ......

原理 --四种解法 sql语句查询表结构和表名和数据库名的方法不止select这一种 预编译 sql转十六进制绕过 handler读表内容 解题过程 进入靶场，提交查询。 字符型注入看是'还是" 最终发现'有空白错误界面，说明是' 接着按常规进行order by猜解。最终确定列项为2 使用联合查询， ......

day01 计算机基础和环境搭建 课程目标：让大家了解计算机基础知识并完成Python的环境搭建。 课程概要： 计算机基础 编程的本质 Python的介绍 Python环境的搭建 1.计算机基础 1.1 基本概念 计算机的组成 计算机是由多个硬件组合而成，常见的硬件有：CPU、硬盘、内存、网卡、显示 ......

题目链接 对于括号问题，考虑区间 \(dp\)。这道题的括号序列是固定的，所以直接找出每个括号对应的括号在进行转化即可。 设 \(f_{l,r,0/1/2,0/1/2}\) 表示 \(l\sim r\)，左括号不染色/染红色/染蓝色，右括号不染色/染红色/染蓝色的方案数。 若 \(l,r\) 是一对 ......

原理 RCE命令执行的多种绕过姿势 解题过程 进入靶场提示要传递参数ip 那就传递一下127.0.0.1,结果正常 试试进行拼接，试了127.0.0.1&&ls或者127.0.0.1&ls都不行，，，直到用；做连接符才可以 payload:127.0.0.1;ls 发现有index.php和flag ......

最详细的题解 题目传送门：Progressions Covering 阅读前人题解时，限于个人能力有限，有一些地方想了好一会儿才懂。发现很多题解都是在 @SDLTF_凌亭风 等作者基础上延伸，但详细程度依旧有限，尽管这篇题解亦是站在他们基础上延伸的，这篇题解更为详细的点明了很多地方。 本人第一次写题 ......

Day5 T1 赛时写了三个点终于写出来了 好的三元组定义为 \[P = a_i \times 2 ^ {\lfloor log_2^{a_j} \rfloor + 1 + \lfloor log_2^{a_k} \rfloor + 1} + a_j \times 2^{\lfloor log_2^ ......

题意 给定一棵由 \(N\) 个节点组成的树，每个节点有黑白两种颜色。定义一个节点 \(u\) 为好的当且仅当路径 \(1 \leftrightarrow u\) 上的节点均为黑色的，反之为坏的。初始情况下所有点均为白色。 定义一次操作为选取一个坏的节点并将其染黑，求将全部节点均染为黑色的期望操作次 ......

题目链接 Power Tree 分析 将叶子节点按dfs序重标号后，每次控制操作可以转化为将子树内叶子节点所在区间加（或减）一个数 不难可以想到将叶子区间进行差分 每次对 \(l\) 到 \(r\) 的操作可以转化为将 \(l\) 上的数转移到 \(r+1\) 上 每次操作后差分数组的和不变 将所有 ......

T1 思路:因为只有三个串故枚举其中一个为调换的串，再枚举k验证即可。 T2 思路:正着不好做，考虑反着做。这样就不会覆盖之前的。赛时没想到这个常见套路，正难则反。 T3 事实上只有一种情况，故只需倒着枚举遇到a统计答案。使用一个变量sum来记录遇到下一个a的次数 如果枚举到b,sum+=1。如果遇 ......

CF632F - Swimmers in the Pool 题目传送门 题意 给定一个大小为 \(n \times n\) 的矩阵 \(A\) 。假设 \(A\) 满足以下条件，那么称该矩阵为 MAGIC ，否则为 NOT MAGIC ，并输出对应的属性（即 \(A\) 是 MAGIC 还是 NOT ......

9.30 考试 考试开始后看了所有题，感觉T4不可做，然后顺序开题。 T1是模拟游戏“2048”，把棋盘上剩余格子和移动后棋盘的信息维护好就行了。我考试时没有注意初始棋盘点数不固定；输出一种条件的步数写成了棋盘大小，但还好只挂了20pts。 T2和单调数列有关，但是需要推一个重要的性质，再将题转化成 ......