做法：数组模拟堆的五个操作

1. 插入
2. 最小值
3. 删除最小值
4. 删除任意元素
5. 修改任意元素

题目描述

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式
第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], Size;

void down(int u)
{
    int t = u;      // t存三个节点中值h[]最小的节点编号
    //存在左儿子 && 左儿子的值< 该节点的值，
    if(u * 2 <= Size && h[u * 2] < h[t]) t = u *2; 
    if(u * 2 + 1 <= Size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t)
    {
        swap(h[u], h[t]); //交换两个节点的值；
        down(t);
    }
}

void up(int u)
{
    while(u /2 && h[u / 2] > h[u])
    {
        swap(h[u/2], h[u]);
        u = u /2;
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i  = 1; i <= n; i++) scanf("%d", &h[i]);
    Size = n;

    for(int i = n / 2; i; i--) down(i);     //down前半部分，时间复杂度是o(n)

    while( m -- )
    {
        printf("%d ", h[1]);    //把堆顶元素等于1
        h[1] = h[Size];
        Size --;
        down(1);
    }

}

思路：并查集

用集合表示连通块，统计集合中点的数量。

当把两个连通块连接时，== 把两个集合合并 == size_祖宗 += size_新儿子  &&  find(新儿子) = find(祖宗)。

题目描述：连通块中点的数量,

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：
1.C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2.Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3.Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为C a b，Q1 a b 或 Q2 a中的一种。

输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3

C++ 并查集

//用集合表示连通块，统计集合中点的数量
//当把两个连通块连接时，== 把两个集合合并
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, m;
char op[4];
int p[N], Size[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);    //当前节点x不是根节点，返回find（父节点）的p[]
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    //initial
    for(int i = 1; i <= n; i++)
    {
        p[i] = i;
        Size[i] = 1;
    }

    while(m--)
    {
        int a, b;

        scanf("%s", op);

        if(op[0] == 'C')
        {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) continue;    //注意特判是否已经在一个联通中

            Size[find(b)] += Size[find(a)]; //先加size
            p[find(a)] = p[find(b)];   //a归到b类，a认b为父

        }
        else if(op[1] == '1')
        {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else{
            scanf("%d", &a);
            printf("%d\n", Size[find(a)]);
        }

    }
    return 0;
}

并查集

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

并查集模板题 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。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int n, m, p[N];

