题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf
std是O(n^3)的算法？
明明NOIP范围内可以O(n^2logn)搞的！
就是二分长度，然后用滑动窗口搞一搞
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 300+9;
const int SGZ = 27;
int n,k;
char S[N],T[N];
queue<int> que;
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 bool judge(int len) {
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (S[++p1] != T[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (S[++p1] != T[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (T[++p1] != S[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (T[++p1] != S[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
return false;
}
int main(){
freopen("master.in","r",stdin);
freopen("master.out","w",stdout);
n = read(); k = read();
scanf("%s%s",S+1,T+1);
int l=1,r=n,ret=0;
while (l <= r) {
int mid = l + r >> 1;
if (judge(mid)) ret = mid, l = mid+1;
else r = mid-1;
}
printf("%d\n",ret);
return 0;
}
Incredible points. Outstanding arguments. Keep up the good work.
What a data of un-ambiguity and preserveness of precious
know-how concerning unpredicted emotions.
With havin so much content do you ever run into any problems of plagorism or
copyright violation? My website has a lot of completely unique content I’ve
either written myself or outsourced but it seems a lot of it is popping it up
all over the web without my authorization. Do you know
any ways to help reduce content from being ripped off?
I’d certainly appreciate it.
Hmm is anyone else experiencing problems with the pictures on this blog loading?
I’m trying to figure out if its a problem on my end or if it’s
the blog. Any feedback would be greatly appreciated.
It’s actually a nice and helpful piece of information. I’m happy that you just shared this useful info with
us. Please stay us up to date like this.
Thank you for sharing.
Hello to all, how is the whole thing, I think every
one is getting more from this web page, and your views are pleasant
for new people.
I am extremely impressed with your writing skills and also with the layout on your weblog.
Is this a paid theme or did you modify it yourself?
Either way keep up the excellent quality writing, it’s rare to see a nice blog like this one nowadays.
Hi there it’s me, I am also visiting this web page regularly, this
site is genuinely nice and the users are truly sharing nice thoughts.
Thanks , I’ve just been searching for info approximately this topic for ages and yours is the best
I’ve discovered so far. However, what about the conclusion? Are you
certain in regards to the supply?
This site was… how do I say it? Relevant!! Finally I’ve found something which helped me.
Cheers!
I am not sure where you are getting your info, but great topic.
I needs to spend some time learning more or understanding more.
Thanks for great information I was looking for this information for my mission.
I’ve read some excellent stuff here. Definitely price bookmarking for revisiting.
I surprise how much effort you place to create one of
these great informative website.
Hi there! This post could not be written any better! Reading this post reminds me of my previous room mate! He always kept talking about this. I will forward this article to him. Fairly certain he will have a good read. Thank you for sharing!
Hi, this weekend is pleasant designed for me,
because this point in time i am reading this impressive educational article here
at my home.
These are really impressive ideas in regarding blogging.
You have touched some pleasant points here. Any way keep up wrinting.
I have been surfing on-line more than three hours as of
late, yet I by no means discovered any fascinating article like yours.
It’s lovely worth enough for me. Personally,
if all website owners and bloggers made good content as you probably did, the net can be a lot more helpful than ever before.
Howdy this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if
you have to manually code with HTML. I’m starting a blog soon but have no
coding know-how so I wanted to get guidance from someone with experience.
Any help would be greatly appreciated!
I needed to thank you for this wonderful read!! I definitely enjoyed every
little bit of it. I’ve got you saved as
a favorite to check out new stuff you post…
We’re a group of volunteers and starting a new scheme in our community.
Your web site provided us with useful information to work on.
You have done an impressive process and our entire community will probably be grateful to you.
Nice blog here! Also your web site loads up very fast!
What host are you using? Can I get your affiliate link to your host?
I wish my website loaded up as fast as yours
lol
This page certainly has all of the information I needed concerning this
subject and didn’t know who to ask.
I as well as my guys happened to be looking through the nice recommendations from your site while the sudden developed a horrible feeling I had not expressed respect to the blog owner for those tips. My guys happened to be so stimulated to learn them and have in effect extremely been taking pleasure in those things. Thanks for truly being really considerate and for choosing these kinds of ideal themes millions of individuals are really needing to be informed on. My very own honest regret for not expressing appreciation to sooner.