作者归档：Eurce

[POJ 3067]

树状数组

题意是，在左右两边各有m和n个点的二分图中有k条边(xi,yi)，问这k条边之间两两相交了多少次（端点不算）。

首先读入每条边，然后按x由小到大排序，初始化ans=0，然后重复：
（1）将xi连续相同的一组边加入图中；
（2）对下一组中的每条边j，求与之前的边相交的次数，由于之前的边必有x<xj，因此求y>yj的边数即可。
最后输出ans即为答案。

其中的（1）和（2）可以用树状数组来实现：通过O(lgn)地修改、询问，可以使总时间复杂度达到O(klgn)。

树状数组的实现有个小技巧，x&-x可以O(1)地取到x最低位的1。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int t,m,n,el,ed[1000001];
long long ans;

struct E
{
    int w,e;
    bool operator < (const E &p) const
    {
        return w<p.w;
    }
}e[1000000];

void init()
{
    int i;
    ans=0;
    memset(ed,0,sizeof ed);
    for(i=0;i<el;i++)
        scanf("%d%d",&e[i].w,&e[i].e);
    sort(e,e+el);
}

void ins(int i)
{
    while(i<=n)
    {
        ed[i]++;
        i+=i&-i;
    }
}

int que(int i)
{
    int s=0;
    while(i)
    {
        s+=ed[i];
        i-=i&-i;
    }
    return s;
}

void solve()
{
    int i,j,k,l;
    for(i=0;i<el&&e[i].w==e[0].w;i++)
        ins(e[i].e);
    for(;i<el;i=j)
    {
        for(j=i;j<el&&e[j].w==e[i].w;j++)
            ans+=i-que(e[j].e);
        for(j=i;j<el&&e[j].w==e[i].w;j++)
            ins(e[j].e);
    }
    printf("Test case %d: %lld\n",++t,ans);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d%d",&n,&m,&el))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int t,m,n,el,ed[1000001];

long long ans;

struct E

{

int w,e;

bool operator < (const E &p) const

{

return w<p.w;

}

}e[1000000];

void init()

{

int i;

ans=0;

memset(ed,0,sizeof ed);

for(i=0;i<el;i++)

scanf("%d%d",&e[i].w,&e[i].e);

sort(e,e+el);

}

void ins(int i)

{

while(i<=n)

{

ed[i]++;

i+=i&-i;

}

int que(int i)

{

int s=0;

while(i)

{

s+=ed[i];

i-=i&-i;

}

return s;

}

void solve()

{

int i,j,k,l;

for(i=0;i<el&&e[i].w==e[0].w;i++)

ins(e[i].e);

for(;i<el;i=j)

{

for(j=i;j<el&&e[j].w==e[i].w;j++)

ans+=i-que(e[j].e);

for(j=i;j<el&&e[j].w==e[i].w;j++)

ins(e[j].e);

}

printf("Test case %d: %lld\n",++t,ans);

}

int main()

{

scanf("%*d");

while(~scanf("%d%d%d",&n,&m,&el))

{

init();

solve();

}

return 0;

}

[POJ 1639]

发表回复

Picnic Planning

度限制最小生成树

给出最多包含最多21个结点的无向图，边权值为正数，求这样的一棵最小生成树：与结点1相连的树边不超过m条。

解法是，先从图中剔除结点1，求最小生成森林。然后重复：遍历结点1相连的所有边，找（1）能联通某森林的最小边；（2）若（1）边不存在，则找加边之后作破圈操作能使树权减少最多的边。直到m次加边机会耗尽或者加边也无法减少树权。

一些小技巧：题目数据量很小，所以邻接矩阵也可以，但如果像我这样习惯用邻接表的话，对树边作标记的时候两个方向的边要同时标记。而由于加边时无向边对应的邻接表项是成对插入的，也即编号仅有最末位不同，所以^1就可以得到另一个方向的边了。这种用邻接表时修改边信息的做法很常用，最开始是在做费用流的题目时学到的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;

int n,m,ans;
int b[22],f[22],el,hd[22],ei[484],eil;
map<string,int>M;
string s;

struct E
{
    int u,v,d,b,p;
}e[484];

struct CP
{
    bool operator () (const int &p,const int &q) const
    {
        return e[p].d<e[q].d;
    }
};

inline void adde(int u,int v,int d)
{
    ei[eil++]=el;
    e[el].u=u; e[el].v=v; e[el].d=d; 
    e[el].b=0; e[el].p=hd[u]; hd[u]=el++;
    e[el].u=v; e[el].v=u; e[el].d=d; 
    e[el].b=0; e[el].p=hd[v]; hd[v]=el++;
}

int fi(int i)
{
    if(f[i]<0)
        return i;
    else
        return f[i]=fi(f[i]);
}

int un(int a,int b)
{
    int fa=fi(a),fb=fi(b);
    if(fa==fb)
        return 0;
    int na=f[fa],nb=f[fb];
    if(na<nb)
    {
        f[fa]+=nb;
        f[fb]=fa;
    }
    else
    {
        f[fb]+=na;
        f[fa]=fb;
    }
    return 1;
}

void init()
{
    int i,j,k,l=1;
    memset(f,-1,sizeof f);
    memset(hd,-1,sizeof hd);
    el=eil=ans=0;
    M.clear();
    M["Park"]=l++;
    while(m--)
    {
        cin>>s;
        if(M[s]==0)
            M[s]=i=l++;
        else
            i=M[s];
        cin>>s;
        if(M[s]==0)
            M[s]=j=l++;
        else
            j=M[s];
        cin>>k;
        adde(i,j,k);
    }
    sort(ei,ei+eil,CP());
    cin>>m;
}

int dfs(int i,int f,int mx,int mxl,int t)
{
    int j,k,l;
    if(i==1)
    {
        if(t)
        {
            ans-=mx;
            e[mxl].b=0;
            e[mxl^1].b=0;
        }
        return mx;
    }
    b[i]=1;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(!e[l].b)
            continue;
        if(b[j]||j==f)
            continue;
        if(mx<e[l].d)
        {
            if(k=dfs(j,i,e[l].d,l,t))
                return k;
        }
        else
        {
            if(k=dfs(j,i,mx,mxl,t))
                return k;
        }
    }
    b[i]=0;
    return 0;
}

void solve()
{
    int i,j,k,l,mxl;
    for(i=0;i<eil;i++)
    {
        if(e[ei[i]].u==1||e[ei[i]].v==1)
            continue;
        j=e[ei[i]].u;
        k=e[ei[i]].v;
        if(un(j,k))
        {
            e[ei[i]].b=1;
            e[ei[i]^1].b=1;
            ans+=e[ei[i]].d;
        }
    }
    while(m)
    {
        k=-1;
        for(l=hd[1];l!=-1;l=e[l].p)
        {
            memset(b,0,sizeof b);
            if(e[l].b)
                continue;
            e[l].b=e[l^1].b=1;
            ans+=e[l].d;
            j=dfs(e[l].v,1,e[l].d,l,0);
            if(j!=e[l].d)
            {
                if(!j)
                    j=0x7fffffff-e[l].d;
                if(j-e[l].d>k)
                {
                    k=j-e[l].d;
                    mxl=l;
                }
            }
            e[l].b=e[l^1].b=0;
            ans-=e[l].d;
        }
        if(k==-1)
            break;
        memset(b,0,sizeof b);
        e[mxl].b=e[mxl^1].b=1;
        ans+=e[mxl].d;
        dfs(e[mxl].v,1,e[mxl].d,l,1);
        m--;
    }
    printf("Total miles driven: %d\n",ans);
}

int main()
{
    while(cin>>m)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<map>

using namespace std;

int n,m,ans;

int b[22],f[22],el,hd[22],ei[484],eil;

map<string,int>M;

string s;

struct E

{

int u,v,d,b,p;

}e[484];

struct CP

{

bool operator () (const int &p,const int &q) const

{

return e[p].d<e[q].d;

}

};

inline void adde(int u,int v,int d)

{

ei[eil++]=el;

e[el].u=u; e[el].v=v; e[el].d=d;

e[el].b=0; e[el].p=hd[u]; hd[u]=el++;

e[el].u=v; e[el].v=u; e[el].d=d;

e[el].b=0; e[el].p=hd[v]; hd[v]=el++;

}

int fi(int i)

{

if(f[i]<0)

return i;

else

return f[i]=fi(f[i]);

}

int un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb)

return 0;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

return 1;

}

