一些CS竞赛知识点

输入技巧

std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 一旦启用后，只能选择cin cout这种C++的或这只能选择printf scanf putchar这种C的

STL

vector

copy(original.begin() + start_pos,original.begin() + start_pos + length,copied.begin());
第一个参数（包含）到第二个参数（不包含）之间内容复制到copied.begin()
vector<int> copied(original.begin() + start_pos, original.begin() + start_pos + length);
assign(copied.size(), 10);// 全部置为10
fill(copied, 10);
/*重新设置尺寸*/
vector<vector<int>> cache;
fast_read(n);
fast_read(N);
fast_read(q);
cache.resize(N, vector<int>(n, -1));

vector<vector<pair<int,int>>> adj;
adj.assign(total, {});
adj.push_back(); // 像后面新加一个元素
adj.pop_back(); // 在最后删除一个元素

queue

queue<int> q;
q.push(10);
q.front();
q.pop();
q.empty(); // 是否空

stack

stack<char> st;
st.push('a');    // 栈顶插入 → [a]
st.push('b');    // → [a, b]
char top = st.top();  // 获取栈顶 → 'b'
st.pop();        // 栈顶删除 → [a]
bool empty = st.empty();  // → false

set 自动排序+去重

set<int> s;
s.insert(3);     // 插入元素 → {3}
s.insert(1);     // → {1, 3}（自动排序）
s.insert(3);     // 重复元素不会插入 → 仍为 {1, 3}

// 查找元素
auto it = s.find(3);  // 查找3，返回迭代器
if (it != s.end()) {  // 若找到（迭代器未到末尾）
    // 操作：如删除
    s.erase(it);      // 删除3 → {1}
}

// 范围删除（删除所有≥2的元素）
s.erase(s.lower_bound(2), s.end());
// set和map类似，也有二分查找的算法

map 键值对 + 自动排序

map<string, int> mp;  // 键为string，值为int
mp["apple"] = 5;      // 插入键值对 → {"apple":5}
mp["banana"] = 3;     // → {"apple":5, "banana":3}（按键排序）

// 查找键
if (mp.count("apple")) {  // 检查键是否存在
    int val = mp["apple"];  // 获取值 → 5
}

// 迭代器遍历
for (auto it = mp.begin(); it != mp.end(); it++) {
    string key = it->first;   // 键
    int val = it->second;     // 值
}
auto it = myMap.lower_bound(2);  // 查找第一个 >= 2 的元素
auto it2 = myMap.upper_bound(2); // 查找第一个大于二的元素
if (it != myMap.end()) {
    std::cout << "键: " << it->first << std::endl;   // 输出：3
    std::cout << "值: " << it->second << std::endl;  // 输出：c

    // 修改值（key 不可修改）
    it->second = "new value";  // 现在 myMap[3] 的值变为 "new value"
}
prev(it);
next(it);

priority_queue 优先级队列

// 大顶堆（默认，最大值在顶部）
priority_queue<int> max_heap;
max_heap.push(5);
max_heap.push(3);
int top = max_heap.top();  // → 5

// 小顶堆（需指定比较器）
priority_queue<int, vector<int>, greater<int>> min_heap;
min_heap.push(5);
min_heap.push(3);
int top = min_heap.top();  // → 3

min_heap.pop();  // 删除顶部元素 → 剩余5

unordered_map

unordered_map <int, int> m;
m[1] = 2;
m[10] = 5;
m[1]++;
for (const auto &[k, v]: m){
    
}
m.find(10) != m.end(); //判断是否存在
m.find(10)->second == 5; // true;
m.clear();

unordered_set

unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
vowels.size(); //5
vowels.count('a');
vowels.contains('a');
vowels.erase('a');
vowels.insert('a');

string

string s("asdfadf");
cin>>s; //遇到空格或换行就停止
getline(cin, s); //读整行
s.length();
s.back()是最后一个的引用
s.substr(left, len) 返回一个string O(len)

