头像

Wilson79


访客:24395

离线:7天前


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

Wilson79
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 7, M = 31 * N;

int a[N];
int son[M][2], idx; // 这里不需要cnt[M],因为长度是固定的

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++idx; // 插入时如果路不存在就添加路
        p = son[p][u];                     // 往下走
    }
}

int query(int x) {
    int p = 0;
    int res = 0; // 记录与x异或结果最大的那个数
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (son[p][!u]) {
            p = son[p][!u]; // 如果另一个方向存在就往那走,因为这样结果会更大
            res = res * 2 + !u;
        } else {
            p = son[p][u]; // 如果另一个方向不能存在只能将就了
            res = res * 2 + u;
        }
    }
    return res;
}

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

    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) insert(a[i]);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int t = query(a[i]); // t表示和a[i]异或最大的数
        ans = max(ans, a[i] ^ t);
    }

    cout << ans << endl;

    return 0;
}


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

Wilson79
1个月前
// N表示输入的字符串的总长度
// son[N][26] 表示每个结点最多连出去 26 条边
// cnt[N] 表示以当前下标结尾的字符串有多少个
// idx 表示当前用的是哪个下标(下标是 0 的点既是根节点,又是空节点)

#include <iostream>

using namespace std;

const int N = 1e5 + 7;

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

void insert(string s) {
    int p = 0; 
    for (auto ch : s) {
        int u = ch - 'a';
        if (!son[p][u]) son[p][u] = ++ idx; // 第一次用 idx = 1
        p = son[p][u]; // p一定有路可走,没路的情况我上面已经创建了路
    }
    cnt[p] ++;
}

int query(string s) {
    int p = 0;
    for (auto ch : s) {
        int u = ch - 'a';
        if (!son[p][u]) return false;
        p = son[p][u];
    }
    return cnt[p];
}


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

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

    return 0;
}


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

Wilson79
1个月前
#include <iostream>

using namespace std;

const int N = 1e6 + 7;

int q[N], hh, tt, a[N];

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

    for (int i = 0; i < n; i ++) cin >> a[i];

    // 求滑动窗口的最小值
    for (int i = 0; i < n; i ++) {
        // 第一个 while 维护窗口的固定长度
        while (hh < tt && i - q[hh] >= k) hh ++;
        // 第二个 while 维护一个单调栈
        while (hh < tt && a[q[tt - 1]] >= a[i]) tt --;
        // 将当前下标加入队尾
        q[tt ++] = i;
        // 满足条件时输出结果
        if (i >= k - 1) cout << a[q[hh]] << " ";
    }

    cout << endl;

    hh = 0, tt = 0; // 重置
    for (int i = 0; i < n; i ++) {
        while (hh < tt && i - q[hh] >= k) hh ++;
        while (hh < tt && a[q[tt - 1]] <= a[i]) tt --;
        q[tt ++] = i;
        if (i >= k - 1) cout << a[q[hh]] << " ";
    }

    return 0;
}



Wilson79
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int stk[N], tt, a[N];

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

    for (int i = 0; i < n; i ++) cin >> a[i];

    // 维护一个单调递减的栈
    int res = 0;
    for (int i = 0; i < n; i ++) {
        while (tt > 0 && a[stk[tt - 1]] <= a[i]) {
            if (tt >= 2) { // 如果栈中至少有两个元素
                res += (i - stk[tt - 2] - 1) * (min(a[i], a[stk[tt - 2]]) - a[stk[tt - 1]]);
            }
            tt --;
        }
        stk[tt ++] = i;

    }
    cout << res << endl;

    return 0;
}


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

Wilson79
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int a[N], stk[N], tt;

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

    for (int i = 0; i < n; i ++) cin >> a[i];

    // 维护单调增栈(存下标比较好)
    for (int i = 0; i < n; i ++) {
        while (tt > 0 && a[stk[tt - 1]] >= a[i]) tt --; // 注意:栈存的是数组下标

        // 退出 while 循环有两种情况
        if (tt == 0) cout << -1 << " "; 
        else cout << a[stk[tt - 1]] << " ";

        stk[tt ++] = i; // 向栈中加入当前数组元素的下标
    }

    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

Wilson79
2个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int q[N], hh, tt;


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

    while (m --) {
        string s;
        cin >> s;
        if (s == "push") {
            cin >> x;
            q[tt ++] = x;
        } else if (s == "pop") {
            hh ++;
        } else if (s == "empty") {
            if (hh < tt) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        } else if (s == "query") {
            cout << q[hh] << endl;
        }
    }


    return 0;
}


活动打卡代码 AcWing 828. 模拟栈

Wilson79
2个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int stk[N], tt;

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

    while (m--) {
        string s;
        cin >> s;
        if (s == "push") {
            cin >> x;
            stk[tt ++] = x;
        } else if (s == "pop") {
            tt--;
        } else if (s == "empty") {
            if (tt <= 0)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else if (s == "query") {
            cout << stk[tt - 1] << endl;
        }
    }

    return 0;
}


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

