总共十道题， 又结束了一场逗比的比赛， 感觉后半场都在梦游，结果被虐了！！！！大家都虐我一万里啊。
正如wushen说的，“那些被虐过的比赛，唯有赛后AK掉来泄愤。”
本弱太菜，还达不到AK的境界，只能搞出这场的8道题。
A
A Matrix
一个很神奇的题目，全场就坑在这题了，其实应该画几组去看看的，比较容易发现规律的。
根据规则可以知道，一个数想要往下走一行，必须有个比它小的数在后面插入，把它推下去。
题目要求输出逆序 后 字典序最大的结果。
其实首先要每行是递增的。
然后每一行的数，在上一行找一个比它小，而且没有使用过的。
然后就形成了一颗颗链， 把链输出就是结果了。
也可以使用拓扑排序，结果是一样的。
这题就是要靠智商啊，要锻炼自己YY的能力了。
来代码吧！
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 11:38:45
File Name :E:\2014ACM\比赛\2014北京邀请赛\A.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN = ;
vector<int>vec[MAXN];
int pre[MAXN];
vector<int>ans;
void add(int u)
{
if(u == -)return ;
add(pre[u]);
ans.push_back(u);
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int iCase = ;
scanf("%d",&T);
int n,m;
while(T--)
{
iCase++;
scanf("%d%d",&n,&m);
for(int i = ;i < m;i++)
vec[i].clear();
for(int i = ;i < m;i++)
{
int num;
int x;
scanf("%d",&num);
while(num--)
{
scanf("%d",&x);
vec[i].push_back(x);
}
}
bool flag = true;
for(int i = ;i < m;i++)
{
int sz = vec[i].size();
for(int j = ;j < sz;j++)
if(vec[i][j] < vec[i][j-])
{
flag = false;
break;
}
}
if(!flag)
{
printf("Case #%d: No solution\n",iCase);
continue;
}
memset(pre,-,sizeof(pre));
for(int i = m-;i > ;i--)
{
int sz = vec[i].size();
int p = vec[i-].size();
for(int j = sz-;j >= ;j--)
{
if(p <= )
{
flag = false;
break;
}
p = lower_bound(vec[i-].begin(),vec[i-].begin()+p,vec[i][j]) - vec[i-].begin() + ;
p--;
if(p <= )
{
flag = false;
break;
}
pre[vec[i-][p-]] = vec[i][j];
p--;
}
}
if(!flag)
{
printf("Case #%d: No solution\n",iCase);
continue;
}
ans.clear();
for(int i = ;i < vec[].size();i++)
add(vec[][i]);
printf("Case #%d:",iCase);
for(int i = ;i < n;i++)
printf(" %d",ans[i]);
printf("\n");
} return ;
}
代码君
B
Beautiful Garden
题目： x轴上有n颗树，要求移动最少树的位置，使得相邻两颗树的距离都一样。
暴力枚举，复杂度是n^4logn的
最后结果肯定有两个树是不动的，然后没有两颗树之间插入几个，就知道公差了，然后去搞。
树可以移动到非整数点，但是好像没有必要，我做的时候是考虑了公差是浮点数啥的。
注意特判n<=2 的时候
代码：
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 12:59:17
File Name :E:\2014ACM\比赛\2014北京邀请赛\B.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
long long gcd(long long a,long long b)
{
if(b == )return a;
return gcd(b,a%b);
}
int a[];
map<long long,int>mp; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n;
int iCase = ;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d",&n);
mp.clear();
for(int i = ;i < n;i++)
{
scanf("%d",&a[i]);
if(mp.find(a[i]) == mp.end())mp[a[i]] = ;
else mp[a[i]]++;
}
if(n <= )
{
printf("Case #%d: 0\n",iCase);
continue;
}
int ans = n;
for(int i = ;i < n;i++)
for(int j = i+;j < n;j++)
{
long long d2 = a[i] - a[j];
if(d2 == )
{
ans = min(ans,n - mp[a[i]]);
continue;
}
if(d2 < )d2 = -d2;
for(int k = ;k <= n-;k++)
{
long long dis = k+;
long long g = gcd(dis,d2);
long long d = d2/g;
dis /= g;
long long c = min(a[i],a[j]);
int cnt = ;
for(int x = ;x < n;x += dis)
{
if(mp.find(c) != mp.end())cnt++;
c += d;
}
ans = min(ans,n-cnt);
}
}
printf("Case #%d: %d\n",iCase,ans);
}
return ;
}
代码君
C
Champions League
这个题目很暴力。
其实可以发现只有前6大的group是有效的，这个可以反证法去思考下。
然后对于前6大，暴力状态压缩DP下就是答案了，情况不多的，很少。
很黄很暴力啊^_^
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 12:03:28
File Name :E:\2014ACM\比赛\2014北京邀请赛\C.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN = ;
struct Node
{
int a[][];
void input()
{
for(int i = ;i < ;i++)
for(int j = ;j < ;j++)
scanf("%d",&a[i][j]);
}
int b[];
void init()
{
int cnt = ;
for(int i = ;i < ;i++)
for(int j = ;j < ;j++)
if(i != j)
b[cnt++] = a[i][j];
sort(b,b+cnt);
reverse(b,b+cnt);
}
int c[];//二进制表示选哪一天的最大值
int day[][];//每天的组合情况
void calc()
{
for(int i = ;i < (<<);i++)
c[i] = ;
int d[];
for(int d1 = ;d1 < ; d1++)
for(int d2 = ; d2 < ;d2++)
if(d1 != d2)
for(int k = ;k < (<<);k++)
{
memset(day,-,sizeof(day));
day[][] = ; day[][] = d1;
day[][] = ; day[][] = d2;
day[][] = ; day[][] = - d1 - d2;
for(int i = ;i < ;i++)
for(int j = ;j < ;j++)
if(j != day[i][] && j != day[i][])
{
if(day[i][] == -)day[i][] = j;
else day[i][] = j;
}
if(k & (<<))swap(day[][],day[][]);
if(k & (<<))swap(day[][],day[][]);
if(k & (<<))swap(day[][],day[][]);
if(k & (<<))swap(day[][],day[][]);
if(k & (<<))swap(day[][],day[][]);
if(k & (<<))swap(day[][],day[][]);
for(int i = ;i < ;i++)
for(int j = ;j < ;j++)
day[i][j] = day[i-][j^];
for(int i = ;i < ;i++)
d[i] = max(a[day[i][]][day[i][]],a[day[i][]][day[i][]]);
for(int i = ;i < (<<);i++)
{
int tmp = ;
for(int j = ;j < ;j++)
if(i & (<<j))
tmp += d[j];
c[i] = max(c[i],tmp);
}
}
}
}node[MAXN];
bool cmp(Node a,Node b)
{
for(int i = ;i < ;i++)
{
if(a.b[i] > b.b[i])return true;
else if(a.b[i] < b.b[i])return false;
}
return true;
} int dp[][];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n;
int iCase = ;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d",&n);
for(int i = ;i < n;i++)
node[i].input();
if(n > )
{
for(int i = ;i < n;i++)
node[i].init();
sort(node,node+n,cmp);
n = ;
}
for(int i = ;i < n;i++)node[i].calc();
memset(dp,,sizeof(dp));
for(int i = ;i <= n;i++)
for(int j = ;j < (<<);j++)
{
for(int k = ;k < (<<);k++)
if((j|k) == j)
dp[i][j] = max(dp[i][j],dp[i-][k]+node[i-].c[j^k]);
}
printf("Case #%d: %d\n",iCase,dp[n][(<<)-]);
}
return ;
}
代码君
D：
Dices in Yahtzee
这题我现场理解错意思了， 那个最佳策略 其实是不知道结果的，是按照一个个分配的。
然后就很水了，状态压缩下，搞概率DP
裸的话，复杂度是2^14 * 6^5 * 14 有点大。
可以把6^5稍微优化下，排序从小到大。
这题更加暴力了，思路也很简单。
我写成5个循环了，就是要体现暴力性！！
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 23:06:03
File Name :E:\2014ACM\比赛\2014北京邀请赛\D.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
double p[]; double pp[][][][][];
int s[][][][][][];
bool used[][][][][];
void calc(int a,int b,int c,int d,int e,double tp)
{
int x[];
x[] = a; x[] = b; x[] = c; x[] = d; x[] = e;
sort(x,x+);
a = x[]; b = x[]; c = x[]; d = x[]; e = x[];
if(used[a][b][c][d][e])
{
pp[a][b][c][d][e] += tp;
return;
}
pp[a][b][c][d][e] = tp;
used[a][b][c][d][e] = true; memset(s[a][b][c][d][e],,sizeof(s[a][b][c][d][e]));
for(int i = ;i < ;i++)
s[a][b][c][d][e][x[i]] += x[i]+;
int sum = a + b + c + d + e + ;
int cnt[];
for(int i = ;i < ;i++)cnt[i] = ;
for(int i = ;i < ;i++)
cnt[x[i]]++;
if( (cnt[] && cnt[] && cnt[] && cnt[] && cnt[]) ||
(cnt[] && cnt[] && cnt[] && cnt[] && cnt[]) )
s[a][b][c][d][e][] = ;
if( (cnt[] && cnt[] && cnt[] && cnt[]) ||
(cnt[] && cnt[] && cnt[] && cnt[]) ||
(cnt[] && cnt[] && cnt[] && cnt[]) )
s[a][b][c][d][e][] = ;
sort(cnt,cnt+);
if(cnt[] >= && cnt[] >= )
s[a][b][c][d][e][] = sum;
if(cnt[] >= )
s[a][b][c][d][e][] = sum;
if(cnt[] >= )
s[a][b][c][d][e][] = sum;
if(cnt[] == && cnt[] == )
s[a][b][c][d][e][] = ;
if(cnt[] == )
s[a][b][d][d][e][] = ;
s[a][b][c][d][e][] = sum;
}
double dp[(<<)+]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int iCase = ;
scanf("%d",&T);
while(T--)
{
iCase++;
for(int i = ;i < ;i++)scanf("%lf",&p[i]);
memset(used,false,sizeof(used));
for(int a = ;a < ;a++)
for(int b = ;b < ;b++)
for(int c = ;c < ;c++)
for(int d = ;d < ;d++)
for(int e = ;e < ;e++)
{
double tp = p[a]*p[b]*p[c]*p[d]*p[e];
calc(a,b,c,d,e,tp);
}
dp[(<<)-] = 0.0;
for(int i = (<<)-;i >= ;i--)
{
dp[i] = 0.0;
for(int a = ;a < ;a++)
for(int b = a;b < ;b++)
for(int c = b;c < ;c++)
for(int d = c;d < ;d++)
for(int e = d;e < ;e++)
{
double tmp = ;
for(int j = ;j < ;j++)
if( (i & (<<j)) == )
tmp = max(tmp,dp[i|(<<j)]+s[a][b][c][d][e][j]);
dp[i] += tmp * pp[a][b][c][d][e];
}
}
printf("Case #%d: %.6lf\n",iCase,dp[]);
}
return ;
}
代码君
E：
Elegant String
写出状态转移方程。
dp[i][j] 表示长度是i, 后面有j个不同。
然后矩阵也很好写了。
注意是要想状态转移方程。
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 13:11:27
File Name :E:\2014ACM\比赛\2014北京邀请赛\E.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MOD = ;
struct Matrix
{
int mat[][];
int n;
void init(int _n)
{
n = _n;
memset(mat,,sizeof(mat));
}
Matrix operator *(const Matrix &b)const
{
Matrix ret;
ret.n = n;
for(int i = ;i < n;i++)
for(int j = ;j < n;j++)
{
ret.mat[i][j] = ;
for(int k = ;k < n;k++)
{
ret.mat[i][j] += (long long)mat[i][k]*b.mat[k][j]%MOD;
if(ret.mat[i][j] >= MOD)
ret.mat[i][j] -= MOD;
}
}
return ret;
}
};
Matrix pow_M(Matrix a,long long n)
{
Matrix ret;
ret.init(a.n);
for(int i = ;i < a.n;i++)
ret.mat[i][i] = ;
Matrix tmp = a;
while(n)
{
if(n&)ret = ret*tmp;
tmp = tmp*tmp;
n >>= ;
}
return ret;
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int k;
long long n;
scanf("%d",&T);
int iCase = ;
while(T--)
{
iCase++;
cin>>n>>k;
if(n <= )
{
printf("Case #%d: %d\n",iCase,k+);
continue;
}
Matrix A;
A.init(k);
for(int i = ;i < k;i++)
for(int j = ;j <= i;j++)
A.mat[i][j] = ;
for(int i = ;i < k-;i++)
A.mat[i][i+] = k - i;
A = pow_M(A,n-);
long long ans = ;
for(int i = ;i < k;i++)
{
ans += (long long)(k+)*A.mat[][i]%MOD;
ans %= MOD;
}
printf("Case #%d: %d\n",iCase,(int)ans);
}
return ;
}
代码君
F：
Football on Table
属于暴力搞过去了，没啥算法。
读懂题就可以了
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 13:50:23
File Name :E:\2014ACM\比赛\2014北京邀请赛\F.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const double eps = 1e-;
double a[];
double b[];
double suma[];
double sumb[]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
double L,W;
int T;
int iCase = ;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%lf%lf",&L,&W);
double X,Y,dx,dy;
scanf("%lf%lf%lf%lf",&X,&Y,&dx,&dy);
int m;
scanf("%d",&m);
double ans = 1.0;
while(m--)
{
double x;
int n;
scanf("%lf%d",&x,&n);
for(int i = ;i <= n;i++)
scanf("%lf",&a[i]);
for(int i = ;i < n;i++)
scanf("%lf",&b[i]);
if(x <= X)
continue;
double y = Y + (x - X)*dy/dx;
suma[] = 0.0;
for(int i = ;i <= n;i++)
suma[i] = suma[i-] + a[i];
sumb[] = 0.0;
for(int i = ;i < n;i++)
sumb[i] = sumb[i-] + b[i];
double LL = W - suma[n] - sumb[n-];
double tmp = ;
for(int i = ;i <= n;i++)
{
double down,up;
if(i == )
{
down = y;
up = LL;
}
else if(i == n)
{
down = ;
up = y - suma[n] - sumb[n-];
}
else
{
down = max(0.0,y - suma[i] - sumb[i]);
up = min(LL,y - suma[i] - sumb[i-]);
}
if(up > down)tmp += up - down;
}
ans *= tmp/LL;
}
printf("Case #%d: %.5lf\n",iCase,ans);
}
return ;
}
代码君
G
Great Escape
不会，(*^__^*) 貌似利用凸性吧， 在弥补中
H：
Happy Reversal
一前一后预处理下，很水。
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 13:23:41
File Name :E:\2014ACM\比赛\2014北京邀请赛\H.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std; long long two[];
long long a[];
long long b[];
long long c[];
long long d[];
char str[]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
two[] = ;
for(int i = ;i < ;i++)
two[i] = *two[i-];
int T;
int iCase = ;
int n,k;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d%d",&n,&k);
for(int i = ;i <= n;i++)
{
scanf("%s",str);
a[i] = b[i] = ;
for(int j = ;j < k;j++)
{
if(str[j] == '')a[i] += two[k-j-];
else b[i] += two[k-j-];
}
}
if(n <= )
{
printf("Case #%d: 0\n",iCase);
continue;
}
c[] = min(a[],b[]);
for(int i = ;i <= n;i++)
{
c[i] = min(a[i],b[i]);
c[i] = min(c[i],c[i-]);
}
d[n] = min(a[n],b[n]);
for(int i = n-;i >= ;i--)
{
d[i] = min(a[i],b[i]);
d[i] = min(d[i],d[i+]);
}
long long ans = ;
for(int i = ;i <= n;i++)
{
long long tmp1 = max(a[i],b[i]);
long long tmp2 ;
if(i == )tmp2 = d[i+];
else if(i == n)tmp2 = c[i-];
else tmp2 = min(c[i-],d[i+]);
ans = max(ans,tmp1-tmp2);
}
printf("Case #%d: %lld\n",iCase,ans);
}
return ;
}
代码君
I：
In A Maze
神几何，还不会
J：
Justice String
可以使用后缀数组，求lcp, 然后最多枚举，最多匹配三次。
或者使用exkmp, 前后求lcp,中间hash判断相等。
现场没有卡nlogn的SA, 重现时候用O(n)的SA才过
/* ***********************************************
Author :kuangbin
Created Time :2014/5/21 13:35:56
File Name :E:\2014ACM\比赛\2014北京邀请赛\J.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN=;
/*
int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中
bool cmp(int *r,int a,int b,int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int str[],int sa[],int rank[],int height[],int n,int m)
{
n++;
int i, j, p, *x = t1, *y = t2;
//第一轮基数排序，如果s的最大值很大，可改为快速排序
for(i = 0;i < m;i++)c[i] = 0;
for(i = 0;i < n;i++)c[x[i] = str[i]]++;
for(i = 1;i < m;i++)c[i] += c[i-1];
for(i = n-1;i >= 0;i--)sa[--c[x[i]]] = i;
for(j = 1;j <= n; j <<= 1)
{
p = 0;
//直接利用sa数组排序第二关键字
for(i = n-j; i < n; i++)y[p++] = i;//后面的j个数第二关键字为空的最小
for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;
//这样数组y保存的就是按照第二关键字排序的结果
//基数排序第一关键字
for(i = 0; i < m; i++)c[i] = 0;
for(i = 0; i < n; i++)c[x[y[i]]]++;
for(i = 1; i < m;i++)c[i] += c[i-1];
for(i = n-1; i >= 0;i--)sa[--c[x[y[i]]]] = y[i];
//根据sa和x数组计算新的x数组
swap(x,y);
p = 1; x[sa[0]] = 0;
for(i = 1;i < n;i++)
x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
if(p >= n)break;
m = p;//下次基数排序的最大值
}
int k = 0;
n--;
for(i = 0;i <= n;i++)rank[sa[i]] = i;
for(i = 0;i < n;i++)
{
if(k)k--;
j = sa[rank[i]-1];
while(str[i+k] == str[j+k])k++;
height[rank[i]] = k;
}
}
*/
/*
* 后缀数组
* DC3算法，复杂度O(n)
* 所有的相关数组都要开三倍
*/
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[MAXN*],wb[MAXN*],wv[MAXN*],wss[MAXN*];
int c0(int *r,int a,int b)
{
return r[a] == r[b] && r[a+] == r[b+] && r[a+] == r[b+];
}
int c12(int k,int *r,int a,int b)
{
if(k == )
return r[a] < r[b] || ( r[a] == r[b] && c12(,r,a+,b+) );
else return r[a] < r[b] || ( r[a] == r[b] && wv[a+] < wv[b+] );
}
void sort(int *r,int *a,int *b,int n,int m)
{
int i;
for(i = ;i < n;i++)wv[i] = r[a[i]];
for(i = ;i < m;i++)wss[i] = ;
for(i = ;i < n;i++)wss[wv[i]]++;
for(i = ;i < m;i++)wss[i] += wss[i-];
for(i = n-;i >= ;i--)
b[--wss[wv[i]]] = a[i];
}
void dc3(int *r,int *sa,int n,int m)
{
int i, j, *rn = r + n;
int *san = sa + n, ta = , tb = (n+)/, tbc = , p;
r[n] = r[n+] = ;
for(i = ;i < n;i++)if(i % != )wa[tbc++] = i;
sort(r + , wa, wb, tbc, m);
sort(r + , wb, wa, tbc, m);
sort(r, wa, wb, tbc, m);
for(p = , rn[F(wb[])] = , i = ;i < tbc;i++)
rn[F(wb[i])] = c0(r, wb[i-], wb[i]) ? p - : p++;
if(p < tbc)dc3(rn,san,tbc,p);
else for(i = ;i < tbc;i++)san[rn[i]] = i;
for(i = ;i < tbc;i++) if(san[i] < tb)wb[ta++] = san[i] * ;
if(n % == )wb[ta++] = n - ;
sort(r, wb, wa, ta, m);
for(i = ;i < tbc;i++)wv[wb[i] = G(san[i])] = i;
for(i = , j = , p = ;i < ta && j < tbc;p++)
sa[p] = c12(wb[j] % , 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++];
}
//str和sa也要三倍
void da(int str[],int sa[],int rank[],int height[],int n,int m)
{
for(int i = n;i < n*;i++)
str[i] = ;
dc3(str, sa, n+, m);
int i,j,k = ;
for(i = ;i <= n;i++)rank[sa[i]] = i;
for(i = ;i < n; i++)
{
if(k) k--;
j = sa[rank[i]-];
while(str[i+k] == str[j+k]) k++;
height[rank[i]] = k;
}
} int rank[MAXN],height[MAXN];
int RMQ[MAXN];
int mm[MAXN];
int best[][MAXN];
void initRMQ(int n)
{
mm[]=-;
for(int i=;i<=n;i++)
mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];
for(int i=;i<=n;i++)best[][i]=i;
for(int i=;i<=mm[n];i++)
for(int j=;j+(<<i)-<=n;j++)
{
int a=best[i-][j];
int b=best[i-][j+(<<(i-))];
if(RMQ[a]<RMQ[b])best[i][j]=a;
else best[i][j]=b;
}
}
int askRMQ(int a,int b)
{
int t;
t=mm[b-a+];
b-=(<<t)-;
a=best[t][a];b=best[t][b];
return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b)
{
a=rank[a];b=rank[b];
if(a>b)swap(a,b);
return height[askRMQ(a+,b)];
}
char A[MAXN],B[MAXN];
int r[MAXN];
int sa[MAXN]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int iCase = ;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%s%s",A,B);
int len1 = strlen(A);
int len2 = strlen(B);
if(len1 < len2)
{
printf("Case #%d: -1\n",iCase);
continue;
}
int n = len1+len2+;
for(int i = ;i < len1;i++)r[i] = A[i];
for(int i = ;i < len2;i++)r[len1++i] = B[i];
r[len1] = ;
r[n] = ;
da(r,sa,rank,height,n,);
for(int i = ;i <= n;i++)RMQ[i] = height[i];
initRMQ(n);
int ans = -;
for(int i = ;i <= len1-len2;i++)
{
int st = i;
int ed = len1 + ;
int tmp = lcp(st,ed);
st += tmp;
ed += tmp;
if(ed >= n)
{
ans = i;
break;
}
st++;
ed++;
if(ed >= n)
{
ans = i;
break;
}
tmp = lcp(st,ed);
st += tmp;
ed += tmp;
if(ed >= n)
{
ans = i;
break;
}
st++;
ed++;
if(ed >= n)
{
ans = i;
break;
}
tmp = lcp(st,ed);
st += tmp;
ed += tmp;
if(ed >= n)
{
ans = i;
break;
}
}
printf("Case #%d: %d\n",iCase,ans);
}
return ;
}
代码君