算法

排序

vector<int> a = {2, 5, ...};
sort(a.begin(), a.end());// 只要能做小于操作就可以排序
class Person {
public:
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {}

    bool operator<(const Person& other) const {
        return age < other.age;  // 按年龄升序排序
    }
};// 自己重载了小于号也可以

三种传入比较函数的方法

自定义比较函数

bool compareByName(const Person& a, const Person& b) {
    return a.name < b.name;
}
std::sort(people.begin(), people.end(), compareByName);

lalmbda表达式

std::sort(people.begin(), people.end(),
          [](const Person& a, const Person& b) {
              return a.age > b.age;  // 按年龄降序排序
          });

比较对象

struct CompareByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};

数字

大小写转换

char c = 'A';
c ^= 0x20; // c = 'a';
c ^= 0x20; // c = 'A'
//小写字母比对应大写字母大0x20 (32)

各位相加

简单理解为返回值循环就好

class Solution {
public:
    int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
};

快速幂

#include <stdio.h>
#include <limits.h> // 用于 LLONG_MAX, LLONG_MIN

/**
 * 整数快速幂 (long long 版本)
 * 计算 base^exponent
 * 
 * @param base 底数
 * @param exponent 指数 (支持负数，但负数指数在整数域通常结果为0，除非底数为±1)
 * @return 计算结果。如果发生错误(如0的负次幂)或溢出，返回特定标记值并在控制台打印错误。
 */
long long fastPowerInt(long long base, int exponent) {
    // 1. 处理指数为 0 的情况
    // 任何数的 0 次幂为 1 (包括 0^0，编程惯例定义为 1)
    if (exponent == 0) {
        return 1;
    }

    // 2. 处理底数为 0 的情况
    if (base == 0) {
        if (exponent < 0) {
            printf("错误：0 的负数次幂无意义！\n");
            return LLONG_MIN; // 用最小值作为错误标记
        }
        // 0 的正数次幂为 0
        return 0;
    }

    // 3. 处理负指数
    // 在整数运算中，除非底数是 1 或 -1，否则 base^(-n) = 1/(base^n) 结果为 0
    if (exponent < 0) {
        if (base == 1) return 1;
        if (base == -1) {
            // (-1)^(-n) 取决于 n 的奇偶性，等同于 (-1)^n
            // 因为 exponent 是负数，如果 exponent 是偶数，结果 1；奇数，结果 -1
            // 注意：-2 是偶数，-3 是奇数。直接判断 exponent % 2 即可
            return (exponent % 2 == 0) ? 1 : -1;
        }
        // 其他情况，整数除法结果为 0
        return 0;
    }

    // 4. 核心快速幂逻辑
    // 使用 long long 存储指数的绝对值，防止 exponent = INT_MIN 时取反溢出
    long long absExponent = exponent; 
    long long result = 1;
    long long currentBase = base;

    while (absExponent > 0) {
        // 如果当前位是 1，则乘入结果
        if (absExponent % 2 == 1) {
            // 溢出检查：result * currentBase 是否超过 LLONG_MAX
            // 简单检查：如果 result > LLONG_MAX / currentBase (需考虑正负)
            // 这里为了代码简洁，假设测试数据不会故意构造溢出，
            // 严谨生产环境需在此处添加详细的溢出判断逻辑
            if (currentBase != 0 && result > LLONG_MAX / currentBase && currentBase > 0) {
                 printf("警告：计算结果溢出 long long 范围！\n");
                 return LLONG_MAX; 
            }
            if (currentBase != 0 && result < LLONG_MIN / currentBase && currentBase < 0) {
                 printf("警告：计算结果溢出 long long 范围！\n");
                 return LLONG_MIN;
            }
            result *= currentBase;
        }

        // 底数平方
        // 准备下一次迭代前，检查 currentBase * currentBase 是否溢出
        if (absExponent > 1) { // 如果还要继续循环，才需要平方
             if (currentBase > 0 && currentBase > 3037000499LL) { 
                 // sqrt(LLONG_MAX) 约为 3.03e9，超过这个数平方必溢出
                 printf("警告：中间计算过程底数平方溢出！\n");
                 // 根据需求决定是返回最大值还是继续（会导致未定义行为）
                 // 这里选择返回最大值以保安全
                 return (exponent % 2 != 0 && result != 1) ? LLONG_MAX : LLONG_MAX; 
             }
             if (currentBase < -3037000499LL) {
                 printf("警告：中间计算过程底数平方溢出！\n");
                 return LLONG_MIN;
             }
             currentBase *= currentBase;
        }

        // 指数折半
        absExponent /= 2;
    }

    return result;
}

