月度归档：2013年12月

[POJ 2559]

扫描栈 + 二分

题意：输入n(<=100,000)，然后是n个整数值h[i](<=10^9)，每个值按顺序描述了一个宽为1高为h[i]的矩形，矩形间是无缝相邻的，求该柱形图内边与坐标轴平行的矩形的最大面积。拿到手之后第一想法是二分面积+RMQ判断，结果发现行不通…… 看了discuss可以用栈水过，就大概写了一下。基本思想是，对于位置i，分别找其左边和右边高度不小于h[i]的最长宽度wl[i]和wr[i]，那么h[i]对应的最大矩形面积就是h[i]*(wl[i]+wr[i]-1)。分别求出对于所有n个位置的最大矩形面积就能得到答案了。具体实现方面，计算wl[i]和wr[i]时，需要维护一个栈stk，记录扫描到i时，到i为止非递减的h[i]序列。例如对于“7 2 1 4 5 1 3 3”的样例，当i=3即h[i]=5时，栈里面分别是1、4、5，同时也需要记录这些值对应的位置。有了该栈，就可以找到刚好不小于h[i]的值stk[l]以及对应的位置si[l]，从而算出wl[i]、wr[i]。其中，由于栈有序，可以二分查找，那么计算wl[i]和wr[i]的时间复杂度便是O(lgn)，从而总体复杂度就是O(nlgn)的。还有一些细节：例如总是将栈顶置为最大值，这样二分查找如果失败将返回栈顶位置，方便了处理；另外结果需要用到long long。

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

#define ll long long 

int n,h[100000],wl[100000],wr[100000];
int stk[100001],si[100001],sl;
ll ans;

int bs(int l,int h,int e)
{
    int m;
    while(l<h)
    {
        m=l+h>>1;
        if(stk[m]>=e)
            h=m;
        else
            l=m+1;
    }
    return l;
}

