头像

上将邢道荣


访客:5564

离线:1天前



#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<string>
#include<set>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
    int l, r;
    char val;
};
node tree[10010];
int idx;
map<char, int> ha;
string a, b;
int build(int pl, int pr, int il, int ir)
{
    int t = ++idx;
    if (pl > pr)
    {
        tree[t].val = '0';
        return 0;
    }
    int cur = ha[a[pl]];
    int l = build(pl + 1, pl + cur - il, il, cur - 1);
    int r = build(pl + cur - il + 1, pr, cur + 1, pr);

    tree[t].l = l;
    tree[t].r = r;
    tree[t].val = a[pl];
    return t;

}
void dfs(int root)
{
    queue<int > q;
    q.push(root);
    while (q.size())
    {
        int top = q.front();
        q.pop();
        cout << tree[top].val;
        if (tree[top].l)
            q.push(tree[top].l);
        if (tree[top].r)
            q.push(tree[top].r);
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    { 
        cin >> a >> b;
        ha.clear();
        idx = 0;
        for (int i = 0; i < b.size(); i++) ha[b[i]] = i;
        int root = build(0, a.size() - 1, 0, b.size() - 1);
        dfs(root);
        cout << endl;
    }
    return 0;
}


//递归建立二叉树的函数



活动打卡代码 AcWing 1137. 选择最佳线路

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010, M = 3e4 + 10, INF = 0x3f3f3f3f;
int h[N], q[N], dist[N], ne[M], w[M], e[M], idx = 1;
int n, m, s;
bool visit[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    visit[0] = true;
    int hh = 0, tt = 1;
    q[0] = 0;
    while(hh != tt)
    {
        int t = q[hh ++];
        if(hh == N) hh = 0;
        visit[t] = false;
        for(int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!visit[j]) 
                {
                    q[tt ++] = j;
                    if(tt == N) tt = 0;
                    visit[j] = true;
                }
            }
        }
    }
    if(dist[s] == INF) return -1;
    else return dist[s];
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &s) != -1)
    {
        memset(h, 0, sizeof(h));
        idx = 1;
        while(m --)
        {
            int p, q, t;
            scanf("%d%d%d", &p, &q, &t);
            add(p, q, t);
        }
        int w;
        scanf("%d", &w);
        while(w --)
        {
            int t;
            scanf("%d", &t);
            add(0, t, 0);
        }

        printf("%d\n", spfa());
    }
    return 0;
}



活动打卡代码 AcWing 1285. 单词


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

using namespace std;

const int N = 1e6 + 10;

int tr[N][26], f[N], idx;

int ne[N], q[N];
int id[210];
char str[N];
void insert(int x)
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int t = str[i] - 'a';
        if(!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
        f[p]++;
    }
    id[x] = p;
}
void build()
{
    int hh = 0, tt = -1;
    for(int i = 0; i < 26; i ++)
        if(tr[0][i])
            q[++ tt] = tr[0][i];
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = 0; i < 26; i ++)
        {
            int c = tr[t][i];
            if(!c) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[c] = tr[ne[t]][i];
                q[++ tt] = c;
            }
        }
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> str;
        insert(i);
    }

    build();

    for(int i = idx - 1; i >= 0; i --) f[ne[q[i]]] += f[q[i]];
    for(int i = 0; i < n; i ++)
    {
        cout << f[id[i]] << endl;
    }
    return 0;
}




活动打卡代码 AcWing 1282. 搜索关键词


#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e4 + 10, S = 55, M = 1e6 + 10;
char str[M];
int tr[N * S][26], ne[N * S], cnt[N], q[N * S], idx;

void insert()
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int t = str[i] - 'a';
        if(tr[p][t] == 0) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p] ++;
}
void build()
{
    int hh = 0, tt = -1;
    for(int i = 0; i < 26; i ++)
        if(tr[0][i]) 
            q[++ tt] = tr[0][i];
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = 0; i < 26; i ++)
        {
            int c = tr[t][i];
            if(!c) continue;
            int j = ne[t];
            while(j && !tr[j][i]) j = ne[j];
            if(tr[j][i]) j = tr[j][i];
            ne[c] = j;
            q[++ tt] = c;
        }
    }
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(str, 0, sizeof str);
        int n;
        cin >> n;
        for(int i = 0; i < n; i ++) 
        {
            cin >> str;
            insert();
        }
        build();
        int res = 0;
        cin >> str;
        for(int i = 0, j = 0; str[i]; i ++)
        {
            int t = str[i] - 'a';
            while(j && !tr[j][t]) j = ne[j];
            if(tr[j][t]) j = tr[j][t];

            int p = j;
            while(p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }
        cout << res << endl;
    }
}




