首页 书籍 挑战程序设计竞赛

# 二分搜索

# 从有序数组中查找某个值

二分查找（Binary Search）是一种在有序数组中查找特定元素的算法。它的基本思想是：首先确定数组的中间元素，然后将待查找的元素与中间元素进行比较，如果相等则返回中间元素的索引；如果待查找元素小于中间元素，则在左半部分继续查找；如果待查找元素大于中间元素，则在右半部分继续查找。通过不断缩小查找范围，最终可以找到目标元素或确定目标元素不存在。

#include <iostream>
#include <vector>
int binarySearch(const std::vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // 找到目标元素，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1; // 在右半部分继续查找
        } else {
            right = mid - 1; // 在左半部分继续查找
        }
    }
    return -1; // 目标元素不存在，返回 -1
}
int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    int result = binarySearch(arr, target);
    if (result != -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }
    return 0;
}
lower_bound


lower_bound  是 C++ STL 中的一个函数，用于在有序容器（如 vector、set、map 等）中查找第一个大于或等于给定值的元素的位置（迭代器）。如果容器中存在该值，则返回指向该值的迭代器；如果容器中不存在该值，返回第一个大于该值的元素的迭代器。


#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> vec = {1, 2, 3, 5, 5, 7, 9};
    // 使用 lower_bound 查找第一个大于或等于 5 的元素的位置
    std::vector<int>::iterator it = std::lower_bound(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        std::cout << "First element greater than or equal to 5 is at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "No element greater than or equal to 5 found" << std::endl;
    }
    return 0;
}
# 判断一个解并判断是否可行




思路：可用贪心，这里尝试用二分，条件 C = 可以得到 K 条长度为 x 的绳子，需要求满足 C 的 x 的最大值，长度为 L【i】的绳子最多可以切出 floor（Li/x）段长度为 x 的绳子，floor（）函数是向下取整。


    

  1. 确定二分搜索的上下界：lb=0，ub=INF
    2. 

  2. 在每次二分搜索中，计算中间长度 mid，然后检查是否可以将绳子按照长度 mid 进行切割，以满足 N 段绳子的条件。
    3. 

  3. 根据检查结果，调整二分搜索的上下界，并不断进行二分搜索，直到找到最优解。
    4. 



#include <iostream>
#include <cmath>// 数学函数
using namespace std;
#define INF 100000
int N, K;
double L[1005];
// 判断是否满足条件
bool C(double x) {
    int num = 0;
    for (int i = 0; i < N; i++) {
        num += static_cast<int>(L[i] / x);// 将浮点数结果 L [i] /x 转换为整数。
    }
    return num >= K;
}
void solve() {
    double lb = 0, ub = INF;
    for (int i = 0; i < 100; i++) {
        double mid = (lb + ub) / 2;
        if (C(mid)) lb = mid;
        else ub = mid;
    }
    printf("%.2f\n", floor(ub * 100) / 100);//floor 函数向下取整，确保结果不超过两位小数
}
int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++)  cin >> L[i];
    solve();
    return 0;
}
循环次数定为 100 是为了保证二分法的精度。二分法是一种逼近法，它通过不断将搜索区间对半分割来逼近目标值，因此循环的次数需要足够多才能得到较为精确的结果。


在这段代码中，循环 100 次是一个经验值，经验表明进行 100 次循环可以达到比较合理的精度，当然也可以根据具体情况调整循环次数。通常情况下，循环次数越多，得到的结果精度越高，但也会增加计算时间。


# 最大化最小值




思路：最大化最小值或最小化最大值可以用二分搜索解决。


C（d）= 可以安排牛的位置使得任意两头牛距离不小于 d，问题则变成了满足 C（d）的最大 d。


贪心求解：1. 对牛舍排序 2. 把第一头牛放到 x0 牛社 3. 如果第 i 头牛放到了 xj 的话，第 i+1 头牛要放入满足 xj+d<= xk 中


复杂度 o（n）


