iOS
数据结构——RMQ（ST表）问题
数据结构——RMQ（ST表）问题 问题描述 对于序列 (A[1dots n])，有 (m) 组询问 (langle l,rrangle)，求 (max_{i=l}^rA_i)。 我们下面使用 (mathcal O(A)simmathcal O(B)) 表示预处理 (mathcal O(A))，单次询问 (mathcal O(B)) 的时间复杂度。 线段树解法 时间复杂度：(mathcal O(n)
P9668 [ICPC2022 Jinan R] Torch 题解
思路 考虑使用矩阵模拟这个过程。 首先，我们可以设初值为： [begin{bmatrix} 0&1 end{bmatrix} ]表示瘦子初始走 (0) 米，胖子初始走 (1) 米。 考虑瘦子走一步。 由于瘦子每走一步都不能超过胖子，我们可以使用 ((min,+)) 矩乘来维护这个性质。 那么瘦子走一步是： [begin{bmatrix} 1&inf -1&0 end{bma
GCC8 编译优化 BUG 导致的内存泄漏
1. 背景 1.1. 接手老系统 最近我们又接手了一套老系统，老系统的迭代效率和稳定性较差，我们打算做重构改造，但重构周期较长，在改造完成之前还有大量的需求迭代。因此我们打算先从稳定性和迭代效率出发做一些微小的升级，其中一项效率提升便是升级编译工具 和 GCC 版本。 老系统使用 Autotools 编译工具链，而我们新服务通常采用 bazel，bazel 在构建速度、依赖描述、工具链等方面有很大
算法入门（6） 7.5
小鱼的航程（改进版） 题目背景 题目描述 有一只小鱼，它平日每天游泳 $250$ 公里，周末休息（实行双休日)，假设从周 $x$ 开始算起，过了 $n$ 天以后，小鱼一共累计游泳了多少公里呢？ 输入格式 输入两个正整数 $x,n$，表示从周 $x$ 算起，经过 $n$ 天。 输出格式 输出一个整数，表示小鱼累计游泳了多少公里。 样例 #1 样例输入 #1 样例输出 #1 提示 数据保证，$1l
D. Shop Game
原题链接 题解 alice只有两种决策 一个也不选 选 (k) 个以上 如果选 (k) 个以上，bob肯定会使其中 (b_i) 最大的 (k) 个免费，所以我们干脆把 (b) 降序排序，然后遍历第 (k) 小的 (i)，由于这 (k) 个数无论怎么选都是赔，所以我们我们选 ([1,i]) 里前 (k) 小的 (a_i)，之后就贪心地选 (b_i > a_i) 的 code
字典序分割字符串 动态规划问题
对于输入字符串： 使用cin cin适用于输入不包含空格的字符串。 cin从输入流中读取字符，直到遇到空格、制表符、换行符或文件结束符为止。 遇到这些分隔符时，cin会停止读取，并将已读取的字符存储在目标变量中。 空格、制表符和换行符本身不会存储在目标变量中。 使用getline getline可以读取包含空格的整行字符串。 使用字符数组和cin.get 这种方法也适用于包含空格的字符串。
P7224 [RC-04] 子集积 （背包 dp + 复杂度优化）
P7224 [RC-04] 子集积 背包 dp + 复杂度优化 考虑 dp。容易想到背包 dp，设 (f_{i,j}) 表示考虑了前 (i) 个，当前乘积为 (j) 的方案数。枚举 (a_i) 的倍数转移。 复杂度 (O(sumlimits_{i=1}^nfrac{m}{a_i}))。如果 (a_i) 互不相同，那么近似于 (O(mln m))。 如果还想要这样的复杂度，可以考虑相同的部分能不能同
算法入门（4） 7.6
[NOIP2008 普及组] ISBN 号码 题目描述 每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 $9$ 位数字、$1$ 位识别码和 $3$ 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 $0$
AtCoder Beginner Contest 361
A - Insert (abc361 A) 题目大意 给定一个数组(a)和数 (k,x)，将 (x)插入第 (k)个数之后，并输出新数组。 解题思路 用(vector)的直接 (insert)即可。 神奇的代码 B - Intesection of Cuboids (abc361 B) 题目大意 给定两个立方体，问是否相交。 解题思路 因为立方体都是平行坐标轴摆放的，若相交，则说明在
[SNCPC2024] 2024 年陕西省大学生程序设计 J题猜质数II 题解
题目链接：CF 或者 洛谷 PS: CF的得等上gym。 前提说明 其实在上个月就见到这题了，当时很想做这题，结果找不到做题链接，也不知道出处，原来是陕西省赛的捧杯题。 个人评价觉得是一道很不错的题，难度适中。 讲解 其实题解写的挺不错的，比很多比赛的题解写的详细许多了。这里站在我的角度分析这题吧： 先观察要求的式子： [score(x,l,r)=sum_{i=l}^r{f(x,a_i)} ]其
Google Test
Google Test Google Test GTest是单元测试的利器。通过在cpp执行文件中，添加TEST函数，函数中设置好测试套件与测试名称两个参数既可以进行预先定义好的测试单元，在最终执行窗口输出测试结果。 安装： 考虑在vscode编辑器下进行工作，首先进行Gtest的安装： 基本介绍： 使用前添加#include <gtest/gtest.h>； 当断言执行失败
北京邮电大学《产品经理-马力》课程笔记
本文禁止转载 B站：Heskey0 这门课是今年（2024年）北京邮电大学面向硕士研究生的产品经理课程，由马力主讲。这门课程可以让各位收获产品经理的思维方式。 课程目的：像产品经理一样思考问题 课程作业：运营一个账号 一、产品经理通识 1. 从面试题开始学习产品经理思维 不同职业往往具有不同的思维习惯： 程序员思维：怎么实现，能不能实现？ 设计思维：怎么呈现，怎么提高用户体验
代码随想录算法训练营第五十六天 | 98.所有可达路径
98.所有可达路径 题目链接 文章讲解 邻接矩阵法 邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组 为了节点标号和下标对其，有n个节点的图申请(n + 1) * (n + 1)的空间 输入m条边构造图 完整代码： 邻接表写法 邻接表使用数组加链表的方式来表示。邻接表是从边的数量来表示图，有多少条边就申请多大的空间 构造邻接表 输入m条
D. Smithing Skill
原题链接 题解 当我剩下 (k) 个金属时，我肯定选 (a_i leq k) 并且 (a_i-b_i) 最小的那个 此题还用了分治法，由于金属数量最高可达 (1e9) 所以当金属数量大于 (1e6) 的时候肯定用 (cost[1e6]) code
逐月信息学 2024 提高组 #3
(color{black}texttt{A. 反转Dag图}) 题目描述 给定一个有向图，每次操作可以花费 (w_i) 的代价来反转边 (i)，最终总代价为每次操作代价的最大值。求最少需要多少代价才能使这张图变为一个 DAG。 思路 首先看这个问题的简化版：把反转操作变为删除操作。 可以用二分解决：二分出最终答案 (x)，把所有代价 (le x) 的边删掉，再拓扑排序判断即可。 这时可以发现，两个
P8298 [COCI2012-2013#2] POPUST （贪心）
P8298 [COCI2012-2013#2] POPUST 贪心 考虑当前选 (k) 道菜，如果我们先选出了付 (A) 元的菜，那么剩下选 (B) 元的一定是前 (k-1) 大的 (B_i)。 这启发我们先将序列按 (B_i) 排序。那么可以看到两种情况： 如果选 (A) 元的菜在 (k) 道菜之外，那么一定选前 (k-1) 道菜付 (B_i) 元，(A) 就从剩下的里面选最小的。 如果选 (
Linux 虚拟网络 Wireguard
WireGuard WireGuard 是一种现代化的虚拟专用网络（VPN）技术，旨在提供简单、高效、安全的网络连接。它基于最新的加密技术，设计轻量，并且便于配置和管理。以下是 WireGuard 的主要特点和优缺点： 优点 简单配置： WireGuard 的配置相对简单，不需要复杂的证书管理，只需少量配置文件即可建立连接。 高效性能： WireGuard 使用高效的加密算法，如
MinGW GCC 5.3.0 编译OpenCV4.5.5 运行到imshow时崩溃
Windows 下通过mingw32-make 编译opencv4.5.5,经过一系列问题解决后发现其他正常，imshow崩溃. GCC版本太低原因，换更高版本的GCC解决. 毕竟GCC 5.3.0是2015年发行的，opencv 4.5.5是2020年发行的 尝试换GCC i686-8.1.0-release-posix-sjlj-rt_v6-rev0编译,调用imshow
HT-014 Div3 扫雷 题解 [ 绿 ] [ 二维差分 ]
分析 观察到是曼哈顿距离 (le r) 的范围可以扫到，联想到如下图形： 左边是 (r=1) 可以扫到的范围，右边是 (r=2) 可以扫到的范围。 于是，我们只要对这样的图形在 (1000*1000) 的格子里差分一下就好了 。 但这样的复杂度是 (O(nm)) 的，会死的很惨。 优化 不难发现这个图形是一个旋转过 (45°) 的正方形，所以我们先把他转回来。 归纳法可以得到原先为 ((x,y)