26春训练 • F16wer's

不开longlong见祖宗。——统计类问题常开longlong统计结果，可存10的18次方量级的数据。

内存爆栈问题。——数组最好放全局变量那。对于256mb来说，longlong开1.5x10的7次方以内是安全的。

对于memset“上限”，一般填0x3f，但在程序当中检测“是否有更新过”时，则不是0x3f，实际大小是0x很多个3f，有效的检测办法是>1e18.

计数时，用 a[++cnt] 而不是 cnt+=1 可以有效防止“多加一次”问题.
注意变量名字冲突问题，命名得有意义一些是一个有效的办法.
深搜时每写一个dfs() 一定要在后面记得加return 和复位.
某值从1到n环形移动时,考虑边界的整除问题，正确的代码是a = (a + x - 1) % n + 1;

多测清空问题：

对于数组：
法1：memset(a + L, 0, (R - L + 1) * sizeof(数据类型));
法2：直接覆盖

对于vector,要用for挨个.clear().

队列/栈：while(!q.empty（）) q.pop();

异或运算：

相同为0，不同为1.
归零律：a⊕a=0 （自己和自己异或，底牌全消）
恒等律：a⊕0=a （和 0 异或，保持真我）
交换律与结合律：a⊕b⊕c=a⊕c⊕b （随便打乱顺序，结果不变）
自反律：如果 a⊕b=c，那么必然有 a⊕c=b 和 b⊕c=a.

预处理：

对于一些无法避免的枚举层数较多的问题（如AcWing 1221 ↗），可以预先计算并存储。

可以考虑对某组输入数据依据某项值（如时间/大小）进行预处理（如排序）来简化后续处理如sort(a,a+n).

数论:

找质数要从2开始找.

已经复习过的算法复述#

1 前缀和：通过b[i] = a[i] + a[i - 1] 实现对“前i项和”的统计，方便后续处理

2 差分：通过b[i] = a[i] - a[i - 1] 实现前缀和的逆运算。

3 二分：处理“有序数据”的查询，可用于解决“最大值最小化”/“最小值最大化”。
一个基本的实现（保证左边界合法右边界不合法）

while (l + 1 < r) {       // 如果两边界不相邻
    int mid = (l + r) / 2;  
    if (check(mid))         
      l = mid;              
    else
      r = mid;  
  }
  return l;  // 返回左边界

4 双指针：在统计区间信息时，一般会“对每个节点往后计算区间长度”再统计，然而我们可以通过维护两端节点的信息来避免重复计算。

5 单源最短路：通过不断的松弛操作，得到最短路.
堆优化的一个模板.

struct node{
  long long dis,u;
  bool operator>(const node& a) const{return dis > a.dis;}
};
priority_queue<node vector<node>,greater<node>>;

6 排序STL模板

sort(v.begin(), v.end());//vector的排序（从小到大）
sort(v.begin(), v.end(), cmp);//自定义比较函数 （也有用结构体＋重载运算符的操作） 
sort(arr, arr + n);//普通数组排序 
sort(arr + 1, arr + 3);//局部排序

bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) {
        // 第一优先级：分数不同时，分数高的排前面（降序）
        return a.score > b.score; 
    } else {
        // 第二优先级：分数相同时，学号小的排前面（升序）
        return a.id < b.id; 
    }
}//以成绩排序为例的一个cmp函数模板

7 区间合并：遇到了如P12144 [蓝桥杯 2025 省 A] 地雷阵 ↗的题目，
存在多个区间而需要求解“覆盖了多少”的问题。
可以通过：先对所有区间按左端点顺序进行排序，如排在后面的区间的左端点出现在了目前区间的右端点的前面——把目前区间的右端点更新至后面区间的右端点，在扫描完目前区间的右端点时把该区间合并，存至另外一个数组。
简而言之：在排序完区间后维护右端点直到无重合且离开区间。

8 三角函数：c++里的函数主要以弧度形式存在

函数名	数学含义	参数要求	返回值范围
`sin(x)`	正弦 $\sin(x)$	弧度值	$[-1, 1]$
`cos(x)`	余弦 $\cos(x)$	弧度值	$[-1, 1]$
`tan(x)`	正切 $\tan(x)$	弧度值	$(-\infty, +\infty)$
`asin(x)`	反正弦 $\arcsin(x)$	必须在 $[-1, 1]$ 之间	$[-\pi/2, \pi/2]$
`acos(x)`	反余弦 $\arccos(x)$	必须在 $[-1, 1]$ 之间	$[0, \pi]$
`atan2(y, x)`	全象限反正切	坐标 $(y, x)$	$(-\pi, \pi]$

度数转化为角度模板

#include <cmath>

const double PI = acos(-1.0);//获取pi
double degree;
double radian = degree * (PI / 180.0); // 将 度数 转换为 弧度

待办#

1 同余性质等基本的数论学习（在实际比赛中往往是部分分到全部分的关键，例如AcWing 1230，不知道同余的话没办法优化到一层循环，我也是看了题解才写出来的）

2 重载运算符学习(已完成).