void init()

{

int i,j,k,l=1;

memset(f,-1,sizeof f);

memset(hd,-1,sizeof hd);

el=eil=ans=0;

M.clear();

M["Park"]=l++;

while(m--)

{

cin>>s;

if(M[s]==0)

M[s]=i=l++;

else

i=M[s];

cin>>s;

if(M[s]==0)

M[s]=j=l++;

else

j=M[s];

cin>>k;

adde(i,j,k);

}

sort(ei,ei+eil,CP());

cin>>m;

}

int dfs(int i,int f,int mx,int mxl,int t)

{

int j,k,l;

if(i==1)

{

if(t)

{

ans-=mx;

e[mxl].b=0;

e[mxl^1].b=0;

}

return mx;

}

b[i]=1;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(!e[l].b)

continue;

if(b[j]||j==f)

continue;

if(mx<e[l].d)

{

if(k=dfs(j,i,e[l].d,l,t))

return k;

}

else

{

if(k=dfs(j,i,mx,mxl,t))

return k;

}

b[i]=0;

return 0;

}

void solve()

{

int i,j,k,l,mxl;

for(i=0;i<eil;i++)

{

if(e[ei[i]].u==1||e[ei[i]].v==1)

continue;

j=e[ei[i]].u;

k=e[ei[i]].v;

if(un(j,k))

{

e[ei[i]].b=1;

e[ei[i]^1].b=1;

ans+=e[ei[i]].d;

}

while(m)

{

k=-1;

for(l=hd[1];l!=-1;l=e[l].p)

{

memset(b,0,sizeof b);

if(e[l].b)

continue;

e[l].b=e[l^1].b=1;

ans+=e[l].d;

j=dfs(e[l].v,1,e[l].d,l,0);

if(j!=e[l].d)

{

if(!j)

j=0x7fffffff-e[l].d;

if(j-e[l].d>k)

{

k=j-e[l].d;

mxl=l;

}

e[l].b=e[l^1].b=0;

ans-=e[l].d;

}

if(k==-1)

break;

memset(b,0,sizeof b);

e[mxl].b=e[mxl^1].b=1;

ans+=e[mxl].d;

dfs(e[mxl].v,1,e[mxl].d,l,1);

m--;

}

printf("Total miles driven: %d\n",ans);

}

int main()

{

while(cin>>m)

{

init();

solve();

}

return 0;

}

[SPOJ 220]

发表回复

Relevant Phrases of Annihilation

后缀数组

给出最多10个字符串，每个字符串长度最多10,000，求这样一个子串的长度：
(1) 在每个字符串中非重叠地出现了两次；
(2) 长度最长。

可以将10个字符串连接在一起，其中每个连接位置用一个大于128的唯一值来隔开不同字符串，然后求后缀数组。随后，可以二分答案，对于某个长度值m，判断：对于h数组中值>=m的某连续区间内，求每个子串对应的原字符串最左和最右子串的位置，若每个字符串中左右子串的位置差>=m，即两个子串非重叠，return 1。而每次某区间内无法满足时，直接从该区间下一个位置开始检查h数组。由此对于每个长度值进行判断的时间复杂度是O(n)的，这里n是后缀数组的长度，最多100,000。总体时间复杂度便是O(nlgn)的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 100100

int t,n,b[M],r[M],sa[M],h[M],mxh,li[10],ri[10];
int d[M],wa[M],wb[M],wv[M],ws[M];
char s[M];

inline int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
 
void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    memset(ws,0,sizeof ws);
    for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(i=1;i<m;i++) ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p)
    {
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        memset(ws,0,sizeof ws);
        for(i=0;i<n;i++) ws[wv[i]]++;
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}

void init()
{
    int i,j,k,l;
    n=0;
    mxh=0;
    for(i=0;i<t;i++)
    {
        scanf("%s",s+n);
        l=strlen(s+n);
        mxh=max(mxh,l);
        for(j=n;j<n+l;j++)
        {
            b[j]=i;
            d[j]=s[j];
        }
        b[j]=i;
        d[j]=128+i;
        n+=l+1;
    }
    d[--n]=0;
    da(d,sa,n+1,max(n+1,228));
    for(i=0;i<n;i++)
        r[sa[i+1]]=i;
    for(i=0;i<n;i++)
        sa[r[i]]=i;
    for(i=k=0;i<n;i++)
    {
        if(!r[i])
            continue;
        for(j=sa[r[i]-1],k?k--:0;d[i+k]==d[j+k];k++);
        h[r[i]]=k;
    }
    n=n+1-t;
}

int calc(int m)
{
    int i,j,k,l;
    for(i=1;i<n;)
    {
        if(h[i]<m)
        {
            i++;
            continue;
        }
        memset(li,127,sizeof li);
        memset(ri,-1,sizeof ri);
        li[b[sa[i-1]]]=min(li[b[sa[i-1]]],sa[i-1]);
        ri[b[sa[i-1]]]=max(ri[b[sa[i-1]]],sa[i-1]);
        for(j=i;h[j]>=m;j++)
        {
            li[b[sa[j]]]=min(li[b[sa[j]]],sa[j]);
            ri[b[sa[j]]]=max(ri[b[sa[j]]],sa[j]);
        }
        for(k=0;k<t;k++)
        {
            if(ri[k]-li[k]<m)
                break;
        }
        if(k==t)
            return 1;
        i=j;
    }
    return 0;
}

void solve()
{
    int i,j,k,l,h,m;
    for(l=0,h=mxh;l<h;)
    {
        m=l+h+1>>1;
        if(calc(m))
            l=m;
        else
            h=m-1;
    }
    printf("%d\n",l);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&t))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 100100

int t,n,b[M],r[M],sa[M],h[M],mxh,li[10],ri[10];

int d[M],wa[M],wb[M],wv[M],ws[M];

char s[M];

inline int cmp(int *r,int a,int b,int l)

{

return r[a]==r[b]&&r[a+l]==r[b+l];

}

void da(int *r,int *sa,int n,int m)

