[P8649 蓝桥杯 2017 省 B] k 倍区间：前缀和 + 同余
题目描述给定长度为 $N$ 的数组 $A$，求有多少个连续区间 $(l, r)$，满足区间和是 $K$ 的倍数。 数据范围：$1 \le N, K \le 10^5$，$1 \le A_i \le 10^5$。 题面：洛谷 P8649 [蓝桥杯 2017 省 B] k 倍区间 一、思路：前缀和 + 同余1.1 前缀和定义前缀和数组 $s$，规定： s[0] = 0,\quad s[i] = A_1 + A_2 + \dots + A_i区间 $(l, r)$ 的总和： \text{sum}(l, r) = s[r] - s[l-1]1.2 题目条件 → 同余关系题目要 "区间和是 $K$ 的倍数"： s[r] - s[l-1] \equiv 0 \pmod K等价变形： \boxed{s[r] \pmod K = s[l-1] \pmod K} 核心结论：只要两个前缀和对 $K$ 取模的余数相等，它们之间的区间和就一定是 $K$ 的倍数。 1.3 直观例子$K = 2$，$s[r] = 15$，$s[l-1] = 3$： $15 \bmod 2 = ...
C++ STL 速查：容器、适配器与配对类型
STL（Standard Template Library，标准模板库）= 容器 + 算法 + 迭代器 + 仿函数 + 配对类型。这一篇只整理容器与配对类型——按"序列 / 关联 / 无序 / 配对"分组，每种给最常用接口 + 易错点。 一、vector：动态数组头文件：<vector> std::vector<T> 是动态可变长的顺序容器，底层单一整块连续内存。 1.1 insert vs emplace：少一次拷贝123456789101112131415161718192021222324252627#include <iostream>#include <vector>using namespace std;struct Student { int id; string name; Student(int i, string n) : id(i), name(n) { cout << "构造 Student\n"; ...
C++ 类型转换：从「隐式转换」到「四种命名转换」
C++ 的类型转换分为两类：隐式转换（编译器自动做）和显式转换（程序员主动写）。其中显式转换又分为 C 风格 (T)expr 和 C++ 风格的四种命名转换 static_cast / dynamic_cast / const_cast / reinterpret_cast。 核心原则：能用隐式就别显式；显式里能用 static_cast 解决的，就别用 reinterpret_cast。 一、隐式转换不需要任何运算符，当一个值赋给另一个兼容类型时会自动发生。 1.1 数值类型自动提升1234int a = 2;double d = a; // int → double，自动char c = 'A';int x = c; // char → int 1.2 派生类指针 → 基类指针12345678class A {};class B : public A {};int main() { B* pSub = new B(); A* pBase = pSub...
C++ 函数指针：把"函数"当"值"传来传去
函数指针就是指向函数的指针变量。函数在内存里同样有地址，所以可以像变量一样被指针"指向"，进而作为参数传递、存到数组里、运行时切换调用。 一、声明函数指针语法：返回类型 (*指针名)(参数列表); 12345678910111213141516171819202122#include <iostream>using namespace std;double multiply(double a, double b) { return a * b;}double add(double a, double b) { return a + b;}int main() { // 声明一个「指向返回 double、参数 (double, double) 函数」的指针 double (*ptr)(double a, double b) = multiply; double res = ptr(4.2, 1.5); // 调用 multiply，res = 6.3 pt...
C++ 函数封装与绑定：std::function、std::bind、std::placeholders
STL 标准库里提供了一些函数包装与绑定模板，可以把"可调用对象"统一包装成一种类型，方便在函数之间传来传去、当作回调。 一、std::function：可调用对象包装器头文件：#include <functional> std::function<R(Args...)> 是可调用对象包装器。一句话：可以把普通函数、lambda、函数对象、成员函数全部包装成同一个类型，统一调用。 模板参数 R(Args...) 中： R：返回值类型 Args...：参数列表（可变参数包） 1.1 能包装哪些东西 可调用类型 是否能包装进 function 普通全局函数 ✅ Lambda 表达式 ✅（带不带捕获都行） 重载了 operator() 的函数对象（仿函数） ✅ 类成员函数 / const 成员函数 ✅（需要额外处理 this） 1.2 基础示例：包装普通函数12345678910111213141516171819#include <iostream>#include <functi...
C++ 运算符重载：让自己的类也能用 +、==、<<
运算符重载（operator overloading）就是给自定义类型（类 / 结构体）定义运算符的行为。默认情况下，int a + int b 这种内置类型能 +，但 MyClass a + MyClass b 编译器不知道怎么办——除非你告诉它「+ 在我的类上应该怎么算」。 一、为什么需要运算符重载举一个简单的例子：复数类想实现两个复数相加： 123struct Complex { double real, imag;}; 如果直接写 c1 + c2，编译报错：no match for 'operator+' ...。 通过运算符重载，可以写成像内置类型一样自然： 1Complex c3 = c1 + c2; // 像 int 那样用 二、运算符重载的语法两种形式： 形式 1：成员函数123456struct Complex { double real, imag; Complex operator+(const Complex& other) const { retur...
C++ 多线程：从「一前一后」到「一起跑」
头文件：<thread> 线程（thread）是操作系统调度的最小单位——一个进程里的多个线程共享同一块内存，轮流被 CPU 执行。多线程适合"互不相关的任务一起跑"（如一边下载一边显示进度），但共享数据需要保护。 一、第一个线程程序123456789101112131415#include <iostream>#include <thread>#include <string>using namespace std;void print(string msg) { cout << msg << endl;}int main() { // 创建线程，把参数传给线程入口函数 thread t(print, "Hello, thread!"); t.join(); // 主线程等待 t 线程结束 return 0;} join() 之后 t 就不能再次 join/detach 了。 二、线程...
C++ 右值引用与移动语义
核心解决的痛点：大对象拷贝时产生昂贵的深拷贝开销，浪费内存、时间。例如 vector<string>、自定义的大数组对象，拷贝会复制全部数据；移动语义可以直接"偷走"资源，不复制数据。 一、左值、右值 venn A(glvalue):::yellow B(rvalue):::green A only A: lvalue A intersect B: xvalue B only B: prvalue classDef yellow fill:#f2d249,stroke:#cc9900 classDef green fill:#309955,stroke:#106633 左值（lvalue）能取地址、可以修改的持久对象，有名字。 12int a = 10; // a 是左值int b = a; // a 作为表达式结果是右值，但 a 这个变量本身是左值 可以写 &a 取地址。 右值（rvalue）临时对象，没有名字，不能取地址，生命周...
C++ 智能指针：用 RAII 让堆内存"自动归还"
头文件：#include <memory> 智能指针的核心目的：自动管理堆内存，离开作用域自动释放，杜绝内存泄漏。底层原理：RAII（Resource Acquisition Is Initialization，资源获取即初始化）——构造时拿到资源，析构时释放资源。 裸指针的痛点：new 出来的内存忘 delete → 内存泄漏；重复 delete；野指针。智能指针把 delete 写进了析构函数。 一、三大智能指针总览 类型 所有权模型 拷贝 底层开销 用途 unique_ptr 独占 ❌ 不可拷贝，只能 move 极小（≈裸指针） 绝大多数场景首选 shared_ptr 共享（引用计数） ✅ 原子计数，开销大 需要多个指针共用一块内存 weak_ptr 弱引用，不拥有 ✅ 很小 配合 shared_ptr 解决循环引用 二、unique_ptr：独占智能指针一块堆内存，只能有一个 unique_ptr 指向它：不能拷贝，只能移动。 123456789101112131415161718192021222324252627#incl...
C++ Lambda 表达式（匿名函数）：写临时小函数的「快捷方式」
Lambda 表达式就是一个当场写、当场用、不用起名字的小函数。在 sort、for_each、STL 容器遍历里写回调非常方便，比单独写全局函数或仿函数更紧凑。 一、完整语法1[捕获列表](参数列表) mutable -> 返回值类型 { 函数体 }; 拆成 5 部分： 位置 名称 说明 [] 捕获列表 把外面变量抓到 lambda 内部使用（最核心、最容易踩坑） () 参数列表 和普通函数参数一样 mutable 可选 允许修改「值捕获」的副本 -> 类型 尾置返回类型 可选，大部分情况编译器能自动推导 {} 函数体 真正执行的代码 大括号后面的分号 ; 不要漏——lambda 整体是一个表达式，表达式必须以分号结尾。 二、捕获列表（最核心、最容易踩坑） 写法 含义 [] 不捕获任何外部变量 [=] 值捕获：复制一份进 lambda，只读；加 mutable 才能改副本，但不会改原值 [&] 引用捕获：全部变量引用，lambda 内修改会直接改动原值 [x] 只值捕获...