void init()
{
    int i,j,k,l;
    ans=0;
    for(i=0;i<n;i++)
        scanf("%d",h+i);
    sl=0;
    stk[sl]=0x7fffffff;
    for(i=0;i<n;i++)
    {
        l=bs(0,sl,h[i]);
        if(l==sl)
        {
            wl[i]=1;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
        else
        {
            wl[i]=i-si[l]+wl[si[l]];
            sl=l;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
    }
    sl=0;
    stk[sl]=0x7fffffff;
    for(i=n-1;i>-1;i--)
    {
        l=bs(0,sl,h[i]);
        if(l==sl)
        {
            wr[i]=1;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
        else
        {
            wr[i]=si[l]-i+wr[si[l]];
            sl=l;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
    }
}

void solve()
{
    ll i,j;
    for(i=0;i<n;i++)
    {
        j=wl[i]+wr[i]-1;
        ans=max(ans,j*h[i]);
    }
    printf("%lld\n",ans);
}

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int n,h[100000],wl[100000],wr[100000];

int stk[100001],si[100001],sl;

ll ans;

int bs(int l,int h,int e)

{

int m;

while(l<h)

{

m=l+h>>1;

if(stk[m]>=e)

h=m;

else

l=m+1;

}

return l;

}

void init()

{

int i,j,k,l;

ans=0;

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

scanf("%d",h+i);

sl=0;

stk[sl]=0x7fffffff;

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

{

l=bs(0,sl,h[i]);

if(l==sl)

{

wl[i]=1;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

else

{

wl[i]=i-si[l]+wl[si[l]];

sl=l;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

sl=0;

stk[sl]=0x7fffffff;

for(i=n-1;i>-1;i--)

{

l=bs(0,sl,h[i]);

if(l==sl)

{

wr[i]=1;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

else

{

wr[i]=si[l]-i+wr[si[l]];

sl=l;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

void solve()

{

ll i,j;

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

{

j=wl[i]+wr[i]-1;

ans=max(ans,j*h[i]);

}

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}

还有一道差不多的：Feel Good

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

#define ll long long 

int n,h[100000],wl[100000],wr[100000];
ll shl[100000],shr[100000];
int stk[100001],si[100001],sl;
ll ans,ansl,ansr;

int bs(int l,int h,int e)
{
    int m;
    while(l<h)
    {
        m=l+h>>1;
        if(stk[m]>=e)
            h=m;
        else
            l=m+1;
    }
    return l;
}

void init()
{
    int i,j,k,l;
    ans=-1;
    for(i=0;i<n;i++)
        scanf("%d",h+i);
    shl[0]=h[0];
    for(i=1;i<n;i++)
        shl[i]=shl[i-1]+h[i];
    shr[n-1]=h[n-1];
    for(i=n-2;i>-1;i--)
        shr[i]=shr[i+1]+h[i];
    sl=0;
    stk[sl]=0x7fffffff;
    for(i=0;i<n;i++)
    {
        l=bs(0,sl,h[i]);
        if(l==sl)
        {
            wl[i]=1;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
        else
        {
            wl[i]=i-si[l]+wl[si[l]];
            sl=l;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
    }
    sl=0;
    stk[sl]=0x7fffffff;
    for(i=n-1;i>-1;i--)
    {
        l=bs(0,sl,h[i]);
        if(l==sl)
        {
            wr[i]=1;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
        else
        {
            wr[i]=si[l]-i+wr[si[l]];
            sl=l;
            stk[sl]=h[i];
            si[sl++]=i;
            stk[sl]=0x7fffffff;
        }
    }
}

void solve()
{
    ll i,ji,ki,j,k,l;
    for(i=0;i<n;i++)
    {
        ji=i-wl[i]+1;
        j=shl[i]-shl[ji]+h[ji];
        ki=i+wr[i]-1;
        k=shr[i]-shr[ki]+h[ki];
        l=h[i]*(j+k-h[i]);
        if(l>ans)
        {
            ans=l;
            ansl=ji+1;
            ansr=ki+1;
        }
    }
    printf("%lld\n%lld %lld\n",ans,ansl,ansr);
}

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

100

101

102

103

104

105

106

107

108

109

110

111

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int n,h[100000],wl[100000],wr[100000];

ll shl[100000],shr[100000];

int stk[100001],si[100001],sl;

ll ans,ansl,ansr;

int bs(int l,int h,int e)

{

int m;

while(l<h)

{

m=l+h>>1;

if(stk[m]>=e)

h=m;

else

l=m+1;

}

return l;

}

void init()

{

int i,j,k,l;

ans=-1;

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

scanf("%d",h+i);

shl[0]=h[0];

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

shl[i]=shl[i-1]+h[i];

shr[n-1]=h[n-1];

for(i=n-2;i>-1;i--)

shr[i]=shr[i+1]+h[i];

sl=0;

stk[sl]=0x7fffffff;

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

{

l=bs(0,sl,h[i]);

if(l==sl)

{

wl[i]=1;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

else

{

wl[i]=i-si[l]+wl[si[l]];

sl=l;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

sl=0;

stk[sl]=0x7fffffff;

for(i=n-1;i>-1;i--)

{

l=bs(0,sl,h[i]);

if(l==sl)

{

wr[i]=1;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

else

{

wr[i]=si[l]-i+wr[si[l]];

sl=l;

stk[sl]=h[i];

si[sl++]=i;

stk[sl]=0x7fffffff;

}

void solve()

{

ll i,ji,ki,j,k,l;

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

{

ji=i-wl[i]+1;

j=shl[i]-shl[ji]+h[ji];

ki=i+wr[i]-1;

k=shr[i]-shr[ki]+h[ki];

l=h[i]*(j+k-h[i]);

if(l>ans)

{

ans=l;

ansl=ji+1;

ansr=ki+1;

}

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}

[POJ 3084]

发表回复

Panic Room

最小割

有向图上有n个结点，某些点有标记，要求对于某特定的m点，要割掉多少条边才能使从m点出发无法到达任何一个标记点。

题目数据范围很小，主要考察的还是最小割的建模，也即将图分成S、T两部分，S包含m，T包含所有标记点，求S和T间的最小割即可。

注意首先要判断是否无解，然后要合并必定可达的结点，最后用最大流即可。

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

int n,m,hd[22],el,b[22],mxf[22],pl[22],t[22],ans,S=20,E=21;
char s[3];

struct EE
{
    int v,f,p;
}e[10000];

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

void init()
{
    int i,j,k,l;
    ans=el=0;
    memset(hd,-1,sizeof hd);
    memset(t,0,sizeof t);
    adde(S,m,0x7fffffff);
    for(i=0;i<n;i++)
    {
        scanf("%s%d",s,&l);
        while(l--)
        {
            scanf("%d",&j);
            adde(i,j,1);
        }
        if(s[0]=='I')
        {
            t[i]=1;
            adde(i,E,0x7fffffff);
        }
    }
}

int dfs(int i)
{
    int j,k,l;
    b[i]=1;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        k=e[l].f;
        if(j==E)
            return 1;
        if(b[j]||k)
            continue;
        if(dfs(j))
            return 1;
    }
    return 0;
}

void bfs(int i)
{
    int j,k,l;
    queue<int>Q;
    memset(b,0,sizeof b);
    b[i]=1;
    Q.push(i);
    while(!Q.empty())
    {
        i=Q.front(); Q.pop();
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            k=e[l].f;
            if(!k&&!b[j])
            {
                adde(i,j,0x7fffffff);
                b[j]=1;
                Q.push(j);
            }
        }
    }
}

void bfsr(int i)
{
    int j,k,l;
    queue<int>Q;
    memset(b,0,sizeof b);
    b[i]=1;
    Q.push(i);
    while(!Q.empty())
    {
        i=Q.front(); Q.pop();
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            k=e[l].f;
            if(k==1&&!b[j])
            {
                adde(j,i,0x7fffffff);
                b[j]=1;
                Q.push(j);
            }
        }
    }
}

void ek()
{
    int i,j,k,l;
    pl[S]=-1;
    queue<int>Q;
    while(1)
    {
        memset(b,0,sizeof b);
        memset(mxf,0,sizeof mxf);
        mxf[S]=0x7fffffff;
        b[S]=1;
        Q.push(S);
        while(!Q.empty())
        {
            i=Q.front(); Q.pop();
            b[i]=0;
            for(l=hd[i];l!=-1;l=e[l].p)
            {
                j=e[l].v;
                k=min(mxf[i],e[l].f);
                if(k<=mxf[j])
                    continue;
                mxf[j]=k;
                pl[j]=l;
                if(!b[j])
                {
                    b[j]=1;
                    Q.push(j);
                }
            }
        }
        if(!mxf[E])
            break;
        ans++;
        for(l=pl[E];l!=-1;l=pl[e[l^1].v])
        {
            e[l].f-=mxf[E];
            e[l^1].f+=mxf[E];
        }
    }
}

void solve()
{
    int i;
    memset(b,0,sizeof b);
    if(dfs(m))
    {
        puts("PANIC ROOM BREACH");
        return;
    }
    bfs(m);
    for(i=0;i<n;i++)
    {
        if(t[i])
            bfsr(i);
    }
    ek();
    printf("%d\n",ans);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d",&n,&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

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,hd[22],el,b[22],mxf[22],pl[22],t[22],ans,S=20,E=21;

char s[3];

struct EE

{

int v,f,p;

}e[10000];

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

{

e[el].v=v; e[el].f=f; e[el].p=hd[u]; hd[u]=el++;

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

}

void init()

{

int i,j,k,l;

ans=el=0;

memset(hd,-1,sizeof hd);

memset(t,0,sizeof t);

adde(S,m,0x7fffffff);

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

{

scanf("%s%d",s,&l);

while(l--)

{

scanf("%d",&j);

adde(i,j,1);

}

if(s[0]=='I')

{

t[i]=1;

adde(i,E,0x7fffffff);

}

int dfs(int i)

{

int j,k,l;

b[i]=1;

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

{

j=e[l].v;

k=e[l].f;

if(j==E)

return 1;

if(b[j]||k)

continue;

if(dfs(j))

return 1;

}

return 0;

}

void bfs(int i)

{

int j,k,l;

queue<int>Q;

memset(b,0,sizeof b);

b[i]=1;

Q.push(i);

while(!Q.empty())

{

i=Q.front(); Q.pop();

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

{

j=e[l].v;

k=e[l].f;

if(!k&&!b[j])

{

adde(i,j,0x7fffffff);

b[j]=1;

Q.push(j);

}

void bfsr(int i)

{

int j,k,l;

queue<int>Q;

memset(b,0,sizeof b);

b[i]=1;

Q.push(i);

while(!Q.empty())

{

i=Q.front(); Q.pop();

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

{

j=e[l].v;

k=e[l].f;

if(k==1&&!b[j])

{

adde(j,i,0x7fffffff);

b[j]=1;

Q.push(j);

}

void ek()

{

int i,j,k,l;

pl[S]=-1;

queue<int>Q;

while(1)

{

memset(b,0,sizeof b);

memset(mxf,0,sizeof mxf);

mxf[S]=0x7fffffff;

b[S]=1;

Q.push(S);

while(!Q.empty())

{

i=Q.front(); Q.pop();

b[i]=0;

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

{

j=e[l].v;

k=min(mxf[i],e[l].f);

if(k<=mxf[j])

continue;

mxf[j]=k;

pl[j]=l;

if(!b[j])

{

b[j]=1;

Q.push(j);

}

if(!mxf[E])

break;

ans++;

for(l=pl[E];l!=-1;l=pl[e[l^1].v])

{

e[l].f-=mxf[E];

e[l^1].f+=mxf[E];

}

void solve()

{

int i;

memset(b,0,sizeof b);

if(dfs(m))

{

puts("PANIC ROOM BREACH");

return;

}

bfs(m);

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

{

if(t[i])

bfsr(i);

}

ek();

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

}

int main()

{

scanf("%*d");

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

{

init();

solve();

}

return 0;

}

ps: 这也是在poj上水掉的第300题，虽然还是很弱，也稍作纪念吧。

[POJ 3067]

发表回复

Japan

树状数组

题意是，在左右两边各有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。