综合性很强的一道题目，结合manacher，后缀数组，哈希，RMQ，二分可解。
基本思路是通过manacher可以找到所有可能的回文串，哈希去重，后缀数组二分找数目。最后暴力求解。
需要注意kth需要为__int64。
/* 4426 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const __int64 mod = 777777777LL;
const int seed = ;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+;
// input
char s[maxn];
int val[];
__int64 V[maxn];
// manacher
char ss[maxn*];
int P[maxn*];
// sa
int a[maxn];
int height[maxn], sa[maxn], rrank[maxn];
int wa[maxn], wb[maxn], wc[maxn], wv[maxn];
// RMQ
int dp[maxn][];
// Hash
unsigned __int64 H[maxn];
// init
unsigned __int64 Base[maxn], Power[maxn];
vpii pal;
set<unsigned __int64> st; void init() {
Base[] = Power[] = ;
rep(i, , maxn) {
Base[i] = 1LL * Base[i-] * % mod;
Power[i] = 1LL * Power[i-] * seed;
}
} void init_Hash(int n) {
H[] = s[] - 'a' + ;
rep(i, , n)
H[i] = H[i-] * seed + s[i]-'a'+;
} unsigned __int64 getHash(int l, int r) {
if (l == )
return H[r];
return H[r] - H[l-] * Power[r-l+];
} bool 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, *x=wa, *y=wb, *t, p; for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[x[i]=r[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) sa[--wc[x[i]]] = i;
for (j=,p=; p<n; j*=, m=p) {
for (p=,i=n-j; i<n; ++i) y[p++] = i;
for (i=; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i]-j;
for (i=; i<n; ++i) wv[i] = x[y[i]];
for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[wv[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) sa[--wc[wv[i]]] = y[i];
for (t=x,x=y,y=t,p=,x[sa[]]=, i=; i<n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;
}
} void calheight(int *r, int *sa, int n) {
int i, j, k = ; for (i=; i<=n; ++i) rrank[sa[i]] = i;
for (i=; i<n; height[rrank[i++]]=k)
for (k?k--:, j=sa[rrank[i]-]; r[j+k]==r[i+k]; ++k) ;
} void init_RMQ(int n) {
int i, j; for (i=; i<=n; ++i)
dp[i][] = height[i];
dp[][] = INF;
for (j=; (<<j)<=n; ++j)
for (i=; i+(<<j)-<=n; ++i)
dp[i][j] = min(dp[i][j-], dp[i+(<<(j-))][j-]);
} int RMQ(int l, int r) {
if (l > r)
swap(l, r); ++l;
int k = ; while (<<(k+) <= r-l+)
++k; return min(dp[l][k], dp[r-(<<k)+][k]);
} void Manacher(char *s, int *P, int n) {
pal.clr();
st.clr(); int i, j, mx = , id = ; for (i=; i<n; ++i) {
P[i] = mx>i ? min(P[*id-i], mx-i) : ;
while (s[i+P[i]] == s[i-P[i]])
++P[i];
if (i+P[i] > mx) {
for (j=mx; j<i+P[i]; ++j) {
int l = *i-j, r = j;
l >>= ;
r = (r & ) ? (r>>) : (r>>)-;
if (l > r)
continue; unsigned __int64 hval = getHash(l, r);
if (st.find(hval) == st.end()) {
st.insert(hval);
pal.pb(mp(l, r));
}
}
mx = i + P[i];
id = i;
}
}
} int getCnt(int fr, int to, int n) {
int len = to - fr + ;
int rankfr = rrank[fr];
int l, r, mid, tmp;
int L = rankfr, R = rankfr; // find left most
l = , r = rankfr - ;
while (l <= r) {
mid = (l + r) >> ;
tmp = RMQ(mid, rankfr);
if (tmp >= len) {
L = mid;
r = mid - ;
} else {
l = mid + ;
}
} // find right most
l = rankfr + , r = n;
while (l <= r) {
mid = (l + r) >> ;
tmp = RMQ(rankfr, mid);
if (tmp >= len) {
R = mid;
l = mid + ;
} else {
r = mid - ;
}
} return R - L + ;
} void init_Val(int n) {
V[] = val[s[]-'a'];
rep(i, , n)
V[i] = (V[i-] * + val[s[i]-'a']) % mod;
} __int64 getVal(int l, int r) {
if (l == )
return V[r];
return (V[r] - V[l-] * Base[r-l+]%mod + mod) % mod;
} void printSa(int n) {
for (int i=; i<=n; ++i)
printf("%d ", sa[i]);
putchar('\n');
} void printHeight(int n) {
for (int i=; i<=n; ++i)
printf("%d ", height[i]);
putchar('\n');
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t;
int n, q;
__int64 kth;
int ans;
vpii vc; init();
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &q);
scanf("%s", s); // init sa
rep(i, , n)
a[i] = s[i]-'a'+;
a[n] = ;
da(a, sa, n+, );
calheight(a, sa, n);
init_RMQ(n); // init Hash
init_Hash(n); // init Manacher
int l = ;
ss[l++] = '@';
// ss[l++] = '#';
rep(i, , n) {
ss[l++] = s[i];
ss[l++] = '#';
}
ss[l] = '\0';
Manacher(ss, P, l); // find count of palindromic
int sz = SZ(pal);
rep(i, , sz) {
wc[i] = getCnt(pal[i].fir, pal[i].sec, n);
pal[i].sec = (pal[i].fir + pal[i].sec) >> ;
} while (q--) {
scanf("%I64d", &kth);
rep(i, , )
scanf("%d", &val[i]);
init_Val(n);
vc.clr();
rep(i, , sz) {
int tmp = getVal(pal[i].fir, pal[i].sec);
vc.pb(mp(tmp, wc[i]));
}
sort(all(vc));
ans = -;
rep(i, , sz) {
if (kth <= vc[i].sec) {
ans = vc[i].fir;
break;
} else {
kth -= vc[i].sec;
}
}
printf("%d\n", ans);
}
putchar('\n');
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
数据发生器。
from random import randint, shuffle
import shutil
import string def GenDataIn():
with open("data.in", "w") as fout:
t = 20
bound = 10**3
lc = list(string.lowercase)
uc = list(string.uppercase)
fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(10**4, 10**5)
q = randint(30, 40)
fout.write("%d %d\n" % (n, q))
line = ""
for j in xrange(n):
idx = randint(0, 25)
line += lc[idx]
fout.write("%s\n" % (line))
for i in xrange(q):
kth = randint(1, 1005)
dataList = [kth]
for j in xrange(26):
val = randint(0, 25)
dataList.append(val)
fout.write(" ".join(map(str, dataList)) + "\n") def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()