头像

4_3




离线:24分钟前


最近来访(140)
用户头像
acwing_1482
用户头像
张耀扬
用户头像
ZXG_DXX
用户头像
77777777777
用户头像
Caesar123
用户头像
我不明智
用户头像
cocoonnnp
用户头像
灰人
用户头像
zufestudy3
用户头像
C++大蒟蒻
用户头像
残疾人
用户头像
ease
用户头像
1564269628
用户头像
不拿NOI金牌不改名
用户头像
狂气电波
用户头像
AcWing2AK
用户头像
Catch-22
用户头像
夜寐
用户头像
抒怀
用户头像
YuWindSky


4_3
11小时前
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for x in arr:
            t = x
            while len(stk) and stk[-1] > x:
                t = max(t, stk[-1])
                stk.pop()
            stk.append(t)
        return len(stk)
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> stk;
        for (int i = 0; i < arr.size(); i ++)
        {
            int t = arr[i];
            while (stk.size() && stk.top() > arr[i])
            {
                t = max(stk.top(), t);
                stk.pop();
            }
            stk.push(t);
        }
        return stk.size();
    }
};


活动打卡代码 LeetCode 1282. 用户分组

4_3
12小时前
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        hash = {}
        res = []
        for i in range(len(groupSizes)):
            if groupSizes[i] not in hash:
                hash[groupSizes[i]] = []
            hash[groupSizes[i]].append(i)

            if len(hash[groupSizes[i]]) == groupSizes[i]:
                res.append(hash[groupSizes[i]])
                hash[groupSizes[i]] = []
        return res
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> hash;
        vector<vector<int>> res;
        for (int i = 0; i < groupSizes.size(); i ++)
        {
            hash[groupSizes[i]].push_back(i);
            if (hash[groupSizes[i]].size() == groupSizes[i])
            {
                res.push_back(hash[groupSizes[i]]);
                hash[groupSizes[i]].clear();
            }
        }
        return res;
    }
};


活动打卡代码 AcWing 1053. 修复DNA

4_3
5天前

循环队列记录ii+1的合法状态,只遍历有效的状态
队列中取出i阶段的有效状态,更新后,把i+1阶段有效状态放入队列
用变量flag来标记队列中ii + 1状态的分界点

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

using namespace std;

const int N = 1010;

int n, m;
int tr[N][4], cnt[N], idx;
char str[N];
int q[N], ne[N];
int f[N][N];
int a[N << 1];

int get(char c)
{
    if (c == 'A') return 0;
    if (c == 'G') return 1;
    if (c == 'C') return 2;
    return 3;
}

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++)
    {
        int t = get(str[i]);
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    cnt[p] = 1;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 4; i ++)
        if (tr[0][i])
            q[++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = 0; i < 4; i ++)
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++ tt] = p;
                cnt[p] |= cnt[ne[p]];
            }
        }
    }
}

int main()
{
    int T = 1;   
    while (scanf("%d", &n), n)
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        for (int i = 0; i < n; i ++)
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str + 1);
        m = strlen(str + 1);

        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;

        int hh = 0, tt = 0;
        a[tt ++] = 0;
        int flag = tt;
        for (int i = 0; i < m; i ++)
        {
            while (hh != tt && hh != flag)
            {
                int j = a[hh ++];
                if (hh == N << 1) hh = 0;

                for (int k = 0; k < 4; k ++)
                {
                    int t = get(str[i + 1]) != k;
                    int p = tr[j][k];
                /*
                    f[i + 1][p]初始值0x3f3f3f3f 
                    f[i][j]是合法状态,加上t,小于 f[i + 1][p]的初始值
                    两者取等时f[i + 1][p]肯定更新过,p已经在队列里了
                */    
                    if (!cnt[p] && f[i][j] + t < f[i + 1][p])  
                    {                                           
                        f[i + 1][p] = f[i][j] + t;      
                        a[tt ++] = p;
                        if (tt == N << 1) tt = 0;
                    }
                }
            }
            flag = tt;
        }
        int res = 0x3f3f3f3f;
        for (int i = 0; i <= idx; i ++) res = min(res, f[m][i]);

        if (res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", T ++, res);
    }

    return 0;
}

