蓝桥 题解 巧克力p8769

发现更多计算机知识，欢迎访问Cr不是铬的个人网站 D迷宫逃脱 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢? 这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候，会消耗一把钥匙。当没有钥匙的时候就不能移动了。想到这里，我们可以定义一个三维的dp数组. 定义dp dp[ ......

feecle 的题单 . 后文复杂度分析中默认 \(v\) 是值域 . 目录CF1292B Aroma's Search (*1700)CF1304C Air Conditioner (*1500)CF1313D Happy New Year (*2500)CF1322B Present (*210 ......

目录DescriptionSolutionCode Description 在一个教室里有 \(n\) 排座位，每排有 \(6\) 个，从左至右标号分别为 ABCDEF，其中 C 和 D 中有过道，通往教室前端和后端的两个房间，每个房间最开始没有人,每个座位上开始都有人。 有 \(m\) 个不同的学 ......

Day 1 kitty 核心思路：将转移过程中的方案加入转移矩阵，边转移边累加 string dp设计：\(f[i][x][y]\) 表示长度为 \(i\)，第一段以 \(x\) 结尾，且 \(x\leqslant p\)，第二段以 \(p\) 开头，以 \(y\) 结尾的两段完全相同的序列的对数。 ......

原题链接 \(b\) 的顺序与答案无关，先排序。能与 \(a_i\) 配对的肯定是 \(b\) 的末尾一段，因为 \(a_i+b_j\ge h\)，那么一定有 \(a_i+b_{j+1}\ge h\)。 设 \(c_i\) 为与 \(b_i\) 配对的 \(a\) 的个数，显然 \(c\) 是单调不 ......

题目链接 依然枚举每个位置作为最小值的情况，记录“值/下标”二元组，按第一维从大到小排序后，每次将第二位的位置在序列中标成 \(1\)，那么选择的一定是序列里一个 \(1\) 的极长段。加入一个位置检查其左右是否加入过，如果加入过就用并查集合并掉，同时维护极长段的和/左右端点是简单的，复杂度 \(\ ......

冶炼金属 题目 小蓝有一个神奇的炉子用于将普通金属О冶炼成为一种特殊金属X。这个炉子有一个称作转换率的属性V,V是一个正整数，这意味着消耗V个普通金属О恰好可以冶炼出一个特殊金属X，当普通金属О的数目不足V时，无法继续冶炼。现在给出了Ⅳ条冶炼记录，每条记录中包含两个整数A和B，这表示本次投入了A个普 ......

P9242 [蓝桥杯 2023 E题] 接龙数列 一眼LIS 但是TLE八个点。 发现是sb了，应该用string来存数直接取首位末位。 改完50分，TLE五个点。 换状态 \[F_i$$ 为以数字 $i$ 结尾的最长接龙数列。 则顺推每个数字，从每个数字的首位 $F_{j_1} + 1$ 以及末位 ......

[NOIP2022] 建造军营 题解 Part I 观察 注意到如果删掉的边在一个边双连通分量里面，那么无论如何都不会影响 A 国，所以 B 国只会删掉桥，于是把图边双缩点之后，同一个边双里面的点要么都不选，要么随便选至少一个。 Part II DP 再次发现军营一定是一个极大的连通块，所以可以考虑 ......

Archaeology 有一颗带权树，有三个操作： 给一个点打上标记。 删除一个点的标记。 查询有标记的点的导出子树的边权和。 \(n, q \le 10^5\)。 求的实际上就是虚树的大小，求这个有一个常用的方法就是把点按 dfn 排序后相邻点对（首尾也算相邻）之间的距离和除以 2。 所以我们可以 ......

这道题的思路非常简单，经过对样例的分析，我们发现，所有区间的总和为： $\sum_{i = 1}^{n} a_i \times d_i $（其中 $a_i$ 为原数组的第 $i$ 项，$d_i$ 为第 $i$ 个元素被区间覆盖的次数） 这里有一个小细节：对于某一个元素被覆盖的次数我们可用差分进行优化 ......

题意 给出一串数，请问，通过将 \(a_i\) 和 \(a_{i+1}\) 同时加 \(1\) 或减 \(1\)若干次，能否使它单调不减？ 思路 我们发现，如果要让 \(a_i\) 和 \(a_{i - 1}\) 满足单调不减，可以通过修改 \(a_i\) 和 \(a_{i+1}\) 让 \(a_i ......

这个小丑看了好久题目才发现保证 \(t\) 不降。 好像与其他题解做法稍有不同。 思路 其他题解的标记做法非常复杂，怎么办。 我们可以使用适用性可加强大的矩阵乘法。 我们考虑维护： \[\begin{bmatrix} \sum v&\sum a\times b&\sum a&\sum b&len\\ ......

### 题意 给出一串数，请尝试在这串数中找到三段**连续**的子段，使得这三个子段的和分别为 $P$、$Q$ 和 $R$。问：是否可行？ ### 思路 通过观察，观察我们可以发现，其实我们可以根据题目的要求写出一段关系式： $A+P+Q+R+B$（其中 $A$ 表示被选子段前面没被选的子段和，其中 ......

题意 给你一个数组 \(a1,a2…an\) 请计算有多少个四元组 \((i,j,k,l)\) 符合以下条件: \(1 <= i < j < k < l <= n\) \(a_i=a_k \ \&\&\ a_j=a_l\) \(4<=n<=3000,1<=a_i<=n\) \(input\) 2 5 ......

题目链接 题意简述 给定一个正整数 \(N\)，将它的因数分解式按规定输出。 题目分析 模拟题意即可。 具体地，我们可以枚举 \(2\) 到 \(\lfloor \sqrt N \rfloor\) 中所有数 \(i\)，如果 \(i\) 能整除 \(N\)，则不断地从 \(N\) 中除掉 \(i\) ......

蓝桥杯管道 -- 二分, 区间覆盖 原题链接 参照执梗大佬的代码, 我太菜了wuwuwu...... import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.S ......

洛谷 AT 完全图的最小生成树是不好求的，但是发现 \(\mathcal{O}(n^2)\) 级别的边中显然有很多都是没有用的，这种时候可以考虑分治。 显然如果对 \(E'(E'\in E)\) 求 MST，没有选择的边一定也不在最后的 MST 的边集中。于是就让选出的边集的并等于原图，然后再求一遍 ......

CF1436E Complicated Computations mex的定义是：一个区间中没有出现过的数中最小的整数。 对于一个区间，当正整数x在区间中没有出现过、[1, x - 1]（整数）在区间中全部出现过，那么正整数x就是该区间的mex 正整数x在区间中没有出现过 我们一共有n个数字，所有的 ......

[APIO2012] 派遣 题目背景 在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。 题目描述 在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给 ......

去年今时，我得了 100 + 0 + 0 + 8 分，太抽象了 QwQ 所以为什么今天才写这个东西？因为今天才做完了 T2…… [NOIP2022] 种花 简单前缀和优化 DP，不谈。 [NOIP2022] 喵了个喵 非常高级的构造题。 看到 \(k = 2n - 1/2\)，我们可能会想到每一个栈 ......

洛谷。 题面 初始状态为全是 \(0\)，将某一为变化的前提是当前节点的前缀（不包括当前节点）是 \(s\) 串的一个后缀，每次变化需要 \(1\) 的代价。问最后要使所有都为 \(1\) 的最小代价。 分析 很有意思的一道题，感觉玩起来跟喵了个喵一样上头。 首先，我们肯定是要先让 \(n\) 这个 ......

原题链接 连 \(S\to A_i\)，流量 \(D_i\)，费用 \(P_i\)，表示最多进货 \(D_i\)，成本为 \(P_i\)。 连 \(A_i\to T\)，流量 \(U_i\)，费用 \(0\)，表示卖出。 连 \(A_i\to A_{i+1}\)，流量 \(+\infty\)，费用 ......

洛谷。 题意 应该好理解的。 分析 我们的所有雪球在同一时间之间的距离都是相同的，因此一段雪，要么是它左侧的第一个所取，要么右侧第一个所取，要么不被取，并且，我们每一个雪球所占有的雪是连续的一段。 我们令 \(L_i\) 表示第 \(i\) 步前所能走的最左点，\(R_i\) 表示第 \(i\) 步 ......

题意 一棵 \(n\) 个结点的树，根节点为 \(1\)，结点 \(i\) 的父亲是 \(f_i\)。\(f_1=f_0=0\)。对于每一个整数 \(i\)，假如 \(f_{f_i}\) 不为 \(0\)，那么就将 \(f_{f_i}\) 与 \(i\) 连上一条边。从每一个结点，每次随机向相邻的结 ......

大家好，我是毒瘤，喜欢用玄学算法过题。 发现题解区没有这个做法，于是来发一篇。 思路 首先发现如果一个点对 \((u,v)\) 的距离为 \(d\)，那么在这棵树以 \(u\) 为根时，\(v\) 的深度为 \(d\)。 Code ......

题目一 简单模拟题 点击查看代码 #include<bits/stdc++.h> using namespace std; #define ebk emplace_back #define x first #define y second typedef pair<int,int> PII; typ ......

第八周 算法题解笔记 1极值点 题目描述 给定一个单峰函数f(x)和它的定义域，求它的极值点 该单峰函数f(x)保证定义域内有且只有一个极值点，且为极大值点 题解 本题感觉和dp关系不大，主要思路是三分法，和二分法非常类似，但没有二分法常用，主要用途是用来求单峰函数的极值 对于任意一个上凸函数，选取 ......

P5522 [yLOI2019] 棠梨煎雪 题解 题目链接 分析1 抛开时间复杂度不谈，先来看看对于每次询问，如何计算合法的字符串个数。 对于每次询问的 \([l,r]\)，我们可以对字符串的每一位按以下种情况讨论（设讨论的这一位为第 \(i\) 位）： \(str[l..r][i]\) 既有 0 ......

小郑下五子棋 题目 五子棋是—种两人对弈的棋类游戏，它使用黑白两种棋子在一个20×20的棋盘上进行。黑方执黑棋，白方执白棋。双方轮流下棋，目标是先在横向、纵向或斜向连成五个己颜色的棋子，即五子相连，即可获胜。五子棋是—种简单却富有策略的游戏，常常被用于智力训练和竞技比赛。这不，小郑在和小张玩五子棋， ......