Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland

题意:

给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串。

问你第一个字符串最多包含多少个第二个字符串。

题解:

考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位.

这样的话复杂度为26*n*m*O(fail).

fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m。

状态转移看代码(就是一个kmp过程),感觉写得有点乱。- -!

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4
 5 const int N=1e5+7;
 6 char s[N],t[N];
 7 int s_len,t_len,now,nxt[N];
 8 int dp[2][N],Nxt[26][N];
 9
10 void kmp_pre(char x[], int m, int nxt[]) {
11     int i, j;  j = nxt[0] = -1;  i = 0;
12     while (i<m) {
13         while (-1 != j && x[i] != x[j])j = nxt[j];
14         nxt[++i] = ++j;
15     }
16 }
17
18 int main()
19 {
20     scanf("%s%s",s,t);
21     s_len=strlen(s),t_len=strlen(t);
22     if(s_len<t_len)return puts("0"),0;
23     kmp_pre(t,t_len,nxt);
24     F(j,0,25)F(k,0,t_len-1)
25     {
26         int idx=k;
27         while(idx!=-1&&(j+‘a‘)!=t[idx])idx=nxt[idx];
28         Nxt[j][k]=idx;
29     }
30     now=0;
31     F(j,0,t_len-1)dp[now][j]=-1;
32     dp[now][0]=0;
33     F(i,0,s_len-1)
34     {
35         F(j,0,t_len-1)dp[now^1][j]=-1;
36         if(s[i]==‘?‘)
37         {
38             F(j,0,25)F(k,0,t_len-1)if(dp[now][k]>=0)
39             {
40                 int idx=k,val=dp[now][k];
41                 if(idx!=-1&&(j+‘a‘)!=t[idx])idx=Nxt[j][idx];
42                 while(idx!=-1&&(j+‘a‘)!=t[idx])idx=nxt[idx];
43                 idx++;
44                 if(idx>=t_len)val++,idx=nxt[idx];
45                 dp[now^1][idx]=max(dp[now^1][idx],val);
46             }
47         }
48         else F(k,0,t_len-1)if(dp[now][k]>=0)
49         {
50             int idx=k,val=dp[now][k];
51             if(idx!=-1&&s[i]!=t[idx])idx=Nxt[s[i]-‘a‘][idx];
52             while(idx!=-1&&s[i]!=t[idx])idx=nxt[idx];
53             idx++;
54             if(idx>=t_len)val++,idx=nxt[idx];
55             dp[now^1][idx]=max(dp[now^1][idx],val);
56         }
57         now^=1;
58     }
59     int ans=0;
60     F(k,0,t_len)ans=max(ans,dp[now][k]);
61     printf("%d\n",ans);
62     return 0;
63 }

时间: 06-25

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)的相关文章

Educational Codeforces Round 21 F. Card Game(网络流之最大点权独立集)

题目链接:Educational Codeforces Round 21 F. Card Game 题意: 有n个卡片,每个卡片有三个值:p,c,l; 现在让你找一个最小的L,使得满足选出来的卡片l<=L,并且所有卡片的p的和不小于k. 选择卡片时有限制,任意两张卡片的c之和不能为质数. 题解: 和hdu 1565 方格取数(2)一样,都是求最大点权独立集. 不难看出来,这题再多一个二分. 注意的是在构造二部图的时候,按照c值的奇偶性构造. 当c==1时要单独处理,因为如果有多个c==1的卡片,

Educational Codeforces Round 25 G. Tree Queries

题目链接:Educational Codeforces Round 25 G. Tree Queries 题意: 给你一棵树,一开始所有的点全是黑色,有两种操作. 1 x 将x这个点变为黑色,保证第一个操作是这个. 2 x 询问x到任意黑色的点的简单路径上的最小节点编号. 题解: 首先将一个变为黑色的点当成树根,然后dfs一下,预处理出所有点的答案. 然后开一个变量记录一下当前变黑的点的答案cur=min(cur,dp[x]). 每次询问的时候答案就是min(cur,dp[x]). 如果觉得很神

Educational Codeforces Round 21 D. Array Division

题目链接:Educational Codeforces Round 21 D. Array Division 题意: 给你n个数,现在你可以改变1<=个数的位置,然后问你是否存在有一个k,使得sum(a[i])(1<=i<=k)==sum(a[j])(k+1<=j<=n) 题解: 分析: 如果需要将一个数移动,无非就是将这个数从第一部分移到第二部分,或者从第二部分移到第一部分. 所以,我们只需要开两个map来记录一下两部分有哪些数. 当两部分的差值/2等于其中一部分的一个数时

(KMP、dp)Codeforces Educational Codeforces Round 21 G-Anthem of Berland

Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem. Though there are lots and lots of victories in history of Berland, there is the one that stand out the most.

Educational Codeforces Round 21 Problem F (Codeforces 808F) - 最小割 - 二分答案

Digital collectible card games have become very popular recently. So Vova decided to try one of these. Vova has n cards in his collection. Each of these cards is characterised by its power pi, magic number ci and level li. Vova wants to build a deck

Educational Codeforces Round 21 Problem A - C

Problem A Lucky Year 题目传送门[here] 题目大意是说,只有一个数字非零的数是幸运的,给出一个数,求下一个幸运的数是多少. 这个幸运的数不是最高位的数字都是零,于是只跟最高位有关,只保留最高位,然后加一求差就是答案. Code 1 /** 2 * Codeforces 3 * Problem#808A 4 * Accepted 5 * Time:15ms 6 * Memory:0k 7 */ 8 #include<iostream> 9 #include<cstd

Educational Codeforces Round 21 A-E题题解

A题      ............太水就不说了,贴下代码 #include<string> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<cstdio> using namespace std; int n,m; int m

Educational Codeforces Round 18 C. Divide by Three DP

C. Divide by Three A positive integer number n is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a beautiful number by erasing some of the digits, and you want to erase as few digits as possible. The n

Educational Codeforces Round 36 (Rated for Div. 2)

Educational Codeforces Round 36 (Rated for Div. 2) F. Imbalance Value of a Tree You are given a tree T consisting of n vertices. A number is written on each vertex; the number written on vertex i is ai. Let's denote the function I(x,?y) as the differ