JJZN0x01习题&&例题

继续…

例题

0x11 栈

ch1101 火车进栈

问有多少种进栈方法,感觉要是不会卡特兰数用递推也挺好想的.假设要求f(n),就有两种情况. 1:f(n-1)进来又出去,然后n进来出去. 2.n-1个先进来k个,n进来,一起出去.之后n-1-k个进来,出去(f(k)*f(n-1-k)) (当然要枚举k).

总结起来就是f(n)=f(k-1)*f(n-k)

poj2559 单调栈

用单调栈维护,如果top高度<=当前则入栈,否则先把栈里所有>(=是可以在栈里的,因为它们可以一直连到当前的矩形)该高度的不断出栈加一加宽度更新ans.最后别忘了要把栈里剩下的一起再拿出来加一下.

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
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
struct cube{ll h,st,len;};
int main()
{
int n;
while(~scanf("%d",&n))
{
if(!n) break;
stack<cube> s;
ll ans=0;
for(int i=1;i<=n;++i)
{
ll tmp;
scanf("%lld",&tmp);
if(s.empty()) s.push((cube){tmp,0,1});
else if(s.top().h<=tmp) s.push((cube){tmp,s.top().st+s.top().len,1});
else{
ll len=0;cube now;
while(!s.empty()&&s.top().h>tmp)
{
now=s.top();s.pop();
ans=max(ans,(len+=now.len)*now.h);
}
s.push((cube){tmp,now.st,len+1});
}
}
ll len=0;cube now;
while(!s.empty())
{
now=s.top();s.pop();
ans=max(ans,(len+=now.len)*now.h);
}
printf("%lld\n",ans);
}
return 0;
}

0x12 队列

bzoj2457

毒瘤题没做.

看出来了,bzoj的题都是思考量特别大,要不然是找一些奇怪规律要不然就是搞一个公式推推推…

ch1201 单调队列

经典单调队列题.其实一开始看这题会感觉和poj2018比较像.但是那道题是使答案序列>=m,这个是<=m,所以不一样.

从前缀和考虑,ans=max(a[i]-a[j]) (j<i).(a是前缀和) 对于每个i来说,a[j]越小越好,所以可以用单调队列去维护这个j(注意存的实际上是j+1),j+1其实也就是序列的left对吧.所以这个单调队列存的就是每个可能的最优的left为后续的i服务.

在答案选择中,要考虑两点:首先,长度要<=m.所以在队列中,j要尽可能的离i近一点,因为越近就越不可能被淘汰对吧.其次,a[j-1]要尽可能小.而按照优先级来说,a[j-1]要小这个条件的优先级是高于j离i近一点这个条件的.(想象一下如果按照这样的优先级对包含两个条件的二元组升序排序怎么排(这些二元组的对应的j与i的距离<=m)).

首先,如果a[j-1]又小j又大,那么所有a[k-1]大or k<j的请全部淘汰,因为它们都可以被j这个答案代替.如果a[j-1]小但j小,那么j应该留下

说的太麻烦了且具有误导性,看书吧.

优先队列思想:及时排除一定不是最优的选项…

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
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[300010];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);a[i]+=a[i-1];
}
deque<ll> q;
ll ans=0;
for(int i=1;i<=n;++i)
{
if(q.empty()) {ans=max(ans,a[i]);q.push_back(i-1);continue;}
while(!q.empty()&&i-q.front()>m) q.pop_front();
ans=max(ans,a[i]-a[q.front()]);
while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();
q.push_back(i);
}
printf("%lld",ans);
return 0;
}

0x13 链表

ch1301

给你一个序列A,对于其中每个a[i]求 min{a[i]-a[j]} (1<=j<i)…没有两个a[i]的值是重复的

因为实际上就是求一个绝对值最小所以可以先按a[i]升序排序然后串成链表,同时开一个数组b[i]记录原序列中下标为i的值在链表中的位置,然后从下标最大的数开始看值与左右两边相减的abs那个最小.然后把这个结点在链表中删去(很显然因为前n-1个数在后面不会取到n),然后就行了.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
struct node{ll l,r;
ll val;ll p;};
vector<node> v;
typedef pair<ll,ll> pii;
vector<pii> a;
int pos[100010];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;++i) {
node t;scanf("%lld",&t.val);t.p=i;v.push_back(t);
}
sort(v.begin(),v.end(),[](const node &a,const node &b){return a.val<b.val;});
for(int i=0;i<v.size();++i)
{
pos[v[i].p]=i;if(i-1>=0) v[i].l=i-1; else v[i].l=-1;
if(i+1<v.size()) v[i].r=i+1; else v[i].r=-1;
}
for(int i=n;i>1;--i)
{
ll ans=1LL<<31,a2=1LL<<31,now=pos[i],l=v[now].l,r=v[now].r;
if(l>=0) {
ans=abs(v[l].val-v[now].val);a2=v[l].p;
//while(v[l].l&&v[v[l].l].val==v[l].val) l=v[l].l,a2=min(a2,v[l].p);
}
if(r>=0&&abs(v[v[now].r].val-v[now].val)<ans) {
ans=abs(v[v[now].r].val-v[now].val);
a2=min(a2,v[r].p);
}
if(l>=0) swap(r,v[v[now].l].r);
if(r>=0) swap(l,v[v[now].r].l);
a.push_back(pii(ans,a2));
}
for(int i=a.size()-1;i>=0;--i)
{
printf("%lld %lld\n",a[i].first,a[i].second);
}
return 0;
}

