头像

17835208153

大同大学




离线:3天前


活动打卡代码 AcWing 840. 模拟散列表

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int h[N],e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx;
    idx ++;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x)
            return true;
    }
    return false;
}

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

    memset(h, -1, sizeof h);

    while (n--) {
        char op[2];
        int x;
        cin >> op >> x;
        if (*op == 'I') {
            insert(x);
        }
        else if (*op == 'Q') {
            if (find(x))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }

    return 0;
}



活动打卡代码 AcWing 839. 模拟堆

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 1e5 + 10;

int h[N];           /* 堆                                                   */
int ph[N];          /* 存储第k个插入的数在堆中的下标                        */
int hp[N];          /* 存储堆中指定下标的值是第k个插入的数,与ph[N]互逆      */
int cnt;            /* 存储当前堆中用到了哪个下标,用于插入与删除等操作      */

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]); /* 1.先通过下标a找到h[a]在堆中是第几个插入的数
                                   2.再通过第几个插入的数k找到在ph中所记录的在
                                    堆中对应的下标 3.最后与b交换            */
    swap(hp[a], hp[b]);         /* 交换所记录的在堆中插入的值的顺序         */
    swap(h[a], h[b]);           /* 交换堆中的值                             */
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) 
        t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) 
        t = u * 2 + 1;

    if (u != t)                 /* 如果u不是当前以u为根节点的堆的最小值     */
    {
        heap_swap(u , t);
        down(t);
    }
}

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

int main()
{
    int n, m = 0;
    cin >> n;
    while (n--) {
        char op[5];
        int k, x;
        cin >> op;
        if (!strcmp(op, "I")) {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt;    /* 堆中第m个插入的数在堆中的下标是cnt   */
            hp[cnt] = m;    /* 堆中下标为cnt的数是在堆中是第m个插入的   */
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM"))
            cout << h[1] << endl;
        else if (!strcmp(op, "DM")) {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        else if (!strcmp(op, "D")) {
            cin >> k;
            k = ph[k];                  /* 取得第k个插入的数在堆中的下标        */
            heap_swap(k, cnt);
            cnt --;
            up(k);
            down(k);
        }
        else if (!strcmp(op, "C")) {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }

    }

    return 0;
}





题目描述

维护一个集合,初始时集合为空,支持如下几种操作:

“I x”,插入一个数x;
“PM”,输出当前集合中的最小值;
“DM”,删除当前集合中的最小值(数据保证此时的最小值唯一);
“D k”,删除第k个插入的数;
“C k x”,修改第k个插入的数,将其变为x;
现在要进行N次操作,对于所有第2个操作,输出当前集合的最小值。

输入格式
第一行包含整数N。

接下来N行,每行包含一个操作指令,操作指令为”I x”,”PM”,”DM”,”D k”或”C k x”中的一种。

输出格式
对于每个输出指令“PM”,输出一个结果,表示当前集合中的最小值。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109
数据保证合法。

输入样例

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例

-10
6

算法1

  1. 除了维护一个堆之外,还开辟了两个额外的数组hp[]与ph[].
  2. hp[]用来存储第k个插入的数在堆中的下标.
  3. ph[]用来存储堆中各个下标的数是第几个插入的(k).

时间复杂度

nlogn

参考文献

y总算法基础课——模拟堆

C++ 代码

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 1e5 + 10;

int h[N];           /* 堆                                                   */
int ph[N];          /* 存储第k个插入的数在堆中的下标                        */
int hp[N];          /* 存储堆中指定下标的值是第k个插入的数,与ph[N]互逆      */
int cnt;            /* 存储当前堆中用到了哪个下标,用于插入与删除等操作      */

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]); /* 1.先通过下标a找到h[a]在堆中是第几个插入的数
                                   2.再通过第几个插入的数k找到在ph中所记录的在
                                    堆中对应的下标 3.最后与b交换            */
    swap(hp[a], hp[b]);         /* 交换所记录的在堆中插入的值的顺序         */
    swap(h[a], h[b]);           /* 交换堆中的值                             */
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) 
        t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) 
        t = u * 2 + 1;

    if (u != t)                 /* 如果u不是当前以u为根节点的堆的最小值     */
    {
        heap_swap(u , t);
        down(t);
    }
}

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