int main() {
    printf("--- 整数快速幂测试 (long long) ---\n");

    // 基础测试
    printf("2^10 = %lld\n", fastPowerInt(2, 10));           // 1024
    printf("3^4 = %lld\n", fastPowerInt(3, 4));             // 81
    printf("5^0 = %lld\n", fastPowerInt(5, 0));             // 1
    printf("0^5 = %lld\n", fastPowerInt(0, 5));             // 0
    
    // 负指数测试 (整数域特性)
    printf("2^-3 = %lld (整数除法应为0)\n", fastPowerInt(2, -3)); // 0
    printf("1^-100 = %lld\n", fastPowerInt(1, -100));       // 1
    printf("-1^-3 = %lld\n", fastPowerInt(-1, -3));         // -1
    printf("-1^-4 = %lld\n", fastPowerInt(-1, -4));         // 1

    // 错误测试
    printf("0^-2 = %lld (应报错)\n", fastPowerInt(0, -2));  
    printf("0^0 = %lld (约定为1)\n", fastPowerInt(0, 0));

    // 大数测试
    printf("10^18 = %lld\n", fastPowerInt(10, 18));         // 1000000000000000000
    // printf("10^19 = %lld\n", fastPowerInt(10, 19));      // 会触发溢出警告

    // 关键边界测试：INT_MIN (-2147483648)
    // 2 的 INT_MIN 次方在数学上极小，整数结果为 0
    // 但如果是 (-1) 的 INT_MIN 次方，结果应为 1 (因为 INT_MIN 是偶数)
    printf("(-1)^INT_MIN = %lld (应为1)\n", fastPowerInt(-1, -2147483648));
    
    return 0;
}

滑动窗口

定长滑动窗口

class Solution {
public:
    int maxVowels(string s, int k) {
        int ans = 0, vowel = 0;
        for (int i = 0; i < s.size(); i++) {
            // 1. 进入窗口
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                vowel++;
            }
            if (i < k - 1) { // 窗口大小不足 k
                continue;
            }
            // 2. 更新答案
            ans = max(ans, vowel);
            // 3. 离开窗口，为下一个循环做准备
            char out = s[i - k + 1];
            if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
                vowel--;
            }
        }
        return ans;
    }
};

不定长滑动窗口