0x14 Hash

poj3349

感觉这个hash函数挺奇妙的…以及这题一看就很恶心…其实感觉可以把雪花角看成字符串去做?不过好像也挺麻烦的…

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
using namespace std;
const int P = 99991;
struct node{long long s[6],ne;};
node h[100010];
int head[P],cnt=0;
inline int get_h(node &a)
{
long long ans=0,x=1;
for(int i=0;i<6;++i) ans=(ans+a.s[i])%P,x=(x*a.s[i])%P;
return (ans+x)%P;
}
bool equal(node &a,node &b)
{
int c1=0,c2=1;
while(c2!=c1&&a.s[c1]!=b.s[c2]) c2=(c2+1)%6;
if(a.s[c1]!=b.s[c2]) return 0;
bool b1=1,b2=1;
for(int i=(c1+1)%6,j=(c2+1)%6;i!=c1;i=(i+1)%6,j=(j+1)%6)
{
if(a.s[i]!=b.s[j]) {b1=0;break;}
}
for(int i=(c1+5)%6,j=(c2+1)%6;i!=c1;i=(i+5)%6,j=(j+1)%6)
{
if(a.s[i]!=b.s[j]) {b2=0;break;}
}
return b1||b2;
}
bool insert(node a)
{
int h1=get_h(a);
if(head[h1])
{
for(int i=head[h1];i;i=h[i].ne)
{
if(equal(a,h[i])) return 1;
}
}
h[++cnt]=a;h[cnt].ne=head[h1],head[h1]=cnt;
return 0;
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)
{
node tmp;for(int i=0;i<6;++i) scanf("%lld",&tmp.s[i]);
if(insert(tmp))
{
printf("Twin snowflakes found.");return 0;
}
}
printf("No two snowflakes are alike.");
return 0;
}

ch1401

字符串hash模板题,没啥可说的…

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
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const ull P = 13331;
char s[1000010];
ull h[1000010];
inline ull fast_pow(ull a,ull b)
{
ull ans=1;
for(;b;a*=a,b>>=1) if(b&1) ans*=a;
return ans;
}
ull get_h(int l,int r)
{
return h[r]-h[l-1]*fast_pow(P,r-l+1);
}
int main()
{
char ch;int len=0;
for(ch=getchar();ch!='\n';ch=getchar())
{
s[++len]=ch;
}
for(int i=1;i<=len;++i)
{
h[i]=h[i-1]*P+s[i];
}
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int al,ar,bl,br;scanf("%d%d%d%d",&al,&ar,&bl,&br);
if(get_h(al,ar)==get_h(bl,br))
{
printf("Yes\n");
} else printf("No\n");
}
return 0;
}

poj3074

学了学马拉车

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char str[2100000];
int p[2100000];
int main(){
int cnt=0,len=0;
while(1)
{
++cnt;len=1;str[1]='#';
char ch;
while((ch=getchar())==' '||ch=='\n'||ch=='\r');
//str[++len]=ch,str[++len]='#';
while(ch!='\n'&&ch!='\r'&&ch!=' ') str[++len]=ch,str[++len]='#',ch=getchar();
str[len+1]='\0';
if(str[2]=='E'&&str[4]=='N'&&str[6]=='D'&&str[8]=='\0') break;
memset(p,0,sizeof p);
int ans=0,pos=0,R=0;
for(int i=1;i<=len;++i)
{
if(i<R) p[i]=min(p[pos*2-i],R-i); else p[i]=1;
while(i-p[i]>=1&&i+p[i]<=len&&str[i-p[i]]==str[i+p[i]]) ++p[i];
if(i+p[i]>R) {R=i+p[i],pos=i;}
ans=max(ans,p[i]-1);
}
printf("Case %d: %d\n",cnt,ans);
}
return 0;
}

