OJ选题集
下列OJ平台仅代表题目信息的一个出处，不一定为OJ平台原创
很少会出现需要数据结构来做的题。基本和数学相关。
每道题下面的均为其中关键的解题思路，题目大意并非完整题目，只出现解题思路中需要的变量。
（因此，基于测试用例t等无关变量将不会出现）
Codeforces
Codeforces Round 1020 div.3 C. Cherry Bomb Problem - C -
Codeforces
tags: greedy math sortings *1000
题目大意
两个非负整数数组a与b，当我们称其互补时，当且仅当对于每个编号i，均有ai=bi。我们希望数组a,b的每个元素均非负且不大于k,并且a与b是互补的。接下来，会给出n和k、完整的数组a，以及不完整的数组b，不完整的地方用-1补齐，请问有多少种填充b的办法满足我们的需要。
我们假设 $a_i+b_i$ 互补时的结果为 $x$
显而易见，由于 \(b\)
是不完整的，我们所做的其中一点就是保证不完整的地方非负且不大于 \( ...
读书屋
未读《硅谷之火》部分简述
b {
all: unset;
font-weight:bold;
}
内容太多，目前只做了第一章的简述，对此感兴趣可以看看原书《硅谷之火》
尽管个人计算机问世于20世纪70年代中期、巨型计算机要回溯到20世纪50年代，我们甚至能够追溯到19世纪末对未来的幻想。
火种
上帝保佑，我真希望计算能用蒸汽运行。
——查尔斯·巴贝奇
这是火种。
诗人拜伦和雪莱注意到科学带来的变化，交流着人工生命与人工思维，雪莱夫人玛丽·雪莱由此创作了《弗兰肯斯坦》，科学怪人这一小说形象令人望而生畏。1833年，查尔斯·巴贝奇谈起利用蒸汽进行计算并真的开始实施，他认为这“分析机”将会让人们从枯燥的脑力劳动中解放出来，而拜伦女儿艾达·拜伦极力支持并提供帮助，由于她做的工作，人们视艾达为世界上第一位程序员(Ada语言的命名因此而生)。巴贝奇关于分析机的3种设计均已失败告终，他设计的差分机虽简单而显雄心，却也仍未实现。1991年，伦敦科学博物馆的一位馆长多伦·斯沃德成功用巴贝奇时代的技术、材料造出了巴贝奇的差分机。事实上，巴贝奇设 ...
.red{
color:red;
font-weight:600; //bold为700，normal为400
}
.lbold{
font-weight:bold;
font-size:24px; //默认16px
}
.bold{
font-weight: bold;
}
details {
border: 1px solid #ccc;
background-color: #f0f8ff; /* 浅蓝，适合白天 */
border-radius: 6px;
padding: 0.5em;
transition: background-color 0.3s ease, border-color 0.3s ease;
}
...
参考资料：动态规划基础 - OI
Wiki
目前绝大多数内容摘自OI-Wiki,个人理解重构等后续更新
动态规划初步
动态规划(Dynamic
Programming)，简称DP，它本身不是一种特定的算法，而是一种思想。当状态变动与之前或之后状态有关时，我们往往可以使用方程来描述这种关系。这种方程被称作状态转移方程。
动态规划原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构
具有最优子结构也可能是用适合贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题
证明问题最优解的第一个组成部分是做出一个选择;
对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解，你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
证明作为构成原问题最优解的组成部分，每个子问题的解就是它本省的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题中的解用 ...
线段树
数据结构系列一下子跳到线段树了，私密马赛，最近太急于蓝桥杯比赛了，落后的教程一定会补上QAQ!
参考: 线段树 - OI Wiki
线段树是一种二叉搜索树、平衡二叉树，对于区间的修改、维护和查询时间复杂度优化为log级别。对区间不断做平分区间，直到划分到只有一个或多个数据的区间，可表示区间的和或者最小最大值。在进行更新区间操作时，通过小区间更新大区间。
对于下面的内容，我们主要针对于区间加法的线段树(即其节点表示区间之和)。
局限性：
问题需满足区间加法：对于[L,R]的区间，它的答案可以由[L,M]和[M+1,R]的答案合并求出。
不满足区间的众数、区间最长连续问题、最长不下降问题等。
建树
当我们拥有数组 \(a\)
并且用来区间求和之类的问题时，我们可以这样做：
以堆的方式实现存储(树形数组)，将元素放至树的最下面一层。
由于我们使用树形数组，为了存储下数组 \(a\), 数组 \(tree\) 的长度应当为 \(a\)
的四倍，并且初始节点位置为1。同时，当前区间[s,t]只有一个元素时(即s==t)，意味着 ...
快速幂
快速幂，即快速取幂的技巧。
对于在取幂过程中，需要不断取模的过程中（例如费马小定理求模逆元）时，单纯的pow函数已经不再满足我们的需要。我们需要明白pow函数的原理，以方便我们“魔改”pow函数。
定义
快速幂，二进制取幂（Binary Exponentiation),是一个在 \(O(logn)\) 的时间计算 \(a^n\) 的小技巧。
实现
递归形式
按幂的定义而言，\(a^n\) 等于 \(n\) 个 \(a\)
相乘，如果我们按照这样的定义实现算法的话，当 \(n\) 足够大时，资源的开销就很大了。
根据指数乘法，\(a^{b+c}=a^{b}+a^{c}\), 当 \(n\) 为偶数时, \(a^{n}=a^{\frac{n}{2}}·a^{\frac{n}{2}}\),
对于 \(n\) 为奇数的情况,
无非是在此基础上再乘以 \(a\)
罢了。因此，我们很容易就能得到实现快速幂的递归形式。
1234567long long pow(long long a, long long b){ if(b == 0) ret ...
并查集
参考资料:并查集 - OI
Wiki
基本概念
并查集是一种管理元素所属的数据结构,实现为一个森林，每颗树表示一个集合,树中的节点表示对应集合的元素。
显然，并查集支持两种操作:
合并(union): 合并两个元素各自所属的集合
查询(find): 查询某个元素所属的集合
初始化
初始时，每个元素都位于一个单独的集合表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。
1234struct dsu{ vector<size_t> pa; explicit dsu(size_t size):pa(size){iota(pa.begin(),pa.end(),0);}}
查询
我们需要沿着树向上移动，直至找到根节点。由于根节点的父亲是自己本身，因此递归的终止应该是pa[x]
== x。
123size_t dsu::find(size_t x){ return pa[x] == x? x: find(pa[x]);}
路径压缩
查询 ...
![[题解][生贺]洛谷P1005-矩阵取数游戏](/images/2025-3-5/%E7%94%9F%E8%B4%BA.jpg)
[题解][生贺]洛谷P1005-矩阵取数游戏
.red{
color:red;
font-weight:600; //bold为700，normal为400
}
.lbold{
font-weight:bold;
font-size:24px; //默认16px
}
.bold{
font-weight: bold;
}
if (typeof MathJax === 'undefined') {
window.MathJax = { loader: { load: ['$tex', '$svg'], async: true } };
}
主要思路构建: 2025.3.3
最终攻破:2025.3.3
文章撰写:2025.3.3 - 2025.3.4
感谢朋友的生日礼物，如封面图所示，miku可爱捏，晕晕晕。
为了庆祝生日，写了这篇题解，预期于生日当天发布(3.5)。 ...
![[前端]HTML+CSS教程](https://ooo.0x0.ooo/2025/05/25/OdQPQl.png?_r_=e3c24f5a-031c-be4d-d9cc-175aa25f31eb)
web开发
未读HTML
参考视频:前端Web开发HTML5+CSS3+移动web视频教程，前端web入门首选黑马程序员_哔哩哔哩_bilibili
css弹性盒子起，参考菜鸟教程
定义：超文本标记语言
超文本: 链接
编辑器：WebStorm或VsCode
标签语法
双标签：
需要包括文字内容的标签
语法： 开始标签–文字–结束标签
例如: <strong>文字内容</strong>
结束标签比开始标签多 /， 表示结束的地方。
单标签：
不需要文字内容的标签
例如水平线标签hr
HTML的基本骨架
12345678<html> <head> <title>网页标题</title> </head> <body> 网页主体 </body></html>
VS Code快速生成骨架:
在HTML文件中,!+Enter/Tab键
html : 整个网页
head : 网页头部
title ...
前情提要: 数据结构-线性表
| 4FGR の Blog
参考资料: 数据结构与算法分析 –Mark Allen Weiss
栈模型
栈是限制在插入和删除在末端的线性表，这决定了它的特性是“后进先出“(LIFO)。在解决一些问题时，我们很容易想到通过栈这种结构来解决，例如，对多项式的求解。
对于栈而言，基本的操作是Pop和Push,尽管有时通过Top返回栈顶元素的值。
注意：栈顶元素是栈中唯一可见的元素。
栈的实现
由于栈是一个表，因此任何实现表的方法都可以实现栈，这里给出两种方法：
栈的数组实现
为了讲解的便利和简洁，这里我们通过静态数组的方式实现，大家可以自己实现下动态分配的方法。
定义
123456#define MAXSIZE 1000typedef struct { int data[MAXSIZE]; int top;}*stack;
基本操作
123456789101112131415161718192021222324252627282930313233343536373839void in ...
