POJ3623 Best Cow Line, Gold 【后缀数组】
2024-09-03 11:28:25
最好的牛线,金
时间限制: 5000MS | 内存限制: 65536K | |
提交总数: 5917 | 接受: 2048 |
描述
FJ即将把他的ñ(1≤ ñ ≤30,000)头牛竞争一年一度的“年度农民”。在这个比赛中,每个农民都把他的牛排成一行,并把他们放在法官面前。
比赛组织者今年通过了一个新的注册方案:只要按照他们将要出现的顺序(即,如果FJ依次注册贝西,西尔维娅和多拉,他只注册BSD)登记每头牛的首字母。注册阶段结束后,按照奶牛姓名首字母的字符串,按增加的字典顺序对每个组进行判断。
FJ今年很忙,不得不赶回农场,所以他想尽早做出判断。他决定重新排列已经列队的牛,然后登记它们。
FJ标志着一个新的竞争奶牛的位置。然后,他通过反复将原始行(剩余部分)中的第一头或最后一头母牛发送到新行的末尾,将母牛从旧行进行编组到新行。当他完成之后,FJ就以这个新的顺序把他的奶牛注册了。
鉴于他的牛的初始秩序,确定他可以这样做的最小的字典串首字母缩写。
输入
*第1行:单个整数:N
*行2 .. N +1:第i + 1行包含原始行中第i个位置的牛的单个初始('A'..'Z')
产量
他能做的最少的字典串。每一行(可能除了最后一行)都包含新行的80头母牛('A'..'Z')的首字母缩写。
示例输入
6
一个
C
d
乙
C
乙
示例输出
ABCBCD
题意:每次从字符串首或尾拿出一个字符,求最小字典序方案
拿出字符字典序最小
①我们比较首尾,如果不同,肯定选最小那个
②如果相同,我们比较它的下一位,以此类推
由此,我们可以看出,其实左边的就是后缀,右边的就是将字符串反过来的后缀,二者进行比较
这就很简单了,我们将字符串翻转接到原字符串后边,用一个#之类的隔开,求一次后缀数组用rank贪心加入答案即可
【80个换一次行是什么蛇皮输出= =,没看到一直PE】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define REP0(i,n) for (int i = 0; i <= (n); i++)
#define PRE(i,n) for (int i = n; i >= 1; i--)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 60005,maxm = 100005,INF = 1000000000;
char s[maxn],ans[maxn];
int sa[maxn],rank[maxn],n,m,N,t1[maxn],t2[maxn],c[maxn];
void SA(){
int *x = t1,*y = t2;
REP0(i,m) c[i] = 0;
REP(i,n) c[x[i] = s[i]]++;
REP(i,m) c[i] += c[i - 1];
PRE(i,n) sa[c[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1){
int p = 0;
for (int i = n - k + 1; i <= n; i++) y[++p] = i;
REP(i,n) if (sa[i] - k > 0) y[++p] = sa[i] - k;
REP0(i,m) c[i] = 0;
REP(i,n) c[x[y[i]]]++;
REP(i,m) c[i] += c[i - 1];
PRE(i,n) sa[c[x[y[i]]]--] = y[i];
swap(x,y);
x[sa[1]] = p = 1;
for (int i = 2; i <= n; i++)
x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p;
if (p >= n) break;
m = p;
}
REP(i,n) rank[sa[i]] = i;
}
int main(){
cin>>N; m = 256; n = (N << 1) + 1;
REP(i,N){
s[i] = getchar();
while (!isalpha(s[i])) s[i] = getchar();
s[n + 1 - i] = s[i];
}
s[N + 1] = '#';
SA();
int L = 1,R = N,ansi = 0,r1,r2;
while (L < R){
r1 = rank[L]; r2 = rank[n + 1 - R];
ans[++ansi] = r1 < r2 ? s[L++] : s[R--];
}
ans[++ansi] = s[L];
REP(i,ansi){
putchar(ans[i]);
if (i % 80 == 0) puts("");
}
return 0;
}
最新文章
- swift开发多线程篇 - 多线程基础
- WIN10 安装不了NET3.5
- <;转>;浏览器内核分类
- Mysql-学习笔记(==》增删主键建立索引 七)
- 软件密码和https协议
- ajax发布评论 、显示评论
- xll
- php&;nbsp;curl_init函数用法
- 关于spring3中No Session found for current thread!and Transaction的配置和管理(转)
- Solr 多核(MultiCore)配置
- Python CRM项目四
- react 阻止事件冒泡
- hadoop常见问题
- scrapy框架原理学习
- qtp 自动货测试桌面程序-笔记(使用函数)
- JavaWeb项目自动部署,持续集成
- (7)Java数据结构--集合map,set,list详解
- 基于oslo_log的日志管理
- 《principal component analysis based cataract grading and classification》学习笔记
- Python内置模块与标准库
热门文章
- Linux Shell常用命令(长期更新)
- Java : java基础(3) IO流
- Hadoop(3)-Hadoop介绍
- Python自动化运维——DNS处理模块
- 「LibreOJ#515」贪心只能过样例 (暴力+bitset)
- 前端面试题目汇总摘录(JS 基础篇 —— 2018.11.02更新)
- LeetCode:16. 3Sum Closest(Medium)
- 台湾ML笔记--1.2 formalize the learning probelm
- Java Swing 图形界面开发(目录)
- javascript的优美与鸡肋