题目描述
blablabla
样例
blablabla
算法1
(贪心)
blablabla
时间复杂度
参考文献
C++ 代码
package com.rainco;
import java.io.*;
import java.util.*;
public class Main {
static int d;
static boolean judge(String str,String stad,int x){
int i=x-1;
int j=x+1;
char c1=str.charAt(i),c2=stad.charAt(i);
char now1=str.charAt(x),now2=stad.charAt(x);
char fu1=str.charAt(j),fu2=stad.charAt(j);
if(c1!=fu1){
return false;
}else{
if(now1=='1'){
if(c1=='0')
return true;
return false;
}else{
if(c1=='1')
return true;
return false;
}
}
}
public static void main(String[] args) throws IOException {
//java快读 快写
//BufferedReader re = new BufferedReader(new InputStreamReader(System.in))
//PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
PrintWriter printWriter=new PrintWriter(new OutputStreamWriter(System.out));
d=Integer.parseInt(sc.readLine());
while (d--!=0){
String t=sc.readLine();
String str=sc.readLine();
int len=str.length();
int res=0;
boolean flag=false;
for(int i=0;i<len;i++){
char ct=t.charAt(i);
char cstr=str.charAt(i);
if(i==0||i==len-1){
if(cstr!=ct){
printWriter.println(-1);
flag=true;
break;
}
}else{
if(ct!=cstr){
int j=i+1;
int k=i-1;
if(!judge(str,t,i)){
printWriter.println(-1);
flag=true;
break;
}else{
res++;
}
}
}
}
if(!flag)
printWriter.println(res);
}
printWriter.flush();
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla