头像

深蓝


访客:12617

离线:2个月前


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

深蓝
4个月前
#include <iostream>

using namespace std;

const int N = 10e5 + 10;
int h[N], len;

void down(int u)    // 往下调堆,是一个递归过程
{
    int t = u;      // t保存三个节点中最小的编号
    if(u * 2 <= len && h[t] > h[u * 2])    t = u * 2;   // 与左孩子比较
    if(u * 2 + 1 <= len && h[t] > h[u * 2 + 1])    t = u * 2 + 1;   // 与右孩子比较
    if(t != u)
    {
        swap(h[t], h[u]);
        down(t);    // 递归调用
    }
}

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

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

    for(int i = n / 2; i >= 1; i--) // O(n)的建堆,一个一个插入建堆是O(nlogn)
        down(i);

    while(m--)
    {
        printf("%d ", h[1]);    // 输出堆顶元素
        h[1] = h[len];          // 将堆末尾元素换到堆顶,并删除末尾元素
        len--;
        down(1);                // 从堆顶开始调堆
    }

    return 0;
}



深蓝
4个月前
#include <iostream>

using namespace std;

const int N = 10e5 + 10;
int p[N], cnt[N];   // 与模板题一样,只需要多维护一个cnt数组(以根节点为标识标识集合的节点个数)

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;
        cnt[i] = 1;
    }

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

        if(op == "C")
        {
            cin >> a >> b;
            if(find(a) == find(b))  continue;   // 如果a与b已经在一个集合里,需要特判
            cnt[find(b)] += cnt[find(a)];   // 注意别写反了
            p[find(a)] = find(b);
        }else if(op == "Q1")
        {
            cin >> a >> b;
            if(find(a) == find(b))  puts("Yes");
            else    puts("No");
        }else
        {   
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }

    return 0;
}


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

深蓝
4个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 10e5 + 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;
    scanf("%d%d", &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[0] == 'Q')
            if(find(a) == find(b))  printf("Yes\n");
            else    printf("No\n");
        else
        {
            p[find(a)] = find(b);
        }
    }

    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

深蓝
4个月前
#include <iostream>

using namespace std;

const int N = 10e5 + 10;

int son[N][26];     // 存储trie树,26表示只用存储小写字母
int cnt[N];         // 以当前结点为结束的字符串个数
int idx;            // 结点索引,用于创建与查找
char str[N];


// 下标是0的点,既是根节点,也是空节点
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--)
    {
        char op[2]; // 有一个空格字符
        scanf("%s%s", op, str);

        if(op[0] == 'I')
            insert(str);
        else
            cout << query(str) << endl;
    }    

    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

深蓝
4个月前
#include <iostream>

using namespace std;

const int N = 10e5 + 10, M = 31 * N;    // trie存的是数的每一位,有10W个数,每个数31位
int son[M][2], idx = 0; 

void insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;     // 位运算里的算法,二进制第i位是多少
        if(!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;
        if(son[p][!u])          // 根据异或运算的性质,优先考虑与当前位不相同的分支
        {
            p = son[p][!u];
            res = res * 2 + !u; // 记录下res,乘2相当于左移1位
        }else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }

    return res;
}

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

    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);

        insert(x);              // 先插入,避免trie树为空时需要特判
        int t = query(x);       // 再在trie树中查询,与当前数最大的异或结果
        res = max(res, t ^ x);  // 更新答案
    }

    printf("%d", res);     
    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

深蓝
4个月前
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
char s[N], p[N];
int ne[N];

int main()
{
    int n, m;

    cin >>  n >> p + 1 >> m  >> s + 1;

    // 求next数组
    for(int i = 2, j = 0; i <= n; i++)  // 字符串长度从2开始才能计算前后缀
    {
        while(j && p[i] != p[j + 1])    // 匹配不成功,从next取出下标继续比较
            j = ne[j];
        if(p[i] == p[j + 1])            // 成功,前后缀相同长度 +1
            j++;
        ne[i] = j;                      // 前后缀最大相同长度 存入next数组
    }

    // 匹配过程
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && s[i] != p[j + 1])
            j = ne[j];
        if(s[i] == p[j + 1])
            j++;
        if(j == n)
        {
            printf("%d ", i - n);
        }
    }

    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

