[C++] [Góp ý] SEARCH - PRE VNOI 2012 tại Hải Phòng

[VTA1011]

LINK ĐỀ BÀI Ở ĐÂY: http://vn.spoj.com/problems/SEARCH/
Bài này thuật toán của mình là xét một đoạn u -> v liên tiếp với u và v là 2 đầu mút chỉ số của dãy con thuộc đoạn c, xét trong đoạn u -> v đã có đủ phần tử của tập A hay chưa, nếu đủ rồi thì update res=max(res,v-u+1)

code của mình như thế này nhưng mà chỉ được 90 điểm, hình như không phải bị TLE thì phải, ai biết mình sai ở đâu thì chỉ mình với:

#include <iostream>#include <cstdio>#include <map> using namespace std;#define nmax 100001map<int,int> dd;int m,n,p,x;int dkn=0,c[nmax],a[nmax];int res=-1; int main(){    //freopen("SEARCH.INP","r",stdin);    cin>>m>>n>>p;    for(int i=1;i<=m;++i)    {        scanf("%d",&x);        if(dd[x]==0)        {            dd[x]=1;            dkn++;            a[dkn]=x;        }    }    for(int i=1;i<=n;++i)    {        scanf("%d",&x);        dd[x]=2;    }    for(int i=1;i<=p;++i) scanf("%d",&c[i]);    for(int i=1;i<=p;++i)        if(dd[c[i]]!=2)    {        int u=i;        int v=i;        bool ok=false;        for(int j=i+1;j<=p;++j)            if(dd[c[j]]==2 || j==p)            {                v=j;                break;            }        if(v==p && dd[v]!=2) ok=true;        if(ok==false) v--;        if(v-u+1>=dkn)        {            map<int,int> f;            for(int j=u;j<=v;++j) f[c[j]]++;            bool ok=true;            for(int j=1;j<=dkn;++j) if(f[a[j]]==0) {ok=false; break;}            if(ok==true) res=max(res,v-u+1);        }        i=v;    }    cout<<res;}

[misaka9982]

bài này hình như tle nó không hiện hay sao ấy

- - - Nội dung đã được cập nhật ngày 14-09-2015 lúc 04:43 AM - - -

LINK ĐỀ BÀI Ở ĐÂY: http://vn.spoj.com/problems/SEARCH/
Bài này thuật toán của mình là xét một đoạn u -> v liên tiếp với u và v là 2 đầu mút chỉ số của dãy con thuộc đoạn c, xét trong đoạn u -> v đã có đủ phần tử của tập A hay chưa, nếu đủ rồi thì update res=max(res,v-u+1)

code của mình như thế này nhưng mà chỉ được 90 điểm, hình như không phải bị TLE thì phải, ai biết mình sai ở đâu thì chỉ mình với:

#include <iostream>#include <cstdio>#include <map> using namespace std;#define nmax 100001map<int,int> dd;int m,n,p,x;int dkn=0,c[nmax],a[nmax];int res=-1; int main(){    //freopen("SEARCH.INP","r",stdin);    cin>>m>>n>>p;    for(int i=1;i<=m;++i)    {        scanf("%d",&x);        if(dd[x]==0)        {            dd[x]=1;            dkn++;            a[dkn]=x;        }    }    for(int i=1;i<=n;++i)    {        scanf("%d",&x);        dd[x]=2;    }    for(int i=1;i<=p;++i) scanf("%d",&c[i]);    for(int i=1;i<=p;++i)        if(dd[c[i]]!=2)    {        int u=i;        int v=i;        bool ok=false;        for(int j=i+1;j<=p;++j)            if(dd[c[j]]==2 || j==p)            {                v=j;                break;            }        if(v==p && dd[v]!=2) ok=true;        if(ok==false) v--;        if(v-u+1>=dkn)        {            map<int,int> f;            for(int j=u;j<=v;++j) f[c[j]]++;            bool ok=true;            for(int j=1;j<=dkn;++j) if(f[a[j]]==0) {ok=false; break;}            if(ok==true) res=max(res,v-u+1);        }        i=v;    }    cout<<res;}

bài này dùng chạy biến thì hay hơn
ban đầu cho low = 1, high = 1;
kiểm tra thằng c[low] xem nó có thoả mãn nằm trong dãy a và không nằm trong dãy b hay không (bài này dữ liệu <= 10^ 5 nên cx chẳng cần dùng map làm gì)
nếu c[low] không thỏa mãn thì đẩy low lên rồi gán high = low

if(!check[c[low]]) {low++; high = low}; // check(x) là hàm kiểm tra x thuộc a và ko thuộc b hay không

còn về phần high thì
một khi mà cái low thỏa mãn đk rồi thì cứ đẩy high đến khi nào c[high] không thỏa mãn đk nữa thì thôi =))

if(!check[c[low]]) {low++; high = low};
else while(check(c[high])) high++;
res = max(res, high - low); // vì khi này c[high] không thỏa mãn đk nữa
low = high; // lại tiếp tục đến khi đi hết dãy c thì thôi