| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 7/7 | O | O | O | Ø | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给一个串，求出是这个串前缀也是其后缀的所有子串，按照长度递增顺序输出长度和在该串中出现的次数。
解题思路
用$kmp$算法求出$next(pre)$数组，那么沿着串最后跑$next$边得到的即是既是前缀也是后缀的串。统计个数的时候，每次可以匹配（前缀等于某个子串，即到某个位置时的后缀）时，都进行计数。最后从后往前沿$next$累加个数即可。
AC代码
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
struct Ans{
int num,pos;
}ans[N];
char b[N];
int pre[N],cnt[N];
int main(){
int i;
scanf("%s",b);
int len=strlen(b);
for(i=1;i<len;i++){
int p=pre[i];
while(b[i]!=b[p]&&p)p=pre[p];
if(b[p]==b[i])pre[i+1]=p+1;
else pre[i+1]=0;
}
for(i=1;i<len;i++){
int p=pre[i];
while(b[i]!=b[p]&&p)p=pre[p];
if(b[p]==b[i])cnt[++p]++;
}
for(i=len;i>=0;i--)if(pre[i])cnt[pre[i]]+=cnt[i];
int now=len,p=0;
while(now){
ans[p++]=(Ans){cnt[now],now};
now=pre[now];
}
printf("%d\n",p);
for(i=p-1;i>=0;i--)printf("%d %d\n",ans[i].pos,ans[i].num+1);
return 0;
}
B
题目描述
给$n$个只由$abc$构成的模式串，$m$个询问串，每次询问该串是否能恰好改变一个位置的字符恰好与模式串中的某一个相等。
解题思路
可以暴力用哈希做，枚举长度和改变的数值，
调调参即可。这东西$mod$和$base$凡是涉及到$19260817$老是$WA$，看来还是不能乱$%$。
AC代码
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
typedef long long ll;
using namespace std;
set<ll>s;
char a[N];
ll h(){
int i,l=strlen(a);
ll now=0;
for(i=0;i<l;i++)now=(now*BASE+a[i])%mod;
return now;
}
ll pw[N]={1};
int jud(){
int i,j,l=strlen(a);
ll hash=h();
for(i=0;i<l;i++)
for(j='a';j<='c';j++)
if(j!=a[i]&&s.find(((hash+(j-a[i])*pw[l-i-1]%mod)%mod+mod)%mod)!=s.end())return 1;
return 0;
}
int main(){
int i,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<N;i++)pw[i]=pw[i-1]*BASE%mod;
for(i=0;i<n;i++)
scanf("%s",a),s.insert(h());
for(i=0;i<m;i++){
scanf("%s",a);
if(jud())printf("YES\n");
else printf("NO\n");
}
return 0;
}
C
题目描述
字符集大小为$4$，给一堆串作为子串时的权值（可为负），问长为$l$的字符串权值（初始为零，某一个带权子串出现则加上该串对应权值，但只能加一次）最大是多少。
解题思路
在$AC$自动机上跑动态规划，$dp[i][j][S]$表示跑到串的第$i$个字符，在$AC$自动机上的节点为$j$，包含的带权字符串集合为$S$这个状态存在不存在。注意状态压缩和滚动数组。注意$ed$在$build$的时候需要根据$fail$更新。
AC代码
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
71
typedef long long ll;
using namespace std;
int trans[520],dp[2][M][(1<<10)+10];
char a[N];
int tr[M][4],ed[M],fail[M],tot,score[N],number;
void insert(){
int i,now=0;
for(i=0;a[i];i++){
int p=trans[(int)a[i]];
if(!tr[now][p]){
tr[now][p]=++tot;
memset(tr[tot],0,sizeof(tr[tot]));
}
now=tr[now][p];
}
ed[now]|=1<<number;
}
queue<int>Q;
void build(){
int i,p;
for(i=0;i<4;i++)if(tr[0][i])Q.push(tr[0][i]);
while(!Q.empty()){
p=Q.front();Q.pop();
for(i=0;i<4;i++){
int now=tr[p][i];
if(!now)tr[p][i]=tr[fail[p]][i];
else fail[now]=tr[fail[p]][i],Q.push(now),ed[now]|=ed[fail[now]];
}
}
}
int n,m;
int f(int x){
int i,ret=0;
for(i=0;i<n;i++)
if(x&(1<<i))ret+=score[i+1];
return ret;
}
int main(){
int i,j,k,l;
trans['A']=0;trans['G']=1;trans['C']=2;trans['T']=3;
while(~scanf("%d%d",&n,&m)){
memset(ed,0,sizeof(ed));
memset(fail,0,sizeof(fail));
memset(tr[0],0,sizeof(tr[0]));
tot=0;
for(i=0;i<n;i++){
number=i;
scanf("%s%d",a,&score[i+1]);
insert();
}
build();
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
int ret=-100,p=1;
for(i=0;i<m;i++){
p^=1;
memset(dp[p^1],0,sizeof(dp[p^1]));
for(j=0;j<=tot;j++)for(k=0;k<1<<n;k++)
if(dp[p][j][k])
for(l=0;l<4;l++)dp[p^1][tr[j][l]][k|ed[tr[j][l]]]=1;
}
for(j=0;j<=tot;j++)for(k=0;k<1<<n;k++)
if(dp[p^1][j][k])ret=max(ret,f(k));
if(ret>=0)printf("%d\n",ret);
else printf("No Rabbit after 2012!\n");
}
return 0;
}
D
题目描述
问一个串中是否存在两个不相交的长度均为$k$的子串，使得串$T$为他们拼起来后串的子串。
解题思路
分别从后向前、从前向后递推地求后缀的前缀和前缀的后缀，没处理到的情况特殊判断一下（在$k$之内）即可。注意特判$k>m$（手动再见.jpg）
AC代码
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
typedef long long ll;
char a[N],b[N];
ll hsa[N],hsb[N],pw[N]={1};
int n,m,k;
void hashf(char c[],int l,ll *h){
int i;
for(i=1;i<=l;i++)h[i]=(h[i-1]*BASE+c[i])%mod;
}
int l[N],r[N];
int main(){
int i;
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",a+1,b+1);
for(i=1;i<=n;i++)pw[i]=pw[i-1]*BASE%mod;
hashf(a,n,hsa);hashf(b,m,hsb);
for(i=m;i<=n;i++){
if((hsa[i]-hsa[i-m]*pw[m]%mod-hsb[m])%mod==0){
if(i+k<=n)return printf("Yes\n%d %d",i-m+1,i-m+k+1),0;
else if(m<k){//i-m~i
int x=1;
while(x+k+k-1<i)x++;
if(x+k+k-1<=n)return printf("Yes\n%d %d",x,x+k),0;
}
}
}
int p=k;
for(i=1;i<=m&&i<=k;i++){
while(p<i)p++;
while(p<=n)if((hsa[p]-hsa[p-i]*pw[i]%mod-hsb[i])%mod==0)break;else p++;
if((hsa[k]-hsa[k-i]*pw[i]%mod-hsb[i])%mod==0)p=k;
l[i]=p;
}
p=n-k+1;
for(i=m;i>=0;i--){
int len=m-i+1;
while(n-p+2<len)p--;
while(p>0)if((hsa[p+len-1]-hsa[p-1]*pw[len]%mod-hsb[m]+hsb[i-1]*pw[len]%mod)%mod==0)break;else p--;
if((hsa[n-k+len]-hsa[n-k]*pw[len]%mod-hsb[m]+hsb[i-1]*pw[len]%mod)%mod==0)p=n-k+1;
r[i]=p;
}
for(i=std::max(0,m-k);i<=m;i++)
if(l[i]>=k&&r[i+1]<=n-k+1&&l[i]&&r[i+1]&&l[i]<r[i+1])
return printf("Yes\n%d %d",l[i]-k+1,r[i+1]),0;
printf("No");
return 0;
}
E
题目描述
给一个模式串，给出匹配半径，求匹配串能够匹配的位置个数。
解题思路
用四个$bitset$保存$ATGC$分别可以在哪里出现，使用差分求出这四个$bitset$。
接下来就是暴力匹配，复杂度可以勉强卡过去。题目很类似于buaa summer practice 2017 字符串专场中的$C$题。
听说正解是$FFT$，看来还是要学习一个。
AC代码
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
using namespace std;
bitset<N>b[4],now;
char s[N],t[N];
int trans[500];
int tmp[4][N];
int main(){
int i,j,n,m,k;
trans['A']=0;trans['G']=1;trans['C']=2;trans['T']=3;
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",s,t);
for(i=0;i<n;i++){
tmp[trans[(int)s[i]]][max(i-k,0)]++;
tmp[trans[(int)s[i]]][min(i+k+1,n)]--;
}
for(i=0;i<=n;i++)
for(j=0;j<4;j++){
if(i)tmp[j][i]+=tmp[j][i-1];
if(tmp[j][i]>0)b[j][i]=1;
else b[j][i]=0;
}
for(i=0;i<n-m+1;i++)now[i]=1;
for(i=0;i<m;i++){
int p=trans[(int)t[i]];
now&=b[p];
now<<=1;
now[0]=0;
}
printf("%d",now.count());
return 0;
}
$upd:$会用$FFT$辣！
分成$ATGC$四部分解决，设$a[i]$表示第$i$位能否匹配当前字符$c$（$0/1$），很容易用差分求出该数组。再设$b[i]=(t[i]==c)$，于是$tot[i]=\sum_{j=0}^{m-1}b[j]\times a[i+j]$表示字符$c$在$i$位能够匹配多少个字符。
考虑把上面的式子转化成卷积的形式。
翻转字符串$T$，设$b[i]=(t[m-1-i]==c)$，则有$tot[i]=\sum_{j=0}^{m-1}b[m-1-j]\times a[i+j]=(b\times a)[i+m-1]$，$FFT$求出即可。
AC代码
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
typedef long long ll;
struct complex{
double x,y;
complex(double xx=0,double yy=0){x=xx;y=yy;}
complex operator+(const complex a)const{return {x+a.x,y+a.y};}
complex operator-(const complex a)const{return {x-a.x,y-a.y};}
complex operator*(const complex a)const{return {x*a.x-y*a.y,x*a.y+y*a.x};}
};
complex a[N],b[N],wn1,wnk;
int m,n,mx,limit;
char s[N],t[N];
int r[N];
void fft(complex *F,int sign){
int i,j,len;
for(i=0;i<limit;i++)if(i<r[i])std::swap(F[r[i]],F[i]);
for(len=1;len<limit;len<<=1){
wn1=complex(cos(acos(-1)/len),sign*sin(acos(-1)/len));
for(j=0;j<limit;j+=(len<<1)){
wnk=complex(1,0);
for(i=j;i<j+len;i++){
complex t=F[i+len]*wnk;
F[i+len]=F[i]-t;
F[i]=F[i]+t;
wnk=wnk*wn1;
}
}
}
if(sign==-1)for(i=0;i<limit;i++)F[i].x/=limit;
}
int tot[N],ans,k;
void calc(char c){
int i;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=0;s[i];i++)if(s[i]==c)a[std::max(i-k,0)].x++,a[i+k+1].x--;
for(i=1;s[i];i++)a[i].x+=a[i-1].x;
for(i=1;s[i];i++)a[i].x=!!a[i].x;
for(i=0;t[i];i++)b[i].x=(t[i]==c);
fft(a,1);fft(b,1);
for(i=0;i<limit;i++)a[i]=a[i]*b[i];
fft(a,-1);
for(i=0;i<n;i++)tot[i]+=(int)(0.5+a[i+m-1].x);
}
int main(){
int i;
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",s,t);
std::reverse(t,t+m);
mx=m+n,limit=1;
while(limit<=mx)limit<<=1;
for(i=0;i<=limit;i++)r[i]=(r[i/2]/2)|((i&1)?limit>>1:0);
calc('A');calc('T');calc('G');calc('C');
for(i=0;i<n;i++)if(tot[i]>=m)ans++;
printf("%d",ans);
return 0;
}
F
题目描述
求一个串的最长回文子串长度。
解题思路
签到题，打一遍马拉车的板子即可。
AC代码
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
char s[2*N]={',','#'},a[N];
int len[2*N],maxright,mid,max,l,i,cnt;
int mn(int x,int y){return x>y?y:x;}
int main(){
int cas=0;
while(~scanf("%s",a)){
max=maxright=0;
if(strcmp(a,"END")==0)break;
cnt=2;
int l=strlen(a);
for(i=0;i<l;i++){
s[cnt++]=a[i];
s[cnt++]='#';
}
s[cnt]='\0';
for(i=1;i<cnt;i++){
if(i<maxright)len[i]=mn(len[mid*2-i],maxright-i);
else len[i]=1;
while(s[i-len[i]]==s[i+len[i]])len[i]++;
if(len[i]+i>maxright){
maxright=len[i]+i;
mid=i;
}
if(len[i]-1>max)max=len[i]-1;
}
printf("Case %d: %d\n",++cas,max);
}
return 0;
}