{

int i,j,p,*x=wa,*y=wb,*t;

memset(ws,0,sizeof ws);

for(i=0;i<n;i++) ws[x[i]=r[i]]++;

for(i=1;i<m;i++) ws[i]+=ws[i-1];

for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;

for(j=1,p=1;p<n;j*=2,m=p)

{

for(p=0,i=n-j;i<n;i++) y[p++]=i;

for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

for(i=0;i<n;i++) wv[i]=x[y[i]];

memset(ws,0,sizeof ws);

for(i=0;i<n;i++) ws[wv[i]]++;

for(i=1;i<m;i++) ws[i]+=ws[i-1];

for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)

x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

}

void init()

{

int i,j,k,l;

n=0;

mxh=0;

for(i=0;i<t;i++)

{

scanf("%s",s+n);

l=strlen(s+n);

mxh=max(mxh,l);

for(j=n;j<n+l;j++)

{

b[j]=i;

d[j]=s[j];

}

b[j]=i;

d[j]=128+i;

n+=l+1;

}

d[--n]=0;

da(d,sa,n+1,max(n+1,228));

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

r[sa[i+1]]=i;

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

sa[r[i]]=i;

for(i=k=0;i<n;i++)

{

if(!r[i])

continue;

for(j=sa[r[i]-1],k?k--:0;d[i+k]==d[j+k];k++);

h[r[i]]=k;

}

n=n+1-t;

}

int calc(int m)

{

int i,j,k,l;

for(i=1;i<n;)

{

if(h[i]<m)

{

i++;

continue;

}

memset(li,127,sizeof li);

memset(ri,-1,sizeof ri);

li[b[sa[i-1]]]=min(li[b[sa[i-1]]],sa[i-1]);

ri[b[sa[i-1]]]=max(ri[b[sa[i-1]]],sa[i-1]);

for(j=i;h[j]>=m;j++)

{

li[b[sa[j]]]=min(li[b[sa[j]]],sa[j]);

ri[b[sa[j]]]=max(ri[b[sa[j]]],sa[j]);

}

for(k=0;k<t;k++)

{

if(ri[k]-li[k]<m)

break;

}

if(k==t)

return 1;

i=j;

}

return 0;

}

void solve()

{

int i,j,k,l,h,m;

for(l=0,h=mxh;l<h;)

{

m=l+h+1>>1;

if(calc(m))

l=m;

else

h=m-1;

}

printf("%d\n",l);

}

int main()

{

scanf("%*d");

while(~scanf("%d",&t))

{

init();

solve();

}

return 0;

}

很好的题目……这题也是罗穗骞论文里推荐的最后一道例题了。虽然还是没太看懂他的DA和DC3，不过确实学到了很有趣的知识。

ps：也推荐一个最近发现的汽车网站：38号测试中心。

[POJ 3415]

发表回复

Common Substrings

后缀数组

给出两个长度最多100,000的字符串s和t，求s和t中所有长度大于K的相同子串配对数。

做法首先是将s[sl]置最大值，并将t放在s[sl]后，计算后缀数组。接下来需要顺序遍历h[n]，遍历到位置i时，如果sa[i]属于s，那么找出0到i-1中所有属于t且与s公共后缀长度>=m的子串，并将累计的配对数记录以类似计数排序的方式记录为ab[n]中，sa[i]对应满足题意的配对总数即为ab[h[i]]。如果sa[i+1]也属于s，且h[i+1]>=h[i]，那么sa[i+1]对应的配对数和sa[i]是相同的；若h[i+1]<h[i]，那么也能根据ab[h[i+1]]来O(1)地得到结果。

这里在更新ab[n]时本来应该是分成ab[2][n]，分别对属于s和属于t的后缀分别维护配对总数的，这样根据平摊分析构造ab的总时间复杂度就是O(n)，但实现起来细节太多了容易错。而现在这种偷懒的做法会导致当sa[i]、sa[i+1]、sa[i+2]……分别属于s、t、s……且都满足h[]>=m时，需要反复重新计算ab，但这种情况实际上较少出现，所以并不会慢上太多。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define M 200002

int sl,n,m,r[M],sa[M],h[M],ei[M];
int d[M],wa[M],wb[M],wv[M],ws[M];
char s[M],b[M];
ll ans,ab[M];

inline int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}

void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) ws[i]=0;
    for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(i=1;i<m;i++) ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p)
    {
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        for(i=0;i<m;i++) ws[i]=0;
        for(i=0;i<n;i++) ws[wv[i]]++;
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}

void init()
{
    memset(ab,0,sizeof ab);
    int i,j,k,l;
    ans=0;
    scanf("%s",s);
    sl=strlen(s);
    s[sl]=126;
    scanf("%s",s+sl+1);
    n=sl+1+strlen(s+sl+1);
    for(i=0;i<=n;i++)
        d[i]=s[i];
    da(d,sa,n+1,max(128,n+1));
    for(i=0;i<n;i++)
        r[sa[i+1]]=i;
    for(i=0;i<n;i++)
        sa[r[i]]=i;
    for(i=k=0;i<n;i++)
    {
        if(!r[i])
            continue;
        for(j=sa[r[i]-1],k?k--:0;s[i+k]==s[j+k];k++);
        h[r[i]]=k;
    }
    for(i=0;i<n;i++)
    {
        if(sa[i]<sl)
            b[i]=0;
        else
            b[i]=1;
    }
}

void solve()
{
    int i,j,k,l;
    for(i=1,k=0;i<n;i++)
    {
        if(b[i-1]!=b[i])
        {
            k=h[i];
            for(j=0;j<=h[i];j++)
                ab[j]=0;
            for(j=i,l=h[j];j&&l>=m&&h[j]>=m;)
            {
                if(b[j-1]!=b[i])
                    ab[l]++;
                j--;
                l=min(l,h[j]);
            }
            for(j=h[i]-1;j>=m;j--)
                ab[j]+=ab[j+1];
            for(j=m+1;j<=h[i];j++)
                ab[j]+=ab[j-1];
        }
        else
            k=min(k,h[i]);
        ans+=ab[k];
    }
    printf("%lld\n",ans);
}

