题目描述
样例
算法1
(暴力枚举) $O(n)$
挺简单的题,看上去很难,实际上直接找就可以了。遇到需要翻转的且连续的就可以一起翻转,为什么这样是最少的(我也不知道)希望大佬可以证明一下。感觉像是一个结论题
时间复杂度
n
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void re(T &x){
int f=1;
x=0;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-f;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
x*=f;
return;
}
template <typename T>void wr(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) wr(x/10);
putchar(x%10+'0');
return;
}
string a;
string b;
int c;
signed main() {
cin>>c;
cin>>a>>b;
int ans = 0;
bool pd = false;
for(int i = 0;i < a.size();i ++) {
if(a[i] != b[i]) {
if(!pd){
pd = true;
}
}
else {
if(pd == true) {
ans ++;
pd = false;
}
}
}
if(pd == true)
ans ++;
cout<<ans;
return 0;
}
****
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla