[USACO 2017 Open Gold] Tutorial

Link:

A:

由于每个颜色只染色一次就确定了所有要染色的区间

要求染色的次数其实就是求区间最多嵌套多少层，如果有区间相交则无解

以上操作明显可以将左端点排序后用栈来维护

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define pb push_back

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

struct node{int x,d,col;};

node dat[MAXN];int st[MAXN],top;

int n,x,l[MAXN],r[MAXN],cur,res,tot;

bool cmp(node a,node b){return a.x==b.x?a.d<b.d:a.x<b.x;}

int main()

{

    scanf("%d",&n);

    memset(l,0x3f,sizeof(l));

    for(int i=;i<=n;i++)

    {

        scanf("%d",&x);

        l[x]=min(l[x],i),r[x]=max(r[x],i);

        if(!x) dat[++tot]=node{i,,};

    }

    for(int i=;i<=n;i++)

        if(r[i]) dat[++tot]=node{l[i],,i},dat[++tot]=node{r[i],,i};

    sort(dat+,dat+tot+,cmp);

    for(int i=;i<=tot;i++)

    {//注意0代表没有颜色要特殊处理

        if(!dat[i].col)

        {

            if(top) return puts("-1"),;

            else continue;

        }

        if(!dat[i].d)

            st[++top]=dat[i].col,cur++;

        else

        {

            if(dat[i].col!=st[top])

                return puts("-1"),;

            top--;cur--;

        }

        res=max(res,cur);

    }

    printf("%d",res);

    return ;

}

Problem A

注意零代表没有颜色要特殊处理……

B:

涉及字符串匹配想到哈希，结果一开始写成了$O(n^3*log(n))$

由于最外层的字符串长度的可行性是单调的，二分后可优化为$O(n^2*log(n)^2)$

但上述的复杂度是可以继续优化的

使用$two pointers$来利用单调性，每次可行就移动左端点，否则移动右端点

这样可以只检验$2*n$个字符串，复杂度降到了$O(2*n^2*log(n))$

同时该题也可以每次暴力构造$Trie$树来进行匹配，复杂度为$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

#define X first

#define RG register

#define Y second

#define pb push_back

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

typedef unsigned long long ull;

const int MAXN=1e3+,base=;

ull hs[MAXN][MAXN],pre[MAXN];

int n,m,f;char s[MAXN];

map<ull,int> mp;

bool check(int x)

{

    for(int i=x;i<=m;i++)

    {

        mp.clear();f=;

        for(RG int k=;k<=n;k++)

            mp[hs[k][i]-hs[k][i-x]*pre[x]]=;

        for(RG int k=n+;k<=*n;k++)

            if(mp[hs[k][i]-hs[k][i-x]*pre[x]]){f=;break;}

        if(f) return true;

    }

    return false;

}

int main()

{

    scanf("%d%d",&n,&m);

    pre[]=;

    for(RG int i=;i<=m;i++) pre[i]=pre[i-]*base;

    for(RG int i=;i<=*n;i++)

    {

        scanf("%s",s+);

        for(RG int j=;j<=m;j++)

            hs[i][j]=hs[i][j-]*base+(s[j]-'A');

    }

    int l=,r=m;

    while(l<=r)

    {

        int mid=(l+r)>>;

        if(check(mid)) r=mid-;

        else l=mid+;

    }

    printf("%d",l);

    return ;

}

Problem B

$two pointers$对比二分的优越之处就在于其能更及时的纠错

如果当前长度不行就直接加长，而二分则要将该长度的所有字符串都检验过再进行调整

巴特西

[USACO 2017 Open Gold] Tutorial

Link:

A:

B:

最新文章

热门文章