今天做离散基础题

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.なんといっても

短篇1