Wilson79
2个月前
// 双链表(数组模拟)
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

// 初始化
void init() {
    // 结点0表示左哨兵,1表示右哨兵
    r[0] = 1, l[1] = 0;
    idx = 2; // 下标0和1已经被用过
}

// 插入元素 - 在下标为k的点的右边插入x
void add(int k, int x) {
    e[idx] = x;

    r[idx] = r[k]; // 先连
    l[idx] = k;    // 先连

    l[r[k]] = idx; // 后断 (这行必须在r[k] = idx前面)
    r[k] = idx;    // 后断
    idx ++;
}
// 注:插入元素 - 在下标为k的点的左边插入x,只需 add(l[k], x);

// 删除元素 - 删除下标为k的结点
void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

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

    init();

    // L : add(0, x)
    // R : add(l[1], x)
    // D : remove(k + 1, x) // 第 k 个插入的数,下标为 k + 1
    // IL : add(l[k + 1], x)
    // IR : add(k + 1, x)
    while (m--) {
        int x, k;
        string s;
        cin >> s;
        if (s == "L") {
            cin >> x;
            add(0, x);
        } else if (s == "R") {
            cin >> x;
            add(l[1], x);
        } else if (s == "D") {
            cin >> k;
            remove(k + 1);
        } else if (s == "IL") {
            cin >> k >> x;
            add(l[k + 1], x);
        } else if (s == "IR") {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    // 从左往右遍历双链表
    for (int i = r[0]; i != 1; i = r[i]) {
        cout << e[i] << " ";
    }

    return 0;
}



Wilson79
2个月前
// 在笔试题中需要用到单链表的数组模拟,因为 new 操作很慢

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

// head 表示头结点的下标(竖着画)
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少
// idx 存储当前已经用到了哪个点
int head, idx, e[N], ne[N];

// 初始化
void init() {
    head = -1; // head = -1 表示当前头结点是空节点(-1)
    idx = 0;   // idx = 0 表示从 0 号结点开始用
}

// 头插法:将 x 插到头结点head后面
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head; // 先连
    head = idx;     // 后断
    idx++;          // 当前 idx 结点已经用过了
}

// 尾插法:将 x 插到尾结点idx-1后面(适用范围小,必须依次进行插入操作)
void add_to_end(int x) {
    e[idx] = x;
    ne[idx] = -1; // 先连

    if (!idx)
        head = idx; // 后断
    else
        ne[idx - 1] = idx; // 后断

    idx++;
}

// 将 x 插到下标是k的节点后面
void add(int k, int x) {
    e[idx] = x;      // 设置 val 值
    ne[idx] = ne[k]; // 先连
    ne[k] = idx;     // 后断
    idx++;
}

// 将下标是 k 的结点后面的结点删除
void remove(int k) {
    ne[k] = ne[ne[k]];
}

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

    init();

    while (m--) {
        int k, x;
        string s;
        cin >> s;
        if (s == "H") {
            cin >> x;
            add_to_head(x);
        } else if (s == "I") {
            cin >> k >> x;
            add(k - 1, x);
        } else if (s == "D") {
            cin >> k;
            if (!k)
                head = ne[head];
            else
                remove(k - 1);
        }
    }

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

    return 0;
}


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

Wilson79
2个月前
// 在笔试题中需要用到单链表的数组模拟,因为 new 操作很慢

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

// head 表示头结点的下标(竖着画)
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少
// idx 存储当前已经用到了哪个点
int head, idx, e[N], ne[N];

// 初始化
void init() {
    head = -1; // head = -1 表示当前头结点是空节点(-1)
    idx = 0;   // idx = 0 表示从 0 号结点开始用
}

// 头插法:将 x 插到头结点head后面
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head; // 先连
    head = idx;     // 后断
    idx++;          // 当前 idx 结点已经用过了
}

// 尾插法:将 x 插到尾结点idx-1后面(适用范围小,必须依次进行插入操作)
void add_to_end(int x) {
    e[idx] = x;
    ne[idx] = -1; // 先连

    if (!idx)
        head = idx; // 后断
    else
        ne[idx - 1] = idx; // 后断

    idx++;
}

// 将 x 插到下标是k的节点后面
void add(int k, int x) {
    e[idx] = x;      // 设置 val 值
    ne[idx] = ne[k]; // 先连
    ne[k] = idx;     // 后断
    idx++;
}

// 将下标是 k 的结点后面的结点删除
void remove(int k) {
    ne[k] = ne[ne[k]];
}

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

    init();

    while (m--) {
        int k, x;
        string s;
        cin >> s;
        if (s == "H") {
            cin >> x;
            add_to_head(x);
        } else if (s == "I") {
            cin >> k >> x;
            add(k - 1, x);
        } else if (s == "D") {
            cin >> k;
            if (!k)
                head = ne[head];
            else
                remove(k - 1);
        }
    }

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

    return 0;
}