习题

ex4 poj1964 单调栈

这个题因为中间可能有墙导致没法直接用单调栈去做。怎么办呢?从最上面一行一行的扫,累加F的高度。但如果当前为R,那么说明这一列当前没法用,所以高度变为0就行了。

当然一开始看到这题想的是求最大子矩阵和。既然没法选R那么可以把R设为-inf。然而这样是n^3的…

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
#include <stack>
#include <cstring>
int n,m;
int a[1024][1023];
int high[1024];
int solve(int k)
{
std::stack<std::pair<int,int> > s;
int ans = 0,len = 0;
for(int i = 1; i <= m; ++i) if(a[k][i]) ++high[i]; else high[i] = 0;
for(int i = 1; i <= m; ++i) {
if(s.empty()) s.push(std::make_pair(high[i],1));
else {
if(s.top().first <= high[i]) {
s.push(std::make_pair(high[i],1));
}
else {
while(!s.empty() && s.top().first > high[i]) {
len += s.top().second;
ans = std::max(ans,s.top().first * len);
s.pop();
}
s.push(std::make_pair(high[i],len)); len = 0;
}
}
}
while(!s.empty()) {
len += s.top().second;
ans = std::max(ans,s.top().first * len);
s.pop();
}
return ans;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
memset(high,0,sizeof high);
int ans = 0;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <=m; ++j) {
char ch; while((ch=getchar())==' '||ch=='\n');
a[i][j] = (ch == 'F')?1:0;
}
}
for(int i = 1; i <= n; ++i) {
ans = std::max(solve(i),ans);
}
printf("%d\n",ans*3);
}
return 0;
}

ex5 poj2823 单调队列

这个题题意就是要静态维护一个区间最大/最小值。其实这题之前做过,当时直接用RMQ搞定了。当然维护一个上升的单调最大值队列和一个下降的最小值队列也是可以的。

ex7 ch1806 Hash

对大矩阵的每一行hash一下,然后两层for遍历所有存在于大矩阵中的小矩阵,然后和每一个得到的小矩阵一行一行的比一下hash就行了。

当然一开始是每得到一个小矩阵都n^3比较,这样实际上就n^4了。所以可以先把每个小矩阵都存进来总的hash一下(就是把每一行hash,然后遍历每一行,让hash[i] += hash[i-1]*pow(p,b)(b为列数),这样就相当于把矩阵看成一个一维序列总的hash一下)。最后用map把hash结果与当前查询的序号映射一下。因为可能会有多个相同查询所以映射的是一个vector来储存当前hash所对应的序号。

然后n^2遍历每个结果,把结果分别hash之后看看是否与hash值相同的小矩阵,然后搞就行了。总体复杂度n^3

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <utility>
#include <map>
#include <vector>
typedef unsigned long long ull;
using namespace std;
const ull p = 1e9+7;
//const int maxn = 1024*1024;
ull h[1024][1024];
ull p_pow[1024];
int m,n,a,b;
bool q_ans[1024];
typedef pair<ull,int> pui;
map<ull,vector<int> > mp;
// ull fast_pow(ull a,ull b) {
// ull ans = 1;
// for(;b;b>>=1,a = a*a) {
// if(b&1) ans = ans*a;
// }
// return ans;
// }
ull geth(int d,int l,int r) {
return h[d][r] - h[d][l-1] * p_pow[r-l+1];
}
char rd() {
char ch;
while((ch = getchar()) == '\n' || ch == ' ' || ch == '\r');
return ch;
}
int main()
{
p_pow[0] = 1;
for(int i = 1; i < 1024; ++i) p_pow[i] = p_pow[i-1] * p;
scanf("%d%d%d%d",&m,&n,&a,&b);
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
char d = rd();//cin>>d;
h[i][j] = h[i][j-1] * p + d;
}
}
int q;scanf("%d",&q);
for(int x = 1; x <= q; ++x)
{
ull q_h = 0;
for(int i = 1; i <=a; ++i) {
for(int j =1; j <= b; ++j) {
char d = rd();//cin>>d;
q_h = q_h * p + d;
}
}
mp[q_h].push_back(x);
}
for(int i = 1; i+a-1 <= m; ++i) {
for(int j = 1; j+b-1 <= n; ++j) {
ull h_h = 0;
for(int k = 1; k <= a; ++k) {
h_h = h_h * p_pow[b] + geth(i+k-1,j,j+b-1);
}
if(mp.find(h_h) != mp.end()) {
vector<int> &v = mp[h_h];
for(int k = 0; k < v.size(); ++k) {
q_ans[v[k]] = 1;
}
}
}
//if(fin == 1) break;
}
for(int i = 1; i <= q; ++i) printf("%d\n",q_ans[i]);
return 0;
}