#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int x[100005];
bool C(int d) {// 能否将牛放置在距离为 d 的牛栏之间
    int last = 0;
    for (int i = 1; i < M; i++) {
        int crt = last + 1;
        while(crt < N && x[crt] - x[last] < d) {
            crt++;
        }
        if (crt == N) return false;
        last = crt;
    }
    return true;
}
void solve() {// 在可能的最小距离范围内确定最大可能距离
    sort(x, x + N);
    int lb = 0, ub = N - 1;
    while(ub - lb > 1) {
       int mid = (lb + ub) / 2;
       if (C(mid)) lb = mid;
       else ub = mid;
    }
    printf("%d\n",lb);
}
int main() {
   cin >> N >> M;
   for (int i = 0; i < N; i++) {
       cin >> x[i];
   }
   solve();
   return 0;
}
# 最大化平均值




思路：贪心法排序选择单价最高算出来是错的


令 C (x) 为可以选择使得单位重量的价值不小于 x。 ∑vi / ∑wi >= x 单位价值不小于 x----》∑(vi - x*wi) >= 0

 这样就可以用二分法来解决，不断二分 x 进行判断，取最大。


#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f// 无穷大
using namespace std;
int n, k;
int w[1005], v[1005];
double y[1005];//v - x * w 需要的单位重量的价值的数组
bool C(double x) {
    for (int i = 0; i < n; i++) {
        y[i] = v[i] - x * w[i];
    }
    sort(y, y + n);
    // 计算 y 数组中从大到小前 k 个数的和
    double sum  = 0;
    for (int i = 0; i < k; i++) {
        sum += y[n - i - 1];
    }
    return sum >= 0;
}
void solve() {
    double lb = 0, ub = INF;
    for (int i = 0; i < 100; i++) {// 精度
        double mid = (lb + ub) / 2;
        if(C(mid)) lb = mid;
        else ub = mid;
    }
    printf("%.2f\n",ub);
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> w[i];
    for(int i = 0; i < n; i++) cin >> v[i];
    solve();
}
# 常用技巧


# 尺取法（双指针）


双指针法是一种常见的算法技巧，通常用于解决数组或链表中的问题。它通过维护两个指针在数组或链表上移动，根据问题的要求来寻找特定的解。这里详细讲解一下双指针法的原理和常见应用：


原理：


双指针法通常使用两个指针，分别称为快指针和慢指针，或者左指针和右指针。这两个指针按照特定规则在数据结构上移动，以达到查找或处理数据的目的。


常见类型：


    

  1. 快慢指针：常用于链表中，快指针移动速度比慢指针快，可以判断链表是否有环、寻找链表的中间节点等。
    2. 

  2. 左右指针：常用于数组或字符串中，左右指针从两端开始，根据问题要求移动指针来寻找满足条件的子数组或子序列。
    3. 



应用场景：


    

  1. Two Sum（两数之和）：通过左右指针在有序数组中寻找两个数的和等于目标值。
    2. 

  2. Three Sum（三数之和）：通过左右指针在数组中寻找三个数的和等于目标值。
    3. 

  3. 反转数组或字符串：使用左右指针交换元素来实现数组或字符串的反转。
    4. 

  4. 滑动窗口问题：通过维护一个窗口（两个指针定义窗口的边界）来解决滑动窗口相关问题。
    5. 



解题步骤：


    

  1. 初始化指针：根据问题要求初始化左右指针位置。
    2. 

  2. 移动指针：根据具体问题，通过移动左右指针来满足特定条件。
    3. 

  3. 更新结果：在移动指针的过程中，根据问题要求更新结果。
    4. 

  4. 终止条件：确定算法终止的条件，通常是其中一个指针到达边界或满足特定条件。
    5. 

  5. 返回结果：根据问题要求返回最终结果。
    6. 



优势：


    

  • 空间复杂度低：双指针法通常不需要额外空间，节省内存消耗。
    • 

  • 时间复杂度低：双指针法能够以较低的时间复杂度解决问题，提高算法效率。
    • 



双指针法是一种灵活且实用的算法技巧，在解决数组和链表相关问题时具有很好的适用性和效率。通过掌握双指针法的原理和应用，可以更好地解决各类算法问题。




思路：  前缀和 sum []，然后使用 lower_bound 二分查找子序列，时间复杂度 o（nlogn）


