VK CUP 2017 C String Reconstruction

Bertha 。 2022-06-12 02:36 103阅读 0赞

[Codeforces Round \#423 (Div. 2, rated, based on VK Cup Finals)][Codeforces Round _423 _Div. 2_ rated_ based on VK Cup Finals]

## [VK CUP 2017 C 3 a 4 1 3 5 7 ab 2 1 5 ca 1 4String Reconstruction][] ##

从给出信息片段,得出字典序最小的一个字符串,题目保证答案存在

信息给出形式:

3 　　　  
a 4 1 3 5 7  
ab 2 1 5  
ca 1 4  
  
第一行 3 代表信息片段个数  
第二行 a 代表片段信息, 4 代表在4个地方出现 1,3,5,7 分别代表出现的位置  
.  
.  
输出:

abacaba

题目给出片段信息和出现位置,相当于给出区间

为避免对已操作区间重复操作,用树状数组加以标记,标记方式为,访问标记为1,未访问为0,树状数组求和,若某区间的和不与区间长度相等,则该区间未标记完全.

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int maxn = 2010000;
    
    char ans[maxn];
    char c[maxn];
    int t[maxn];
    
    void add(int k)
    {
        while(k <= maxn)
        {
            t[k]++;
            k += k & -k;
        }
    }
    int sum(int l, int r)
    {
        l--;
        int suml = 0;
        while(l)
        {
            suml += t[l];
            l -= l & -l;
        }
        int sumr = 0;
        while(r)
        {
            sumr += t[r];
            r -= r & -r;
        }
        return sumr - suml;
    }
    
    void updata(int l, int r, int k)
    {
        if(l == r)
        {
            if(!ans[l])
            {
                add(l);
                ans[l] = c[k];
            }
            return ;
        }
        int mid = (l + r) >> 1;
        if(sum(l, mid) < mid - l + 1) updata(l, mid, k);
        if(sum(mid + 1, r) < r - mid) updata(mid + 1, r, k + mid - l + 1);
    }
    
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            int lans = 0;
            memset(ans,0,sizeof(ans));
            memset(t,0,sizeof(t));
            while(n--)
            {
                int m = 0;
                scanf("%s%d", c, &m);
                int len = strlen(c);
                for(int i = 0; i < m; i++)
                {
                    int l = 0;
                    scanf("%d", &l);
                    lans = max(lans, l + len);
                    updata(l, l + len - 1, 0);
                }
            }
            for(int i = 1; i < lans; i++)
            {
                putchar(ans[i]? ans[i]: 'a');
            }
            printf("\n");
        }
        return 0;
    }

用并查集标记已被访问区域,标记方式为,已被访问区域所有元素的根设为最近未被访问的元素,这样不仅标记了访问区域,访问时还提供一个到未访问区域的方向.

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int maxn = 2000100;
    
    char ans[maxn];
    char c[maxn];
    int fa[maxn];
    
    int f(int x)
    {
        return x == fa[x] ? x : fa[x] = f(fa[x]);
    }
    
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            int lans = 0;
            memset(ans,0,sizeof(ans));
            for(int i = 0; i < maxn; i++) fa[i] = i;
            while(n--)
            {
                int m = 0;
                scanf("%s%d", c, &m);
                int len = strlen(c);
                for(int i = 0; i < m; i++)
                {
                    int l = 0;
                    scanf("%d", &l);
                    lans = max(lans,l+len);
                    for(int j = f(l); j < l + len; j++)
                    {
                        fa[j] = max(f(l + len),fa[j]);
                        ans[j] = c[j-l];
                    }
                }
            }
            for(int i = 1; i < lans; i++)
            {
                putchar(ans[i]? ans[i] : 'a');
            }
            printf("\n");
        }
        return 0;
    }

[Codeforces Round _423 _Div. 2_ rated_ based on VK Cup Finals]: http://codeforces.com/contest/828
[VK CUP 2017 C 3 a 4 1 3 5 7 ab 2 1 5 ca 1 4String Reconstruction]: http://www.cnblogs.com/duanshen/p/7159970.html