c++&oi
USACO5.5.2最小表示法
后缀数组不会,也不知道他们怎么暴力做掉的。
于是拜读了一篇论文,学习了最小表示法。
让后AC了。
...
/**/
/*
USER:zyn19961
TASK:hidden
LANG:C++
*/
#include
<
string
>
#include
<
cstdio
>
#include
<
cstring
>
#include
<
fstream
>
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
//
#define
MM(a,i) memset(a,i,sizeof(a))
#define
FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define
NFOR(i,l,r) for (i=(l);i<=(r);i++)
#define
DFOR(i,r,l) for (int i=(r);i>=(l);i--)
//
#define
MP make_pair
#define
FT first
#define
SD second
//
typedef
long
long
Int64;
const
int
INF
=~
0U
>>
2
;
const
int
maxn
=
200007
;
//
ifstream fin(
"
hidden.in
"
);
ofstream fout(
"
hidden.out
"
);
//
string
S(maxn,
0
),s(maxn,
0
);
int
main()
{
int
n;fin
>>
n;
S.clear();
FOR(i,
1
,(n
-
1
)
/
72
+
1
)fin
>>
s,S
+=
s;S
+=
S;
int
i
=
0
,j
=
1
,k;
for
(;j
<
n;)
{
NFOR(k,
0
,n
-
1
)
if
(S[i
+
k]
!=
S[j
+
k])
break
;
if
(k
==
n)
break
;
if
(S[i
+
k]
>
S[j
+
k])i
+=
k
+
1
;
else
j
+=
k
+
1
;
if
(j
==
i)j
++
;
}
fout
<<
i
<<
"
\n
"
;
fin.close();
fout.close();
return
0
;
}
posted on 2012-04-06 12:48
zyn.cpp
阅读(152)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
<
2011年12月
>
日
一
二
三
四
五
六
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 57
文章 - 13
评论 - 11
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
(57)
2012年6月 (2)
2012年5月 (4)
2012年4月 (18)
2012年3月 (7)
2012年2月 (14)
2012年1月 (3)
2011年12月 (8)
2011年11月 (1)
文章档案
(13)
2012年2月 (1)
2011年12月 (7)
2011年11月 (1)
2011年9月 (3)
2011年8月 (1)
搜索
最新评论
1. re: 培训作业-第三周(STL&USACO+4)
评论内容较长,点击标题查看
--佛教网
2. re: 培训作业-第三周(STL&USACO+4)
评论内容较长,点击标题查看
--happem
3. re: NOIP2011解题报告
sum[i]表示前i个点的单位数?这。。,sum[i]表示i点前下车的乘客数吧?
--锐
4. re: NOIP2011解题报告
顶一下。。
--锐
5. re: 培训作业-第三周(STL&USACO+4)
@zyn.cpp
用vector暴力平衡树啊。。。
--姚京韬
阅读排行榜
1. NOIP2011普及组的第三题:瑞士轮(2632)
2. NOI LINUX 安装记(1975)
3. 随便说说状态压缩(1532)
4. 迎接初中同学——整理OI知识点(building)(805)
5. POJ 1733 (553)
评论排行榜
1. 培训作业-第三周(STL&USACO+4)(5)
2. NOIP2011普及组的第三题:瑞士轮(2)
3. POJ 1733 (1)
4. 给count-base sort正身(0)
5. 奇怪的乘法运算(cm)(0)
Powered by:
C++博客
Copyright © zyn.cpp