1. 结构体基础

核心理解 结构体是一种自定义数据类型，允许我们将多个不同类型的变量（如整数、字符串、浮点数）组合成一个逻辑上的整体。这比单独使用多个数组更智能、更便于管理。

定义与使用示例

struct student {
    int y, s, w;   // 语文、数学、外语成绩
    int zf;        // 总分
    int xh;        // 学号
} s[310];          // 定义结构体后，直接声明一个包含310个元素的数组

复习要点

• 定义：struct 结构体名 { 成员变量; };
• 访问：通过 . 运算符访问，如 s[i].y，s[i].xh。
• 意义：将相关的数据（如一个学生的所有信息）打包在一起，使代码逻辑更清晰。

2. 结构体排序：sort 与自定义比较函数

核心场景 我们需要根据自定义的规则对结构体数组进行排序（例如，先按总分排，再按语文排）。

自定义比较函数 cmp 这是排序的核心。sort 函数会根据 cmp 的返回值来决定元素的顺序。

• 规则：cmp(s1, s2) 返回 true，意味着 s1 应该排在 s2 前面。
• 格式：

  bool cmp(结构体名 a, 结构体名 b) {
      if (a.属性1 == b.属性1) {
          // 按属性2排序，返回真则a在前
          return a.属性2 > b.属性2; 
      } else {
          // 直接按属性1排序
          return a.属性1 > b.属性1;
      }
  }
  

• 调用：sort(起始地址, 结束地址的下一个, cmp);

综合案例：学生成绩排名 需求：

1. 按总分从高到低排序。
2. 若总分相同，按语文成绩从高到低排序。
3. 若总分和语文均相同，学号小的排在前面。

代码实现

#include<bits/stdc++.h>
using namespace std;
struct student {
    int y, s, w; // 语数外
    int zf;      // 总分
    int xh;      // 学号
} s[310];
int n;

bool cmp(student s1, student s2){
    if (s1.zf == s2.zf){                 // 总分相同
        if (s1.y == s2.y){               // 语文也相同
            return s1.xh < s2.xh;        // 学号小的在前
        } else {
            return s1.y > s2.y;          // 语文高的在前
        }
    } else {
        return s1.zf > s2.zf;            // 总分高的在前
    }
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s[i].y >> s[i].s >> s[i].w;
        s[i].xh = i;
        s[i].zf = s[i].y + s[i].s + s[i].w; // 计算总分
    }
    sort(s + 1, s + 1 + n, cmp); // 排序

    // 输出前5名学生的学号和总分
    for (int i = 1; i <= 5; i++){
        cout << s[i].xh <<  " " << s[i].zf << endl;
    }
    return 0;
}

3. 进阶应用：排名与多轮排序

核心场景 有时我们不仅需要排序，还需要根据排序结果给出“名次”，然后再恢复原始顺序输出。这通常需要两次排序。

代码解析

1. 第一次排序 (cmp)：按分数从高到低，分数相同按学号从小到大排。计算名次 mc。
   • 名次规则：若分数与前一人相同，则名次相同；否则，名次 = 前一人名次 + 1。
2. 第二次排序 (cmp2)：按原始输入位置 wz 恢复顺序。
3. 输出：按原始顺序输出每个人的名次。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct stu{
    int xh, fs;      // 学号，分数
    string name;     // 姓名
    int mc, wz;      // 名次，原始位置
}s[1010];
int n;

// 排序规则1：用于确定名次
bool cmp(stu s1, stu s2){
    if(s1.fs == s2.fs) return s1.xh < s2.xh; // 分数相同，学号小的在前
    else return s1.fs > s2.fs;               // 分数高的在前
}

