离散化

802. 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
const int N = 3e5;
using namespace std;
typedef pair<int, int> PII;
int a[N];
vector<PII>add,query;
vector<int>alls;
int find(int x){
    int l = 0;
    int r = alls.size()-1;
    while(l<r){
        int mid = l+r>>1;
        if(alls[mid]==x){
            return mid+1;
        }else if(alls[mid]>x){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    return r+1;
}
// find函数也可以下面这种写法
int find(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        int x,c;
        cin >> x >> c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++ ){
        int l,r;
        cin >> l >> r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    // 处理插入
    for(auto item:add){
        int x = find(item.x);
        a[x]+=item.y;
    }
    // 预处理前缀和
    for (int i = 2; i <= alls.size(); i ++ ){
        a[i]+=a[i-1];
    }
    // 处理查询
    for(auto item:query){
        int l = find(item.x);
        int r = find(item.y);
        cout << a[r] - a[l-1]<<endl;
    }
}

并查集

836. 合并集合

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int p[N];
int find(int x){
    if(p[x]!=x){
        p[x] = find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
    }
    while (m -- ){
        string t;
        int a,b;
        cin >> t >> a >> b;
        int fa = find(a);
        int fb = find(b);
        if(t[0]=='M'){
            p[fa] = fb;
        }else{
            if(fa==fb){
                puts("Yes");
            }else{
                puts("No");
            }
        }
    }
}

837. 连通块中点的数量

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int p[N],sz[N];
int find(int x){
    if(p[x]!=x){
        p[x] = find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        sz[i] = 1;
    }
    while (m -- ){
        string t;
        int a,b;
        cin >> t;
        if(t[0]=='C'){
            cin >> a >> b;
            int fa = find(a);
            int fb = find(b);
            if(fa==fb){
                continue; // 这点很重要，如果两个点已经在一个集合中了就不需要合并了
            }
            sz[fb]+=sz[fa];
            p[fa] = fb;
        }else if(t[1]=='1'){
            cin >> a >> b;
            int fa = find(a);
            int fb = find(b);
            if(fa==fb){
                puts("Yes");
            }else{
                puts("No");
            }
        }else{
            cin >> a;
            cout << sz[find(a)]<<endl;
        }
    }
}

240. 食物链

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。
A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1∼N 编号。
每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 X 和 Y 是同类。
第二种说法是 2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
当前的话与前面的某些真的话冲突，就是假话；
当前的话中 X 或 Y 比 N 大，就是假话；
当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。
输出格式
只有一个整数，表示假话的数目。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int p[N],d[N];
int find(int x)  // 并查集
{
    if(p[x]!=x){
        int t = find(p[x]);
        d[x]+=d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
    }
    int res=0;
    while (m -- ){
        int t,x,y;
        cin >> t >> x >> y;
        if(x>n||y>n){
            res++;
            continue;
        }
        int px = find(x);
        int py = find(y);
        if(t==1){ //同类
            if(px==py&&(d[x]-d[y])%3){ // 查出来已经在集合中，但是不是同类
                res++;
            }else if(px!=py){ // 目前没说过这句话以及和这句话矛盾的话
                p[px] = py;
                d[px] = d[y]-d[x];
            }
        }else{ // x吃y
            if(px==py&&(d[y]-d[x]-1)%3){
                res++;
            }else if(px!=py){
                p[px] = py;
                d[px] = d[y]-d[x]-1;
            }
        }
    }
    cout << res;
}

1242. 修改数组

给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。
小明会依次修改 A2,A3,⋅⋅⋅,AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1∼Ai−1 中出现过。
如果出现过，则小明会给 Ai 加上 1；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1，直到 Ai 没有在 A1∼Ai−1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。
输出格式
输出 N 个整数，依次是最终的 A1,A2,⋅⋅⋅,AN。
输入样例：
5
2 1 1 3 4
输出样例：
2 1 3 4 5

#include <cstdio>
const int N = 1100010;
int p[N];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i < N; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        x = find(x);
        printf("%d ", x);
        p[x] = x + 1;
    }
    return 0;
}