#include <iostream>
using namespace std;
int n, S;
int a[10005];
int sum[100005];// 前缀和数组
void solve() {
    for(int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + a[i];// 从 sum【】是 1-n
    }
    if(sum[n] < S) {
        // 没有解
        printf("0\n");
        return;
    }
    int res = n;
    for (int s = 0; sum[s] + S <= sum[n]; s++) {
        // 二分求 t
        // 找到一个位置 t，使得 sum [t] 第一次大于或等于 sum [s] + S。
        int t = lower_bound(sum + s, sum + n, sum[s] + S) - sum;//sum 是数组的起始位置，这里是为了找相对位置
        res = min(res, t - s);
    }
    printf("%d\n", res);
}
int main() {
    cin >> n >> S;
    for(int i = 0; i < n; i++) cin >> a[i];
    solve();
}
两个指针 s 和 t 来维护子序列的起始位置和结束位置，并通过循环遍历数组来不断调整这两个指针。在最坏情况下，每个指针都需要遍历整个数组一次，即 O (n) 的时间复杂度。


void solve() {
    int res = n + 1;// 初始化
    int s = 0, t = 0, sum = 0;// 当前子序列的起始位置、结束位置（不包括）和和
    for(;;) {
        while (t < n && sum < S) {// 在内层循环中不断向右扩展子序列的结束位置 t，直到子序列的和大于等于目标值 S 或者 t 达到数组末尾
            sum += a[t++];
        }
        if (sum < S) break;// 没有子序列和满足大于 S
        res = min(res, t - s);
        sum -= a[s++];// 缩小子序列的范围，向右移动起始位置 s，同时减去移动后位置的元素值，以继续寻找更短的满足条件的子序列
    }
    if (res > n) {
        // 解不存在
        res = 0;
    }
    printf("%d\n", res);
}


这种反复推动区间开头和结尾，来求满足条件的最小区间的方法叫做尺取法。




思路：




#include <iostream>
#include <set>
#include <map>
using namespace std;
int P;
int a[100005];
void solve() {
    // 计算所有的知识点
    set<int> all;
    for(int i = 0; i < P; i++) {
        all.insert(a[i]);
    }
    int n = all.size();// 得到不同知识点的总数 n
    // 尺取求解
    int s = 0, t = 0, num = 0;//num 记录当前窗口内包含的不同知识点数量
    map<int, int> count;// 知识点  出现次数
    int res = P;
    for(;;) {
        while (t < P && num < n) {// 不断向右移动窗口，并更新窗口内的状态，直到窗口内包含了所有不同的知识点或者 t 指针超出数组范围
            if(count[a[t++]]++ == 0) {// 查找该知识点在 count 映射中的计数并将其增加 1。如果该知识点之前没有出现过，则在 count 中新增该知识点，并将其计数设为 1。
                // 出现新知识点
                num++;
            }
        }
        if (num < n) break;
        res = min(res, t - s);
        if (--count[a[s++]] == 0) {// 检查左边界 s 处的知识点在窗口内的计数是否为 0
            //--count [a [s++]]：将左边界处知识点的计数减 1，并将左边界向右移动一位。
            // 检查左边界处知识点在窗口内的计数是否变为 0。若计数为 0，表示该知识点不再在窗口内，执行以下操作：
            // 不同知识点数量减 1（num--），表示窗口内丢失了一个不同的知识点。
            num--;
        }
    }
    printf("%d\n", res);
}
int main() {
    cin >> P ;
    for (int i = 0; i < P; i++) cin >> a[i];
    solve();
}
# 反转（开关问题）




思路：


    

  1. 定义一个函数  calc(K) ，用于计算给定 K 值下的最小操作次数。在这个函数中，通过遍历不同的区间范围来模拟牛群的移动：

      

    • 对于每个区间，检查这个区间内牛的朝向是否需要调整，如果需要调整则记录操作次数，并更新一个辅助数组  f 。
      • 

    • 同时维护一个变量  sum ，记录  f  数组的和，以便后续判断是否存在无法调整的情况。
      • 

    • 最后，通过对比数组末尾部分是否有牛朝向后方来判断是否存在无解的情况。
      • 

    

    2. 

  2. 定义一个函数  solve() ，用于遍历不同的 K 值并找到最优解：

      

    • 初始化最小操作次数  M  和对应的最小 K 值  K 。
      • 

    • 遍历所有可能的 K 值（从 1 到 N），调用  calc(K)  计算对应的最小操作次数，并更新最小操作次数  M  和最小 K 值  K 。
      • 

    

    3. 