int main()
{
    int n, m = 0;
    cin >> n;
    while (n--) {
        char op[5];
        int k, x;
        cin >> op;
        if (!strcmp(op, "I")) {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt;    /* 堆中第m个插入的数在堆中的下标是cnt   */
            hp[cnt] = m;    /* 堆中下标为cnt的数是在堆中是第m个插入的   */
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM"))
            cout << h[1] << endl;
        else if (!strcmp(op, "DM")) {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        else if (!strcmp(op, "D")) {
            cin >> k;
            k = ph[k];                  /* 取得第k个插入的数在堆中的下标        */
            heap_swap(k, cnt);
            cnt --;
            up(k);
            down(k);
        }
        else if (!strcmp(op, "C")) {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }

    }

    return 0;
}




活动打卡代码 AcWing 756. 蛇形矩阵

算法思想

  1. 偏移量的引入,dx[], dy[];
#include<iostream>

using namespace std;

const int N =101;

int q[N][N];
int n, m;

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

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    int x = 0, y = 0, d = 1;

    for (int i = 1; i <= n * m; i++) {
        q[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || q[a][b]) {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << q[i][j] << ' ';
        cout << endl;
    }

    return 0;

}



活动打卡代码 AcWing 838. 堆排序

算法1

  1. 模板题,主要实现堆的down操作
  2. 堆排序时,从n / 2开始进行down操作
  3. 删除堆顶元素时,用最后一个元素覆盖第一个元素,然后size–,down(1);
#include<iostream>

using namespace std;

const int N = 1e5 + 10;

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

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) 
        t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])
        t = u * 2 + 1;

    if (t != u) {
        swap(h[t], h[u]);
        down(t);
    }

}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> h[i];

    cnt = n;

    // 排序
    for (int i = n / 2; i; i--) {
        down(i);
    }

    while (m--) {
        cout << h[1] << ' ';
        h[1] = h[cnt--];
        down(1);
    }
    cout << endl;
    return 0;
}



题目描述

维护一个字符串集合,支持两种操作:

“I x”向集合中插入一个字符串x;
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

输入格式
第一行包含整数N,表示操作数。

接下来N行,每行包含一个操作指令,指令为”I x”或”Q x”中的一种。

输出格式
对于每个询问指令”Q x”,都要输出一个整数作为结果,表示x在集合中出现的次数。

每个结果占一行。

数据范围
1≤N≤2∗104

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

算法1

  1. 用一个二维数组son[N][26]来模拟Trie树来存储和维护字符串集合,每个下标存储一个字符的ascii码,字符由son[N][26]中的idx连成字符串.
  2. 需要维护的操作由两个,插入insert(char str)和查询query(char str).
  3. 开辟一个cnt[N]数组来存储以当前idx结尾的字符串在son[N][26]当中出现了多少次
  4. idx表示当前在数组中已存储字符的总长度,在插入时会同时赋值给son数组的一维下标,保证插入不会冲突。

时间复杂度

nlogn

参考文献

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

char str[N];
int son[N][26], cnt[N], idx;

void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u])
            return 0;
        p = son[p][u];
    }
    return cnt[p];
}

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

    while(n--) {
        string op;
        cin >> op;
        if (op == "I") {
            cin >> str;
            insert(str);
        }
        else {
            cin >> str;
            cout << query(str) << endl;
        }
    }
    return 0;
}



活动打卡代码 AcWing 898. 数字三角形

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;
int n;
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> f[i][j];

    for (int i = n - 1; i > 0; i--)
        for (int j = 1; j <= i; j++)
            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
    cout << f[1][1] << endl;

    return 0;


}




#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[N];

int find(int x )
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

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

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

    while (m--) {
        string op;
        int a, b;
        cin >> op;

        if (op == "C") {
            cin >> a >> b;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1") {
            cin >> a >> b;
            if (find(a) == find(b))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
        else if (op == "Q2") {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }

    return 0;
}



题目描述

给定一个包含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所在连通块中点的数量

每个结果占一行。

数据范围
1≤n,m≤105

样例

输入样例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例:
Yes
2
3

前置题目

AcWing836 合并集合
https://www.acwing.com/activity/content/problem/content/885/1/

算法1

(并查集+路径压缩+记录连通点的数量) $O(n)$

1.找寻集合的根并进行路径压缩

int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}

2.

int cnt[N]

用来记录当前根结点的集合内所有节点的数量

时间复杂度

O(n)

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[N];

int find(int x )
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

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

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

    while (m--) {
        string op;
        int a, b;
        cin >> op;

        if (op == "C") {
            cin >> a >> b;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1") {
            cin >> a >> b;
            if (find(a) == find(b))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
        else if (op == "Q2") {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }

    return 0;
}



活动打卡代码 AcWing 836. 合并集合

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

//用来记录当前下标结点的父节点
int p[N];

// 寻找x的根节点
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--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M')
            p[find(a)] = find(b);
        else if (*op == 'Q') {
            if (find(a) == find(b))
                puts("Yes");
            else
                puts("No");
        }

    }

    return 0;
}