2015-team5
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== 队伍信息 ==
* 队名：tdmxtxwd
* 成员：
* 梁露(potaty)
* 蔡嘉楠(Naylor)
* 华铱炜(mssjtxwd)
== jiaxun ==
http://opentrains.snarknews.info/~ejudge/team.cgi?SID=4f3b1d33e5ab972a&action=2<=1
== 补题 ==
'''zimpha学长姿势题补题情况'''
{{{
http://codeforces.com/gym/100633 D题, 树分治的一个应用
http://acm.hdu.edu.cn/showproblem.php?pid=5314, 树分治的一个应用 已补By mssjtxwd
http://acm.zju.edu.cn:9999/onlinejudge/showProblem.do?problemId=5427, 7月集训, 树分治的一个应用
http://www.lydsy.com/JudgeOnline/problem.php?id=4182, 树分治的一个应用
http://codeforces.com/gym/100633 J题, 一类组合数取模
http://main.edu.pl/en/archive/ontak/2010/pal, 一类字符串计数题, kmp数组也可做
http://main.edu.pl/en/archive/ontak/2010/dus, 一定在二分图最大匹配上的点
https://www.codechef.com/JULY15/problems/HAMILG, 一定在一般图最大匹配上的点
https://www.codechef.com/JUNE15/problems/CHEFBOOK, 线性规划->费用流
https://www.codechef.com/JULY15/problems/EASYEX, 生成函数的应用
https://www.codechef.com/MAY15/problems/GRAPHCNT, Dominator Tree的应用
https://www.codechef.com/problems/PALPROB, 回文树的一个应用
https://www.hackerrank.com/contests/csindia14-er1/challenges/fill-the-tank, 某天晚上群里介绍过的姿势
http://acm.hdu.edu.cn/showproblem.php?pid=5189, 树链剖分+线段树维护凸壳
https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2014/p/sum/, 一道有趣的构造题, 题解参考http://yun.baidu.com/share/link?shareid=3559646679&uk=3627228315
https://www.hackerrank.com/contests/w8/challenges/black-box-1, 线性基(好像是这么叫的)
http://codeforces.com/gym/100551, 5到图论分治题, 参考讨论http://codeforces.com/blog/entry/15296
对生成函数有需求的可以看这里: http://pan.baidu.com/s/1kTKJip5
dominator tree可以做的题:
1. shi哥当年多校有一题
2. codechef有一题(见之前推荐的题目列表)
3. neerc 2014 southern有一题
4. spoj有若干模板题
推荐一些波兰人的题目 https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/p/
题目翻译在这里http://zimpha.github.io/2015/09/23/ontak-2015-translation/, 今天晚上可以完工, 感兴趣的学长可以去做下
后缀树：
opencup I题用后缀树的代码 http://ideone.com/1zLpMn
http://codeforces.com/blog/entry/16780
http://ideone.com/sT8Vd1
}}}
== 模板 ==
'''函数式线段树模板:'''
{{{
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000007
#define M 100007
#define N 111
#define ll long long
#define mod 1000000007
#define eps 1e-8
int L[M<<5], R[M<<5], sum[M<<5];
int tail;
int a[M], b[M], lisan[M], cnt;
void build( int l, int r, int &p )
{
p = ++tail; sum[p] = 0;
if( l >= r ) return;
int m = l + r >> 1;
build( l, m, L[p] );
build( m+1, r, R[p] );
}
void update( int pre, int &p, int l, int r, int x )
{
p = ++tail;
L[p] = L[pre], R[p] = R[pre], sum[p] = sum[pre] + 1;
if( l >= r ) return;
int m = l + r >> 1;
if( x <= m ) update( L[pre], L[p], l, m, x );
else update( R[pre], R[p], m+1, r, x );
}
int query( int u, int v, int l, int r, int k )
{
if( l >= r ) return l;
int m = l + r >> 1;
int num = sum[L[v]] - sum[L[u]];
if( num >= k ) return query( L[u], L[v], l, m, k );
else return query( R[u], R[v], m+1, r, k - num );
}
int main()
{
//freopen( "a.in", "r", stdin );
int T, n, m, x, l, r, k;
scanf( "%d", &T );
while( T-- ){
scanf( "%d%d", &n, &m );
tail = 0;
for( int i = 1; i <= n; ++i ){
scanf( "%d", a+i );
lisan[i] = a[i];
}
sort( lisan + 1, lisan + n + 1 );
cnt = unique( lisan + 1, lisan + n + 1 ) - lisan - 1;
build( 1, cnt, b[0] );
for( int i = 1; i <= n; ++i ){
x = lower_bound( lisan+1, lisan + cnt + 1, a[i] ) - lisan;
update( b[i-1], b[i], 1, cnt, x );
}
for( int i = 0; i < m; ++i ){
scanf( "%d%d%d", &l, &r, &k );
x = query( b[l-1], b[r], 1, cnt, k );
printf( "%d\n", lisan[x] );
}
}
}
}}}
'''FFT模板：'''
{{{
#define mul(a, b) (Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x))
struct Complex {}; // `something omitted`
void FFT(Complex P[], int n, int oper) {
for (int i = 1, j = 0; i < n - 1; i++) {
for (int s = n; j ^= s >>= 1, ~j & s; );
if (i < j) swap(P[i], P[j]);
}
for (int d = 0; (1 << d) < n; d++) {
int m = 1 << d, m2 = m * 2;
double p0 = PI / m * oper;
Complex unit_p0(cos(p0), sin(p0));
for (int i = 0; i < n; i += m2) {
Complex unit(1.0, 0.0);
for (int j = 0; j < m; j++) {
Complex &P1 = P[i + j + m], &P2 = P[i + j];
Complex t = mul(unit, P1);
P1 = Complex(P2.x - t.x, P2.y - t.y);
P2 = Complex(P2.x + t.x, P2.y - t.y);
unit = mul(unit, unit_p0);
}}}}
vector<int> doFFT(const vector<int> &a, const vector<int> &b) {
vector<int> ret(max(0, (int) a.size() + (int) b.size() - 1), 0);
static Complex A[MAXB], B[MAXB], C[MAXB];
int len = 1; while (len < (int)ret.size()) len *= 2;
for (int i = 0; i < len; i++) A[i] = i < (int)a.size() ? a[i] : 0;
for (int i = 0; i < len; i++) B[i] = i < (int)b.size() ? b[i] : 0;
FFT(A, len, 1); FFT(B, len, 1);
for (int i = 0; i < len; i++) C[i] = mul(A[i], B[i]);
FFT(C, len, -1);
for (int i = 0; i < (int)ret.size(); i++)
ret[i] = (int) (C[i].x / len + 0.5);
return ret;
}
}}}
'''NTT模板：'''
{{{
const int MOD = 786433, PRIMITIVE_ROOT = 10; // `$3 * 2 ^ {18} + 1$`
const int MAXB = 1 << 20;
int getMod(int downLimit) { // `或者现场自己找一个MOD`
for (int c = 3; ; ++c) { int t = (c << 21) | 1;
if (t >= downLimit && isPrime(t)) return t;
}}
int modInv(int a) { return a <= 1 ? a : (long long) (MOD - MOD / a) * modInv(MOD % a) % MOD; }
void NTT(int P[], int n, int oper) {
for (int i = 1, j = 0; i < n - 1; i++) {
for (int s = n; j ^= s >>= 1, ~j & s;);
if (i < j) swap(P[i], P[j]);
}
for (int d = 0; (1 << d) < n; d++) {
int m = 1 << d, m2 = m * 2;
long long unit_p0 = powMod(PRIMITIVE_ROOT, (MOD - 1) / m2);
if (oper < 0) unit_p0 = modInv(unit_p0);
for (int i = 0; i < n; i += m2) {
long long unit = 1;
for (int j = 0; j < m; j++) {
int &P1 = P[i + j + m], &P2 = P[i + j];
int t = unit * P1 % MOD;
P1 = (P2 - t + MOD) % MOD; P2 = (P2 + t) % MOD;
unit = unit * unit_p0 % MOD;
}}}}
vector<int> mul(const vector<int> &a, const vector<int> &b) {
vector<int> ret(max(0, (int) a.size() + (int) b.size() - 1), 0);
static int A[MAXB], B[MAXB], C[MAXB];
int len = 1; while (len < (int)ret.size()) len <<= 1;
for (int i = 0; i < len; i++) A[i] = i < (int)a.size() ? a[i] : 0;
for (int i = 0; i < len; i++) B[i] = i < (int)b.size() ? b[i] : 0;
NTT(A, len, 1); NTT(B, len, 1);
for (int i = 0; i < len; i++) C[i] = (long long) A[i] * B[i] % MOD;
NTT(C, len, -1); for (int i = 0, inv = modInv(len); i < (int)ret.size(); i++) ret[i] = (long long) C[i] * inv % MOD;
return ret;
}
}}}
''' 倍增 '''
{{{
1. DFS预处理出所有节点的深度和父节点
inline void dfs(int u)
{
int i;
for(i=head[u];i!=-1;i=next[i])
{
if (!deep[to[i]])
{
deep[to[i]] = deep[u]+1;
p[to[i]][0] = u; //p[x][0]保存x的父节点为u;
dfs(to[i]);
}
}
}
2. 初始各个点的2^j祖先是谁 ,其中 2^j (j =0...log(该点深度))倍祖先，1倍祖先就是父亲，2倍祖先是父亲的父亲......。
void init()
{
int i,j;
//p[i][j]表示i结点的第2^j祖先
for(j=1;(1<<j)<=n;j++)
for(i=1;i<=n;i++)
if(p[i][j-1]!=-1)
p[i][j]=p[p[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
3.从深度大的节点上升至深度小的节点同层，如果此时两节点相同直接返回此节点，即lca。
否则，利用倍增法找到最小深度的 p[a][j]!=p[b][j]，此时他们的父亲p[a][0]即lca。
int lca(int a,int b)//最近公共祖先
{
int i,j;
if(deep[a]<deep[b])swap(a,b);
for(i=0;(1<<i)<=deep[a];i++);
i--;
//使a，b两点的深度相同
for(j=i;j>=0;j--)
if(deep[a]-(1<<j)>=deep[b])
a=p[a][j];
if(a==b)return a;
//倍增法，每次向上进深度2^j，找到最近公共祖先的子结点
for(j=i;j>=0;j--)
{
if(p[a][j]!=-1&&p[a][j]!=p[b][j])
{
a=p[a][j];
b=p[b][j];
}
}
return p[a][0];
}
}}}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？
{{{
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 100000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const int *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
int n,k;
int u[20010]={};
bool pan(int x,int y)
{
int num=0;
for(int i=1;i<n;i++)
{
if(nico.ht[i]>=x) num++;
else num=0;
if(num>=y) return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&u[i]);
}
nico.construct(u,n,256);
k--;
int l=0;
int r=n;
while(l<r)
{
int mid=(l+r)/2+1;
if(pan(mid,k)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
}}}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？
因为两次这个情况非常特殊，所以我们可以把字典序相邻的，整体公共前缀长度>k>k的打包，然后求一下最近的位置mama和最远的位置mimi，用ma−mi>=kma−mi>=k来判断这个公共前缀是否重复两次。
{{{
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 100000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const int *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
bool pan(int k,int n)
{
int ma,mi;
for(int i=0;i<n;i++)
{
if(ht[i]<k)
{
ma=sa[i];
mi=sa[i];
}
else
{
ma=max(ma,sa[i]);
mi=min(mi,sa[i]);
if(ma-mi>=k) return 1;
}
}
return 0;
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
int n;
int u[100010]={};
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&u[i]);
}
nico.construct(u,n,256);
int l=0;
int r=n;
while(l<r)
{
int mid=(l+r)/2+1;
if(nico.pan(mid,n)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
}}}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。
旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？
思路比较显然，就是把字符串合起来排个序，然后判断一下相邻字典序的后缀是不是属于两个串，感觉也可以推广到多个串？
{{{
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 300000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const char *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
bool pan(int k,int n)
{
int ma,mi;
for(int i=0;i<n;i++)
{
if(ht[i]<k)
{
ma=sa[i];
mi=sa[i];
}
else
{
ma=max(ma,sa[i]);
mi=min(mi,sa[i]);
if(ma-mi>=k) return 1;
}
}
return 0;
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
string a,b;
char *c;
int n;
int t;
int main()
{
cin>>a>>b;
t=a.size();
a=a+'#'+b;
n=a.size();
c=(char*)a.data();
nico.construct(c,n,256);
int ans=0;
for(int i=1;i<n;i++)
{
if(nico.sa[i]>t&&nico.sa[i-1]<t) ans=max(ans,nico.ht[i]);
if(nico.sa[i]<t&&nico.sa[i-1]>t) ans=max(ans,nico.ht[i]);
}
cout<<ans<<endl;
return 0;
}
}}}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。
{{{
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 100000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const char *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
int ff()
{
int ans=0;
for(int L=1;L<=len;L++)
{
for (int i=0;i+L<len;i+=L)
{
int R=lcp(i,i+L);
ans=max(ans,R/L+1);
if (i>=L-R%L)
{
ans=max(lcp(i-L+R%L,i+R%L)/L+1,ans);
}
}
}
return ans;
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
int n,k;
char u[100010]={};
int main()
{
scanf("%s",u);
nico.construct(u,strlen(u),256);
printf("%d\n",nico.ff());
return 0;
}
}}}
执行方法：在终端下，进入当前目录，输入"sh ./nick.sh",（其中nick.sh为当前shell脚本名）
{{{
while true; do
./make>tmp.in #出数据
./tmp<tmp.in>tmp.out #被测程序
./tmp2<tmp.in>tmp2.out #正确（暴力）程序
if diff tmp.out tmp2.out; then #比较两个输出文件
printf AC #结果相同显示AC
else
echo WA #结果不同显示WA，并退出
#cat tmp.out tmp2.out
exit 0
fi #if的结束标志,与C语言相反，0为真
done # while的结束标志
#BY NICK WONG 2014-08-29
#在终端下，进入当前目录，输入"sh ./nick.sh",（其中nick.sh为当前shell脚本名） '#'表示单行注释
#diff在两文件相同时返回空串
}}}队伍信息
- 队名：tdmxtxwd
- 成员：
- 梁露(potaty)
- 蔡嘉楠(Naylor)
- 华铱炜(mssjtxwd)
jiaxun
http://opentrains.snarknews.info/~ejudge/team.cgi?SID=4f3b1d33e5ab972a&action=2<=1
补题
zimpha学长姿势题补题情况
http://codeforces.com/gym/100633 D题, 树分治的一个应用
http://acm.hdu.edu.cn/showproblem.php?pid=5314, 树分治的一个应用 已补By mssjtxwd
http://acm.zju.edu.cn:9999/onlinejudge/showProblem.do?problemId=5427, 7月集训, 树分治的一个应用
http://www.lydsy.com/JudgeOnline/problem.php?id=4182, 树分治的一个应用
http://codeforces.com/gym/100633 J题, 一类组合数取模
http://main.edu.pl/en/archive/ontak/2010/pal, 一类字符串计数题, kmp数组也可做
http://main.edu.pl/en/archive/ontak/2010/dus, 一定在二分图最大匹配上的点
https://www.codechef.com/JULY15/problems/HAMILG, 一定在一般图最大匹配上的点
https://www.codechef.com/JUNE15/problems/CHEFBOOK, 线性规划->费用流
https://www.codechef.com/JULY15/problems/EASYEX, 生成函数的应用
https://www.codechef.com/MAY15/problems/GRAPHCNT, Dominator Tree的应用
https://www.codechef.com/problems/PALPROB, 回文树的一个应用
https://www.hackerrank.com/contests/csindia14-er1/challenges/fill-the-tank, 某天晚上群里介绍过的姿势
http://acm.hdu.edu.cn/showproblem.php?pid=5189, 树链剖分+线段树维护凸壳
https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2014/p/sum/, 一道有趣的构造题, 题解参考http://yun.baidu.com/share/link?shareid=3559646679&uk=3627228315
https://www.hackerrank.com/contests/w8/challenges/black-box-1, 线性基(好像是这么叫的)
http://codeforces.com/gym/100551, 5到图论分治题, 参考讨论http://codeforces.com/blog/entry/15296
对生成函数有需求的可以看这里: http://pan.baidu.com/s/1kTKJip5
dominator tree可以做的题:
1. shi哥当年多校有一题
2. codechef有一题(见之前推荐的题目列表)
3. neerc 2014 southern有一题
4. spoj有若干模板题
推荐一些波兰人的题目 https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/p/
题目翻译在这里http://zimpha.github.io/2015/09/23/ontak-2015-translation/, 今天晚上可以完工, 感兴趣的学长可以去做下
后缀树：
opencup I题用后缀树的代码 http://ideone.com/1zLpMn
http://codeforces.com/blog/entry/16780
http://ideone.com/sT8Vd1
模板
函数式线段树模板:
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000007
#define M 100007
#define N 111
#define ll long long
#define mod 1000000007
#define eps 1e-8
int L[M<<5], R[M<<5], sum[M<<5];
int tail;
int a[M], b[M], lisan[M], cnt;
void build( int l, int r, int &p )
{
p = ++tail; sum[p] = 0;
if( l >= r ) return;
int m = l + r >> 1;
build( l, m, L[p] );
build( m+1, r, R[p] );
}
void update( int pre, int &p, int l, int r, int x )
{
p = ++tail;
L[p] = L[pre], R[p] = R[pre], sum[p] = sum[pre] + 1;
if( l >= r ) return;
int m = l + r >> 1;
if( x <= m ) update( L[pre], L[p], l, m, x );
else update( R[pre], R[p], m+1, r, x );
}
int query( int u, int v, int l, int r, int k )
{
if( l >= r ) return l;
int m = l + r >> 1;
int num = sum[L[v]] - sum[L[u]];
if( num >= k ) return query( L[u], L[v], l, m, k );
else return query( R[u], R[v], m+1, r, k - num );
}
int main()
{
//freopen( "a.in", "r", stdin );
int T, n, m, x, l, r, k;
scanf( "%d", &T );
while( T-- ){
scanf( "%d%d", &n, &m );
tail = 0;
for( int i = 1; i <= n; ++i ){
scanf( "%d", a+i );
lisan[i] = a[i];
}
sort( lisan + 1, lisan + n + 1 );
cnt = unique( lisan + 1, lisan + n + 1 ) - lisan - 1;
build( 1, cnt, b[0] );
for( int i = 1; i <= n; ++i ){
x = lower_bound( lisan+1, lisan + cnt + 1, a[i] ) - lisan;
update( b[i-1], b[i], 1, cnt, x );
}
for( int i = 0; i < m; ++i ){
scanf( "%d%d%d", &l, &r, &k );
x = query( b[l-1], b[r], 1, cnt, k );
printf( "%d\n", lisan[x] );
}
}
}
FFT模板：
#define mul(a, b) (Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x))
struct Complex {}; // `something omitted`
void FFT(Complex P[], int n, int oper) {
for (int i = 1, j = 0; i < n - 1; i++) {
for (int s = n; j ^= s >>= 1, ~j & s; );
if (i < j) swap(P[i], P[j]);
}
for (int d = 0; (1 << d) < n; d++) {
int m = 1 << d, m2 = m * 2;
double p0 = PI / m * oper;
Complex unit_p0(cos(p0), sin(p0));
for (int i = 0; i < n; i += m2) {
Complex unit(1.0, 0.0);
for (int j = 0; j < m; j++) {
Complex &P1 = P[i + j + m], &P2 = P[i + j];
Complex t = mul(unit, P1);
P1 = Complex(P2.x - t.x, P2.y - t.y);
P2 = Complex(P2.x + t.x, P2.y - t.y);
unit = mul(unit, unit_p0);
}}}}
vector<int> doFFT(const vector<int> &a, const vector<int> &b) {
vector<int> ret(max(0, (int) a.size() + (int) b.size() - 1), 0);
static Complex A[MAXB], B[MAXB], C[MAXB];
int len = 1; while (len < (int)ret.size()) len *= 2;
for (int i = 0; i < len; i++) A[i] = i < (int)a.size() ? a[i] : 0;
for (int i = 0; i < len; i++) B[i] = i < (int)b.size() ? b[i] : 0;
FFT(A, len, 1); FFT(B, len, 1);
for (int i = 0; i < len; i++) C[i] = mul(A[i], B[i]);
FFT(C, len, -1);
for (int i = 0; i < (int)ret.size(); i++)
ret[i] = (int) (C[i].x / len + 0.5);
return ret;
}
NTT模板：
const int MOD = 786433, PRIMITIVE_ROOT = 10; // `$3 * 2 ^ {18} + 1$`
const int MAXB = 1 << 20;
int getMod(int downLimit) { // `或者现场自己找一个MOD`
for (int c = 3; ; ++c) { int t = (c << 21) | 1;
if (t >= downLimit && isPrime(t)) return t;
}}
int modInv(int a) { return a <= 1 ? a : (long long) (MOD - MOD / a) * modInv(MOD % a) % MOD; }
void NTT(int P[], int n, int oper) {
for (int i = 1, j = 0; i < n - 1; i++) {
for (int s = n; j ^= s >>= 1, ~j & s;);
if (i < j) swap(P[i], P[j]);
}
for (int d = 0; (1 << d) < n; d++) {
int m = 1 << d, m2 = m * 2;
long long unit_p0 = powMod(PRIMITIVE_ROOT, (MOD - 1) / m2);
if (oper < 0) unit_p0 = modInv(unit_p0);
for (int i = 0; i < n; i += m2) {
long long unit = 1;
for (int j = 0; j < m; j++) {
int &P1 = P[i + j + m], &P2 = P[i + j];
int t = unit * P1 % MOD;
P1 = (P2 - t + MOD) % MOD; P2 = (P2 + t) % MOD;
unit = unit * unit_p0 % MOD;
}}}}
vector<int> mul(const vector<int> &a, const vector<int> &b) {
vector<int> ret(max(0, (int) a.size() + (int) b.size() - 1), 0);
static int A[MAXB], B[MAXB], C[MAXB];
int len = 1; while (len < (int)ret.size()) len <<= 1;
for (int i = 0; i < len; i++) A[i] = i < (int)a.size() ? a[i] : 0;
for (int i = 0; i < len; i++) B[i] = i < (int)b.size() ? b[i] : 0;
NTT(A, len, 1); NTT(B, len, 1);
for (int i = 0; i < len; i++) C[i] = (long long) A[i] * B[i] % MOD;
NTT(C, len, -1); for (int i = 0, inv = modInv(len); i < (int)ret.size(); i++) ret[i] = (long long) C[i] * inv % MOD;
return ret;
}
倍增
1. DFS预处理出所有节点的深度和父节点
inline void dfs(int u)
{
int i;
for(i=head[u];i!=-1;i=next[i])
{
if (!deep[to[i]])
{
deep[to[i]] = deep[u]+1;
p[to[i]][0] = u; //p[x][0]保存x的父节点为u;
dfs(to[i]);
}
}
}
2. 初始各个点的2^j祖先是谁 ,其中 2^j (j =0...log(该点深度))倍祖先，1倍祖先就是父亲，2倍祖先是父亲的父亲......。
void init()
{
int i,j;
//p[i][j]表示i结点的第2^j祖先
for(j=1;(1<<j)<=n;j++)
for(i=1;i<=n;i++)
if(p[i][j-1]!=-1)
p[i][j]=p[p[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
3.从深度大的节点上升至深度小的节点同层，如果此时两节点相同直接返回此节点，即lca。
否则，利用倍增法找到最小深度的 p[a][j]!=p[b][j]，此时他们的父亲p[a][0]即lca。
int lca(int a,int b)//最近公共祖先
{
int i,j;
if(deep[a]<deep[b])swap(a,b);
for(i=0;(1<<i)<=deep[a];i++);
i--;
//使a，b两点的深度相同
for(j=i;j>=0;j--)
if(deep[a]-(1<<j)>=deep[b])
a=p[a][j];
if(a==b)return a;
//倍增法，每次向上进深度2^j，找到最近公共祖先的子结点
for(j=i;j>=0;j--)
{
if(p[a][j]!=-1&&p[a][j]!=p[b][j])
{
a=p[a][j];
b=p[b][j];
}
}
return p[a][0];
}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 100000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const int *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
int n,k;
int u[20010]={};
bool pan(int x,int y)
{
int num=0;
for(int i=1;i<n;i++)
{
if(nico.ht[i]>=x) num++;
else num=0;
if(num>=y) return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&u[i]);
}
nico.construct(u,n,256);
k--;
int l=0;
int r=n;
while(l<r)
{
int mid=(l+r)/2+1;
if(pan(mid,k)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？
因为两次这个情况非常特殊，所以我们可以把字典序相邻的，整体公共前缀长度>k>k的打包，然后求一下最近的位置mama和最远的位置mimi，用ma−mi>=kma−mi>=k来判断这个公共前缀是否重复两次。
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 100000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const int *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
bool pan(int k,int n)
{
int ma,mi;
for(int i=0;i<n;i++)
{
if(ht[i]<k)
{
ma=sa[i];
mi=sa[i];
}
else
{
ma=max(ma,sa[i]);
mi=min(mi,sa[i]);
if(ma-mi>=k) return 1;
}
}
return 0;
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
int n;
int u[100010]={};
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&u[i]);
}
nico.construct(u,n,256);
int l=0;
int r=n;
while(l<r)
{
int mid=(l+r)/2+1;
if(nico.pan(mid,n)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。
旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？
思路比较显然，就是把字符串合起来排个序，然后判断一下相邻字典序的后缀是不是属于两个串，感觉也可以推广到多个串？
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 300000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const char *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
bool pan(int k,int n)
{
int ma,mi;
for(int i=0;i<n;i++)
{
if(ht[i]<k)
{
ma=sa[i];
mi=sa[i];
}
else
{
ma=max(ma,sa[i]);
mi=min(mi,sa[i]);
if(ma-mi>=k) return 1;
}
}
return 0;
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
string a,b;
char *c;
int n;
int t;
int main()
{
cin>>a>>b;
t=a.size();
a=a+'#'+b;
n=a.size();
c=(char*)a.data();
nico.construct(c,n,256);
int ans=0;
for(int i=1;i<n;i++)
{
if(nico.sa[i]>t&&nico.sa[i-1]<t) ans=max(ans,nico.ht[i]);
if(nico.sa[i]<t&&nico.sa[i-1]>t) ans=max(ans,nico.ht[i]);
}
cout<<ans<<endl;
return 0;
}
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
const static int MAXN = 100000 + 10;
int cnt[MAXN], tr[2][MAXN], ts[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN], len;
void construct(const char *s, int n, int m=256) {
int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
for (k=1;k<=n;k<<=1) {
for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
partial_sum(cnt,cnt+n+1,cnt);
for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
for (i=rk[sa[0]]=0;i+1<n;++i) {
rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
}
}
for (i=0,k=0;i<n;++i) {
if (!rk[i]) continue;
for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
ht[rk[i]]=k; if (k) k--;
}
rmq_init(n);
}
inline int lcp(int a, int b) {
a=rk[a],b=rk[b];
if (a == b) return len - a + 1;
if (a>b) swap(a,b);
return rmq(a+1,b);
}
int ff()
{
int ans=0;
for(int L=1;L<=len;L++)
{
for (int i=0;i+L<len;i+=L)
{
int R=lcp(i,i+L);
ans=max(ans,R/L+1);
if (i>=L-R%L)
{
ans=max(lcp(i-L+R%L,i+R%L)/L+1,ans);
}
}
}
return ans;
}
private:
int mx[MAXN][20], LOG[MAXN];
void rmq_init(int n) {
for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
for (int i=0;i<n;++i) mx[i][0]=ht[i];
for (int i,j=1;(1<<j)<n;++j) {
for (i=0;i+(1<<j)<=n;++i)
mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int a, int b) {
int k=LOG[b-a+1];
return min(mx[a][k],mx[b-(1<<k)+1][k]);
}
} nico;
int n,k;
char u[100010]={};
int main()
{
scanf("%s",u);
nico.construct(u,strlen(u),256);
printf("%d\n",nico.ff());
return 0;
}
执行方法：在终端下，进入当前目录，输入"sh ./nick.sh",（其中nick.sh为当前shell脚本名）
while true; do
./make>tmp.in #出数据
./tmp<tmp.in>tmp.out #被测程序
./tmp2<tmp.in>tmp2.out #正确（暴力）程序
if diff tmp.out tmp2.out; then #比较两个输出文件
printf AC #结果相同显示AC
else
echo WA #结果不同显示WA，并退出
#cat tmp.out tmp2.out
exit 0
fi #if的结束标志,与C语言相反，0为真
done # while的结束标志
#BY NICK WONG 2014-08-29
#在终端下，进入当前目录，输入"sh ./nick.sh",（其中nick.sh为当前shell脚本名） '#'表示单行注释
#diff在两文件相同时返回空串
附加文件
- treeSplit.cpp by mssjtxwd
- 1005.cpp by mssjtxwd