相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/12/26312367.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2016/12/324324132.pdf
解题报告
之前鏼爷讲课的时候讲过了
于是这一次直接开始写了
就是每种字母都分开做一遍
符合条件/是该字母就置为1
否则置为0，之后FFT就好
似乎NTT就可以做了？然而不会 QwQ
Code
#include<bits/stdc++.h>
#define E complex<double>
using namespace std;
const int N = 1100000+9;
const double EPS = 1e-3;
const double PI = acos(-1);
int n,m,K,stp,len,a1[N],a2[N],sum[N];
char pat[N]; int vout[N],pos[N];
complex<double> s1[N],s2[N];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void prework() {
for (int tmp=1;tmp<=len;tmp<<=1,stp++);
len = (1<<stp);
for (int i=1,hig=1<<stp-1;i<=len;i++) {
pos[i] = pos[i>>1] >> 1;
if (i & 1) pos[i] |= hig;
}
}
inline void FFT(complex<double> *arr, int t) {
for (int i=0;i<len;i++)
if (pos[i] < i) swap(arr[pos[i]], arr[i]);
for (int i=1,num=2;i<=stp;i++,num<<=1) {
complex<double> wn(cos(2*PI/num),sin(t*2.0*PI/num));
for (int j=0;j<len;j+=num) {
complex<double> w(1,0),buf;
for (int i=j,lim=num/2+j;i<lim;i++,w*=wn) {
buf = w * arr[i+num/2];
arr[i+num/2] = arr[i] - buf;
arr[i] += buf;
}
}
}
if (!~t) for (int i=0;i<len;i++)
s1[i].real() /= len;
}
int main() {
freopen("biology.in","r",stdin);
freopen("biology.out","w",stdout);
n = read(); m = read();
K = read(); len = n + m;
scanf("%s",pat);
for (int i=0;i<n;i++) {
if (pat[i] == 'A') a1[i] = 1;
else if (pat[i] == 'C') a1[i] = 2;
else if (pat[i] == 'G') a1[i] = 3;
else if (pat[i] == 'T') a1[i] = 4;
}
scanf("%s",pat);
for (int i=0;i<m;i++) {
if (pat[i] == 'A') a2[i] = 1;
else if (pat[i] == 'C') a2[i] = 2;
else if (pat[i] == 'G') a2[i] = 3;
else if (pat[i] == 'T') a2[i] = 4;
}
prework();
for (int j=1;j<=4;j++) {
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
for (int i=0;i<n;i++)
sum[i] = (i>0?sum[i-1]:0) + (a1[i] == j);
for (int i=0;i<n;i++)
s1[i].real() = (sum[min(n-1,i+K)]!=((i-K-1)>=0?sum[i-K-1]:0));
for (int i=0;i<m;i++)
s2[i].real() = (a2[i] == j);
for (int l=0,r=m-1;l<r;l++,r--)
swap(s2[l], s2[r]);
FFT(s1,1); FFT(s2,1);
for (int i=0;i<len;i++)
s1[i] = s1[i] * s2[i];
FFT(s1,-1);
for (int i=1;i<=n;i++)
vout[i] += s1[i+m-2].real() + EPS;
}
int ret = 0;
for (int i=1;i<=n;i++)
ret += (vout[i] == m);
printf("%d\n",ret);
return 0;
}
Excellent post. I’m facing some of these issues as well..
Hey there, I think your website might be having browser compatibility issues.
When I look at your blog site in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, wonderful blog!
After exploring a few of the blog articles on your web site,
I honestly appreciate your technique of writing a blog.
I saved as a favorite it to my bookmark site list and
will be checking back soon. Please check out my web site as well
and tell me how you feel.
I blog frequently and I really appreciate your content.
This great article has really peaked my interest.
I am going to book mark your blog and keep checking for new details
about once per week. I subscribed to your Feed too.
Good web site you have got here.. It’s difficult to find high quality writing like yours these days.
I truly appreciate individuals like you! Take care!!
This is very interesting, You’re a very skilled
blogger. I have joined your feed and look forward to seeking more of your excellent
post. Also, I have shared your site in my social
networks!
We stumbled over here by a different web address and thought I might as well check things out.
I like what I see so i am just following you. Look
forward to finding out about your web page for a second time.
Hello, i think that i saw you visited my weblog
so i came to “return the favor”.I’m attempting to find things to
improve my site!I suppose its ok to use a few of your ideas!!
Your means of telling everything in this piece of writing is
in fact good, every one can effortlessly understand it, Thanks a lot.
Howdy! This blog post couldn’t be written much better!
Reading through this article reminds me of my
previous roommate! He always kept preaching about this.
I’ll send this post to him. Pretty sure he will have a great read.
Thanks for sharing!
I like this weblog its a master peace ! Glad I noticed this on google .
What’s up to all, how is the whole thing, I think every one
is getting more from this web site, and your views are
good in favor of new viewers.
I used to be recommended this blog through my cousin. I’m no longer sure whether this post is written by means of him as no one else
realize such unique approximately my trouble. You’re amazing!
Thank you!
After looking at a few of the blog posts on your web site, I honestly like
your technique of writing a blog. I added it to my bookmark website list and will be checking back soon. Please visit my website as well and tell me how you
feel.
Why viewers still make use of to read news papers when in this technological world all is existing on web?
What’s up, its good paragraph about media print, we all understand media is
a fantastic source of facts.
Admiring the commitment you put into your site and in depth information you provide.
It’s great to come across a blog every once in a while that
isn’t the same old rehashed information. Excellent read! I’ve saved your
site and I’m adding your RSS feeds to my Google account.
Ridiculous quest there. What occurred after? Good luck!
Wow, fantastic weblog layout! How lengthy have you been running a blog for?
you made running a blog look easy. The full look
of your website is magnificent, let alone the content material!
What a data of un-ambiguity and preserveness of valuable knowledge on the topic of unexpected emotions.
What’s up, this weekend is fastidious in favor of
me, since this point in time i am reading this enormous informative
post here at my residence.
Spot on with this write-up, I seriously think this web site needs
much more attention. I’ll probably be back again to read through
more, thanks for the advice!
Good post. I learn something new and challenging
on sites I stumbleupon everyday. It’s always exciting to read
content from other writers and use something from their web
sites.
Very fantastic information can be found on web blog. “I said I didn’t want to run for president. I didn’t ask you to believe me.” by Mario M Cuomo.