深蓝
4个月前
#include <iostream>

using namespace std;

const int N = 10e6 + 10;
int a[N], q[N];          // 队列q存的是下标
int hh = 0, tt = -1;    


int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for(int i = 0; i < n; i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) // i 从0开始,所以要减去k要加1
            hh++;  // 队头元素不在窗口内,删掉
        while(hh <= tt && a[q[tt]] >= a[i])
            tt--;  // 队列中,队尾元素比当前元素还大,冗余,需要删掉
        q[++tt] = i;    // 当前元素如队列

        if(i >= k - 1)  // i必须大于一个窗口值,才能有输出
            printf("%d ", a[q[hh]]); // 最小值在单调队列的队头
    }

    puts("");

    for(int i = 0; i < n; i++)  // 找窗口最大值,为窗口最小值的镜像代码
    {
        if(hh <= tt && q[hh] < i - k + 1)
            hh++;
        while(hh <= tt && a[q[tt]] <= a[i])
            tt--;
        q[++tt] = i;

        if(i >= k - 1)
            printf("%d ", a[q[hh]]);
    }

    return 0;
}


活动打卡代码 AcWing 830. 单调栈

深蓝
4个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int stk[N], top = 0;

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

    for(int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);

        while(top && x <= stk[top]) // 栈顶元素比当前元素还要大,则不可能被「选中」,弹出栈顶元素
            top--;
        if(top)     // 如果栈中有值,说明存在比当前值小的数,输出栈顶元素
            printf("%d ", stk[top]);
        else        // 栈为空,说明没有符合要求的数,输出-1
            printf("-1 ");

        stk[++top] = x; // 
    }


    return 0;
}


活动打卡代码 AcWing 827. 双链表

深蓝
4个月前
用数组来模拟栈操作

# 模板题

[AcWing 828. 模拟栈](https://www.acwing.com/problem/content/830/)

- `top`也可以初始化为`-1`,这样的话数组中实际存在有值的下标从`0`开始,这里是从`1`开始

include [HTML_REMOVED]

using namespace std;

const int N = 1e5 + 10;
int stk[N], top = 0;

void push(int x)
{
stk[++top] = x;
}

int query()
{
return stk[top];
}

void pop()
{
top–;
}

bool empty()
{
return top <= 0;
}

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

while(m--)
{
    string op;
    cin >> op;

    if(op == "push")
    {
        int x;
        cin >> x;
        push(x);
    }else if(op == "query") 
        cout << query() << endl;
    else if(op == "empty")
        cout << (empty() ? "YES" : "NO") << endl;
    else
        pop();
}

return 0;

}







活动打卡代码 AcWing 826. 单链表

深蓝
4个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

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

// head为头指针:指向第一个结点的位置
// idx为当前索引
// e[i]: i结点的值
// ne[i]:i结点的下一结点的位置
void init()
{
    head = -1;
    idx = 0;
}

void head_insert(int x)
{
    e[idx] = x;
    ne[idx] = head;     // head指向的就是第一个节点位置
    head = idx;
    idx ++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

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

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

    init();

    while(m--)
    {
        char op;
        int k, x;

        scanf(" %c", &op);
        if(op == 'H') 
        {
            scanf("%d", &x);
            head_insert(x);
        }else if(op == 'D')
        {
            scanf("%d", &k);
            if(!k)  head = ne[head];    // k为0特判,删除头结点
            remove(k - 1);
        }else
        {
            scanf("%d%d", &k, &x);
            insert(k - 1, x);
        }
    }

    for(int i = head; i != -1; i = ne[i])
        cout << e[i] << ' ';

    return 0;
}