#include <iostream>
#include <string.h>
using namespace std;
int N;
int dir[5005];// 牛的方向 0,1
int f[5005];// 区间【i，i+K-1】是否反转
// 固定 k，求对应的最小操作回数
// 无解返回 - 1
int calc(int K) {
    memset(f, 0, sizeof(f));
    int res = 0;
    int sum = 0; //f 的和
    for (int i = 0; i + K <= N; i++) {
        // 计算区间【i,i+K-1] 窗口
        if ((dir[i] + sum) % 2 != 0) {//sum 则是一个累积值，用来表示当前位置之前所有牛的朝向总和。如果 dir [i] 加上 sum 的值为奇数，说明当前牛的朝向与前面所有牛的朝向总和不匹配，需要进行调整。
            // 前端的牛面朝后方
            res++;
            f[i] = 1;
        }
        sum += f[i];
        if (i - K + 1 >= 0) {// 更新窗口内的 sum
            sum -= f[i - K + 1];
        }
    }
    // 检查剩下的牛是否面朝后方
    for (int i = N - K + 1; i < N; i++) {
        if((dir[i] + sum) % 2 != 0) {
            // 无解
            return -1;
        }
        if (i - K + 1 >= 0) {
            sum -= f[i - K + 1];
        }
    }
    return res;
}
void solve() {
    int K = 1, M = N;
    for (int k = 1; k <= N; k++) {
        int m = calc(k);
        if (m >= 0 && M > m) {
            M = m;
            K = k;
        }
    }
    printf("%d %d\n", K, M);
}
int main() {
    cin >> N;
    for(int i = 0; i < N; i++) cin >> dir[i];
    solve();


思路：第一行的格子能被第一行翻转影响，也能被第二行反转影响，所以第一行要特殊处理，二进制枚举第一行所有翻转情况，之后每一行的反转就都有唯一解了。因为剩下的过程就是：用第二行翻转来保证第一行全白，用第三行翻转来保证第二行全白...... 依次类推，最后检查最后一行是否都是白色，如果是就得到一个结果，否则就无解。


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <climits>
using namespace std;
const int MAXN = 17;
// 五个方向
const int dirx[5] = {0, 1, -1, 0, 0};
const int diry[5] = {0, 0, 0, 1, -1};
int m, n; // 行数，列数
int board[MAXN][MAXN]; // 初始情况
int tra[MAXN][MAXN]; // 临时的翻转记录
int ans[MAXN][MAXN]; // 最终结果（最终的翻转记录）
// 查询 (x, y) 的颜色
int get(int x, int y){
    int c = board[x][y]; // 初始颜色
    for(int i=0; i<5; i++){
        int xi = x + dirx[i];
        int yi = y + diry[i];
        if(xi>=0 && xi<m && yi>=0 && yi<n){
            // 加上所有翻转情况
            c += tra[xi][yi];
        }
    }
    return c % 2; // 返回最后得到的颜色
}
// 求第 1 行确定的情况下的最少操作次数
// 解不存在的话返回 - 1
int dfs(){
    // 首先确定从第二行开始的翻转方法
    for(int i=1; i<m; i++){ // 遍历行
        for(int j=0; j<n; j++){ // 遍历列
            if(get(i-1, j) == 1){ // 检查上一行是否为黑色，判断是否需要翻转
                // 如果是 1，需要翻转
                tra[i][j] = 1;
            }
        }
    }
    // 然后检查最后一行是否都为白色，判断这种方法是否可行
    for(int j=0; j<n; j++){
        if(get(m-1, j) == 1) return -1; // 只要有一个是黑色，就不可行
    }
    // 能到达这里，说明该方法可行，那就统计翻转次数并返回
    int count = 0;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            count += tra[i][j];
        }
    }
    return count;
}
int main(){
    // 提高 C++ 的输入输出效率，特别是在需要大量输入输出时。
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // 输入
    cin >> m >> n;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            cin >> board[i][j];
        }
    }
    int res = -1;
    for(int i=0; i<(1<<m); i++){ // 遍历第一行所有翻转情况 (1<<m) 来表示长度为 m 的二进制数的最大取值
        memset(tra, 0, sizeof(tra));
        for(int j=0; j<n; j++){
            tra[0][j] = (i>>j) & 1; // 记录第一行的翻转结果
        }
        int cur = dfs(); // 计算当前情况的翻转次数
        if(cur >= 0 && (res == -1 || cur < res)){
            // 遇到更优解，就重新记录
            res = cur;
            memcpy(ans, tra, sizeof(tra)); // 把 tra 复制到 ans 中去
        }
    }
    if(res == -1) {cout << "IMPOSSIBLE" << endl; return 0;}
    else {
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                printf("%d%c", ans[i][j], j+1 == n ? '\n' : ' ');
            }
        }
    }