判断不合法状态直接continue

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

using namespace std;

const int N = 1010;

int n, m;
int tr[N][4], cnt[N], idx;
char str[N];
int q[N], ne[N];
int f[N][N];

int get(char c)
{
    if (c == 'A') return 0;
    if (c == 'G') return 1;
    if (c == 'C') return 2;
    return 3;
}

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++)
    {
        int t = get(str[i]);
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    cnt[p] = 1;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 4; i ++)
        if (tr[0][i])
            q[++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = 0; i < 4; i ++)
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++ tt] = p;
                cnt[p] |= cnt[ne[p]];
            }
        }
    }
}

int main()
{
    int T = 1;   
    while (scanf("%d", &n), n)
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        for (int i = 0; i < n; i ++)
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str + 1);
        m = strlen(str + 1);

        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;

        for (int i = 0; i < m; i ++)
            for (int j = 0; j <= idx; j ++)
            {
                if (f[i][j] == 0x3f3f3f3f || cnt[j]) continue;
                for (int k = 0; k < 4; k ++)
                {
                    int t = get(str[i + 1]) != k;
                    int p = tr[j][k];
                    if (!cnt[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
                }
            }

        int res = 0x3f3f3f3f;
        for (int i = 0; i <= idx; i ++) res = min(res, f[m][i]);

        if (res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", T ++, res);
    }

    return 0;
}


活动打卡代码 AcWing 1285. 单词

4_3
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = 1000010;

int n;
int tr[M][26], cnt[M], idx;
int q[M], ne[M];
char str[M];
int id[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];
        cnt[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 p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++ tt] = p;
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
    {
        scanf("%s", str);
        insert(i);
    }

    build();

    for (int i = idx - 1; ~i; i --) cnt[ne[q[i]]] += cnt[q[i]];

    for (int i = 0; i < n; i ++) printf("%d\n", cnt[id[i]]);

    return 0;
}


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

4_3
7天前

trie图中有父节点的空节点,直接存其可以在树上回跳的节点编号
当查询到这个空节点走不下去的时候,直接往回指,也就是图上往回指的线
相当于把一部分next数组嵌入到图中

查询的是trie图中有多少个以当前文本中第i个字母结尾的单词
与一维的kmp不同的是,当前字母匹配成功时,需要往回跳
kmp只匹配一个单词,trie图匹配多个,可能有以i结尾的子单词匹配成功,所以要跳

而非空节点,记录着他的儿子节点的编号,只能借助next数组跳

匹配不成功时,当前的”空节点”(记录的回跳的节点编号)直接在图上往回跳成匹配成功的非空节点,再去执行匹配成功的回跳
匹配成功需要借助next数组回跳查询有多少以i结尾的子单词

匹配不成功的回跳建图时已经建立了,在图上(tr[][]内部)独立完成
匹配成功的回跳是我们的需求,借助next数组完成查询

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

using namespace std;

const int N = 550010, M = 1000010;

int n, T;
int tr[N][26], cnt[N], idx;
int q[N], ne[N];
char str[M];
bool st[N];

void insert()
{
    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];
    }
    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 p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++ tt] = p;
            }
        }
    }
}

int main()
{
    scanf("%d", &T);
    while (T --)
    {
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(cnt, 0, sizeof cnt);
        memset(st, 0, sizeof st);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++)
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++)
        {
            int t = str[i] - 'a';
            j = tr[j][t];

            int p = j;
            while (p && !st[p])
            {
                res += cnt[p];
                cnt[p] = 0;
                st[p] = true;
                p = ne[p];
            }
        }
        printf("%d\n", res);
    }
    return 0;
}


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

4_3
7天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n, m;
int a[N];
vector<int> nums;
struct Node{
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];

int root[N], idx;


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 v)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if (l == r) 
    {
        tr[q].cnt ++;
        return q;
    }
    int mid = l + r >> 1;
    if (v <= mid) tr[q].l = insert(tr[q].l, l, mid, v);
    else tr[q].r = insert(tr[q].r, mid + 1, r, v);

    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 mid = l + r >> 1;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    if (k <= cnt) 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()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) 
    {
        scanf("%d", &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]));

    int l, r, k;
    while (m --)
    {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)]);
    }

    return 0;
}