/*
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length(), ans = 0, left = 0;
        unordered_map<char, int> cnt; // 维护从下标 left 到下标 right 的字符
        for (int right = 0; right < n; right++) {
            char c = s[right];
            cnt[c]++;
            while (cnt[c] > 1) { // 窗口内有重复字母
                cnt[s[left]]--; // 移除窗口左端点字母
                left++; // 缩小窗口
            }
            ans = max(ans, right - left + 1); // 更新窗口长度最大值
        }
        return ans;
    }
};
// 用unordered_set反而更慢？

数组

二分查找

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        auto it = lower_bound(nums.begin(), nums.end(), target);
        return static_cast<int>(it - nums.begin());
    }
};

std::upper_bound 和 std::lower_bound 这两个算法函数并不关心 std::vector 内部存储的具体类型，而是关心 该类型是否支持必要的比较操作。

struct Point {
    int x;
    int y;
    // 告诉算法：按 x 升序比较
    bool operator<(const Point& rhs) const {
        return x < rhs.x;        // 你想怎么排序就怎么写
    }
};
std::vector<Point> v = {{1,2}, {3,4}, {5,6}};
auto it = std::lower_bound(v.begin(), v.end(), Point{3,0});
// 注意：比较时只用到了 x，y 不参与比较

如果你更喜欢用 Lambda 而不想改类，也可以给算法传一个自定义比较器：

auto cmp = [](const Point& a, const Point& b){ return a.x < b.x; };
auto it = std::lower_bound(v.begin(), v.end(), Point{3,0}, cmp);

auto 名字 = [](const 左值类型& a, const 右值类型& b) -> bool {
    /* 返回 true 表示 a 应该排在 b 前面 */
};
#include <algorithm>
#include <vector>
#include <iostream>

struct Point { int x; int y; };

int main() {
    std::vector<Point> v = {{1,2}, {3,4}, {3,1}, {5,6}};

    // 1. 写一个 lambda
    auto cmp = [](const Point& a, const Point& b) -> bool {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    };

    // 2. 把 lambda 作为第 4 个实参传进去
    Point key{3, 2};
    auto it = std::lower_bound(v.begin(), v.end(), key, cmp);

    if (it != v.end())
        std::cout << "found: (" << it->x << ',' << it->y << ")\n";
}

获取第k小的数字

// 分区操作，返回基准元素的最终位置
int partition(vector<int>& arr, int low, int high) {
    // 随机选择一个元素作为基准，避免最坏情况
    int pivotIndex = low + rand() % (high - low + 1);
    swap(arr[pivotIndex], arr[high]);
    int pivot = arr[high];  // 基准元素
    int i = low - 1;        // 小于基准的元素的边界
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++;  // 扩大小于基准的区域
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);  // 将基准放到正确的位置
    return i + 1;
}

// 查找第k小的元素（k从1开始）
// 包括low 和 high
int findKthSmallest(vector<int>& arr, int low, int high, int k) {
    if (k > 0 && k <= high - low + 1) {
        // 进行分区操作
        int pivotPos = partition(arr, low, high);
        
        // 如果基准位置就是第k小元素
        if (pivotPos - low == k - 1) {
            return arr[pivotPos];
        }
        
        // 如果第k小元素在基准左侧
        if (pivotPos - low > k - 1) {
            return findKthSmallest(arr, low, pivotPos - 1, k);
        }
        
        // 如果第k小元素在基准右侧
        return findKthSmallest(arr, pivotPos + 1, high, k - pivotPos + low - 1);
    }
    
    // 如果k无效，返回一个特殊值
    return -1;
}

树

线段树

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = 4e18; // 使用一个足够大的数表示无穷大