# 弹性碰撞




思路在下降过程中，多个球之间会有碰撞，以 R=0 为例子。我的理解是：因为每一个球都是一样的，并且碰撞都是弹性碰撞，产生碰撞之后，它们速度不变，只是交换了方向，我理解为它们直接相互穿过，并继续按原状态运动。当它们没有碰到地面时，都是向下运动的，又因为相邻的两个球之间下落时间间隔是一秒，所以不会存在两个球距离底端长度相等的情况。我们只需要将每一个球作为单独个体，计算 T 秒后距离地面的长度，然后将其排序，从小到大就是 0~i 到底端的距离。


#include <iostream>
#include <math.h>
using namespace std;
 
const double g=10.0;
int N = 1,H = 10,R = 10,T = 100;
double y[1];
 
 
/******************** 核心代码 ***************************/
double calc(int T)
{
	if(T<0) return H;
	double t = sqrt(2*H/g);
	int k = (int)(T/t);
	if(k%2 == 0) //k 为偶数时在下落，为奇数时在上升 
	{
		double d = T - k*t;
		return H-g*d*d/2;     // 距离底端时的距离 
	}else{
		double d = k*t+t-T;
		return H-g*d*d/2;
	}
 } 
 
void solve()
{
	for(int i=0;i<N;i++)
	{
		y[i] = calc(T-i);
	}
/********************************************************/ 
	sort(y , y+N);
	for(int i=0;i<N;i++)
	{
		printf("%.2f%c",y[i]+2*R*i/100.0,i+1 == N ? '\n':' ');  // 除以 100 是 cm 到 m 的转换 
		
	}
}
 
int main()
{
	solve(); 
	return 0;
}
# 折半枚举（双向搜索）




思路：每行分别为 a、b、c、d 的取值。将所有可能的 a 和 b 的组合进行枚举，并将其和作为一个新的数存储起来。将所有可能的 c 和 d 的组合进行枚举，并计算它们的和。使用二分查找来寻找是否有相反数，也就是 -(a+b) 是否等于 c+d，如果相等则说明有一组解


// 读入 n 行数据
for (int i = 0; i < n; i++) {
    读入 a, b, c, d;
    // 将 a+b 的和存入数组 sum1 中
    sum1.push_back(a + b);
    // 将 c+d 的和存入数组 sum2 中
    sum2.push_back(c + d);
}
// 对 sum1 和 sum2 进行排序
sort(sum1.begin(), sum1.end());
sort(sum2.begin(), sum2.end());
int count = 0;
// 遍历 sum1 中的每个元素
for (int i = 0; i < sum1.size(); i++) {
    // 在 sum2 中查找 -(sum1 [i]) 是否存在
    if (binary_search(sum2.begin(), sum2.end(), -sum1[i])) {
        // 如果存在，则表示有一组解
        count++;
    }
}
// 输出结果
输出 count;


思路：大容量背包问题的特点是物品数量很少，但物品的价值特别大，因此不能使用动态规划求解，通用的做法是枚举 + 二分，以下分步骤来描述。