1171. 距离

给出 n 个点的一棵树，多次询问两点之间的最短距离。
注意：
边是无向的。
所有节点的编号是 1,2,…,n。
输入格式
第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；
下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；
再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行，对于每次询问，输出一行询问结果。
输入样例1：
2 2
1 2 100
1 2
2 1
输出样例1：
100
100
输入样例2：
3 2
1 2 10
3 1 15
1 2
3 2
输出样例2：
10
25

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];//每个点和1号点的距离
int p[N];
int res[M];
int st[N];
vector<PII> query[N];//把询问存下来   
// query[i][first][second] first存查询距离i的另外一个点j，second存查询编号idx
void add(int a,int b,int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}
int find(int x)
{
    if(p[x]!=x)p[x] = find(p[x]);
    return p[x];
}
void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa) continue;
        dist[j] = dist[u]+w[i];
        dfs(j,u);
    }
}
// 利用并查集求最近公共祖先
void tarjan(int u)
{
    st[u]=1;//当前路径点标记为1
    // u这条路上的根节点的左下的点用并查集合并到根节点
    for(int i = h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            tarjan(j);//往左下搜
            p[j] = u;//从左下回溯后把左下的点合并到根节点
        }
    }
    // 对于当前点u 搜索所有和u
    for(auto item:query[u])
    {
        int y = item.first,id = item.second;
        if(st[y]==2)//如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2)
        {
            int anc = find(y);//y的根节点
            // x到y的距离 = d[x]+d[y] - 2*d[lca] 
            res[id] = dist[u]+dist[y] - dist[anc]*2;//第idx次查询的结果 res[idx]
        }
    }
    //点u已经搜索完且要回溯了 就把st[u]标记为2 
    st[u] = 2;
}
int main()
{
    cin >> n >> m;
    // 建图
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
    }
    // 存下询问
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;
        if(a!=b)
        {
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }
    for(int i=1;i<=n;i++)p[i] = i;
    dfs(1,-1);
    tarjan(1);
    for(int i=0;i<m;i++)cout << res[i] << '\n';//把每次询问的答案输出
    return 0;
}

Trie

835. Trie字符串统计

