线段树
数据结构系列一下子跳到线段树了，私密马赛，最近太急于蓝桥杯比赛了，落后的教程一定会补上QAQ!
参考: 线段树 - OI Wiki
线段树是一种二叉搜索树、平衡二叉树，对于区间的修改、维护和查询时间复杂度优化为log级别。对区间不断做平分区间，直到划分到只有一个或多个数据的区间，可表示区间的和或者最小最大值。在进行更新区间操作时，通过小区间更新大区间。
对于下面的内容，我们主要针对于区间加法的线段树(即其节点表示区间之和)。
局限性：
问题需满足区间加法：对于[L,R]的区间，它的答案可以由[L,M]和[M+1,R]的答案合并求出。
不满足区间的众数、区间最长连续问题、最长不下降问题等。
建树当我们拥有数组 并且用来区间求和之类的问题时，我们可以这样做：
以堆的方式实现存储(树形数组)，将元素放至树的最下面一层。
由于我们使用树形数组，为了存储下数组 , 数组 的长度应当为 的四倍，并且初始节点位置为1。同时，当前区间[s,t]只有一个元素时(即s==t)，意味着当前节点为叶子节点，就要让当前节点 。对于其它的情况，我们求 ...
![[题解][生贺]洛谷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)。
可惜3月3号爆发感冒，不知道生日那天会不会好~(QAQ)。
P1 ...
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 : 网页标题
body ...
前情提要: 数据结构-线性表 | 4FGR の Blog
参考资料: 数据结构与算法分析 —Mark Allen Weiss
栈模型 栈是限制在插入和删除在末端的线性表，这决定了它的特性是”后进先出”(LIFO)。在解决一些问题时，我们很容易想到通过栈这种结构来解决，例如，对多项式的求解。
对于栈而言，基本的操作是Pop和Push,尽管有时通过Top返回栈顶元素的值。
注意：栈顶元素是栈中唯一可见的元素。
栈的实现 由于栈是一个表，因此任何实现表的方法都可以实现栈，这里给出两种方法：
栈的数组实现为了讲解的便利和简洁，这里我们通过静态数组的方式实现，大家可以自己实现下动态分配的方法。
定义
123456#define MAXSIZE 1000typedef struct { int data[MAXSIZE]; int top;}*stack;
基本操作
123456789101112131415161718192021222324252627282930313233343536373839void initialStack(stack s){ s-&g ...
前情提要：数据结构-线性表 | 4FGR の Blog
单链表 线性表的链式存储，其存储并非是一段连续的存储空间，为了能够访问链表中的元素，每个链表节点不仅存储了元素信息，还需要存放一个指向其后继的指针。（本文所有链表实现均有头节点）
结构体定义
1234typedef struct LNode{ int data; struct LNode *next;}LNode, *LinkList;
基本操作的实现
初始化
123456789// 初始化链表bool initList(LinkedList &L){ L = (LNode*)malloc(sizeof(LNode)); if(L == NULL){ return false; } L->next = NULL; return true;}
检查空表
即检查头节点的后继是否为空
1234//检查链表是否为空bool isEmpty(LinkedList L){ return L->next == NULL;}
查找
123456789// ...
数据结构-线性表
本文仅对线性表进行简单叙述，具体实现会专门出教程，并在具体的数据结构后面给出链接。
定义：线性表是具有相同数据类型的n个元素的有限序列
基本操作： 初始化、取值、查找、插入、删除、判空、销毁
线性表的顺序表示-顺序表我们可以这样定义顺序表
12345#define MAXSIZE 100typedef struct{ int data[MAXSIZE]; //顺序表的元素(假设类型为int，本文元素均以int为例) int lenth; //顺序表的当前长度}SqList;
当然，如果我们想要通过动态分配的顺序表，只需要让data成为一个指针，并且结构体中存在MaxSize描述当前最大容量即可。
特点：逻辑位置与其存储的物理顺序相同
优点：
可随机访问（取值的时间复杂度为O(1)）
存储密度高
缺点：
插入和删除的时间花费较大
线性表的存储表示-链表
为了避免顺序表插入和删除的线性开销，我们可以允许表不连续存储，于是链表应运而生
我们常常使用头节点head置于链表最前端，其data域无任何东西，优点如下
1.第一个节点存放在头节点的指针域中，与 ...
数据结构绪论由于几天后数据结构要期末考试，最近几天会出数据结构相关的教程，以作复习。
参考资料：
数据结构(C语言版) —严蔚敏，吴伟民
数据结构与算法分析 —Mark Allen Weiss
2025年数据结构考研复习指导 —王道论坛
数据结构的基本概念基本术语数据元素：数据的基本单位，由若干数据项组成
数据对象：具有相同性质的数据元素的集合
抽象数据类型：一组操作的集合
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素之间的关系称为结构。数据结构包括三方面内容：逻辑结构、存储结构和数据的运算
数据结构三要素1.数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，分为线性结构和非线性结构
集合：结构中的数据元素除“同属一个集合”外，别无其他关系。
线性结构：结构中的数据存在一对一的关系
树形结构：结构中的数据存在一对多的关系
图状结构：结构中的数据存在多对多的关系
2.数据的存储结构
存储结构是指数据结构在计算机中表示(又称映像)，也称物 ...
题目难点对数学功底的考察，能否根据题目描述建立起数学公式, 解出关键的未知数(第二次上下车的人数)
题目
洛谷链接： P1011 [NOIP1998 提高组] 车站 - 洛谷 | 计算机科学教育新生态
[NOIP1998 提高组] 车站题目描述火车从始发站（称为第 站）开出，在始发站上车的人数为 ，然后到达第 站，在第 站有人上、下车，但上、下车的人数相同，因此在第 站开出时（即在到达第 站之前）车上的人数保持为 人。从第 站起（包括第 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 站），都满足此规律。现给出的条件是：共有 个车站，始发站上车的人数为 ，最后一站下车的人数是 （全部下车）。试问 站开出时车上的人数是多少？
输入格式输入只有一行四个整数，分别表示始发站上车人数 ，车站数 ，终点站下车人数 和所求的站点编号 。
输出格式输出一行一个整数表示答案：从 站开出时车上的人数。
样例 #1样例输入 #11>5 7 32 4
样例输出 #11>13
提示对于全部的测试点，保 ...
题目链接：TUOJ（需有账号）
题目背景传说每当月光遍布西西艾弗岛，总有一道身影默默守护着居民们的美梦。
题目描述梦境中的西西艾弗岛由n+1 个区域组成。梦境巡查员顿顿每天都会从梦之源（0 号区域）出发，顺次巡查 1,2,⋯,n 号区域，最后从n 号区域返回梦之源。
在梦境梭需要消耗美梦能量：
从梦之源出发时，顿顿会携带若干初始能量；
从第 i 号区域前往下一区域（0≤i≤n）需要消耗 ai 单位能量，因此从第 i 号区域出发时，顿顿剩余的美梦能量需要大于或等于ai单位；
顺利到达第 i 号区域（1≤i≤n*）后，顿顿可以从当地居民的美梦中汲取 bi 单位能量作为补给。
假设顿顿初始携带 w 单位美梦能量，那么首先需要保证 w≥a0，这样顿顿便可消耗a0 能量穿梭到 1 号区域、进而获得 b1 单位能量补给。巡查 1 号区域后，顿顿剩余能量为 w−a0+b1，如果该数值大于或等于 a1，顿顿便可继续前往 2 号区域。依此类推，直至最后消耗 an 单位能量从 n 号区域返回梦之源，便算是顺利完成整个巡查。西西艾弗岛，又迎来安宁的一夜，可喜可贺！
作为一个成熟的梦境巡查员，顿顿已经 ...
数据结构-散列表(hash table)
参考资料：数据结构与算法分析 —Mark Allen Weiss
一、基本介绍散列(hashing) ：一种以常数平均时间执行插入、删除和查找的技术，但对元素间进行排序的操作不被支持，例如寻找最大值和最小值。
散列表（hash table）: 一个含有关键字的具有固定大小的数组，通过关键字查找对应值，只需要O(1)的时间复杂度。
散列函数：将每个关键字映射到从0到size-1这个范围中的某个数，并且放到适当的单元。这个映射就叫做散列函数。
二、散列函数关键字为整数的设置方法:
如果输入的关键字是整数，则一般合理的方法就是直接返回 关键字% 表长, 最好保证表长为素数（质数），以避免某些特殊情况，例如表长为10，而关键字均以0为个位的情况。
关键字为字符串的设置方法:
通常，关键字是字符串，在这种情形下，散列函数需要仔细选择。
用ASCII码直接相加并取余并不合适, 表长很大，就不能均匀地很好地分配关键字。
代码如下
1234567891011int Hash(const char *key, int len){ unsigned i ...