4_3
7天前

关于max_id[0] = -1

max_id记录节点及其子树中数据版本号最大是多少
max_id[0] = -1,表示树中所有idx = 0的点版本号为-1,本题查询时,最小查询的是0版本号(l最小为1L = l - 1最小为0),初始化成-1表示用不到它
树初始化时节点的值全为0,表示当前节点为空,每个节点被用到时,会给其赋值一个大于0idx值,表示它不为空,同时也指出其子节点位置为tr[idx][]

关于insert(0, 23, 0, root[0])

本题用到了差分,整棵版本树第n个版本就是前n项异或和
而且会用到S_0所以要初始化S_0,比如p = 1时,会用到S_0,所以要初始化

初始化分两步:
1.初始化其值
这跟一维数组的前n项和没区别,本题是前n项异或和,初始化S_0 = 0, S_n ^ S_0 = S_n

2.本题不同的是,要在树中搜索查询的版本号,不插入0版本的S_0 = 0,搜索时查不到
比如当l = r = 1时,最终答案是S_n ^ x ^ S_0
而查询root[0]时(query(root[0], S_n ^ x, 0))
所谓的版本0的子树所有子节点的idx都是最开始的0,都是空节点,他们的max_id-1

所以要为版本号为0的树插入S_0,也就是数字0

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

using namespace std;

const int N = 600010, M = N * 25;

int n, m, idx;
int s[N];
int tr[M][2], max_id[M];
int root[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 (tr[p][v ^ 1]) 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_id[tr[q][v]];
}

int query(int root, int C, int L)
{
    int p = root;
    for (int i = 23; ~i; i --)
    {
        int v = C >> i & 1;
        if (max_id[tr[p][v ^ 1]] >= L) v ^= 1;
        p = tr[p][v];
    }

    return C ^ s[max_id[p]];
}

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

    max_id[0] = -1;
    root[0] = ++ idx;
    insert(0, 23, 0, root[0]);

    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &s[i]);
        s[i] ^= s[i - 1];
        root[i] = ++ idx;
        insert(i, 23, root[i - 1], root[i]);
    }

    char op[2];
    int l, r, x;
    while (m --)
    {
        scanf("%s", op);
        if (*op == 'A')
        {
            scanf("%d", &x);
            root[++ n] = ++ idx;
            s[n] = s[n - 1] ^ x;
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }

    return 0;
}


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

4_3
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 600010, M = N * 25;

int n, m, idx;
int s[N];
int tr[M][2], max_id[M];
int root[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 (tr[p][v ^ 1]) 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_id[tr[q][v]];
}

int query(int root, int C, int L)
{
    int p = root;
    for (int i = 23; ~i; i --)
    {
        int v = C >> i & 1;
        if (max_id[tr[p][v ^ 1]] >= L) v ^= 1;
        p = tr[p][v];
    }

    return C ^ s[max_id[p]];
}

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

    max_id[0] = -1;
    root[0] = ++ idx;
    insert(0, 23, 0, root[0]);

    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &s[i]);
        s[i] ^= s[i - 1];
        root[i] = ++ idx;
        insert(i, 23, root[i - 1], root[i]);
    }

    char op[2];
    int l, r, x;
    while (m --)
    {
        scanf("%s", op);
        if (*op == 'A')
        {
            scanf("%d", &x);
            root[++ n] = ++ idx;
            s[n] = s[n - 1] ^ x;
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }

    return 0;
}


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

4_3
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;

int n, idx;
int a[N];
int son[M][2];

void insert(int x)
{
    int p = 0;
    for (int i = 30; ~i; i --)
    {
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; ~i; i --)
    {
        int t = x >> i & 1;
        if (son[p][!t]) 
        {
            res += 1 << i;
            t ^= 1;
        }
        p = son[p][t];
    }
    return res;
}

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

    int res = 0;
    for (int i = 0; i < n; i ++) res = max(res, search(a[i]));
    printf("%d\n", res);

    return 0;
}


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

4_3
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

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

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()
{
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}