#include <iostream>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int Max = 42;
typedef long long ll;
ll w[Max], v[Max];
ll N, W; 
pair<ll, ll> arr[1 << (Max / 2)];  // 重量，价值
pair<ll, ll> arr2[1 << (Max / 2)];  // 重量，价值
pair<ll, ll> temp[1 << Max / 2];
ll ans = 0;
bool cmp(pair<ll, ll>& a, pair<ll, ll>& b)
{
    return a.second < b.second;
}
// 解决大背包问题的函数
void solve()
{
    ll n = N / 2;
    // 计算第一组物品的所有可能组合的重量和价值
    for (ll i = 0; i < (1ll << n); i++)
    {
        ll now_w = 0ll, now_v = 0ll;
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)   // 对于二进制数 i，它的第 j 位是 1
            {
                now_w += w[j];
                now_v += v[j];
            }
        }
        arr[i].first = now_w;    // 记录当前组合的重量
        arr[i].second = now_v;   // 记录当前组合的价值
    }
    sort(arr, arr + (1ll << n));     // 按照价值升序排序
    ll current_min = arr[0].second;
    ll j = 0;
    for (ll i = 1; i < pow(2, n); i++)
    {
        // 去除重复状态，保留每种重量下最大的价值
        if (arr[i].second > current_min)
            arr2[j++] = arr[i];
        else
            current_min = arr[i].second;
    }
    for (ll i = 0; i < (1ll << (N - n)); i++)
    {
        ll now_w = 0, now_v = 0;
        // 计算第二组物品的所有可能组合的重量和价值
        for (ll k = 0; k < (N - n); k++)
        {
            if ((i >> k) & 1)
            {
                now_w += w[n + k];
                now_v += v[n + k];
            }
        }
        if (now_w <= W)
        {
            ll v = 0;
            // 找到符合背包容量的最佳价值组合
            for (ll s = j - 1; s >= 0; s--)
            {
                if (arr2[s].first <= W - now_w)
                {
                    for (int p = 0; p <= s; p++)
                        temp[p] = arr2[p];
                    sort(temp, temp + s + 1, cmp);
                    v = temp[s].second;
                    break;
                }
            }
            ans = max(ans, v + now_v);  // 更新最大总价值
        }
    }
}
int main()
{
    cin >> N >> W;
    for (ll i = 0; i < N; i++)
        cin >> w[i] >> v[i];
    solve();
    cout << ans << endl;
    return 0;
}
# 坐标离散化




思路：因为 w*h 的值太大，考虑离散化压缩 w 和 h 的值，建立新的棋盘。然后 BFS 求连通分量数即可


#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 505
using namespace std;
int w, h, n; // 网格宽度、高度，矩形数量
int x1[maxn], y1[maxn], x2[maxn], y2[maxn]; // 每个矩形的左上角和右下角坐标
int dx[] = {0, 0, -1, 1}; // 四连块 x 方向坐标变化
int dy[] = {1, -1, 0, 0}; // 四连块 y 方向坐标变化
bool fld[maxn * 6][maxn * 6]; // 标记数组，表示每个位置是否被访问过
struct zb {
    int x, y; // BFS 时用结构体存储点的坐标
};
zb q[9000000]; // 手工队列，用于 BFS
void init() {
    scanf("%d%d%d", &w, &h, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
    }
}
// 坐标离散化函数
int lisan(int *x1, int *x2, int w) {
    vector<int> xs;
    vector<int>::iterator it;
    for (int i = 0; i < n; i++) {
        for (int d = -1; d <= 1; d++) {
            if (x1[i] + d >= 1 && x1[i] + d <= w)
                xs.push_back(x1[i] + d);
            if (x2[i] + d >= 1 && x2[i] + d <= w)
                xs.push_back(x2[i] + d);
        }
    }
    sort(xs.begin(), xs.end());
    it = unique(xs.begin(), xs.end());// 对 xs 进行排序，然后利用 unique 函数将重复的元素移到向量末尾，并返回指向第一个重复元素的迭代器。
    xs.erase(it, xs.end());// 将重复的元素从向量中删除
    // 线性查找（find 函数）找到每个矩形左上角和右下角坐标在 xs 中的位置，并将其更新为新的坐标值
    for (int i = 0; i < n; i++) {
        x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
        x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
    }
    return xs.size();
}
// 广度优先搜索函数
void BFS(int x, int y) {
    q[rear++] = (zb){x, y};
    fld[x][y] = 1;
    
    while (front != rear) {
        zb s = q[front++];
        
        for (int i = 0; i < 4; i++) {
            int tx = s.x + dx[i], ty = s.y + dy[i];
            
            if (tx < 0 || tx >= w || ty < 0 || ty >= h) continue;
            if (fld[tx][ty]) continue;
            
            q[rear++] = (zb){tx, ty};
            fld[tx][ty] = 1;
        }
    }
}
void solve() {
    w = lisan(x1, x2, w);
    h = lisan(y1, y2, h);
    memset(fld, 0, sizeof(fld));
    for (int i = 0; i < n; i++) {
        for (int x = x1[i]; x <= x2[i]; x++) {
            for (int y = y1[i]; y <= y2[i]; y++) {
                fld[x][y] = 1;
            }
        }
    }
    int ans = 0;
    for (int x = 0; x < w; x++) {
        for (int y = 0; y < h; y++) {
            if (!fld[x][y]) {
                BFS(x, y);
                ans++;
            }
        }
    }
    printf("%d\n", ans);
}
int main() {
    init();
    solve();
    
    return 0;
}
# 数据结构


