今天也是离散化题目

https://www.luogu.com.cn/problem/P1496


# 火烧赤壁
## 题目背景
曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
## 题目描述
给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。
## 输入格式
第一行一个整数，表示起火的信息条数 $n$。  
接下来 $n$ 行，每行两个整数 $a, b$，表示一个着火位置的起点和终点（**注意：左闭右开**）。
## 输出格式
输出一行一个整数表示答案。
## 样例 #1
### 样例输入 #1
```
3
-1 1
5 11
2 9
```
### 样例输出 #1
```
11
```
## 提示
### 数据规模与约定
对于全部的测试点，保证 $1 \leq n \leq 2 \times 10^4$，$-2^{31} \leq a <  b \lt 2^{31}$，且答案小于 $2^{31}$。


```cpp
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 200001; // 最大区间数量
const int MAX_POINTS = 400002; // 最大端点数量（每个区间两个端点，乘以2）

int n;
int intervals[MAX_N][2]; // 存储区间
int points[MAX_POINTS]; // 存储所有端点
int cover_count[MAX_POINTS]; // 记录每个端点的覆盖次数

int main() {
    cin >> n;

    int point_count = 0;

    // 读取区间并提取端点
    for (int i = 0; i < n; i++) {
        cin >> intervals[i][0] >> intervals[i][1];
        points[point_count++] = intervals[i][0];
        points[point_count++] = intervals[i][1];
    }

    // 排序并去重
    sort(points, points + point_count);
    int unique_count = unique(points, points + point_count) - points;

    // 离散化并记录覆盖次数
    for (int i = 0; i < n; i++) {
        int start = lower_bound(points, points + unique_count, intervals[i][0]) - points;
        int end = lower_bound(points, points + unique_count, intervals[i][1]) - points;
        cover_count[start]++;
        cover_count[end]--;
    }

    // 计算覆盖长度
    int current_count = 0;
    int total_length = 0;
    for (int i = 0; i < unique_count - 1; i++) {
        current_count += cover_count[i];
        if (current_count > 0) {
            total_length += points[i + 1] - points[i];
        }
    }

    cout << total_length << endl;

    return 0;
}

```



9.20算法题

今天做离散基础题

https://www.acwing.com/problem/content/105/

离散指的应该就是hash了


```cpp
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 200001; // 科学家的最大数量
const int MAX_M = 200001; // 电影的最大数量

int n, m;
int lang[MAX_N]; // 科学家懂得的语言
int voice[MAX_M], sub[MAX_M]; // 电影的语音和字幕语言
int unique_langs[MAX_N + 2 * MAX_M]; // 所有出现的语言编号
int lang_count[MAX_N + 2 * MAX_M]; // 统计每种语言有多少科学家懂得

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> lang[i];
        unique_langs[i] = lang[i];
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> voice[i];
        unique_langs[n + i] = voice[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> sub[i];
        unique_langs[n + m + i] = sub[i];
    }

    // 离散化语言编号
    sort(unique_langs, unique_langs + n + 2 * m);
    int unique_count = unique(unique_langs, unique_langs + n + 2 * m) - unique_langs;

    // 统计每种语言有多少科学家懂得
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(unique_langs, unique_langs + unique_count, lang[i]) - unique_langs;
        lang_count[idx]++;
    }

    // 计算每部电影能让多少科学家开心和比较开心
    int max_happy = -1;
    int max_happy_idx = -1;
    int max_comp_happy = -1;

    for (int i = 0; i < m; i++) {
        int voice_idx = lower_bound(unique_langs, unique_langs + unique_count, voice[i]) - unique_langs;
        int sub_idx = lower_bound(unique_langs, unique_langs + unique_count, sub[i]) - unique_langs;
        int happy = lang_count[voice_idx];
        int comp_happy = lang_count[sub_idx];

        if (happy > max_happy || (happy == max_happy && comp_happy > max_comp_happy)) {
            max_happy = happy;
            max_happy_idx = i;
            max_comp_happy = comp_happy;
        }
    }

    // 输出最终选择的电影编号
    cout << max_happy_idx + 1 << endl;

    return 0;
}
```

9.19算法题

普及二分https://www.luogu.com.cn/problem/B3627



# 立方根

## 题目描述

给定正整数 $n$，求 $\sqrt[3]{n}$。答案向下取整。

## 输入格式

仅一行，一个正整数 $n$。

## 输出格式

仅一行，一个正整数，表示 $\sqrt[3]n$。向下取整输出。

## 样例 #1

### 样例输入 #1

```
27
```

### 样例输出 #1

```
3
```

## 样例 #2

### 样例输入 #2

```
100000
```

### 样例输出 #2

```
46
```

## 样例 #3

### 样例输入 #3

```
1000000000000000
```

### 样例输出 #3

```
100000
```

## 提示

对于 $100\%$ 的数据，有 $n\leq 10^{15}$。



```c

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);

    long long left = 0, right = n;
    long long result = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        long long mid_cubed = mid * mid * mid;

        if (mid_cubed <= n) {
            result = mid; // 记录当前的 mid 值
            left = mid + 1; // 尝试更大的值
        } else {
            right = mid - 1; // 尝试更小的值
        }
    }

    printf("%lld\n", result);

    return 0;
}

```



库函数
```c
#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    scanf("%lld", &n);

    long long result = cbrt(n);
    printf("%lld\n", result);

    return 0;
}
```

9.22普及算法

2014.12阅读精读

## 1.なんといっても