int find(int x)     //返回x的祖宗节点
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++ ) p[i] = i;

    while(m--)
    {
        int a, b;
        char op[2];
        scanf("%s%d%d", op, &a, &b);
        //printf("%s", op);

        if(op[0] == 'M') p[find(a)] = p[find(b)];  //让a的祖宗节点等于b，也就是a认b为父

        else{
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

题目描述

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。

给定整数n，求Fibnmod10000Fibnmod10000。

输入格式
输入包含多组测试用例。

每个测试用例占一行，包含一个整数n。

当输入用例n=-1时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围
0≤n≤2∗1090≤n≤2∗109
样例
输入样例：
0
9
999999999
1000000000
-1
输出样例：
0
34
626
6875

算法1 迭代

时间复杂度 O(N)

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {

        int result[2] = {0, 1};
        if(n < 2)
        {
            return result[n];
        }
        int fib1 = 1;
        int fib2 = 0;
        int fibn = 0;
        for(int i = 2; i <= n; i++)
        {
            fibn = fib1 + fib2;
            fib2 = fib1;
            fib1 = fibn;
        }
        return fibn;

    }
};

算法2 矩阵相乘

矩阵乘法
如果这道题目N不大的话,那么上面的题目描述已经告诉你递推O(n)O(n)做法了,但是现在N范围很大,我们必须使用一种速度极快的算法,加速我们的时间效率.
一般来说遇到这种递推的题目,或者说变化形式是一种线性递推的运算,我们就可以初步判断这道题目是矩阵乘法了.
我们可以设一个1*2的矩阵F(n)=[Fibn−1,Fibn]F(n)=[Fibn−1,Fibn],然后我们的目标就是要通过这个矩阵去推出FibnFibn
那么我们可以这样设计F(n)=F(n−1)∗AF(n)=F(n−1)∗A其中A为我们设计的转移状态矩阵,那么现在我们思考一下,怎么设计出这样的矩阵A呢?并且我们不仅要保存FibnFibn还要保存Fibn−1Fibn−1为下一次Fibn+1Fibn+1做好准备.
其实不难,我们可以令A矩阵为[01 11][01 11],换行符被吞掉了.
这是什么意思呢?其实第一行意思是Fibn−1∗0+FibnFibn−1∗0+Fibn,第二行意思则是Fibn−1×1+Fibn×1Fibn−1×1+Fibn×1
然后我们最后再用快速幂快速计算,达到优化速度.

时间复杂度O(logN)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int K=10000;
int n;
void mul(int f[2],int a[2][2])
{
    int c[2];
    memset(c,0,sizeof(c));
    for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
            c[j]=(c[j]+f[k]*a[k][j])%K;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[2][2])
{
    int c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%K;
    memcpy(a,c,sizeof(c));
}
int power(int b,int c)
{
    int f[2]={0,1};
    int a[2][2]={{0,1},{1,1}};
    while(b)
    {
        if (b&1)
            mul(f,a);
        mulself(a);
        b>>=1;
    }
    cout<<f[0]<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    while(cin>>n && n!=-1)
        power(n,K);
    return 0;
}

题目描述

样例

CPP版本

cpp
#include <iostream>
#include <vector>
using namespace std;

int res = 0;

int height(vector<vector<int>>& nums, int root) {
    if (root == -1) {
        return 0;
    }
    return max(height(nums, nums[root - 1][0]), height(nums, nums[root - 1][1])) + 1;
}

bool isFullTree(vector<vector<int>>& nums, int root) {
    if (root == -1) {
        return true;
    }
    if (isFullTree(nums, nums[root - 1][0]) && isFullTree(nums, nums[root - 1][1]) && height(nums, nums[root - 1][0]) == height(nums, nums[root - 1][1])) {
        res ++;
        return true;
    } else {
        return false;
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> nums(n, vector<int>(2));
    for (int i = 0; i < n; i ++) {
        cin >> nums[i][0] >> nums[i][1];
    }
    isFullTree(nums, 1);
    cout << res << endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围
1≤n,m≤105
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1

c++ 宽度优先搜索

路径边权值为1， 宽度优先搜索

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx; //链表头，
int d[N], q[N];     //d[]存储到这个值的距离，q[]模拟队列，存储路径/顺序

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);    //d[]存储脚标的距离
    d[1] = 0;

    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i])   //队头没有被遍历过，拓展下一步
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;    //等于上一步的距离 +1
                q[ ++ tt] = j;
            }
        }
    }
    return d[n];
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}

题目描述

blablabla

样例

blablabla

算法1

需要考虑奇偶性。
并且，需要注意是str. size()

#include<iostream>
#include<cstring>
#include <algorithm>


int res;

using namespace std;

int main()
{
    string str;
    getline(cin, str);

    for(int i = 0; i< str.size(); i++)
    {
        int l = i - 1;
        int r = i + 1;
        while(l >=0 && r < str.size() && str[l] == str[r]) l--, r++;
        res = max(res, r- l -1);

        l = i, r = i + 1;
        while(l >=0 && r < str.size() && str[l] == str[r]) l--, r++;
        res = max(res, r- l -1);
    }
    cout << res << endl;
    return 0;
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式
第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤105
输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例：

4

C++ 图的深搜

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;

void add(int a, int b)
{
    //把a->b
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;

}
//以u为根的子树中的点的数量
int dfs(int u)
{
    st[u] = true;   //被搜过

    int sum = 1, res = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j);
            res = max(res, s);  //res是子根节点最大值
            sum += s;       //sum是根节点的包含的数

        }
    }
    res = max(res, n - sum);    //去掉这个子根节点的最大值

    ans = min(ans, res);        //最大值最小
    return sum ;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b; 
        add(a, b), add(b, a);
    }

    dfs(1);

    cout << ans << endl;
    return 0;
}

对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。

而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。

所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：

0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级，而一般场合下的数据都是小于10^9的。
0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。
可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。

#include <iostream>
#include <cstring>

using namespace std;
int main()
{
    int a = 0x3f3f3f3f;
    printf("%d\n", a);
    int array[10];
    memset(array, 0x3f, sizeof(array));
    printf("%d", array[1]);
    return 0;
}

#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
    for(int i = 1; i <= n; i++) s[i] += s[i-1];     //前缀和

    for(int len = 2; len <= n; len ++)
    {
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int l = i, r = i + len -1;
            f[l][r] = 1e9;
            for(int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l - 1]);
        }
    }
    printf("%d\n", f[1][n]);    
    return 0;    
}