# 线段树


线段树（Segment Tree）是一种常用的数据结构，用于高效地处理区间查询问题。它主要用于解决静态或动态数组上的各种区间操作，比如区间最值查询、区间和查询、区间更新等。


线段树的基本概念


线段树的核心思想是将一个区间划分成多个子区间，并递归地构建一棵树来表示这些子区间。每个节点代表一个区间，并存储该区间的信息。例如，对于一个包含 N 个元素的数组，线段树可以看作是一棵满二叉树，其中树的每个叶子节点表示数组的一个元素，而非叶子节点表示若干元素的区间。


线段树的构建


线段树的构建过程可以通过自底向上的方式进行，即从叶子节点开始，逐层向上计算父节点的信息。具体步骤如下：


    

  1. 如果当前节点表示的区间只包含一个元素，则将该元素的值存储在节点中，并返回。
    2. 

  2. 否则，将当前区间分成两个子区间，分别构建左子树和右子树。
    3. 

  3. 计算左子树和右子树的信息，如区间和、区间最大值等，并将结果保存在当前节点中。
    4. 

  4. 返回当前节点的信息。
    5. 



线段树的查询


线段树的查询操作主要用于获取指定区间的信息。查询的过程可以通过递归实现，具体步骤如下：


    

  1. 如果当前节点表示的区间与目标区间完全不重叠，则返回一个表示 "无效" 的值。
    2. 

  2. 如果当前节点表示的区间完全包含在目标区间内，则直接返回当前节点存储的信息。
    3. 

  3. 否则，将查询范围分成两部分，分别递归查询左子树和右子树，并将结果合并。
    4. 



线段树的更新


线段树的更新操作用于修改某个位置上的元素值，或者修改某个区间上的所有元素值。更新操作的过程可以通过递归实现，具体步骤如下：


    

  1. 如果当前节点表示的区间与目标区间完全不重叠，则不进行任何修改。
    2. 

  2. 如果当前节点表示的区间完全包含在目标区间内，则更新当前节点存储的信息。
    3. 

  3. 否则，将更新范围分成两部分，分别递归更新左子树和右子树，并更新当前节点的信息。
    4. 



线段树的时间复杂度


线段树的时间复杂度为 O (logN)，其中 N 为数组的大小。线段树在处理区间操作问题时，具有较高的效率和灵活性，因此被广泛应用于各种算法和数据结构中。


