蓝桥 例题 区间
区间dp
1.acwing 282石子合并问题 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n; 5 const int N = 310; 6 int s[N]; 7 int f[N][N]; 8 9 int main () 10 { 11 ......
【区间 dp】UVA1331 最大面积最小的三角剖分 Minimax Triangulation 题解
UVA1331 区间 dp。 有一个很经典的问题：给定一个凸多边形，求它的最优三角剖分，对每个三角形规定一个权函数 \(f(i,j,k)\)，求所有剖分方案中最大的权值。 发现这个东西不好直接入手。但是这个东西与矩阵最优链乘是相似的。考虑区间 dp。因为随意的转移是难以维护的，维护区间信息就等于强制 ......
P8613 [蓝桥杯 2014 省 B] 小朋友排队
因为相邻两个数字交换，每次只能减少一个逆序对数量，所以这道题最终的交换次数就等于原序列当中逆序对的数量。 但是因为每个数字的交换代价会随着交换次数而增加，所以虽然我们知道Σ数字交换次数 = 逆序对数量，我们也不能按照传统的逆序对数量统计方式直接计算，这样子会导致我们只知道最终的交换次数，但不知道每个 ......
关于区间连续段问题 （析合树）
有部分题目需要处理关于区间连续段的问题（一般来说，对于一个排列，如果一个区间的值连读，就为一个连续段。）区间连续段看似不太好维护，其实有一种处理它的利器：析合树。（也可能只是析合树的思想），就能方便的维护这一个东西。 析合树 其实这个名字不重要 ......
P8611 [蓝桥杯 2014 省 AB] 蚂蚁感冒
这道题采用贪心，两只蚂蚁相互传染后再同时掉头走，相当于穿过了对方，若无其事地走，并不会影响最后感冒的传播结果。 #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <queue> u ......
第十四届蓝桥杯省赛 C++B组 ---- 景区导游
第十四届蓝桥杯省赛 C++B组 景区导游 LCA 原题连接 lca 同时得到按原来路径走的总时间 最后输出时处理跳过某个点的时间 预处理用 bfs 或 dfs 都可以 import java.io.BufferedReader; import java.io.InputStreamRea ......
用矩阵乘法推导区间覆盖区间历史和
区间加区间历史和，在网上的博客已经烂大街了。但还没有区间覆盖区间历史和。 众所周知，我们一般把线段树上维护的分类为信息与懒标记。用矩阵乘法的角度来看就是 I 和 T 两个矩阵。 线段树上，我们要处理信息与信息合并，信息与懒标记合并，懒标记与懒标记合并。 信息与信息合并就是矩阵相加。其他两个是乘。 于 ......
区间树上查找所有与给定区间相交的区间-算法复杂度正确性证明
区间树是在平衡树上维护的数据结构，按照左端点大小排序。详见《算法导论》。 算法设计思路 红黑树的拓展 在红黑树上维护结点属性\(min, max\)： \(min\)表示该结点及其所有后代结点中的区间低端的最小值。 \(max\)表示该结点及其所有后代结点中的区间高端的最大值。 在插入时，对结点路上 ......
蓝桥杯之模拟与枚举day1
Question1卡片(C/C++A组第一题) 这个是一道简单的模拟枚举题目，只要把对应每次的i的各个位都提取出来，然后对应的卡片数目减去1即可。属于打卡题目。注意for循环的特殊使用即可 #include <iostream> using namespace std; bool solve(int ......
蓝桥杯第三周算法竞赛D题&&E题
发现更多计算机知识，欢迎访问Cr不是铬的个人网站 D迷宫逃脱 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢? 这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候，会消耗一把钥匙。当没有钥匙的时候就不能移动了。想到这里，我们可以定义一个三维的dp数组. 定义dp dp[ ......
【每日例题】 蓝桥杯 c++ 冶炼金属
冶炼金属 题目 小蓝有一个神奇的炉子用于将普通金属О冶炼成为一种特殊金属X。这个炉子有一个称作转换率的属性V,V是一个正整数，这意味着消耗V个普通金属О恰好可以冶炼出一个特殊金属X，当普通金属О的数目不足V时，无法继续冶炼。现在给出了Ⅳ条冶炼记录，每条记录中包含两个整数A和B，这表示本次投入了A个普 ......
P9242 [蓝桥杯 2023 E题] 接龙数列
P9242 [蓝桥杯 2023 E题] 接龙数列 一眼LIS 但是TLE八个点。 发现是sb了，应该用string来存数直接取首位末位。 改完50分，TLE五个点。 换状态 \[F_i$$ 为以数字 $i$ 结尾的最长接龙数列。 则顺推每个数字，从每个数字的首位 $F_{j_1} + 1$ 以及末位 ......
蓝桥杯管道 -- 二分, 区间覆盖
蓝桥杯管道 -- 二分, 区间覆盖 原题链接 参照执梗大佬的代码, 我太菜了wuwuwu...... import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.S ......
代码随想训练营第三十六天（Python）｜ 435. 无重叠区间、763.划分字母区间、56. 合并区间
435. 无重叠区间 class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: x[0]) count = 0 for i in r ......
【每日例题】蓝桥杯 c++ 小郑下五子棋
小郑下五子棋 题目 五子棋是—种两人对弈的棋类游戏，它使用黑白两种棋子在一个20×20的棋盘上进行。黑方执黑棋，白方执白棋。双方轮流下棋，目标是先在横向、纵向或斜向连成五个己颜色的棋子，即五子相连，即可获胜。五子棋是—种简单却富有策略的游戏，常常被用于智力训练和竞技比赛。这不，小郑在和小张玩五子棋， ......
【每日例题】蓝桥杯 c++ 被替换的身份证
被替换的身份证 题目 蓝桥杯 被替换的身份证 思路分析 斗地主简化版？！废话少说，四种情况 ShallowDream一开始出对子或者王炸，ShallowDream胜 ShallowDream一开始出单，Joker出王炸，Joker胜 ShallowDream一开始出单，Joker手中最大的牌比Sha ......
P8317 [FOI2021] 幸运区间
P8317 [FOI2021] 幸运区间 题目传送门 分治 + dfs 首先可以发现 \(k\) 和 \(d\) 很小，所以是可以搜索的。 那么就考虑如何枚举区间，显然 \(n^2\) 枚举是会超时的，所以就考虑分治来求。 求的过程中就分成三种情况来处理：在左边一半，在右边一半，以及跨越中间点。显而 ......
Excel区间频率统计
有时候会使用Excel统计一下分段区间数据的频率，也就是数据在不同的区间的分布情况。下面案例就是使用Excel统计一下数据的区间分布情况。 使用frequency函数可以得到想要的结果。 公式=frequency(数据列，分界区间)，然后CTRL + SHIFT + ENTER 注意点：要全部选中要 ......
【1111算法题】蓝桥杯 c++（一）第一二题
【1111算法题】 第一题 双十一的祈祷【算法赛】 题目 双十—，不仅是购物狂欢节，更有"光棍节"之称。这源于11:11由四个1构成，象征着单身。作为大学生的小蓝也想经历甜甜的校园恋爱，于是他找到了爱神丘比特，向他祈祷能为自己带来—段邂逅。丘比特是乐于助人的，他承诺小蓝只要回答出一个简单的数学问题， ......
第十五届蓝桥杯模拟赛 -- 删掉m个字符使得字典序最小
第十五届蓝桥杯模拟赛 -- 删掉m个字符使得字典序最小 贪心 + 单调栈 import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Main { public static ......
蓝桥杯2019 估计人数
蓝桥杯2019 估计人数 题目描述 给定一个 \(N \times M\) 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。 已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1，包括开始和结束 ......
区间DP
一.定义 即对于一个区间进行的dp 二.经典转移方程 1.枚举断点型 f[l][r]=min(f[l][k-1],f[k][r]) (l+1<=k<=r) 2.左右端点型 f[l][r]=min(f[l][r-1],f[l+1][r]) 3.有一定条件型 f[l][r][k]=f[l][r-1][k ......
【题解 P8763】[蓝桥杯 2021 国 ABC] 异或变换
同楼上dalao做法： #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #inclu ......
2023-11-11：用go语言，字符串哈希+二分的例题。 给定长为 n 的源串 s，以及长度为 m 的模式串 p， 要求查找源串中有多少子串与模式串匹配， s‘ 与 s 匹配，当且仅当 s‘ 与 s
2023-11-11：用go语言，字符串哈希+二分的例题。 给定长为 n 的源串 s，以及长度为 m 的模式串 p， 要求查找源串中有多少子串与模式串匹配， s' 与 s 匹配，当且仅当 s' 与 s 长度相同，且最多有 k 个位置字符不同。 其中 1 <= n, m <= 10^6，0 <= k ......
区间 DP、环形 DP
区间 DP 区间 DP 是可以由小区间的结果往两边扩展一位得到大区间的结果，或者由两个小区间的结果可以拼出大区间的结果的一类 DP 问题 往往设 \(dp[i][j]\) 表示处理完 \([i,j]\) 区间得到的答案，按长度从小到大转移 因此一般是先写一层循环从小到大枚举长度 \(len\)，再写 ......
【每日例题】蓝桥杯 c++ 手机尾数
手机尾数 题目 30年的改革开放，给中国带来了翻天覆地的变化。2011全年中国手机产量约为11.72亿部。手机已经成为百姓的基本日用品!给手机选个好听又好记的号码可能是许多人的心愿。但号源有限，只能辅以有偿选号的方法了。这个程序的目的就是:根据给定的手机尾号(4位)，按照—定的规则来打分。其规则如下 ......
力扣2406. 将区间分为最少组数
给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。 你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。 请你返回 最 ......