「なんといっても」は、「どんなことを言っても」「どう考えても」という意味で、主に強調や断定を表す表現です。以下に5つの例文を示します。

1. **なんといっても、彼は優秀な選手だ。**  
   (どんなことを言っても、彼は優秀な選手だ。)  
   （无论如何，他都是一个优秀的选手。）

2. **なんといっても、健康が一番だ。**  
   (どんなことを言っても、健康が一番だ。)  
   （无论如何，健康都是最重要的。）

3. **なんといっても、彼女の料理は美味しい。**  
   (どんなことを言っても、彼女の料理は美味しい。)  
   （无论如何，她的料理都非常美味。）

4. **なんといっても、この映画は面白かった。**  
   (どんなことを言っても、この映画は面白かった。)  
   （无论如何，这部电影都非常有趣。）

5. **なんといっても、彼の努力は認めるべきだ。**  
   (どんなことを言っても、彼の努力は認めるべきだ。)  
   （无论如何，他的努力都值得认可。）

この表現は、ある事柄に対して強い確信や断定的な意見を表現する際によく使われます。


## 2.何とも…ない
「何とも…ない」は、「特に感じない」「特に言うことはない」という意味で、主に何かに対する感想や評価がないことを表す表現です。以下に5つの例文を示します。

1. **この映画は何とも言えない。**  
   (この映画は特に感じない。)  
   （这部电影没什么特别的感受。）

2. **彼の言葉は何とも思わなかった。**  
   (彼の言葉は特に感じなかった。)  
   （他的话我没什么特别的感觉。）

3. **この料理は何とも美味しくない。**  
   (この料理は特に美味しくない。)  
   （这道菜没什么特别的美味。）

4. **彼の態度は何とも気にならなかった。**  
   (彼の態度は特に気にならなかった。)  
   （他的态度我没什么特别在意。）

5. **この本は何とも面白くない。**  
   (この本は特に面白くない。)  
   （这本书没什么特别的趣味。）

この表現は、何かに対して特に感想や評価がないことを表現する際によく使われます。

## 3.何とかして
「何とかして」は、「どうにかして」「必ずしも簡単ではないが、努力して」という意味で、主に困難な状況を克服しようとする意志や決意を表す表現です。以下に5つの例文を示します。

1. **何とかして、この仕事を完成させたい。**  
   (どうにかして、この仕事を完成させたい。)  
   （无论如何，我都想完成这项工作。）

2. **何とかして、彼女との関係を修復したい。**  
   (どうにかして、彼女との関係を修復したい。)  
   （无论如何，我都想修复与她的关系。）

3. **何とかして、この試験に合格したい。**  
   (どうにかして、この試験に合格したい。)  
   （无论如何，我都想通过这次考试。）

4. **何とかして、この問題を解決したい。**  
   (どうにかして、この問題を解決したい。)  
   （无论如何，我都想解决这个问题。）

5. **何とかして、彼の気持ちを理解したい。**  
   (どうにかして、彼の気持ちを理解したい。)  
   （无论如何，我都想理解他的心情。）

この表現は、困難な状況に直面しているが、それを克服しようとする強い意志や決意を表現する際によく使われます。


## 4.いずれにしても
「いずれにしても」は、「どちらにせよ」「どういう結果になっても」という意味で、主にどんな状況でも同じ結論や行動を取ることを表す表現です。以下に5つの例文を示します。

1. **いずれにしても、明日は早く起きなければならない。**  
   (どちらにせよ、明日は早く起きなければならない。)  
   （无论如何，明天都必须早起。）

2. **いずれにしても、彼は来週の会議に出席するだろう。**  
   (どちらにせよ、彼は来週の会議に出席するだろう。)  
   （无论如何，他都会出席下周的会议吧。）

3. **いずれにしても、この計画は変更される可能性がある。**  
   (どちらにせよ、この計画は変更される可能性がある。)  
   （无论如何，这个计划都有可能被修改。）

4. **いずれにしても、私は彼の意見を尊重するつもりだ。**  
   (どちらにせよ、私は彼の意見を尊重するつもりだ。)  
   （无论如何，我都打算尊重他的意见。）

5. **いずれにしても、この問題は解決しなければならない。**  
   (どちらにせよ、この問題は解決しなければならない。)  
   （无论如何，这个问题都必须解决。）

この表現は、どんな状況でも同じ結論や行動を取ることを表現する際によく使われます。

## 5.ものと思われる

「ものと思われる」は、「そう考えられる」「そう思われる」という意味で、主に推測や推論を表す表現です。以下に5つの例文を示します。

1. **彼が遅刻した理由は、交通渋滞だったものと思われる。**  
   (彼が遅刻した理由は、交通渋滞だったと考えられる。)  
   （他迟到的原因，应该是交通堵塞。）

2. **この事件は内部告発によるものと思われる。**  
   (この事件は内部告発によると考えられる。)  
   （这起事件，应该是由内部告发引起的。）

3. **彼女は今回のプロジェクトに成功したものと思われる。**  
   (彼女は今回のプロジェクトに成功したと考えられる。)  
   （她这次的项目，应该是成功了。）

4. **この製品は人気があるものと思われる。**  
   (この製品は人気があると考えられる。)  
   （这款产品，应该是很受欢迎的。）

5. **彼は無実だったものと思われる。**  
   (彼は無実だったと考えられる。)  
   （他应该是无辜的。）

この表現は、何かについての推測や推論を表現する際によく使われます。


立方

短篇1

1.なんといっても