ex8 ch1807 字符串最小表示法

就是求字符串字典序最小的表示方法。比如4321的最小表示就是1432.

具体比较方法是O(n)的,详情看书.

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
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char str[2000010],str2[2000010];
int len;
int min_expr(char *str)
{
for(int i = len; i < 2*len; ++i)
str[i] = str[i-len];
str[2*len] = '\0';
int i = 0,j = 1;
while(i < 2*len && j < 2*len) {
int k = 0;
while(str[i+k] == str[j+k] && max(i+k,j+k) < 2 * len) ++k;
if(i + k >= 2*len) return j;
if(j + k >= 2*len) return i;
if(str[i+k]<str[j+k]) {j = j+k+1; if(i == j) ++j;}
else {i = i+k+1; if(i == j) ++i;}
}
return min(i,j);
}
bool Strcmp(char *a,char *b,int len) {
for(int i = 0; i < len; ++i) {
if(a[i] != b[i]) return 0;
}
return 1;
}
int main() {
//freopen("tmp.out","w",stdout);
scanf("%s%s",str,str2); len = strlen(str);
int a = min_expr(str),
b = min_expr(str2);
if(Strcmp(str+a,str2+b,len)) {
printf("Yes\n");
for(int i = 0; i < len; ++i)
printf("%c",str[i+a]);
} else printf("No\n");
return 0;
}

ex9 poj2185 kmp 最小循环节

这题是poj1961的升级版。

首先循环节咋求:若s[1~i] 有一个长度为len的循环节的充要条件是 i%len == 0 且s[1~i-len] = s[len+1~i] (就是next[i] == i-len),至于为啥请看书。

然后先用kmp求next[i],最小的循环节肯定是i-next[i] (不明白就仔细画画图,然后看看书上的poj1961).

然后再看这题的样例,因为要求这个最小循环节不一定能覆盖所有的(就是最后一个循环节不一定是完整的),所以ABABA循环节是AB(最后一个B缺失)。但是这咋求呢?假设把那个B补上,然后求一下不就行了?和完整时的原理是一样的。此时next[i] = 3,最小循环节就是i-next[i] = 2;

当然这时候就不能检查i % (i-next[i]) == 0了。因为如果i%(len)有余数x,那我可以随意口胡说原串是实际上长度是i+(len-x)只是缺失了但是也符合题意啊~

这样只解决了每一行的最小循环节,如果多行咋办?一开始我随意脑补了一下:求所有行的最小循环节的最小值。然而很显然并不对。上网搜了一下,有人用的是求所有行的最小循环节的最小公倍数,如果超过列数就用列数,这样看似是对的,实际上并不对。比如下面这个样例:

2 8
ABCDEFAB
AAAABAAA

第一行最小循环是6,第二行是5.lcm = 30 > 8 所以这两行最小共有的循环节取8,但实际上并不是8,而是6。

那咋办呢?求出next后枚举每一行所有可能的循环节长度并标记一下。最后看一下标记数==行数的最小的循环节长度(看不懂就看code)

怎么枚举?字符串最小循环节==i-next[i],那么所有的循环节长度就是从i-next[i]~i;其中因为s[1~next[i]] = s[i-next[i]+1~i],所以所有的j<=next[i]的情况也都是符合s[1~j] = s[i-j+1~i] (画图画图)

然后就求出了所有行公有的循环节长度len,但是对于每一列可能也有循环节,于是可以在对每一列做一遍kmp求最小循环节,其中把每一行s[i][1~len]看成是一个元素,比较时进行字符串比较.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <algorithm>
#include <cstring>
int R,C;
char str[10010][100];
int Next[100];
int rnext[10010];
int ans_c[10010];
const int inf = 1e9+7;
void get_Next(int x) {
Next[1] = 0;
for(int i = 2, j = 0; i <= C; ++i)
{
while(j > 0 && str[x][i] != str[x][j+1]) j = Next[j];
if(str[x][i] == str[x][j+1]) ++j;
Next[i] = j;
}
}
bool Strcmp(char *a,char *b,int len) {
for(int i = 1; i <= len; ++i)
if(a[i] != b[i]) return 0;
return 1;
}
void get_rnext(int x)
{
rnext[1] = 0;
for(int i = 2, j = 0; i <= R; ++i)
{
while(j > 0 && !Strcmp(str[i],str[j+1],x)) j = rnext[j];
if(Strcmp(str[i],str[j+1],x)) ++j;
rnext[i] = j;
}
}
int main()
{
scanf("%d%d",&R,&C);
int min_c = inf,min_r = inf;
for(int i = 1; i <= R; ++i) {
scanf("%s",str[i]+1);
get_Next(i);
for(int j = 0;j <= Next[C]; ++j)
++ans_c[C - j];
}
for(int i = 1; i <= C; ++i)
if(ans_c[i] == R) {
min_c = i; break;
}
get_rnext(min_c);
printf("%d",(R-rnext[R])*min_c);
return 0;
}

