Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 2 trên tổng số 2 kết quả

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

  1. #1
    Ngày gia nhập
    02 2014
    Nơi ở
    Hạ Long, Vietnam
    Bài viết
    20

    Mặc định [C++] [Góp ý] SEARCH - PRE VNOI 2012 tại Hải Phòng

    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:

    C++ Code:
    1. #include <iostream>
    2. #include <cstdio>
    3. #include <map>
    4.  
    5. using namespace std;
    6. #define nmax 100001
    7. map<int,int> dd;
    8. int m,n,p,x;
    9. int dkn=0,c[nmax],a[nmax];
    10. int res=-1;
    11.  
    12. int main()
    13. {
    14.     //freopen("SEARCH.INP","r",stdin);
    15.     cin>>m>>n>>p;
    16.     for(int i=1;i<=m;++i)
    17.     {
    18.         scanf("%d",&x);
    19.         if(dd[x]==0)
    20.         {
    21.             dd[x]=1;
    22.             dkn++;
    23.             a[dkn]=x;
    24.         }
    25.     }
    26.     for(int i=1;i<=n;++i)
    27.     {
    28.         scanf("%d",&x);
    29.         dd[x]=2;
    30.     }
    31.     for(int i=1;i<=p;++i) scanf("%d",&c[i]);
    32.     for(int i=1;i<=p;++i)
    33.         if(dd[c[i]]!=2)
    34.     {
    35.         int u=i;
    36.         int v=i;
    37.         bool ok=false;
    38.         for(int j=i+1;j<=p;++j)
    39.             if(dd[c[j]]==2 || j==p)
    40.             {
    41.                 v=j;
    42.                 break;
    43.             }
    44.         if(v==p && dd[v]!=2) ok=true;
    45.         if(ok==false) v--;
    46.         if(v-u+1>=dkn)
    47.         {
    48.             map<int,int> f;
    49.             for(int j=u;j<=v;++j) f[c[j]]++;
    50.             bool ok=true;
    51.             for(int j=1;j<=dkn;++j) if(f[a[j]]==0) {ok=false; break;}
    52.             if(ok==true) res=max(res,v-u+1);
    53.         }
    54.         i=v;
    55.     }
    56.     cout<<res;
    57. }
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    09 2015
    Bài viết
    6

    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 - - -

    Trích dẫn Nguyên bản được gửi bởi VTA1011 Xem bài viết
    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:

    C++ Code:
    1. #include <iostream>
    2. #include <cstdio>
    3. #include <map>
    4.  
    5. using namespace std;
    6. #define nmax 100001
    7. map<int,int> dd;
    8. int m,n,p,x;
    9. int dkn=0,c[nmax],a[nmax];
    10. int res=-1;
    11.  
    12. int main()
    13. {
    14.     //freopen("SEARCH.INP","r",stdin);
    15.     cin>>m>>n>>p;
    16.     for(int i=1;i<=m;++i)
    17.     {
    18.         scanf("%d",&x);
    19.         if(dd[x]==0)
    20.         {
    21.             dd[x]=1;
    22.             dkn++;
    23.             a[dkn]=x;
    24.         }
    25.     }
    26.     for(int i=1;i<=n;++i)
    27.     {
    28.         scanf("%d",&x);
    29.         dd[x]=2;
    30.     }
    31.     for(int i=1;i<=p;++i) scanf("%d",&c[i]);
    32.     for(int i=1;i<=p;++i)
    33.         if(dd[c[i]]!=2)
    34.     {
    35.         int u=i;
    36.         int v=i;
    37.         bool ok=false;
    38.         for(int j=i+1;j<=p;++j)
    39.             if(dd[c[j]]==2 || j==p)
    40.             {
    41.                 v=j;
    42.                 break;
    43.             }
    44.         if(v==p && dd[v]!=2) ok=true;
    45.         if(ok==false) v--;
    46.         if(v-u+1>=dkn)
    47.         {
    48.             map<int,int> f;
    49.             for(int j=u;j<=v;++j) f[c[j]]++;
    50.             bool ok=true;
    51.             for(int j=1;j<=dkn;++j) if(f[a[j]]==0) {ok=false; break;}
    52.             if(ok==true) res=max(res,v-u+1);
    53.         }
    54.         i=v;
    55.     }
    56.     cout<<res;
    57. }
    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
    Code:
    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 =))
    Code:
    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
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn