)
多多的灰度发布拼多多技术岗 7月19号笔试 第一题题目内容多多在维护一批编号1 , 2 , … , n 1,\ 2,\ \dots,\ n1,2,…,n排列的实例。每个实例只有两种状态0 00表示使用旧版本1 11表示使用新版本。多多在灰度发布平台执行了一次操作选择一个非空连续区间[ L , R ] [L,\ R][L,R]选择一个目标状态v vv其中v vv为0 00或1 11把区间内所有实例的状态都设为v vv区间中可以包含原本就已经处于状态v vv的实例但这次操作必须至少改变一个实例的状态。发布前后的实例状态串A AA和B BB被完整保留但操作日志丢失了保证至少存在一种操作可以把A AA变为B BB。请判断这次操作能否被唯一确定。若合法的三元组( L , R , V ) (L,\ R,\ V)(L,R,V)恰好只有一个输出它否则输出− 1 -1−1。 注意只要L 、 R L、RL、R或V VV中有任意一项不同就视为不同的操作即使它们得到的发布后状态完全相同。输入描述第一行包含一个正整数T TT表示测试用例的数量。对于每个测试用例第一行包含一个整数n nn表示实例数量。第二行包含一个长度为n nn的01 0101串A AA表示发布前的状态。第三行包含一个长度为n nn的01 0101串B BB表示发布后的状态。输出描述对于每个测试用例如果操作唯一输出一行三个整数L R V L\ R\ VLRV。如果不存在唯一操作输出一行− 1 -1−1。补充说明1 ≤ T ≤ 10 1 \le T \le 101≤T≤10A AA和B BB均为长度恰好为n nn的01 0101串单个输入文件中所有测试用例的n nn之和不超过2 ∗ 10 5 2 * 10^52∗105保证每组数据至少存在一种合法操作。样例1输入6 5 00000 01110 5 01000 01110 6 111111 100001 7 0001000 0111110 1 0 1 5 00010 01110输出2 4 1 -1 2 5 0 2 6 1 1 1 1 -1题解和思路思路实现思路逻辑分析对于每组输入通过遍历发布前/后字符串找到对应start 第一个不同位置和end 最后一个不同的位置根据第一步得出start和end可以完成一下判断start -1,说明发布前/后字符串完全相同不存在唯一解。将发布前变更为发布后唯一可能的v就是B[start], 判断[start, end]是否全为v,不全为v说明根本无法通过一次操作将发布前变更为发布后。由于区间中可以包含原本就已经处于状态v vv的实例通过上面判断之后可以得知[start, end, v]肯定是一个合法操作。要保证是否唯一主要看是否能够进行区间左右扩展。B[start - 1] v说明能往左侧扩展答案不唯一B[end-1] v说明能往右侧扩展答案不唯一算法平均时间复杂度为OnC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;string A,B;cinA;cinB;// 不同的开始和结束位置intstart-1;intend-1;for(inti0;in;i){if(A[i]!B[i]){if(start-1){starti;}endi;}}// 没有变化不存在合法操作if(start-1){cout-1endl;continue;}// 确定vintvB[start]-0;booloktrue;// 判断B [start,end]是否都为v v肯定为B[start]for(intistart;iend;i){if(B[i]!B[start]){okfalse;break;}}// 左右扩展判断是否唯一if(okstart0B[start-1]B[start]){okfalse;}if(okendn-1B[end1]B[start]){okfalse;}// 不唯一if(!ok){cout-1endl;}else{coutstart1 end1 B[start]-0endl;}}return0;}Javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intTsc.nextInt();while(T--0){intnsc.nextInt();StringAsc.next();StringBsc.next();// 不同的开始和结束位置intstart-1;intend-1;for(inti0;in;i){if(A.charAt(i)!B.charAt(i)){if(start-1){starti;}endi;}}// 没有变化不存在合法操作if(start-1){System.out.println(-1);continue;}// 确定vintvB.charAt(start)-0;booleanoktrue;// 判断B[start,end]是否都为vv肯定为B[start]for(intistart;iend;i){if(B.charAt(i)!B.charAt(start)){okfalse;break;}}// 左右扩展判断是否唯一if(okstart0B.charAt(start-1)B.charAt(start)){okfalse;}if(okendn-1B.charAt(end1)B.charAt(start)){okfalse;}// 不唯一if(!ok){System.out.println(-1);}else{System.out.println((start1) (end1) v);}}}}pythonTint(input())for_inrange(T):nint(input())Ainput().strip()Binput().strip()# 不同的开始和结束位置start-1end-1foriinrange(n):ifA[i]!B[i]:ifstart-1:starti endi# 没有变化不存在合法操作ifstart-1:print(-1)continue# 确定vvint(B[start])okTrue# 判断B[start,end]是否都为vv肯定为B[start]foriinrange(start,end1):ifB[i]!B[start]:okFalsebreak# 左右扩展判断是否唯一ifokandstart0andB[start-1]B[start]:okFalseifokandendn-1andB[end1]B[start]:okFalse# 不唯一ifnotok:print(-1)else:print(start1,end1,v)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,(line){input.push(line);});rl.on(close,(){letidx0;constTNumber(input[idx]);constans[];for(lett0;tT;t){constnNumber(input[idx]);constAinput[idx];constBinput[idx];// 不同的开始和结束位置letstart-1;letend-1;for(leti0;in;i){if(A[i]!B[i]){if(start-1){starti;}endi;}}// 没有变化不存在合法操作if(start-1){ans.push(-1);continue;}// 确定vconstvNumber(B[start]);letoktrue;// 判断B[start,end]是否都为vv肯定为B[start]for(letistart;iend;i){if(B[i]!B[start]){okfalse;break;}}// 左右扩展判断是否唯一if(okstart0B[start-1]B[start]){okfalse;}if(okendn-1B[end1]B[start]){okfalse;}// 不唯一if(!ok){ans.push(-1);}else{ans.push(${start1}${end1}${v});}}console.log(ans.join(\n));});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,T)for;T0;T--{varnintfmt.Fscan(in,n)varA,Bstringfmt.Fscan(in,A)fmt.Fscan(in,B)// 不同的开始和结束位置start:-1end:-1fori:0;in;i{ifA[i]!B[i]{ifstart-1{starti}endi}}// 没有变化不存在合法操作ifstart-1{fmt.Println(-1)continue}// 确定vv:int(B[start]-0)ok:true// 判断B[start,end]是否都为vv肯定为B[start]fori:start;iend;i{ifB[i]!B[start]{okfalsebreak}}// 左右扩展判断是否唯一ifokstart0B[start-1]B[start]{okfalse}ifokendn-1B[end1]B[start]{okfalse}// 不唯一if!ok{fmt.Println(-1)}else{fmt.Println(start1,end1,v)}}}
