# NOIP 知识清单（入门+提高） ## 一、数据结构(STL) ### 1. 栈 & 队列（入门） #### 核心概念 - 栈：先进后出（FILO），支持 $push/pop/top$ 操作； - 队列：先进先出（FIFO），支持 $push/pop/front/back$ 操作； - 双端队列（deque）：两端…

多测不清空，爆零两行泪QwQ

在文章《题解：P14362 [CSP-S 2025] 道路修复 / road（民间数据）》发表评论：

%%%姐姐强👍

在文章《题解：P14233 [COI 2011] 收视率 / TELKA》发表评论：

dalao~~~%%%Orz

在文章《题解：CF1718B Fibonacci Strings》发表评论：

姐姐好可爱(●'◡'●)😘

在文章《题解：P4796 [BalticOI 2018] 路径》发表评论：

学长好强，这么厉害的搜索%%%o(*￣▽￣*)ブ 0rz

在文章《题解：B4156 [厦门小学生 C++ 2023] 太空旅行》发表评论：

%%%

### P4796 [BalticOI 2018] 路径 - 方法：记忆化搜索。 - 首先根据题意，可以先打个暴搜，可以得到 $70$ 分。 ::::success[暴力搜索] ```cpp line-numbers il void dfs(int u,int fa){ if(vis[a[u]]) return ; v…

### CF190E Counter Attack题解 - [双倍经验](https://www.luogu.com.cn/problem/CF920E) 。 - 首先，删去的边数只有 $m$ 条，所以至少存在一个点，删去的与它连接的边的条数不超过 $m / n$ 条。 - 找到这个连边数最大的点，把它和它相邻的点合并…

## CF1693B Fake Plastic Trees 题解 - 首先，对于一条路径，从根走到叶子节点明显更优（对于使操作次数更少来说）。 - 对于叶子节点 $v$，$l_v \leq a_v \leq r_v$，我们使对应的 $c_v = r_v$ 肯定是不劣的。 - 对于 $v$ 的父节点 $u$（或任意非叶子…

在文章《题解：CF1693B Fake Plastic Trees》发表评论：

姐姐好棒( •̀ ω •́ )✧

### B4167 [GXPC-S 2024] 扫雷 题解 - 对于本题，我们可以采用类似状压（状态压缩）的方式进行解决，用 `01` 串表示，`1` 表示雷（同时 `?` 的数量小于等于 $10$ 也是突破口），然后依照题意遍历判断即可 QwQ。 ::::success[code] ```cpp #include #…

在文章《题解：B4167 [GXPC-S 2024] 扫雷》发表评论：

发现其实就是状压的简单应用

## CF1718B Fibonacci 题解 - 模拟，贪心。 ### **前置知识** 斐波那契数列有一个性质： - 前 $n$ 项和 $f_0+f_1+ \ldots +f_{n-1} = f_{n+1}-1$。 - 证明（知道的可以略过)： $\begin{aligned} s_n &= f_{n}+f_{n-…

在文章《CSP-S 2025 游记》发表评论：

姐~~~姐~~~

在文章《CSP-S 2025 游记》发表评论：

姐姐文笔好好QwQヾ(≧▽≦*)o (´▽`ʃ♡ƪ)，加油，我们想要的都会有^o^y

```cpp for(int j=i+1;j<=m;++j){ if(vis[j]) continue; if(!cross(i,j)) continue; int a=find(i),b=find(j); if(a==b) return 0; fa[a]=find(j+m); fa[b]=find(i+m); } `…

### P13524 跳跃 题解 ### **分析** - 首先，对于子任务 $1$，暴力枚举即可，复杂度为 $O(n^2 \times (n-2)!)$。 - 假设原始排列为 $1,2,3,\ldots,n$，每一个点的原始贡献为 $1$，将一个点向前移贡献会加上 $2$，如 $1,2,4,3,5$ 中 $4$ 的贡…

检查函数返回值

# P14178 Jueves题解 ### - **前置知识** 1. $a \operatorname{and} b= a \lor b$; 2. $a \operatorname{or} b=a \land b$; 3. $a \operatorname{xor} b=a\oplus b=a \lor b - a…

在文章《题解：P14174 【MX-X23-T4】卡常数》发表评论：

ooorrrzzz学长好厉害 马蜂好好看QwQ

# P14172括号串题解 ### **多测不清空，爆零两行泪 QwQ** (主包因为 cnt 和 top 没清空检查许久) - 简单模拟 - 遇到 `( )` 匹配直接弹出栈 - 注意到 `) (`的情况只能弹出一次(cnt派上用场了 嘿嘿QwQ) -最后如果栈不为空则不可爱，反之则可爱 代码放在这里啦 ```cpp…

**这是一道简单的模拟QwQ** - 注意取模$((i+x) \bmod n+n) \bmod n$,否则当x为负时会爆 RE。 - 注意排序(这里用的结构体)。 - 代码如下。 ```cpp #include #define ll long long using namespace std; const int N=…

# **动态开点线段树做法** - 这道题与《线段树模板1》的主要区别在于$n \le 10^9$,但是$m \le 10^5$,这是本篇题解的主要切入点。 ## **优点** - 不需要预先分配整个线段树的空间，而是在需要时才创建节点; - 对于稀疏操作的大规模区间，能节省大量内存; - 时间复杂度仍保持 $O (l…

在文章《题解：B4167 [GXPC-S 2024] 扫雷》发表评论：

学长牛！！！