题解p9669 jinan order

好久没写博客，上次写还是在上次（三年前）。 如题，写一次CTF的题解 根据题目提示得知这应该是一个注入，什么注入还不知道，进入靶场。 仅有三个地方可点，都点进去看看。 从URL处可以看到前端是传了一个参数id给后端（另外两个类似，就不贴图了）。 那很明显了是SQL注入。 首先在参数后面打个'（单引号 ......

CSP-J 2023 题解 T1 小苹果 这个题直接遍历枚举必定 TLE，这是 CCF 的出题风格，每题 T1 巨水无比，但是往往又需要一些思维。 这道题我们可以发现每一轮操作都会拿走 \(1 + (n - 1) / 3\) 个苹果，所以每次让 \(n\) 减去 \(1 + (n - 1) / 3\ ......

非常显然的，我们展开 \(f(k)\)，于是有： \[\begin{align} &\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}k^{i}x^{k}\binom{n}{k}\\ =&\sum\limits_{k=0}^{n}\sum\limits_{ ......

分析 看到这个题就想到了二维偏序。 你们很自然地，以 \(b\) 为第一关键字降序排序，当有若干个片 \(b\) 相等时，我们发现由于 \(a < b\)，所以排到最后的片一定能把这些 \(b\) 相等的片都统计上，而前面的片能否统计是依赖于 \(b\)，所以考虑如何让后面的片更好统计，显然 \(a ......

NOIP2023模拟5联测26 题解 感觉我这场的官方题解写的是真的挺好的，所以我只能作少量补充。你可以直接去看官方题解，如果你想的话。 T1 x 题解 \(n = 2\) 没啥可说的。\(\color{white}{这档分你要是没拿到那你还是蛮强的。}\) \(n = 3\) 的时候，我们需要比较 ......

PTA数组及排序查找题解与解题思路 函数题目 函数题目为平台提供的裁判程序调用所完成的函数进行判题，题目规定语言为C语言 6-1 求出二维数组的最大元素及其所在的坐标 本题较为简单，考察的是如何遍历一个二维数组，只需要两个循环依次遍历其每个维度和元素即可 如何寻找最大值？只需要在遍历每个元素的过程中 ......

[TopCoder 13001] BigO 题解 题目描述 给定一张有向图，当 \(L\) 趋近于无穷大时，长度为 \(L\) 的路径条数有 \(S\) 条，此时若 \(S = O(L^k)\)，输出 \(k\)，否则如果没有多项式的大 O 表示法，输出 \(-1\)。 指数情况 首先如果一张图中存 ......

具体思路 设 \(f_{i,x}\) 表示 \(i\) 个盘子从 \(x\) 柱子出发的步数。 设 \(g_{i,x}\) 表示 \(i\) 个盘子从 \(x\) 柱子出发到哪个柱子。 记 \(y=g_{i-1,x}\)，\(z=6-x-y\)。 其中，\(y\) 代表将前 \(i-1\) 个盘子从 ......

非常好题目，第一步都想不出来。 可以观察出来最优方案必定是从大往小将 \(x\) 放到 \(x+1\) 前，有可能不动，中间的比他小的一定要放到前面去。考虑用 dp 计算最小值。 这里是这道题最重要的一步：相对位置的变化非常不好描述，考虑将所有数固定。一次操作改为：不影响其他其他数的位置，将一个数放 ......

传送门 提供一种基于贪心的解法。 首先是将 \(p\) 从小到大排序 考虑到该系统是一棵树，所以对于系统中的每个点，我们记： \(tr_{son}\) 表示该点(目录)的儿子的位置 \(tr_{fa}\) 表示该点(目录)的父亲的位置 \(tr_{siz}\) 表示该点(目录)包含的点的个数 \(t ......

题目传送门 题目大意 给定一个长度为 \(N\) 的序列 \(a\)，可以进行最多 \(K\) 次操作，每次操作可以选择一个区间加 \(1\)。 求操作之后最长的最长不降升子序列长度。 \(1\le N\le 10^4\)，\(1\le K \le 500\)，\(1\le a_i\le 5000\ ......

目前只有 T2，其他题目我在看。 题目链接1 题目链接2 题目链接3 T2 很简单的一道题，将图分为若干个连通块，然后分别求最小生成树。 从货车运输中得到的结论，最小生成树等价于最小边权上限生成树，也就是它也能够保证选出边中最大的边权最小。 而题目中明确说了这个最小生成树的权值是其中边权的最大值。 ......

[NOI2010] 超级钢琴 题解 说点闲话 原本不想写这个题解的 但是看到我的代码居然长度为2048B->刚好2KiB，然后还跟题号相同QAQ 题目翻译 给你一段序列，求出其中从第\(1\)大到第\(k\)大的子区间的和。 思路解析 首先可以想到一个简单的暴力，对于每一个区间开头\(i\)，和区间 ......

今年的 \(CSP−J\) 对本蒟蒻来说有点难度。。。 A [CSP-J 2023] 小苹果 题目描述 小 Y 的桌子上放着 \(n\) 个苹果从左到右排成一列，编号为从 \(1\) 到 \(n\)。 小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。 每天在拿的时候，小苞都是从左侧第 \(1\) ......

[TJOI2013] 松鼠聚会 题解 切比雪夫距离 切比雪夫距离指的是在平面上的两个点\((x_1,y_1)\),\((x_2,y_2)\)之间横纵坐标之差绝对值中的大者。用公式表示则是\(f(a,b)=max(|x_a-x_b|,|y_a-y_b|)\)。 切比雪夫距离与曼哈顿距离之间可以相互转换 ......

[NOIP 2013提高组]货车运输题解 前置知识 Kruskal 重构树（内含讲解）+任意一种LCA 题目翻译 \(n\)座城市，\(m\)条道路，\(q\)次询问，每次求两个点\(x,y\)之间所有路径的最小值的最大值。 题目分析 其实学了Kruskal重构树差不多看到这个题目就知道怎么写了。 ......

分析 发现每个字符串只会被它的后缀规定，那么就从后往前计算，使得计算每个字符串的时候其后缀已经合法。 因为每一次计算我们都只想删最少的字符，而且删得越少这个字符串的字典序就越大，所以它的前缀的最小字典序就越大，需要删的字符就越少，所以对于每一次计算都只删最少的字符的贪心策略符合全局最优，所以这个贪心 ......

分析 先对每一列都做 DP 寻找极长单调不降区间，能够得到若干极长单调不降区间，只要询问的区间是这些区间的子区间，那么说明在这个区间内必有一列的这个区间是单调不降的。 思考如何快速判断子区间。 用 \(f_{x}\) 表示以 \(x\) 为所有左端点为 \(x\) 的区间的右端点最大值，那么对于询问 ......

分析 思考对于 \(M\) 的每个数而言，贡献是一定的，它最多只能换掉一个数。 那么贪心地能换就换，但是如果换小的可能会导致更小的数换不掉，那么就换能换的最大的，这样不会干扰只能换小数的其他数，能换这个数的可以去换其他数，如果连其他数都换不掉说明这两个数等效，换谁都一样，所以这样换一定是最优的。 如 ......

分析 发现操作 \(6\) 次后就会回到初状态，于是将状态打表，将 \(n\bmod6\) 即可。 代码 #include <iostream> using namespace std; constexpr int MAXN(1000007); int a[6][3] = { {0, 1, 2}, ......

分析 看到异或不难想到 01Trie。 不难想到，当两个数的值相等的时候，我们可以当这两个点是一个点，因为连边的费用为 \(0\)。 那么对于一个序列 \(n\)，若存在 \(m\) 种不同的权值，那么在 Trie 树上子节点数为 \(2\) 的节点就有 \(m-1\) 个（因为如果一个数新加进来与 ......

20231026 P3400 仓鼠窝 题解-单调栈典题 Statement 传送门 输出 01 矩阵中不含 0 的子矩阵的个数。\(n,m \le 3000\) Solution 很妙的做法，典题，于是写了题解。 做法也很简单，就是你枚举每一个节点作为右上角的点的方案数， 发现其实有很多无用的点，比 ......

前言 去年多测不清空导致即便 CCF 放过了我的 \(O(n^2 m)\) 的代码但依然挂成了 \(0pts\)。 当时看清空数组后能过 CCF 数据就没再管。 时隔 \(1\) 年，重做这道题写了 \(O(nm)\) 的正解，终于完成了当年的心愿。 \(O(n^2 m)\) 思路 想到计算方案的话 ......

几万年前做的 dp 题了，有亿点点水 题意简述 求一个字符串添加多少个空格距离最小 解法 求距离最小，可以考虑动规，其实这题的写法和最长公共子序列的写法类似。 我们设 \(f(i,j)\) 表示 \(a[1] \sim a[i]\) 和 \(b[1] \sim b[j]\) 的距离 不加空格的时候为 ......

同步发布与洛谷（太懒了不想写东西直接搬过来了（（（逃 ） 原题链接 简单贪心。 题意 求一个起始全为 \(0\) 的数列 \(a_1,a_2 \cdots a_n\) 每次可以选择一个数 \(i\) 使 \(a_i \cdots a_n\) 都加上或减去 \(1\)，求修改成给定的序列 \(b_1, ......

题意 给定一个满足 \(A_i=i\) 的排列 \(A\)，求对其进行一次 \(\mathrm{shuffle}(1,N)\) 操作后其第 \(K\) 项的值。其中 \(\mathrm{shuffle}(L,R)\) 的定义如下： 若 \(R = L + 1\)，那么交换 \(A_L\) 和 \(A ......

P4678 [BalticOI 2005] Bus Trip 题解(RE:题解再改造!!) 贴码 #include<bits/stdc++.h>#define MAXN 500010using namespace std;//ifstream is("trip.in",ios::in); //ofs ......

分析 手玩样例发现连一条边实际上是将一个多边形分割成两个部分，而且不能在这两个部分直接连边，发现这两个部分是完全独立的，于是考虑区间 DP。 设状态 \(f_{l,r}\) 表示将 \([l,r]\) 区间连成树的方法数量。 那么存在两种转移，一种是 \(l,r\) 间不直接连边，这样中间的点都需要 ......

考虑预处理。 处理 $a$ 数组，每次走到一个位置 $i$，往前搜索。 当前位置不等于 $i$ 则通过这个位置继续往前查找。一直到当前位置等于 $i$，或者到达最前端则停止。 接下来进行第二次处理。 由于已经对 $a$ 进行过预处理，在计算时只需要从有值的点分别往前统计即可。 最后求一遍和。 /* ......

CF1586I 题解 传送门 更好的阅读体验 简化题意：有 $n\times n$ 的网格，你需要进行黑白染色，使得每个格子的颜色恰好与 2 个与其四联通的格子的颜色相同，其中有些位置已经确定，问是否有解及是否有唯一解。 思路： 很神仙的构造题。 先从特殊的地方入手。对于 4 个角，它们只和 2 个 ......