int main() {
    // 提高cin/cout效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 存储初始的 a 和 b 数组
    vector<long long> a_base(n + 1);
    vector<long long> b_base(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a_base[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b_base[i];
    }

    int q;
    cin >> q;

    // 循环处理每次查询
    while (q--) {
        int k_changed;
        long long a_new, b_new;
        cin >> k_changed >> a_new >> b_new;

        // 每次查询都基于初始局面进行修改
        vector<long long> a = a_base;
        vector<long long> b = b_base;
        a[k_changed] = a_new;
        b[k_changed] = b_new;

        // 1. 预处理：计算 b 的前缀和
        // sumB[i] 表示 b[1] + ... + b[i]
        vector<long long> sumB(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            sumB[i] = sumB[i - 1] + b[i];
        }
        
        // 用于存储每个起点的最终答案
        vector<long long> p(n + 1);
        long long xor_sum = 0;

        // 2. 主循环：遍历每一个可能的起始点 k
        for (int k = 1; k <= n; ++k) {
            // L[i] : 从 k 出发，一路向左打到 i 的最小需求
            vector<long long> L(n + 1);
            // R[j] : 从 k 出发，一路向右打到 j 的最小需求
            vector<long long> R(n + 1);

            // 2a. 计算 L 和 R 数组 (线性DP)
            L[k] = a[k];
            for (int i = k - 1; i >= 1; --i) {
                // 打[i+1, k]获得的b总和为 sumB[k] - sumB[i]
                L[i] = max(L[i + 1], a[i] - (sumB[k] - sumB[i]));
            }

            R[k] = a[k];
            for (int j = k + 1; j <= n; ++j) {
                // 打[k, j-1]获得的b总和为 sumB[j-1] - sumB[k-1]
                R[j] = max(R[j - 1], a[j] - (sumB[j - 1] - sumB[k - 1]));
            }

            long long min_req_for_k = INF;

            // 2b. 枚举所有可能的路径（通过枚举“掉头点”）
            // 路径1：先向左打到 i，再掉头向右打通关
            for (int i = 1; i <= k; ++i) {
                long long cost_left_part = L[i];
                long long cost_right_part = 0; // 如果 k=n 且 i=k, 则没有右边部分
                
                if (k < n) {
                    // 打完 [i, k] 后，获得的 b 总和为 sumB[k] - sumB[i-1]
                    // 现在需要从 k+1 打到 n
                    // 对于任意 p in [k+1, n]，打它时的需求是 a[p] - (sumB[k]-sumB[i-1]) - (sumB[p-1]-sumB[k])
                    // a[p] - sumB[p-1] + sumB[i-1]
                    // 我们需要求 max_{p=k+1..n} (a[p] - sumB[p-1] + sumB[i-1])
                    // 这个问题可以分解，但是直接循环计算也可以接受，因为N不大
                    // 为了清晰，这里暂时用 O(N) 计算，但可以优化
                    cost_right_part = -INF;
                     for (int p = k + 1; p <= n; ++p) {
                        cost_right_part = max(cost_right_part, a[p] - (sumB[p - 1] - sumB[i - 1]));
                    }
                }
                min_req_for_k = min(min_req_for_k, max(cost_left_part, cost_right_part));
            }

            // 路径2：先向右打到 j，再掉头向左打通关
            for (int j = k; j <= n; ++j) {
                long long cost_right_part = R[j];
                long long cost_left_part = 0; // 如果 k=1 且 j=k, 则没有左边部分

                if (k > 1) {
                    // 打完 [k, j] 后，获得的 b 总和为 sumB[j] - sumB[k-1]
                    // 现在需要从 k-1 打到 1
                    cost_left_part = -INF;
                    for (int p = k - 1; p >= 1; --p) {
                         // 打 p 的时候，已经清了 [k,j] 和 [p+1, k-1], 总共是 [p+1, j]
                        cost_left_part = max(cost_left_part, a[p] - (sumB[j] - sumB[p]));
                    }
                }
                 min_req_for_k = min(min_req_for_k, max(cost_right_part, cost_left_part));
            }
            
            p[k] = min_req_for_k + 1;
        }

        // 3. 计算并输出最终的异或和
        for (int i = 1; i <= n; ++i) {
            xor_sum ^= p[i];
        }
        cout << xor_sum << "\n";
    }

    return 0;
}

二进制操作

unsigned int x = 13; // 二进制: 1101
cout << __builtin_popcount(x) << endl; // 输出 3 计算unsigned int中1的个数
x = 8; // 二进制: 1000
cout << __builtin_ctz(x) << endl; // 输出 3 计算unsigned int中末尾0的个数
cout << __builtin_clz(x) << endl; // 输出 28 计算unsigned int中前面0的个数
// 以上函数如果统计unsigned long long的，在函数名字后面加上ll
string binary_str = "1101";
int num = stoi(binary_str, nullptr, 2); // 从二进制字符串转换为整数
cout << num << endl; // 输出 13