// 排序规则2：用于恢复原始顺序
bool cmp2(stu s1, stu s2){
    return s1.wz < s2.wz; // 按原始位置升序
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s[i].xh >> s[i].name >> s[i].fs;
        s[i].wz = i;      // 记录原始输入位置
    }
    
    // --- 第一次排序：计算名次 ---
    sort(s + 1, s + 1 + n, cmp);
    s[1].mc = 1;          // 第一名
    for(int i = 2; i <= n; i++){
        if(s[i].fs == s[i-1].fs) s[i].mc = s[i-1].mc;      // 同分同名次
        else s[i].mc = s[i-1].mc + 1;                       // 不同分名次+1
    }
    
    // --- 第二次排序：恢复原顺序并输出 ---
    sort(s + 1, s + 1 + n, cmp2);
    for(int i = 1; i <= n; i++) cout << s[i].mc << endl;
    return 0;
}

4. 数论基础：质数与因数

判断一个数 x 是否为质数

• 原理：如果 x 是合数，它必然有一个小于等于 sqrt(x) 的因数。
• 时间复杂度：O(sqrt(n))，适用于 n 在 1e9 左右的单次判断。

bool isP(int x){
    if (x <= 1) return false;
    int tem = sqrt(x); // 计算平方根
    for (int i = 2; i <= tem; i++){
        if (x % i == 0) return false; // 找到因数，是合数
    }
    return true; // 找不到因数，是质数
}

计算一个数 x 的所有因数之和

• 原理：因数总是成对出现（i 和 x/i）。遍历到 sqrt(x) 即可，避免重复计算平方根。
• 注意：当 i == x / i（即 x 为完全平方数）时，只加一次。

long long js(int x){
    long long sum = 0, tem = sqrt(x);
    for (int i = 1; i <= tem; i++){
        if (x % i == 0){
            if (i == x / i) sum += i;      // 如 16 的因数 4
            else sum += i + x / i;         // 如 16 的因数 2 和 8
        }
    }
    return sum;
}

5. 算法优化：埃氏筛与回文数生成

埃氏筛法

• 场景：快速找出 [1, 1e7] 范围内所有的质数。
• 原理：从2开始，如果一个数是质数，就将其所有倍数（2倍、3倍...）标记为合数。
• 优势：比单独判断每个数快得多。

bool isP[10000010]; // 全局数组，默认值为 false

void beishushai(){
    isP[1] = true;   // 1不是质数，标记为true
    for(int i = 2; i <= 1e7; i++){
        if(isP[i] == false){          // i 是质数
            for(int j = 2; i * j <= 1e7; j++){
                isP[i * j] = true;    // 将i的所有倍数标记为合数
            }
        }
    }
}

回文数的生成

• 场景：判断一个范围 [a, b] 内的回文质数。直接生成回文数再判断质数，比枚举所有数字效率高得多。
• 生成方式：将数字的一半翻转过去。
  • 偶位回文数：123 -> 123321
  • 奇位回文数：123 -> 12321

// 生成偶位回文数：123 -> 123321
int hw1(int x){ 
    int res = x;
    while(x){
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

// 生成奇位回文数：123 -> 12321
int hw2(int x){
    int res = x;
    x /= 10; // 去掉最后一位
    while(x){
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

// 主逻辑
int a, b, cnt, h[10000010];
void jiejue(){
    cin >> a >> b;
    // 生成回文数
    for(int i = 1; i <= 1e4; i++){
        int n1 = hw1(i), n2 = hw2(i);
        if(n1 >= a && n1 <= b) h[++cnt] = n1;
        if(n2 >= a && n2 <= b) h[++cnt] = n2;
    }
    // 排序并判断质数
    sort(h + 1, h + 1 + cnt);
    for(int i = 1; i <= cnt; i++){
        if(isP(h[i]) == true) cout << h[i] << endl; // isP为质数判断函数
    }
}

复习要点总结

• 结构体：理解其为“打包数据”的工具。
• 比较函数：牢记返回 true 表示第一个参数排在前面。
• 排序套路：先排序计算名次，再恢复顺序输出。
• 数论：掌握 sqrt(n) 判断质数和求因数的模板。
• 筛法：埃氏筛法用于快速求大范围质数，回文数生成是典型的“构造优于枚举”的优化思想。