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

Nguyên bản được gửi bởi
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 100001
map<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);
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;
}
}
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