维护一个字符串集合，支持两种操作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4+10;
int tr[N][26],idx;
int cnt[N];
void insert(string s){
    int p=0;
    for (int i = 0; i < s.size(); i ++ ){
        int u = s[i]-'a';
        if(!tr[p][u]){
            tr[p][u]=++idx;
        }
        p = tr[p][u];
    }
    cnt[p]++;
}
int query(string s){
    int p=0;
    for (int i = 0; i < s.size(); i ++ ){
        int u = s[i]-'a';
        if(!tr[p][u]){
            return 0;
        }
        p = tr[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    string t,s;
    cin >> n;
    while (n -- ){
        cin >> t >> s;
        if(t=="I"){
            insert(s);
        }else{
            cout << query(s)<<endl;
        }
    }
}

143. 最大异或对

在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
输入样例：
3
1 2 3

下面trie枚举的时候必须从最高位开始枚举
因为要使得异或起来最大，就得使得最高位优先选择不同的
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 1e5+10;
typedef long long LL;
using namespace std;
LL a[N];
int n;
int son[3100010][2], idx;
LL res;
void insert(int x)  // 插入字符串
{
    int p = 0;
    for (int i = 31; i>=0; i -- )
    {
        int u = (x>>i)&1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}
void query(int x)  // 查询字符串出现次数
{
    int p = 0;
    LL t=0;
    for (int i = 31; i>=0; i -- )
    {
        int u = x>>i&1;
        if(son[p][!u]){
            p = son[p][!u];
            t |= (1<<i);
        }else if(son[p][u]){
            p = son[p][u];
        }else{
            return ;
        }
    }
    res = max(res,t);
    return ;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i];
        insert(a[i]);
    }
    for (int i = 0; i < n; i ++ ){
        query(a[i]);
    }
    cout << res;
}

记忆化搜索

901. 滑雪

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int g[N][N];
int d[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int m,n;
int ans;
int dfs(int x,int y){
    if(d[x][y]){
        return d[x][y];
    }
    for (int i = 0; i < 4; i ++ ){
        int tx = x+dx[i];
        int ty = y+dy[i];
        if(tx<0||tx>=m||ty<0||ty>=n){
            continue;
        }
        if(g[tx][ty]>=g[x][y]){
            continue;
        }
        dfs(tx,ty);
        d[x][y] = max(d[x][y],d[tx][ty]); 
    }
    d[x][y]+=1;
}
int main()
{
    cin >> m >> n;
    for (int i = 0; i < m; i ++ ){
        for (int j = 0; j < n; j ++ ){
            cin >> g[i][j];
        }
    }
    for (int i = 0; i < m; i ++ ){
        for (int j = 0; j < n; j ++ ){
            dfs(i,j);
            ans = max(ans,d[i][j]);
        }
    }
    cout << ans;
}

哈希

字符串哈希

这个经验值一般不会冲突

841. 字符串哈希

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

#include <iostream>
#include <cstring>
#include <algorithm>
typedef unsigned long long ULL;
using namespace std;
const int N = 1e5+10;
int P = 131;
ULL h[N], p[N];
string str;
ULL get(int l, int r)  // 计算子串 str[l ~ r] 的哈希值
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
    int n,m;
    cin >> n >> m;
    cin >> str;
    str = " "+str;
    p[0] = 1;
    // 哈希
    for (int i = 1; i <= n; i ++ ){
        h[i] = h[i-1]*P + str[i];
        p[i] = p[i-1]*P;
    }
    while (m -- ){
        int l1,r1,l2,r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(get(l1,r1)==get(l2,r2)){
            cout << "Yes"<<endl;
        }else{
            cout << "No" <<endl;
        }
    }
}

贪心

114. 国王游戏

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。
首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。
然后，让这 n 位大臣排成一排，国王站在队伍的最前面。
排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是:
排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。
注意，国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n;
PII p[N];
vector<int> mul(vector<int>a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}
vector<int> div(vector<int>a, int b)
{
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i -- )
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x)
        {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}
vector<int> max_vec(vector<int> a, vector<int> b)
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;
    return b;
}
int main()
{
    cin >> n;
    for (int i = 0; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        p[i] = {a * b, a};
    }
    sort(p + 1, p + n + 1);
    vector<int> product(1, 1);
    vector<int> res(1, 0);
    for (int i = 0; i <= n; i ++ )
    {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }
    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    cout << endl;
    return 0;
}

1. 国王游戏

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。
首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。
然后，让这 n 位大臣排成一排，国王站在队伍的最前面。
排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是:
排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。
注意，国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

125. 耍杂技的牛

农民约翰的 N 头奶牛（编号为 1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数 N，表示奶牛数量。
接下来 N 行，每行输入两个整数，表示牛的重量和强壮程度，第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。
输出格式
输出一个整数，表示最大风险值的最小可能值。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4;
int n;
struct Node{
    int w,s,sum;
    bool operator<(const Node t)const{
        return sum<t.sum;
    }
}g[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        int w,s;
        cin >> w >> s;
        g[i] = {w,s,w+s};    
    }
    sort(g,g+n);
    int sum=g[0].w;
    int res=-g[0].s;
    for (int i = 1; i < n; i ++ ){
        res = max(res,sum-g[i].s);
        sum+=g[i].w;
    }
    cout << res;
}

905. 区间选点

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。

908. 最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。

// 只要枚举最小的右边的位置即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int, int> PII;
vector<PII>g;
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int l,r;
        cin >> l >> r;
        g.push_back({l,r});
    }
    sort(g.begin(),g.end());
    int r=g[0].y;
    int res = 0;
    for (int i = 1; i < n; i ++ ){
        if(g[i].x>r){
            res++;
            r = g[i].y;
        }else{
            r = min(r,g[i].y);
        }
    }
    res++;
    cout << res;
}