活动打卡代码 AcWing 265. 营业额统计


#include <iostream>
#include <cmath>
using namespace std;

const int N = 6e5 + 10, INF = 1e7;
using ll = long long;
struct node
{
    int l, r;
    int key, val;
}tr[N];
int idx, root;
int get_node(int key)
{
    tr[++ idx].key = key;
    tr[idx].val = rand();
    return idx;
}
void build()
{
    get_node(-INF), get_node(INF);
    root = 1;
    tr[root].r = 2;
}
void zig(int &p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
}
void zag(int &p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
}
void insert(int &p, int key)
{
    if(!p) p = get_node(key);
    else if(tr[p].key == key) return;
    else if(tr[p].key < key)
    {

        insert(tr[p].r, key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    else if(tr[p].key > key)
    {
        insert(tr[p].l, key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    }
}
int get_prev(int p, int key)
{
    if(!p) return -INF;
    if(tr[p].key > key) return get_prev(tr[p].l, key);
    else return max(tr[p].key, get_prev(tr[p].r, key));

}
int get_next(int p, int key)
{
    if(!p) return INF;
    if(tr[p].key < key) return get_next(tr[p].r, key);
    else return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
    int n;
    cin >> n;
    ll res = 0;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        if(i == 1) res += x;
        else res += min(x - get_prev(root, x), get_next(root, x) - x);
        insert(root, x);
    }
    cout << res << endl;
    return 0;
}




活动打卡代码 AcWing 253. 普通平衡树

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, INF = 1e8;

struct node
{
    int l, r;
    int key, val;
    int cnt, size;
}tr[N]; 

int n, root, idx;;
void pushup(int &p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key)
{
    int p = ++ idx;
    tr[p] = {0, 0, key, rand(), 1, 1};
    return p;
}
void build()
{
    get_node(-INF), get_node(INF);
    root = 1;
    tr[root].r = 2;
    pushup(root);
}
void zig(int &p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}
void zag(int &p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}
void insert(int &p, int key)
{
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt ++;
    else if(tr[p].key > key)
    {
        insert(tr[p].l, key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else if(tr[p].key < key)
    {
        insert(tr[p].r, key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}
void remove(int &p, int key)
{
    if(!p) return;
    if(tr[p].key == key)
    {
        if(tr[p].cnt > 1) tr[p].cnt --;
        else if(tr[p].l || tr[p].r)
        {
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else 
            {
                zag(p);
                remove(tr[p].l, key);
            }
        } 
        else p = 0;
    }
    else if(tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);
    pushup(p);
}
int get_rank_by_key(int p, int key)
{
    if(!p) return 0;
    if(tr[p].key == key) return tr[tr[p].l].size + 1;
    else if(tr[p].key > key) return  get_rank_by_key(tr[p].l, key);
    else return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}
int get_key_by_rank(int p, int rank)
{
    if(!p) return INF;
    if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    else if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);

}

int get_prev(int p, int key)
{
    if(!p) return -INF;
    if(tr[p].key >= key) return get_prev(tr[p].l, key);
    else return max(tr[p].key, get_prev(tr[p].r, key));

}
int get_next(int p, int key)
{
    if(!p) return INF;
    if(tr[p].key <= key) return get_next(tr[p].r, key);
    else return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
    cin >> n;
    build();
    while(n --)
    {
        int opt, x;
        cin >> opt >> x;
        if(opt == 1) insert(root, x);
        else if(opt == 2) remove(root, x);
        else if(opt == 3) cout << get_rank_by_key(root, x) - 1 << endl;
        else if(opt == 4) cout << get_key_by_rank(root, x + 1) << endl;
        else if(opt == 5) cout << get_prev(root, x) << endl;
        else cout << get_next(root, x) << endl;
    }
    return 0;
}




活动打卡代码 AcWing 255. 第K小数


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10, M = 1e4 + 10;

int a[N];
int n, m;
vector<int> nums;
int root[N], idx;
struct node
{
    int l, r, cnt;
}tr[N * 21];
int find(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int build(int l, int r)
{
    int p = ++idx; 
    if(l == r)
    {
        return p;
    }
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}
int insert(int p, int l, int r, int x)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if(l == r)
    {
        tr[q].cnt ++;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}
int query(int p, int q, int l, int r, int k)
{
    if(l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if(cnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
    else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    root[0] = build(0, nums.size() - 1);

    for(int i = 1; i <= n; i ++)
    {
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
    }
    while(m --)
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout << nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)] << endl;
    }
    return 0;
}




活动打卡代码 AcWing 256. 最大异或和


#include <iostream>
#include <cstring>
using namespace std;

const int N = 6e5 + 10, M = N * 25;
int tr[M][2], max_id[M], root[N], idx;
int s[N];
void insert(int i, int k, int p, int q)
{
    if(k < 0)
    {
        max_id[q] = i;
        return;
    }
    int v = s[i] >> k & 1;
    if(p) tr[q][v ^ 1] = tr[p][v ^ 1];
    tr[q][v] = ++ idx;
    insert(i, k - 1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int root, int C, int L)
{
    int p = root;
    for(int i = 23; i >= 0; i --)
    {
        int v = C >> i & 1;
        if(max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];
    }
    return s[max_id[p]] ^ C;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    root[0] = ++ idx;
    max_id[0] = -1;
    insert(0, 23, 0, root[0]);

    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        s[i] = s[i - 1] ^ x;
        root[i] = ++ idx;
        insert(i, 23, root[i - 1], root[i]);

    }
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "A")
        {
            int x; cin >> x;
            n ++;
            s[n] = s[n - 1] ^ x;
            root[n] = ++ idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            int l, r, x;
            cin >> l >> r >> x;
            //cout << query(root[r - 1], s[n] ^ x, l - 1) << endl;
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }
    return 0;
} 





活动打卡代码 AcWing 1277. 维护序列


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

typedef long long ll;
int a[N];    int n, m, p;
struct node
{
    int l, r;
    int sum, mul, add;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = (ll) ( tr[u << 1].sum + tr[u << 1 | 1].sum ) % p;
}
void eval(node &root, int mul, int add)
{
    root.sum = ((ll) root.sum * mul + (ll) (root.r - root.l + 1) * add) % p;
    root.mul = (ll) root.mul * mul  % p;
    root.add = ((ll) root.add * mul + add) % p;
}
void pushdown(int u)
{
    eval(tr[u << 1], tr[u].mul, tr[u].add);
    eval(tr[u << 1 | 1], tr[u].mul, tr[u].add);

    tr[u].add = 0, tr[u].mul = 1;
}
int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum % p;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int sum = 0;
        if(l <= mid) sum = query(u << 1, l, r) % p;
        if(r > mid) sum = (ll) (sum + query(u << 1 | 1, l, r)) % p;
        return sum;
    }
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, a[l], 1, 0};
    else
    {
        tr[u] = {l, r, 0, 1, 0};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add, int mul)
{
    if(tr[u].l >= l && tr[u].r <= r) 
    {
        eval(tr[u], mul, add);
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, add, mul);
        if(r > mid) modify(u << 1 | 1, l, r, add, mul);
        pushup(u);
    }
}

int main()
{
    cin >> n >> p;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);
    cin >> m;
    while(m --)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if(op == 1)
        {
            int e; cin >> e;
            modify(1, l, r, 0, e);
        }
        else if(op == 2)
        {
            int e;
            cin >> e;
            modify(1, l, r, e, 1);
        }
        else
        {
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}








活动打卡代码 AcWing 113. 特殊排序

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1, 1);
        for(int i = 2; i <= N; i ++)
        {
            int l = 0, r = res.size() - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(compare(res[mid], i)) l = mid;
                else r = mid - 1;
            }
            res.push_back(i);
            for(int j = res.size() - 2; j > r; j --) swap(res[j], res[j + 1]);
            if(compare(i, res[r])) swap(res[r], res[r + 1]);
        }
        return res;
    }
};