#include <iostream>
#include <vector>
#include <climits>
using namespace std;
class SegmentTree {
private:
    vector<int> st; // 线段树数组
    int n; // 数组大小
    // 获取左子节点
    int left(int p) { return p << 1; }
    // 获取右子节点
    int right(int p) { return (p << 1) + 1; }
    // 构建线段树
    void build(int p, int L, int R, vector<int>& A) {
        if (L == R)
            st[p] = A[L]; // 叶子节点存储原始数组的值
        else {
            build(left(p), L, (L + R) / 2, A); // 递归构建左子树
            build(right(p), (L + R) / 2 + 1, R, A); // 递归构建右子树
            int p1 = st[left(p)], p2 = st[right(p)];
            st[p] = (p1 <= p2) ? p1 : p2; // 内部节点存储左右子节点的最小值
        }
    }
    // 区间最小值查询
    int rmq(int p, int L, int R, int i, int j) {
        //INT_MAX 是 C++ 中 <climits> 头文件中定义的一个常量，表示 int 类型的最大值
        if (i > R || j < L) return INT_MAX; // 查询范围和当前区间不相交
        if (L >= i && R <= j) return st[p]; // 当前区间完全包含在查询范围内
        // 递归查询左右子树
        int p1 = rmq(left(p), L, (L + R) / 2, i, j);
        int p2 = rmq(right(p), (L + R) / 2 + 1, R, i, j);
        if (p1 == INT_MAX) return p2; // 左子树为空，返回右子树的结果
        if (p2 == INT_MAX) return p1; // 右子树为空，返回左子树的结果
        return (p1 <= p2) ? p1 : p2; // 返回左右子树的最小值
    }
public:
    // 构造函数
    SegmentTree(vector<int>& A) {
        n = A.size();
        st.assign(4 * n, 0); // 初始化线段树数组
        build(1, 0, n - 1, A); // 构建线段树
    }
    // 对外接口，区间最小值查询
    int rmq(int i, int j) {
        return rmq(1, 0, n - 1, i, j);
    }
};
int main() {
    vector<int> arr = {18, 17, 13, 19, 15, 11, 20};
    SegmentTree st(arr);
    cout << "RMQ(1, 3): " << st.rmq(1, 3) << endl; // 输出 RMQ (1, 3): 13
    cout << "RMQ(2, 5): " << st.rmq(2, 5) << endl; // 输出 RMQ (2, 5): 11
    return 0;
}


思路：线段树，每个节点表示一段连续的线段集合，维护下面两个值


1、节点相对它起点的偏移 节点相对于它终点偏移的 y


2、两个儿子相连后，右儿子需要旋转的角度


#include <iostream>
#include <math.h>
using namespace std;
const int ST_SIZE = (1 << 15) - 1;
int N, C;
int L[10005];
int S[360], A[360];
// 线段树维护的数据
double vx[ST_SIZE], vy[ST_SIZE];// 各节点的向量
double ang[ST_SIZE]; // 各节点的角度
// 为了查询角度的变化而保存的当前角度的数组
double prv[10005];
// 初始化线段树
//k 是节点的编号，l，r 表示当前节点对应的是【l，r】区间
void init(int k, int l, int r) {
    ang[k] = vx[k] = 0.0;
    if (r - 1 == 1) {
        // 叶子节点
        vy[k] = L[l];
    } else {
        // 非叶子节点
        int chl = k * 2 + 1, chr = k * 2 + 2;
        init(chl, l, (1 + r) / 2);
        init(chr, (1 + r) / 2, r);
        vy[k] = vy[chl] + vy[chr];
    }
}
// 把 s 和 s+1 的角度变为 a
//v 是节点的编号，1，r 表示当前节点对应的是【l，r】区间
void change(int s, double a, int v, int l, int r) {
    if (s <= 1) return;
    else if (s < r) {
        int chl = v * 2 + 1, chr = v * 2 + 2;
        int m = (1 + r) / 2;
        change(s, a, chl, l, m);
        change(s, a, chr, m, r);
        if (s <= m) ang[v] += a;
        double s = sin(ang[v]), c = cos(ang[v]);
        vx[v] = vx[chl] + (c * vx[chr] - s * vy[chr]);
        vy[v] = vy[chl] + (s * vy[chr] + c * vy[chr]);
    }
}
void solve() {
    init(0, 0, N);
    for (int i = 1; i < N; i++) prv[i] = M_PI;
    for (int i = 0; i < C; i++) {
        int s = S[i];
        double a = A[i] / 360.0 * M_PI;// 把角度转为弧度
        change(s, a - prv[s], 0, 0, N);
        prv[s] = a;
        printf("%.2f %.2f\n",vx[0],vy[0]);
    }
}
int main() {
    cin >> N >> C;
    for (int i = 0; i < N; i++) cin >> L[i];
    for (int i = 0; i < C; i++) cin >> S[i];
    for (int i = 0; i < C; i++) cin >> A[i];
    solve();
}

      

          
          
      

  


   


    

  
    
      
    
    更新于