906. 区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int, int> PII;
vector<PII>g;
struct Node{
    int r;
    bool operator<(const Node t)const{
        return r>t.r;
    }
};
priority_queue<Node>q;
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int l,r;
        cin >> l >> r;
        g.push_back({l,r});
    }
    sort(g.begin(),g.end());
    q.push({g[0].y});
    int res=1;
    for (int i = 1; i <n; i ++ ){
        if(q.top().r<g[i].x){
            q.pop();
            q.push({g[i].y});
        }else{
            res++;
            q.push({g[i].y});
        }
    }
    cout << res;
}

907. 区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。
第二行包含整数 N，表示给定区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出 −1。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int, int> PII;
vector<PII>g;
int st[N];
int main()
{
    int s,t;
    cin >> s >> t;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int l,r;
        cin >> l >> r;
        g.push_back({l,r});
    }
    sort(g.begin(),g.end());
    int res=0;
    int s1=s,s2=s; // 从s1开始匹配，能匹配到的最远点为s2
    for (int i = 0; i < n && s2<t; i ++ ){
        if(g[i].x<=s1){ // 
            s2 = max(s2,g[i].y);
        }else{     // 当前点已经不含该s1,那么就应该从s2开始匹配了
            res++;
            st[i]++; // 所以还要从当前这个i继续从s2开始匹配，所以i--,
            // 当如果下次这个点超过了s2，那么就无法全部覆盖了
            if(st[i]>1){
                cout << -1<<endl;
                return 0;
            }
            s1 = s2;
            i--;
        }
    }
    if(s2>=t){ // 最后一步要加上
        res++; 
        cout << res;   
    }else{
        cout << -1 <<endl;
    }
}

803. 区间合并

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5;
PII g[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> g[i].x >> g[i].y;
    }
    sort(g,g+n);
    int r = g[0].y;
    int res = 0;
    for (int i = 1; i < n; i ++ ){
        if(g[i].x<=r){
            r = max(r,g[i].y);
        }else{
            r = g[i].y;
            res++;
        }
    }
    res++;
    cout << res;
}

1235. 付账问题

几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有 n 个人出去吃饭，他们总共消费了 S 元。
其中第 i 个人带了 ai 元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e5 + 10;
int n;
int a[N];
int main() {
    long double s;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a + n);
    long double res = 0, avg = s / n;
    for (int i = 0; i < n; i++) {
        double cur = s / (n - i);
        if (a[i] < cur) cur = a[i];
        res += (cur - avg) * (cur - avg);
        s -= cur;
    }
    printf("%.4Lf", sqrt(res / n));  //为了避免丢失精度，到最后再除n
}

归并

787. 归并排序

给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e5+10;
int a[N],t[N];
void merge_sort(int l,int r){
    if(l>=r){
        return;
    }
    int mid = (l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(a[i]<a[j]){
            t[k++] = a[i++];
        }else{
            t[k++] = a[j++];
        }
    }
    while(i<=mid){
        t[k++] = a[i++];
    }
    while(j<=r){
        t[k++] = a[j++];
    }
    for(int i=l,j=0; i<=r; i++,j++){
        a[i] = t[j];
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i];
    }
    merge_sort(0,n-1);
    for (int i = 0; i < n; i ++ ){
        cout << a[i]<<" ";
    }
}

788. 逆序对的数量

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int N = 1e5+10;
int n;
int a[N],t[N];
LL merge_sort(int l,int r){
    if(l>=r){
        return 0;
    }
    int mid = (l+r)/2;
    LL res=0;
    res += merge_sort(l,mid);
    res += merge_sort(mid+1,r);
    // 计算res
    int i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            res += mid-i+1;
            j++;
        }else{
            i++;
        }
    }
    // 归并排序
    i = l,j=mid+1;
    int k=0;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[k++] = a[j++];
        }else{
            t[k++] = a[i++];
        }
    }
    while(i<=mid){
        t[k++] = a[i++];
    }
    while(j<=r){
        t[k++] = a[j++];
    }
    for (int i = l,k=0; i <= r; i ++,k++ ){
        a[i] = t[k];
    }
    return res;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i];
    }
    cout << merge_sort(0,n-1);
}