int main()
{
    while(~scanf("%d",&m)&&m)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define M 200002

int sl,n,m,r[M],sa[M],h[M],ei[M];

int d[M],wa[M],wb[M],wv[M],ws[M];

char s[M],b[M];

ll ans,ab[M];

inline int cmp(int *r,int a,int b,int l)

{

return r[a]==r[b]&&r[a+l]==r[b+l];

}

void da(int *r,int *sa,int n,int m)

{

int i,j,p,*x=wa,*y=wb,*t;

for(i=0;i<m;i++) ws[i]=0;

for(i=0;i<n;i++) ws[x[i]=r[i]]++;

for(i=1;i<m;i++) ws[i]+=ws[i-1];

for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;

for(j=1,p=1;p<n;j*=2,m=p)

{

for(p=0,i=n-j;i<n;i++) y[p++]=i;

for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

for(i=0;i<n;i++) wv[i]=x[y[i]];

for(i=0;i<m;i++) ws[i]=0;

for(i=0;i<n;i++) ws[wv[i]]++;

for(i=1;i<m;i++) ws[i]+=ws[i-1];

for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)

x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

}

void init()

{

memset(ab,0,sizeof ab);

int i,j,k,l;

ans=0;

scanf("%s",s);

sl=strlen(s);

s[sl]=126;

scanf("%s",s+sl+1);

n=sl+1+strlen(s+sl+1);

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

d[i]=s[i];

da(d,sa,n+1,max(128,n+1));

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

r[sa[i+1]]=i;

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

sa[r[i]]=i;

for(i=k=0;i<n;i++)

{

if(!r[i])

continue;

for(j=sa[r[i]-1],k?k--:0;s[i+k]==s[j+k];k++);

h[r[i]]=k;

}

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

{

if(sa[i]<sl)

b[i]=0;

else

b[i]=1;

}

void solve()

{

int i,j,k,l;

for(i=1,k=0;i<n;i++)

{

if(b[i-1]!=b[i])

{

k=h[i];

for(j=0;j<=h[i];j++)

ab[j]=0;

for(j=i,l=h[j];j&&l>=m&&h[j]>=m;)

{

if(b[j-1]!=b[i])

ab[l]++;

j--;

l=min(l,h[j]);

}

for(j=h[i]-1;j>=m;j--)

ab[j]+=ab[j+1];

for(j=m+1;j<=h[i];j++)

ab[j]+=ab[j-1];

}

else

k=min(k,h[i]);

ans+=ab[k];

}

printf("%lld\n",ans);

}

int main()

{

while(~scanf("%d",&m)&&m)

{

init();

solve();

}

return 0;

}

ps：上周刚赶完第二篇论文，以为可以稍微轻松点了，结果马上又被安排写专利…… 总不会到时候真的让我写第三篇吧？

ps2：另外，最近也在看毛姆的《月亮和六便士》。

Learning Emacs

发表回复

发生错误，请稍后重试。

[POJ 3264]

发表回复

Balanced Lineup

RMQ

题意是，有长度最多50,000的正整数序列，最多200,000次询问，对于每次询问(l, r)，需要输出下标[l, r]范围内序列最大值和最小值的差。

最近啃的是郭华阳的《RMQ与LCA问题》，敲了下基于倍增思想的ST算法。O(nlgn)预处理后，可以O(1)回答每次询问。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 100000

int n,q,mx[M][20],mn[M][20];

void init()
{
    memset(mn,127,sizeof mn);
    memset(mx,0,sizeof mx);
    int i,j,k,l;
    for(i=0;i<n;i++)
    {
        scanf("%d",&j);
        mx[i][0]=mn[i][0]=j;
    }
    for(k=l=1;l<n;k++,l<<=1)
    {
        for(i=0;i<n;i++)
        {
            mx[i][k]=max(mx[i][k-1],mx[i+l][k-1]);
            mn[i][k]=min(mn[i][k-1],mn[i+l][k-1]);
        }
    }
}

void solve()
{
    int i,j,k,l;
    while(q--)
    {
        scanf("%d%d",&i,&j);
        if(--i==--j)
        {
            puts("0");
            continue;
        }
        for(k=0,l=1;i+l<=j+1;k++,l<<=1);
        k--;
        l>>=1;
        printf("%d\n",max(mx[i][k],mx[j+1-l][k])
                -min(mn[i][k],mn[j+1-l][k]));
    }
}

int main()
{
    while(~scanf("%d%d",&n,&q))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 100000

int n,q,mx[M][20],mn[M][20];

void init()

{

memset(mn,127,sizeof mn);

memset(mx,0,sizeof mx);

int i,j,k,l;

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

{

scanf("%d",&j);

mx[i][0]=mn[i][0]=j;

}

for(k=l=1;l<n;k++,l<<=1)

{

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

{

mx[i][k]=max(mx[i][k-1],mx[i+l][k-1]);

mn[i][k]=min(mn[i][k-1],mn[i+l][k-1]);

}

void solve()

{

int i,j,k,l;

while(q--)

{

scanf("%d%d",&i,&j);

if(--i==--j)

{

puts("0");

continue;

}

for(k=0,l=1;i+l<=j+1;k++,l<<=1);

k--;

l>>=1;

printf("%d\n",max(mx[i][k],mx[j+1-l][k])

-min(mn[i][k],mn[j+1-l][k]));

}

int main()

{

while(~scanf("%d%d",&n,&q))

{

init();

solve();

}

return 0;

}

之前做这题用的是O(qlgn)的线段树：

#include<cstdio>

int n,q,ml,h[50000],mx,mn;

struct node
{
	int mx,mn;
	node *l,*r;
}mem[100000],*root;

void init(int L,int R,node *p)
{
	int m=L+R>>1;
	if(L==R)
	{
		p->mx=p->mn=h[m];
		return;
	}
	p->l=&mem[ml++];
	init(L,m,p->l);
	p->r=&mem[ml++];
	init(m+1,R,p->r);
	p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;
	p->mn=p->l->mn<p->r->mn?p->l->mn:p->r->mn;
}

void ins(int l,int r,int L,int R,node *p)
{
	int m=L+R>>1;
	if(l==L&&r==R)
	{
		mx=mx>p->mx?mx:p->mx;
		mn=mn<p->mn?mn:p->mn;
		return;
	}
	if(r<=m) ins(l,r,L,m,p->l);
	else if(l>m) ins(l,r,m+1,R,p->r);
	else
	{
		ins(l,m,L,m,p->l);
		ins(m+1,r,m+1,R,p->r);
	}
}

int main()
{
	int i,j,k;
	while(~scanf("%d%d",&n,&q))
	{
		ml=0;
		root=&mem[ml++];
		for(i=0;i<n;i++) scanf("%d",&h[i]);
		init(0,n-1,root);
		while(q--)
		{
			scanf("%d%d",&i,&j);
			mn=1000001;
			mx=0;
			ins(i-1,j-1,0,n-1,root);
			printf("%d\n",mx-mn);
		}
	}
	return 0;
}

#include<cstdio>

int n,q,ml,h[50000],mx,mn;

struct node

{

int mx,mn;

node *l,*r;

}mem[100000],*root;

void init(int L,int R,node *p)

{

int m=L+R>>1;

if(L==R)

{

p->mx=p->mn=h[m];

return;

}

p->l=&mem[ml++];

init(L,m,p->l);

p->r=&mem[ml++];

init(m+1,R,p->r);

p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;

p->mn=p->l->mn<p->r->mn?p->l->mn:p->r->mn;

}

void ins(int l,int r,int L,int R,node *p)

{

int m=L+R>>1;

if(l==L&&r==R)

{

mx=mx>p->mx?mx:p->mx;

mn=mn<p->mn?mn:p->mn;

return;

}

if(r<=m) ins(l,r,L,m,p->l);

else if(l>m) ins(l,r,m+1,R,p->r);

else

{

ins(l,m,L,m,p->l);

ins(m+1,r,m+1,R,p->r);

}

int main()

{

int i,j,k;

while(~scanf("%d%d",&n,&q))

{

ml=0;

root=&mem[ml++];

for(i=0;i<n;i++) scanf("%d",&h[i]);

init(0,n-1,root);

while(q--)

{

scanf("%d%d",&i,&j);

mn=1000001;

mx=0;

ins(i-1,j-1,0,n-1,root);

printf("%d\n",mx-mn);

}

return 0;

}

[POJ 2406]

发表回复

Power Strings

后缀数组（？）

题意是，给出一个最长1,000,000的字符串，求该字符串是否为某子串的完全重复，并输出最大的重复数。

……之前敲的快排二倍增完全没有任何AC的希望，贴了个基排二倍增TLE依旧，随后又颤抖着贴了一份DC3……2938ms刚好卡过……：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 2000010
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)

char s[M];
int n,d[M],sa[M],r[M],h[M];
int wa[M],wb[M],wv[M],ws[M];

int c0(int *r,int a,int b)
{
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}

int c12(int k,int *r,int a,int b)
{
    if(k==2)
        return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    else
        return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}

void sort(int *r,int *a,int *b,int n,int m)
{
     int i;
     for(i=0;i<n;i++) wv[i]=r[a[i]];
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[wv[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
     return;
}

void dc3(int *r,int *sa,int n,int m)
{
    int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0;i<n;i++)
        if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else for(i=0;i<tbc;i++) san[rn[i]]=i;
    for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
    for(i=0,j=0,p=0;i<ta && j<tbc;p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
    return;
}

void init()
{
    n=strlen(s);
    memset(d,0,sizeof d);
    memset(sa,0,sizeof sa);
    memset(r,0,sizeof r);
    memset(h,0,sizeof h);
    int i,j,k,l;
    for(i=0;i<n;i++)
        d[i]=s[i]-'a'+1;
    dc3(d,sa,n+1,max(128,n+1));
    for(i=1;i<=n;i++)
        r[sa[i]]=i-1;
    for(i=0;i<n;i++)
        sa[r[i]]=i;
    for(i=k=0;i<n;i++)
    {
        if(!r[i])
            continue;
        for(k?k--:0,j=sa[r[i]-1];r[i]&&s[i+k]==s[j+k];k++);
        h[r[i]]=k;
    }
    memset(s,0,sizeof s);
}

void solve()
{
    int i=n-h[r[0]];
    if(!r[0]||!h[r[0]]||h[r[0]]-h[r[i]]!=i||n%i)
    {
        puts("1");
        return;
    }
    printf("%d\n",n/i);
}

int main()
{
    while(~scanf("%s",s))
    {
        if(s[0]=='.'&&!s[1])
            break;
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 2000010

#define F(x) ((x)/3+((x)%3==1?0:tb))

#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)

char s[M];

int n,d[M],sa[M],r[M],h[M];

int wa[M],wb[M],wv[M],ws[M];

int c0(int *r,int a,int b)

{

return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];

}

int c12(int k,int *r,int a,int b)

{

if(k==2)

return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);

else

return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];

}

void sort(int *r,int *a,int *b,int n,int m)

{

int i;

for(i=0;i<n;i++) wv[i]=r[a[i]];

for(i=0;i<m;i++) ws[i]=0;

for(i=0;i<n;i++) ws[wv[i]]++;

for(i=1;i<m;i++) ws[i]+=ws[i-1];

for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];

return;

}

void dc3(int *r,int *sa,int n,int m)

{

int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;

r[n]=r[n+1]=0;

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

if(i%3!=0) wa[tbc++]=i;

sort(r+2,wa,wb,tbc,m);

sort(r+1,wb,wa,tbc,m);

sort(r,wa,wb,tbc,m);

for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)

rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;

if(p<tbc) dc3(rn,san,tbc,p);

else for(i=0;i<tbc;i++) san[rn[i]]=i;

for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;

if(n%3==1) wb[ta++]=n-1;

sort(r,wb,wa,ta,m);

for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;

for(i=0,j=0,p=0;i<ta && j<tbc;p++)

sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];

for(;i<ta;p++) sa[p]=wa[i++];

for(;j<tbc;p++) sa[p]=wb[j++];

return;

}

void init()

{

n=strlen(s);

memset(d,0,sizeof d);

memset(sa,0,sizeof sa);

memset(r,0,sizeof r);

memset(h,0,sizeof h);

int i,j,k,l;

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

d[i]=s[i]-'a'+1;

dc3(d,sa,n+1,max(128,n+1));

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

r[sa[i]]=i-1;

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

sa[r[i]]=i;

for(i=k=0;i<n;i++)

{

if(!r[i])

continue;

for(k?k--:0,j=sa[r[i]-1];r[i]&&s[i+k]==s[j+k];k++);

h[r[i]]=k;

}

memset(s,0,sizeof s);

}

void solve()

{

int i=n-h[r[0]];

if(!r[0]||!h[r[0]]||h[r[0]]-h[r[i]]!=i||n%i)

{

puts("1");

return;

}

printf("%d\n",n/i);

}

int main()

{

while(~scanf("%s",s))

{

if(s[0]=='.'&&!s[1])

break;

init();

solve();

}

return 0;

}

虽然罗穗骞神牛号称DC3实现得很精简……但是……这压行也太严重了吧……反正我是没怎么看懂……

另外贴一个之前自己写的KMP：

#include<cstdio>
#include<cstring>

int sl,p[1000000],d[1000000];
char s[1000001];

int main()
{
	int i,j,k,l;
	while(~scanf("%s",s))
	{
		sl=strlen(s);
		if(sl==1&&s[0]=='.') break;
		p[0]=-1;
		d[0]=1;
		for(i=1,j=-1;i<sl;i++)
		{
			while(j!=-1&&s[i]!=s[j+1]) j=p[j];
			if(s[i]==s[j+1]) j++;
			if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;
			else d[i]=1;
		}
		printf("%d\n",d[sl-1]);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int sl,p[1000000],d[1000000];

char s[1000001];

int main()

{

int i,j,k,l;

while(~scanf("%s",s))

{

sl=strlen(s);

if(sl==1&&s[0]=='.') break;

p[0]=-1;

d[0]=1;

for(i=1,j=-1;i<sl;i++)

{

while(j!=-1&&s[i]!=s[j+1]) j=p[j];

if(s[i]==s[j+1]) j++;

if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;

else d[i]=1;

}

printf("%d\n",d[sl-1]);

}

return 0;

}

同样是O(n)的复杂度，却只跑了219ms。

总感觉后缀数组是重剑无锋呢，现在的功力要驾驭实在是比较吃力……

[POJ 1743]

发表回复

Musical Theme

后缀数组。

这两天都在研究罗穗骞神牛的《后缀数组——处理字符串的有力工具》，很久以前就听过的数据结构，现在总算用到了。

题意是给出一个长20000的数组，值范围是1到88，问是否存在长度大于等于5的一个子串，其满足“变调”后非重叠地出现在原数组的其他位置。这里变调的意思是整个子串同时加上或减去某个值。

分析题意后可以发现，如果取值间的差值建立一个新数组，那么新数组上长度为m的非重叠重复出现的子串对应着原数组中长度为m+1的子串。这样就解决了“变调”的问题。

进一步分析，可以发现可以二分答案：对于某个值l，当m<=l时满足题意的子串总存在。从而将问题转化为判定性问题。然后对每次枚举的m值，使用后缀数组建立的height[]，便可O(n)地判断是否可行了。不过由于建立数组时我只实现了基于快排的二倍增，因此总体复杂度被拖低成O(n(lgn)^2)了，g++下跑了610ms。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,d[40000],sa[40000],r[40000],h[40000];

struct E
{
    int i,r;
    bool operator < (const E &p) const
    {
        return r<p.r;
    }
}e[40000];

int gi()
{
    char c;
    while((c=getchar())<'0'||c>'9');
    int d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void init()
{
    memset(d,0,sizeof d);
    memset(sa,0,sizeof sa);
    memset(r,0,sizeof r);
    memset(h,0,sizeof h);
    memset(e,0,sizeof e);
    int i,j,k,l;
    j=gi();
    n--;
    for(i=0;i<n;i++)
    {
        k=gi();
        e[i].i=i;
        d[i]=e[i].r=k-j+88;
        j=k;
    }
    sort(e,e+n);
    r[e[0].i]=1;
    for(i=j=1;i<n;i++)
    {
        if(e[i].r==e[i-1].r)
            r[e[i].i]=j;
        else
            r[e[i].i]=++j;
    }
    for(l=1;l<n;l<<=1)
    {
        for(i=0;i<n;i++)
        {
            e[i].i=i;
            e[i].r=r[i]*(n+1)+r[i+l];
        }
        sort(e,e+n);
        r[e[0].i]=1;
        for(i=j=1;i<n;i++)
        {
            if(e[i].r==e[i-1].r)
                r[e[i].i]=j;
            else
                r[e[i].i]=++j;
        }
    }
    for(i=0;i<n;i++)
        sa[r[i]-1]=i;
    for(i=0;i<n;i++)
        r[sa[i]]=i;
    for(i=k=0;i<n;i++)
    {
        if(!r[i])
            continue;
        for(k?k--:0,j=sa[r[i]-1];d[i+k]==d[j+k];k++);
        h[r[i]]=k;
    }
}

int calc(int m)
{
    int i,mn,mx;
    for(i=1,mx=mn=-1;i<n;i++)
    {
        if(h[i]<m)
        {
            if(mx!=-1&&mx-mn>m)
                return 1;
            mx=mn=-1;
        }
        else
        {
            if(mx==-1)
            {
                mx=max(sa[i],sa[i-1]);
                mn=min(sa[i],sa[i-1]);
            }
            else
            {
                mx=max(mx,sa[i]);
                mn=min(mn,sa[i]);
            }
        }
    }
    if(mx!=-1&&mx-mn>m)
        return 1;
    return 0;
}

void solve()
{
    int l,h,m;
    for(l=3,h=n/2;l<h;)
    {
        m=l+h+1>>1;
        if(calc(m))
            l=m;
        else
            h=m-1;
    }
    if(l==3)
        puts("0");
    else
        printf("%d\n",l+1);
}

int main()
{
    while(n=gi())
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,d[40000],sa[40000],r[40000],h[40000];

struct E

{

int i,r;

bool operator < (const E &p) const

{

return r<p.r;

}

}e[40000];

int gi()

{

char c;

while((c=getchar())<'0'||c>'9');

int d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void init()

{

memset(d,0,sizeof d);

memset(sa,0,sizeof sa);

memset(r,0,sizeof r);

memset(h,0,sizeof h);

memset(e,0,sizeof e);

int i,j,k,l;

j=gi();

n--;

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

{

k=gi();

e[i].i=i;

d[i]=e[i].r=k-j+88;

j=k;

}

sort(e,e+n);

r[e[0].i]=1;

for(i=j=1;i<n;i++)

{

if(e[i].r==e[i-1].r)

r[e[i].i]=j;

else

r[e[i].i]=++j;

}

for(l=1;l<n;l<<=1)

{

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

{

e[i].i=i;

e[i].r=r[i]*(n+1)+r[i+l];

}

sort(e,e+n);

r[e[0].i]=1;

for(i=j=1;i<n;i++)

{

if(e[i].r==e[i-1].r)

r[e[i].i]=j;

else

r[e[i].i]=++j;

}

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

sa[r[i]-1]=i;

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

r[sa[i]]=i;

for(i=k=0;i<n;i++)

{

if(!r[i])

continue;

for(k?k--:0,j=sa[r[i]-1];d[i+k]==d[j+k];k++);

h[r[i]]=k;

}

int calc(int m)

{

int i,mn,mx;

for(i=1,mx=mn=-1;i<n;i++)

{

if(h[i]<m)

{

if(mx!=-1&&mx-mn>m)

return 1;

mx=mn=-1;

}

else

{

if(mx==-1)

{

mx=max(sa[i],sa[i-1]);

mn=min(sa[i],sa[i-1]);

}

else

{

mx=max(mx,sa[i]);

mn=min(mn,sa[i]);

}

if(mx!=-1&&mx-mn>m)

return 1;

return 0;

}

void solve()

{

int l,h,m;

for(l=3,h=n/2;l<h;)

{

m=l+h+1>>1;

if(calc(m))

l=m;

else

h=m-1;

}

if(l==3)

puts("0");

else

printf("%d\n",l+1);

}

int main()

{

while(n=gi())

{

init();

solve();

}

return 0;

}

另外，这题之前也已经用字符串hash做过了的（半年前还在用数组实现hash表），竟然比后缀数组还要快些（g++ 438ms）……

#include<cstdio>
#include<cstring>

int n,a[20000],b[20000],hs[10007][20];

int gi()
{
    char c;
    while((c=getchar())<'0'||c>'9');
    int d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

int ck(int m)
{
	int i,j,l,h,k,g;
	memset(hs,0,sizeof(hs));
	for(j=0,k=0,g=1;j<m-1;j++)
	{
		k=(k*131+b[j])%10007;
		g=(g*131)%10007;
	}
	hs[k][++hs[k][0]]=0;
	for(i=1;i<n-m+1;i++)
	{
		k=k*131+b[i+m-2]+10007;
		k-=g*b[i-1]%10007;
		k%=10007;
		if(hs[k][0])
		{
			for(j=1;j<=hs[k][0];j++)
			{
				h=hs[k][j];
				if(i-h<m) continue;
				for(l=0;l<m-1&&b[i+l]==b[h+l];l++);
				if(l==m-1) return 1;
			}
		}
		hs[k][++hs[k][0]]=i;
	}
	return 0;
}

int main()
{
	int i,l,h,m;
	while(n=gi())
	{
		for(i=0;i<n;i++) a[i]=gi();
		for(i=0;i<n-1;i++) b[i]=a[i]-a[i+1]+88;
		for(l=5,h=n/2;l<h;)
		{
			m=l+h+1>>1;
			if(ck(m)) l=m;
			else h=m-1;
		}
		if(ck(l)) printf("%d\n",l);
		else puts("0");
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int n,a[20000],b[20000],hs[10007][20];

int gi()

{

char c;

while((c=getchar())<'0'||c>'9');

int d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

int ck(int m)

{

int i,j,l,h,k,g;

memset(hs,0,sizeof(hs));

for(j=0,k=0,g=1;j<m-1;j++)

{

k=(k*131+b[j])%10007;

g=(g*131)%10007;

}

hs[k][++hs[k][0]]=0;

for(i=1;i<n-m+1;i++)

{

k=k*131+b[i+m-2]+10007;

k-=g*b[i-1]%10007;

k%=10007;

if(hs[k][0])

{

for(j=1;j<=hs[k][0];j++)

{

h=hs[k][j];

if(i-h<m) continue;

for(l=0;l<m-1&&b[i+l]==b[h+l];l++);

if(l==m-1) return 1;

}

hs[k][++hs[k][0]]=i;

}

return 0;

}

int main()

{

int i,l,h,m;

while(n=gi())

{

for(i=0;i<n;i++) a[i]=gi();

for(i=0;i<n-1;i++) b[i]=a[i]-a[i+1]+88;

for(l=5,h=n/2;l<h;)

{

m=l+h+1>>1;

if(ck(m)) l=m;

else h=m-1;

}

if(ck(l)) printf("%d\n",l);

else puts("0");

}

return 0;

}

ps: 又发现了一个很有趣的blog：Summer’s Mariner。

[POJ 1200]

发表回复

Crazy Search

字符串hash

很基本的hash题目，现在做这种程度的题10分钟就敲完1A了。整个程序都是模块化的，思路也能很自然地延伸。

#include<cstdio>
#include<cstring>

#define MAXP 100003

int n,nc,hd[MAXP],el,sl,ans;
char s[16000001];

struct E
{
    int i,p;
}e[16000000];

inline void adde(int hs,int i)
{
    e[el].i=i; e[el].p=hd[hs]; hd[hs]=el++;
}

void init()
{
    memset(hd,-1,sizeof hd);
    el=ans=0;
    sl=strlen(s);
}

int bkdr(char *s,char *e)
{
    int hs=0;
    while(s!=e)
        hs=(hs*131+*s++)%MAXP;
    return hs;
}

int fi(int hs,int i)
{
    int j,k,l;
    for(l=hd[hs];l!=-1;l=e[l].p)
    {
        j=e[l].i;
        for(k=0;k<n&&s[i+k]==s[j+k];k++);
        if(k==n)
            return 1;
    }
    return 0;
}

void solve()
{
    int i,j,k,l;
    for(i=0;i+n<=sl;i++)
    {
        j=bkdr(s+i,s+i+n);
        if(!fi(j,i))
        {
            adde(j,i);
            ans++;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    while(~scanf("%d%d%s",&n,&nc,s))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#define MAXP 100003

int n,nc,hd[MAXP],el,sl,ans;

char s[16000001];

struct E

{

int i,p;

}e[16000000];

inline void adde(int hs,int i)

{

e[el].i=i; e[el].p=hd[hs]; hd[hs]=el++;

}

void init()

{

memset(hd,-1,sizeof hd);

el=ans=0;

sl=strlen(s);

}

int bkdr(char *s,char *e)

{

int hs=0;

while(s!=e)

hs=(hs*131+*s++)%MAXP;

return hs;

}

int fi(int hs,int i)

{

int j,k,l;

for(l=hd[hs];l!=-1;l=e[l].p)

{

j=e[l].i;

for(k=0;k<n&&s[i+k]==s[j+k];k++);

if(k==n)

return 1;

}

return 0;

}

void solve()

{

int i,j,k,l;

for(i=0;i+n<=sl;i++)

{

j=bkdr(s+i,s+i+n);

if(!fi(j,i))

{

adde(j,i);

ans++;

}

printf("%d\n",ans);

}

int main()

{

while(~scanf("%d%d%s",&n,&nc,s))

{

init();

solve();

}

return 0;

}

[POJ 1421]

发表回复

Peter’s Calculator

模拟（难）

给出一段程序，要求按照给定的运行方式，对每次PRINT操作判断是否有效，若有效还需求值。

并没有太多算法的题目，但各种细节很多

大致思路就是先将全部程序文本读入，进行预处理：记录每行程序的类型（赋值、打印或重置），并且
（1）如果是赋值，则对被赋值的变量进行编号，并将等号右边的内容以纯文本方式保存下来
（2）如果是打印，则检查被打印的变量之前是否存在相应赋值，若有则记录变量编号，若无则记录编号为-1
（3）如果是重置，无需特殊处理

然后就是求解了，按顺序对每行i进行处理，期间维护一个搜索赋值语句的上下界[es,ee]，初始es=ee=0，并且
（1）如果是赋值，忽略
（2）如果是打印，则ee=i-1，并尝试对该变量求值，若成功则打印值，否则打印”UNDEF”
（3）如果是重置，则es=i+1

每次对变量id求值的操作可能涉及其他变量，因此使用递归结构。而要防止循环求值，因此初始化全0数组st[]来记录变量是否在递归栈中。每次递归内部结构大致如下：
（1）若st[id]!=0，直接返回；st[id]=1，按从后往前(从ee到es)的顺序找第一个对va赋值的语句
（2）对将赋值字符串中的所有变量调用递归求值，若某变量求值失败，直接返回
（3）用一个新字符串保存将赋值字符串中所有变量替换为值后的结果（必须不修改原来的赋值字符串），随后使用递归下降分析求解该字符串的值
（4）记录变量的值，st[id]=2

最后求值完毕后，若要打印的变量st[]为2，则表示成功求值。

程序的主要部分想清楚后实现也花了不少时间，最后则是在空格问题上卡了很久。

#include<cstdio>
#include<cstring>
#define MAXL 1000

int el,sl,st[MAXL],v[MAXL],es,ee,ti;

char s[MAXL][MAXL],t[MAXL];

struct E
{
    int ins,id;
    char s[MAXL];
}e[MAXL];

int exp();

int gi(int b)
{
    int i;
    for(i=0;i<sl&&strcmp(s[i],t);i++);
    if(i==sl)
    {
        if(b)
            strcpy(s[sl++],t);
        else
            i=-1;
    }
    return i;
}

int fact()
{
    while(t[ti]&&t[ti]==' ')
        ti++;
    int d;
    if(t[ti]=='(')
    {
        ti++;
        d=exp();
        while(t[ti]!=')')
            ti++;
        ti++;
        return d;
    }
    sscanf(t+ti,"%d",&d);
    if(t[ti]&&t[ti]=='-')
        ti++;
    while(t[ti]&&t[ti]>='0'&&t[ti]<='9')
        ti++;
    return d;
}

int term()
{
    while(t[ti]&&t[ti]==' ')
        ti++;
    int d=fact();
    while(t[ti])
    {
        while(t[ti]&&t[ti]==' ')
            ti++;
        if(!t[ti]||t[ti]!='*')
            break;
        ti++;
        d*=fact();
    }
    return d;
}

int exp()
{
    while(t[ti]&&t[ti]==' ')
        ti++;
    int d=term();
    while(t[ti])
    {
        while(t[ti]&&t[ti]==' ')
            ti++;
        if(!t[ti]||t[ti]!='+'&&t[ti]!='-')
            break;
        ti++;
        if(t[ti-1]=='+')
            d+=term();
        else
            d-=term();
    }
    return d;
}

void vl(int id)
{
    if(st[id]!=0)
        return;
    st[id]=1;
    int i,j,k,rl;
    char r[MAXL];
    for(i=ee-1;i>=es;i--)
    {
        if(e[i].ins==1&&e[i].id==id)
            break;
    }
    if(i<es)
        return;
    memset(r,0,sizeof r);
    for(j=rl=0;e[i].s[j];)
    {
        if(e[i].s[j]=='('||e[i].s[j]==')'||e[i].s[j]==' '||
                e[i].s[j]=='+'||e[i].s[j]=='-'||e[i].s[j]=='*')
        {
            r[rl++]=e[i].s[j++];
        }
        else if(e[i].s[j]=='-'||e[i].s[j]>='0'&&e[i].s[j]<='9')
        {
            r[rl++]=e[i].s[j++];
            while(e[i].s[j]&&e[i].s[j]>='0'&&e[i].s[j]<='9')
            {
                r[rl++]=e[i].s[j++];
            }
        }
        else
        {
            for(k=j;e[i].s[k]>='a'&&e[i].s[k]<='z'
                    ||e[i].s[k]>='A'&&e[i].s[k]<='Z'
                    ||e[i].s[k]>='0'&&e[i].s[k]<='9';k++)
                t[k-j]=e[i].s[k];
            t[k-j]=0;
            k=gi(0);
            if(k==-1)
                return;
            vl(k);
            if(st[k]!=2)
                return;
            sprintf(r+rl,"%d",v[k]);
            while(r[rl])
                rl++;
            while(e[i].s[j]&&(e[i].s[j]>='a'&&e[i].s[j]<='z'
                    ||e[i].s[j]>='A'&&e[i].s[j]<='Z'
                    ||e[i].s[j]>='0'&&e[i].s[j]<='9'))
                j++;
        }
    }
    memcpy(t,r,sizeof t);
    ti=0;
    v[id]=exp();
    st[id]=2;
}

void init()
{
    while(~scanf("%s",t))
    {
        if(!strcmp(t,"PRINT"))
        {
            e[el].ins=2;
            scanf("%s",t);
            e[el].id=gi(0);
        }
        else if(!strcmp(t,"RESET"))
        {
            e[el].ins=3;
        }
        else
        {
            for(ti=1;t[ti]&&!(t[ti-1]==':'&&t[ti]=='=');ti++);
            if(!t[ti])
            {
                e[el].ins=1;
                e[el].id=gi(1);
                scanf("%s",t);
                if(!strcmp(t,":="))
                    gets(e[el].s);
                else
                    strcpy(e[el].s,t+2);
            }
            else
            {
                strcpy(e[el].s,t+ti+1);
                t[ti-1]=0;
                e[el].ins=1;
                e[el].id=gi(1);
            }
        }
        el++;
    }
}

void solve()
{
    int i;
    for(i=0;i<el;i++)
    {
        if(e[i].ins==2)
        {
            if(e[i].id==-1)
            {
                puts("UNDEF");
                continue;
            }
            memset(st,0,sizeof st);
            ee=i;
            vl(e[i].id);
            if(st[e[i].id]<2)
                puts("UNDEF");
            else
                printf("%d\n",v[e[i].id]);
        }
        else if(e[i].ins==3)
        {
            es=i+1;
        }
    }
}

int main()
{
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

#include<cstdio>

#include<cstring>

#define MAXL 1000

int el,sl,st[MAXL],v[MAXL],es,ee,ti;

char s[MAXL][MAXL],t[MAXL];

struct E

{

int ins,id;

char s[MAXL];

}e[MAXL];

int exp();

int gi(int b)

{

int i;

for(i=0;i<sl&&strcmp(s[i],t);i++);

if(i==sl)

{

if(b)

strcpy(s[sl++],t);

else

i=-1;

}

return i;

}

int fact()

{

while(t[ti]&&t[ti]==' ')

ti++;

int d;

if(t[ti]=='(')

{

ti++;

d=exp();

while(t[ti]!=')')

ti++;

return d;

}

sscanf(t+ti,"%d",&d);

if(t[ti]&&t[ti]=='-')

ti++;

while(t[ti]&&t[ti]>='0'&&t[ti]<='9')

ti++;

return d;

}

int term()

{

while(t[ti]&&t[ti]==' ')

ti++;

int d=fact();

while(t[ti])

{

while(t[ti]&&t[ti]==' ')

ti++;

if(!t[ti]||t[ti]!='*')

break;

ti++;

d*=fact();

}

return d;

}

int exp()

{

while(t[ti]&&t[ti]==' ')

ti++;

int d=term();

while(t[ti])

{

while(t[ti]&&t[ti]==' ')

ti++;

if(!t[ti]||t[ti]!='+'&&t[ti]!='-')

break;

ti++;

if(t[ti-1]=='+')

d+=term();

else

d-=term();

}

return d;

}

void vl(int id)

{

if(st[id]!=0)

return;

st[id]=1;

int i,j,k,rl;

char r[MAXL];

for(i=ee-1;i>=es;i--)

{

if(e[i].ins==1&&e[i].id==id)

break;

}

if(i<es)

return;

memset(r,0,sizeof r);

for(j=rl=0;e[i].s[j];)

{

if(e[i].s[j]=='('||e[i].s[j]==')'||e[i].s[j]==' '||

e[i].s[j]=='+'||e[i].s[j]=='-'||e[i].s[j]=='*')

{

r[rl++]=e[i].s[j++];

}

else if(e[i].s[j]=='-'||e[i].s[j]>='0'&&e[i].s[j]<='9')

{

r[rl++]=e[i].s[j++];

while(e[i].s[j]&&e[i].s[j]>='0'&&e[i].s[j]<='9')

{

r[rl++]=e[i].s[j++];

}

else

{

for(k=j;e[i].s[k]>='a'&&e[i].s[k]<='z'

||e[i].s[k]>='A'&&e[i].s[k]<='Z'

||e[i].s[k]>='0'&&e[i].s[k]<='9';k++)

t[k-j]=e[i].s[k];

t[k-j]=0;

k=gi(0);

if(k==-1)

return;

vl(k);

if(st[k]!=2)

return;

sprintf(r+rl,"%d",v[k]);

while(r[rl])

rl++;

while(e[i].s[j]&&(e[i].s[j]>='a'&&e[i].s[j]<='z'

||e[i].s[j]>='A'&&e[i].s[j]<='Z'

||e[i].s[j]>='0'&&e[i].s[j]<='9'))

j++;

}

memcpy(t,r,sizeof t);

ti=0;

v[id]=exp();

st[id]=2;

}

void init()

{

while(~scanf("%s",t))

{

if(!strcmp(t,"PRINT"))

{

e[el].ins=2;

scanf("%s",t);

e[el].id=gi(0);

}

else if(!strcmp(t,"RESET"))

{

e[el].ins=3;

}

else

{

for(ti=1;t[ti]&&!(t[ti-1]==':'&&t[ti]=='=');ti++);

if(!t[ti])

{

e[el].ins=1;

e[el].id=gi(1);

scanf("%s",t);

if(!strcmp(t,":="))

gets(e[el].s);

else

strcpy(e[el].s,t+2);

}

else

{

strcpy(e[el].s,t+ti+1);

t[ti-1]=0;

e[el].ins=1;

e[el].id=gi(1);

}

el++;

}

void solve()

{

int i;

for(i=0;i<el;i++)

{

if(e[i].ins==2)

{

if(e[i].id==-1)

{

puts("UNDEF");

continue;

}

memset(st,0,sizeof st);

ee=i;

vl(e[i].id);

if(st[e[i].id]<2)

puts("UNDEF");

else

printf("%d\n",v[e[i].id]);

}

else if(e[i].ins==3)

{

es=i+1;

}

int main()

{

init();

solve();

return 0;

}

在POJ上做过最冷门的题目了，算上我也才53个人AC。但貌似数据比较弱哦，总觉得比想象中要顺利得多……