标程一开始用的是求最小公倍数的方法,在群里说了之后XuHt写了一种新的方法:就是把一列看做一个字符求所有行的最小循环节,再把一行看做一个字符求所有列的最小循环节,然后相乘就行了。这种方法是最优的。因为要对整个行/列比较所以要求hash。

XuHt的标程:

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
32
33
34
35
36
//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
#define ull unsigned long long
using namespace std;
const int R = 10006, C = 81, P = 13331;
int r, c, nxt[R];
char s[R][C];
ull H[R];

int work(int len) {
int i = 0, j = -1;
nxt[0] = -1;
while (i < len)
if (j == -1 || H[i] == H[j]) nxt[++i] = ++j;
else j = nxt[j];
return len - nxt[len];
}

int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) scanf("%s", s[i]);
memset(H, 0, sizeof(H));
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
H[i] = H[i] * P + s[i][j];
int ans = work(r);
memset(H, 0, sizeof(H));
for (int i = 0; i < c; i++)
for (int j = 0; j < r; j++)
H[i] = H[i] * P + s[j][i];
ans *= work(c);
cout << ans << endl;
return 0;
}

ex10 kmp 求子串变形

题意是求串A的每个后缀子串与串B的匹配长度,然后给q个询问,每个询问x输出有多少个后缀匹配的长度等于x.

假设len(A)=n。首先要套kmp的话,我们只能求每个A[1~i]的后缀与B的前缀的匹配情况,而不是每个A[i~n]与B的匹配.怎么办呢?假设已经有A[1~i]的后缀与B的前缀B[1~j]的匹配,匹配长度为j。那么A[i-j+1~n]与B至少匹配长度为j(也许A[i+1]也能匹配对吧).用一个cnt[len]记录所有长度>=len的子串数量,此时cnt[j]++;而对于B[1~k] (k<j且能与A[1~i]匹配)
来说,它们匹配的长度肯定小于j,那它们的长度计数也应该增加对吧,而k == next[j].

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
32
33
34
35
36
37
38
39
40
#include <cstdio>
using namespace std;
int n,m,q;
const int maxn = 2e5+10;
char a[maxn],b[maxn];
int Next[maxn],f[maxn];
int cnt[maxn];
void get_next()
{
for (int i = 2, j = 0; i <= m; i++)
{
while (j>0 && b[j + 1] != b[i]) j = Next[j];
if (b[j + 1] == b[i]) j++;
Next[i] = j;
}
}
void get_f()
{
for(int i = 1,j = 0; i <= n; ++i)
{
while(j > 0 && (j == m ||a[i] != b[j+1])) j = Next[j];
if(a[i] == b[j+1]) ++j;
f[i] = j;
cnt[f[i]]++;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
scanf("%s%s",a+1,b+1);
get_next();
get_f();
for (int i = n; i; i--) //cnt[Next[i]] += cnt[i];
cnt[i] += cnt[i+1];
while(q--) {
int x; scanf("%d",&x);
printf("%d\n",cnt[x]-cnt[x+1]);
}
return 0;
}

当然据说用hash加二分也可以……

ex11 poj3630 trie

模板题

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
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstring>
struct Node {
int cur[10];
int num;
int size;
bool end;
} trie[100100];
int cnt = 0;
char str[10010][20];
bool add(char * str,int cur) {
if(*str == '\0') {
if(trie[cur].size || trie[cur].end) return 1;
trie[cur].end = 1;return 0;
}
if(trie[cur].end) return 1;
int num = *str - '0';
if(!trie[cur].cur[num]) {
++cnt; trie[cnt].num = num; trie[cur].cur[num] = cnt;
}
++trie[cur].size;
return add(str+1,trie[cur].cur[num]);
}
int main()
{
int T; scanf("%d",&T);
while(T--) {
memset(trie,0,sizeof trie);
cnt = 0;
bool fin = 0;
int n; scanf("%d",&n);
for(int i = 1; i <= n; ++i) scanf("%s",str[i]);
for(int i = 1; i <= n; ++i) {
if(add(str[i],0)) {fin = 1;break;}
}
if(!fin) printf("YES\n"); else printf("NO\n");
}
return 0;
}