首页 > 代码库 > 才吉布提

才吉布提

C - String Reconstruction

我只服这个题原字符串的范围,刚开始没注意一直wa,以为代码写错,后来网上找了份代码对拍,发现数据范围写小了,ki最大取到1e6,加上字符串最大1e6,所以范围是2e6。

技术分享
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char s[maxn];
char init[maxn];
int main()
{
    int n,k,pre,x;
    cin>>n;
    memset(init,0,sizeof(init));
    int maxlen = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>s>>k;
        int slen = strlen(s);
        pre = -1,x;
        int startpos = 0;
        for(int j=1;j<=k;j++)
        {
            cin>>x;
            startpos = max(pre+1,x);
            for(int p=startpos-x;p<slen;p++)
            {
                init[p+x] = s[p];
            }
            pre = x+slen-1;
        }
        maxlen = max(maxlen,pre);
    }
    for(int i=1;i<=maxlen;i++)
    {
        if(init[i]==0)
        {
            init[i] = a;
        }
    }
    cout<<init+1<<endl;
    return 0;
}
Code

 

才吉布提