2018 计蒜之道初赛第二场（字典树）

程序员文章站 2024-03-20 10:08:10

...

转载请注明出处https://blog.csdn.net/the_Little_Penguin/article/details/80339641

第一次写博客，如有不足，还请多多指教。

赛后过的题…..
2018 计蒜之道初赛第二场（字典树）
题目是字典树，只不过是后缀的。

C题阿里巴巴的手机代理商（中等）

记原后缀为s1，新后缀为s2，要修改的情况下，分成两种情况：

一、s1不包含（见注释①）在s2中，可直接处理，即增加新后缀，然后将s1后面的内容接到s2后面。

二、s1包含在s2中，在字典树中沿着s1往下走，结束后，直接开新枝记录s2，s2结束后，然后将s1后面的内容接到s2后面。

这里要注意，要防止成环，在处理过程中记录一下s1结束后与s2对应位置的下一个字母（如s1=”ty”，s2=”arty”，那么这个字母指的是r）在字典树中s1这条枝下的标号（因为如果s1这条枝的下一个字母上存在与s2相同的字母，则会被覆盖，而到时候将s1的后续接到s2时则会成环）。

这里举一个例子：字典树中存在rty这个单词，现在要将ty改为rrty，会发现，如果不记录r，就会出现旧的rty丢失，那么，以rty为后缀的单词也都会丢失，而rrty在字典树中，由于将t的子孙都搬了过来，那么ttrr这条路下最后的r的下个一子孙r指向了前一个r，就出现了环。那么，只要记录下原来r在字典树中的位置，再对其进行更新就可以了。
2018 计蒜之道初赛第二场（字典树）
注释：①包含：指的是，lens1小于lens2（因为lens1==lens2的情况就算是“包含”也是conflict），且在s1的长度内，该后缀从后往前每一个字母都与s2匹配如：ty –> rty 则记为包含，而 ty –> tyr 不记为包含

注意最终的数据是有可能超过int的。

更新部分的代码

bool contains(char s1[], char s2[]) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int i = len1 - 1, j = len2 - 1;
    if (len1 >= len2)
        return false;
    while (j >= 0) {
        if (i < 0)
            return true;
        if (s1[i] != s2[j])
            return false;
        i--;
        j--;
    }
}

int update_insert(char s2[], int len1, int endd, bool contain) {
    int len2 = strlen(s2);
    ll val = num[endd];
    int now = 0;
    int start = len2 - 1;
    int save = ztree[endd][s2[len2 - len1 - 1] - 'a'];
    for (int i = start; i >= 0; i--) {
        if (contain && i <= len2 - len1 - 1 || ztree[now][s2[i] - 'a'] == 0)
            ztree[now][s2[i] - 'a'] = cnt++;
        now = ztree[now][s2[i] - 'a'];
        num[now] += val;
    }
    for (int i = 0; i < 26; i++) {
        if (ztree[endd][i]) {
            ztree[now][i] = ztree[endd][i];
            num[ztree[now][i]] = num[ztree[endd][i]];
        }
    }
    if (contain) {
        ztree[now][s2[len2 - len1 - 1] - 'a'] = save;
        num[ztree[now][s2[len2 - len1 - 1] - 'a']] = num[save];
    }
    return ztree[endd][s2[len2 - len1 - 1] - 'a'];
}

void update_del(char s1[], ll val) {
    int len1 = strlen(s1);
    int now = 0;
    int aa = 0;
    for (int i = len1 - 1; i >= 0; i--) {
        de[aa][0] = now;
        de[aa++][1] = s1[i] - 'a';
        now = ztree[now][s1[i] - 'a'];
        num[now] -= val;
    }
    de[aa++][0] = now;
    for (int i = 0; i < aa - 1; i++) {
        if (num[de[i + 1][0]] == 0)
            ztree[de[i][0]][de[i][1]] = 0;
    }
    for (int i = 0; i < 26; i++) {
        ztree[now][i] = 0;
    }
}

void update(char s1[], char s2[]) {
    bool con = contains(s1, s2);
    int endd = query(s1);
    ll val = num[endd];
    int connect = update_insert(s2, strlen(s1), endd, con);
    update_del(s1, val);
    if (con)
        ztree[endd][s2[strlen(s2) - strlen(s1) - 1] - 'a'] = connect;
}

D题阿里巴巴的手机代理商（困难）

暴力一下，跑二次字典树。

第一遍，先把各种操作保存起来，离线跑一下，记录一下各个询问的版本号。

第二遍，按照版本排下序，过一遍（过程中会经历0~x个版本号，就在其中对排序好的vquery进行处理），到达指定id（第几个操作）时再输出。因为dirV<=id，可一遍完成。

struct VQ {
    int dirV;
    int id;
    string qstring;
}vquery[1000005];

注意题意那个修改操作empty的时候也是不记版本号的，题意没说。

上一篇： servlet三个监听器-servlet,request,session

下一篇： 2018 计蒜之道初赛第二场赛后总结

2018 计蒜之道初赛第二场（字典树）

C题阿里巴巴的手机代理商（中等）

D题阿里巴巴的手机代理商（困难）