MiQiu

LIS 题型整理 LIS模型 解决的是这样一个标准问题：给定一维序列，在保持原顺序的前提下，寻找最长的单调子序列。 但在实际问题中，很少会直接给出一列数并要求 LIS。更多时候，我们需要先从题意中找到一条链，再判断题目究竟需要这条链的什么信息。 因此，LIS 题型可以沿着两条主线展开： 怎样找到这条链：对象是什么，顺序在哪里，两个对象怎样连接； 怎样询问这条链：求最长长度、最少修改、最大权值，还

ABC441E - A > B substring 1. 题意 给定一个由 A,B,CA, B, CA,B,C 组成的字符串，问有多少 AAA 的数量多于 BBB 的数量的子串。 N≤5e5N \le 5e5N≤5e5 2. 思路 首先由一个显然的结论，一个长度为 NNN 的字符串一共有 N(N+1)2\frac{N(N+1)}{2}2N(N+1)​ 个子串。 我们考虑 A B C 三个

ABC440 F - Egoism 1. 题意 有 NNN 匹马，每匹马有两个属性：AiA_iAi​：心情值；BiB_iBi​：整洁度 {1,2}\{1, 2\}{1,2}。每天会修改一匹马的 (Ai,Bi)(A_i,B_i)(Ai​,Bi​)。 若洗澡顺序为 p1,p2,…,pNp_1,p_2,\dots,p_Np1​,p2​,…,pN​，则第 pjp_jpj​ 匹马的满意度为：若 j=1j=1

ABC440D - Forbidden List 2 1. 题意 给定一个长度为 NNN 的整数列表 AAA，其中所有 AiA_iAi​ 互不相同。 对于每个询问 (X,Y)(X,Y)(X,Y)，要求在所有大于等于 XXX 且不在列表 AAA 中的整数里，找到第 YYY 小的数。 N,Q≤3×105N,Q \le 3\times 10^5N,Q≤3×105，1≤Ai,X,Y≤1091\le A_

F - Beautiful Kadomatsu 1. 题意 给定一个 1∼N1 \sim N1∼N 的排列 PPP，求有多少个非空子序列是 kadomatsu-like。 对于一个序列 a=(a1,a2,…,ak)a=(a_1,a_2,\dots,a_k)a=(a1​,a2​,…,ak​)： 若 ai−1<ai>ai+1a_{i-1}<a_i>a_{i+1}ai−1​<

ABC440 E - Cookies 1. 题意 有 NNN 中类型的饼干，第 iii 种类型饼干价值为 AiA_iAi​。 需要选 KKK 块饼干（可重复），请按降序输出前 XXX 大的组合总价值。 1≤N≤501 \le N \le 501≤N≤50，1≤K≤1051 \le K \le 10^51≤K≤105，1≤X≤1051 \le X \le 10^51≤X≤105，−109≤Ai≤1

晴天待命，雨天救人 雨是上课时落下来的。 一开始很轻，落在窗台上，像有人在玻璃外面试探着敲门。教室里还亮着灯，老师站在讲台前写板书，粉笔灰在灯光下浮起一点，又很快散开。 他低着头记笔记，写到一半，窗缝里钻进来的风把纸页掀起来，正好盖住了他的笔尖。 他手忙脚乱地按住纸，旁边传来一声很轻的笑。 他转头看过去，她正托着脸看他，眼睛弯弯的。 “你笑什么？” 她没说话，只从本子边缘撕下一张小小的便签，在上面

数学知识体系 这里整理数学概念本身：它们如何定义，为什么成立，彼此之间有什么结构，以及怎样支撑算法与计算机科学。 0 数学知识的四个层次 整个专题沿着以下层次展开： 数学语言与证明 → 离散结构 → 具体数学分支 → 算法与计算机科学中的应用。 其中： 数学语言与证明提供集合、关系、映射、命题和证明方法； 离散结构研究图、顺序、运算与代数结构； 具体数学分支在这些语言和结构上继续发展数论

数学语言与证明 这一部分提供描述数学对象、表达数学命题和组织推理所需的基础语言。 1 整体主线 集合 → 关系 → 映射 → 命题逻辑与证明方法。 这四篇不是独立的知识点，而是一条逐步加强的语言链： 集合说明研究对象由哪些元素组成； 关系描述对象之间是否存在某种联系； 映射是在关系上加入存在性与唯一性； 命题逻辑与证明方法负责准确表达条件并建立结论。 2 章节导航 2.1 集合 集合

集合 本章主线：集合与元素 → 集合运算 → 幂集 → 笛卡尔积 → 算法中的集合表示。 1 集合与元素 集合是由若干确定对象组成的整体，其中的对象称为集合的元素。 若元素 xxx 属于集合 AAA，记作 x∈Ax\in Ax∈A；若 xxx 不属于集合 AAA，记作 x∉Ax\notin Ax∈/A。 例如，设 A={1,2,3}A=\{1,2,3\}A={1,2,3}，则 1∈A1\in