HDU 4898 The Revenge of the Princess’ Knight(后缀数组+二分+暴力)(2014 Multi-University Training Contest 4)
The devil’s birthday is approaching, of course, she wants some beautiful gift from the king. The king search everywhere in this kingdom, and finds a beautiful ring for her.
For simplicity, we can see this ring as a ring(so it is a cycle!) of lowercase characters with length n.
The king’s cute daughter, WJMZBMR, gets nothing from her father in her birthday. She feels very sad. By the influence of the king and the devil, this kingdom is full of lolicon, some people think the king is unfair to his kawayi daughter, so they form a party called princess’s knight and plan to destroy king’s gift for the devil to make things fair.
The knight of the knight (or the lolicon of the lolicon), a man called z*p, has the chance to destroy the ring now. But due to his limitless of strength, he can only cut this ring into exactly k continuous parts. To please the princess, he want among those part, the maximum one respect to the lexicographical order is minimized. How can he do it?
For each test case, the first line contains two integers n and k, which are the length of the ring and the parts z*p can cut.
The next line is a string represent the ring.
n <= 1000,1<=k<=n.
T <= 5.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; const int MAXN = ; char s[MAXN];
int sa[MAXN], rank[MAXN], c[MAXN], tmp[MAXN], height[MAXN];
int n, k, T; void makesa(int n, int m) {
memset(c, , m * sizeof(int));
for(int i = ; i < n; ++i) ++c[rank[i] = s[i]];
for(int i = ; i < m; ++i) c[i] += c[i - ];
for(int i = ; i < n; ++i) sa[--c[rank[i]]] = i;
for(int k = ; k < n; k <<= ) {
for(int i = ; i < n; ++i) {
int j = sa[i] - k;
if(j < ) j += n;
tmp[c[rank[j]]++] = j;
}
int j = c[] = sa[tmp[]] = ;
for(int i = ; i < n; ++i) {
if(rank[tmp[i]] != rank[tmp[i - ]] || rank[tmp[i] + k] != rank[tmp[i - ] + k])
c[++j] = i;
sa[tmp[i]] = j;
}
memcpy(rank, sa, n * sizeof(int));
memcpy(sa, tmp, n * sizeof(int));
}
} void calheight(int n) {
for(int i = , k = ; i < n; height[rank[i++]] = k) {
k -= (k > );
int j = sa[rank[i] - ];
while(s[i + k] == s[j + k]) ++k;
}
} int logn[MAXN];
int best[][MAXN]; void init(int n = ) {
static bool done = false;
if(done) return ;
logn[] = -;
for(int i = ; i <= n; ++i)
logn[i] = logn[i - ] + ((i & (i - )) == );
done = true;
} void initRMQ(int n) {
init();
for(int i = ; i <= n; ++i) best[][i] = height[i];
for(int i = ; i <= logn[n]; ++i) {
int ed = n - ( << i) + ;
for(int j = ; j <= ed; ++j)
best[i][j] = min(best[i - ][j], best[i - ][j + ( << (i - ))]);
}
} int lcp(int a, int b) {
if(a == b) return n;
a = rank[a], b = rank[b];
if(a > b) swap(a, b);
++a;
int t = logn[b - a + ];
return min(best[t][a], best[t][b - ( << t) + ]);
} int cmp(int x, int n, int y, int m) {
int t = lcp(x, y);
if(n > t && m > t) return s[x + t] - s[y + t];
return n - m;
} struct Node {
int pos, len;
Node() {}
Node(int pos, int len): pos(pos), len(len) {}
bool operator < (const Node &rhs) const {
return cmp(pos, len, rhs.pos, rhs.len) < ;
}
void print() {
for(int i = pos; i < pos + len; ++i)
putchar(s[i]);
puts("");
}
}; const int MAXV = MAXN >> ;
Node src[MAXV * MAXV];
bool mat[MAXV][MAXV], ban[MAXV];
int go[MAXV], cnt[MAXV]; bool check(Node p) {
memset(mat, , sizeof(mat));
memset(ban, , sizeof(ban));
for(int i = ; i < n; ++i) {
go[i] = n;
if(cmp(i, n, p.pos, p.len) >= ) go[i] = min(go[i], min(p.len, lcp(p.pos % n, i)));
cnt[i] = go[i];
for(int j = i + ; j <= i + go[i]; ++j)
mat[j % n][i] = true;
}
for(int _ = ; _ < n; ++_) {
bool flag = false;
for(int i = ; i < n; ++i) if(!ban[i] && !cnt[i]) {
ban[i] = flag = true;
for(int j = ; j < n; ++j) cnt[j] -= mat[i][j];
}
if(!flag) break;
}
int c = ;
for(int i = ; i < n; ++i) if(cnt[i]) cnt[c++] = cnt[i];
for(int st = ; st < c; ++st) {
int x = st, y = ;
while(x < st + c) x += cnt[x % c], ++y;
if(c >= k && y <= k) return true;
}
return false;
} void solve() {
int c = ;
for(int i = ; i < n; ++i)
for(int j = ; j <= n; ++j) src[c++] = Node(i, j);
sort(src, src + c);
//c = unique(src, src + c) - src;
int l = , r = c;
while(l < r) {
int mid = (l + r) >> ;
//src[mid].print();
if(!check(src[mid])) l = mid + ;
else r = mid;
}
src[l].print();
} int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
scanf("%s", s);
memcpy(s + n, s, n * sizeof(char));
s[n << ] = ;
makesa( * n + , );
calheight( * n);
initRMQ( * n);
solve();
}
}
最新文章
- [转] IIS配置文件的XML格式不正确 applicationHost.config崩溃 恢复解决办法
- NET 自带IOC容器MEF指初体验
- js中Unicode转义序列
- VS2015 推荐插件
- 【转】Xcelsius2008 水晶易表问题 部分汇总
- [深入浅出Windows 10]应用实战:Bing在线壁纸
- css之opacity
- DedeCMS调用多说评论系统遇到的一些问题
- 【iOS发展-44】通过案例谈iOS重构:合并、格式化输出、宏观变量、使用数组来存储数据字典,而且使用plist最终的知识
- 菜鸟进阶——grunt
- mysql水平分表和垂直分表的优缺点
- CAP 2.3版本发布,支持 MongoDB
- HANA SQL备忘录
- Siki的虚幻第一季
- Dubbox:来自当当网的SOA服务框架
- Node核心模块
- 使用【 ajax 】【 bootstrap 】显示出小窗口 详情内容 一些代码意思可以参考下一个文章
- Http Header Content-Typ
- Java基础(1)IntelliJ IDEA入门、常用快捷键和数组操作
- Css3不透明