展廊灯带后缀点亮拼多多技术岗 8月23号笔试 第一题题目内容展廊里沿墙装了一条灯带分成mmm段从左到右编号为111到mmm。每段有两种状态亮记为1灭记为0。值班员从最左侧开始只向右走走到第iii段时可以按一次该段的总控。按下后第iii段到第mmm段的状态全部翻转1变成00变成1。走过某段后不能再回头。要求走完全部灯段后每一段都是1。求最少按几次总控。形式化地给定长度为mmm的0/1序列b1,b2,…,bmb_1,b_2,\ldots,b_mb1​,b2​,…,bm​。一次操作选定下标iii把bi,bi1,…,bmb_i,b_{i1},\ldots,b_mbi​,bi1​,…,bm​全部取反。操作必须按下标从小到大决定且每个下标最多操作一次。求使序列变为全1的最少操作次数。输入描述第一行一个整数mmm1≤m≤1051\le m\le 10^51≤m≤105表示灯段数。第二行mmm个整数b1,b2,…,bmb_1,b_2,\ldots,b_mb1​,b2​,…,bm​每个数只能是0或1表示各段初始状态。输出描述输出一个非负整数表示最少操作次数。样例1输入1 1输出0说明只有一段且已经是1不必按总控。样例2输入3 0 1 0输出3说明第1段是0必须按序列变为1 0 1。第2段此时是0必须按序列变为1 1 0。第3段此时是0再按一次变为1 1 1。共3次。样例3输入4 0 0 1 1输出2说明先按第1段得到1 1 0 0走到第3段时再按一次得到1 1 1 1。共2次。数据范围1≤m≤1051\le m\le 10^51≤m≤105bi∈{0,1}b_i\in\{0,1\}bi​∈{0,1}所有输入均为整数题解和思路思路实现思路模拟其实反转次数就是从前往后遍历过程中当前位置值 经过前面反转处理之后是否为0为0的情况就需要进行一次反转。基于1的分析使用flag记录后续位置是否需要进行反转初始设置值为0.从前往后遍历a时将state a[i] ^ flag如果state 0需要进行一次反转并更新flag ^1算法时间复杂度为OnC#includebits/stdc.husingnamespacestd;intmain(){intm;cinm;vectorinta(m);for(inti0;im;i){cina[i];}intans0;// 反转intflag0;for(inti0;im;i){// 异或 之后 1 0 才是正确intstateflag^a[i];if(state1){continue;}// 说明当前位置为0需要进行反转ans;flag^1;}coutans;return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intmsc.nextInt();int[]anewint[m];for(inti0;im;i){a[i]sc.nextInt();}intans0;// 反转intflag0;for(inti0;im;i){// 异或 之后 1 0 才是正确intstateflag^a[i];if(state1){continue;}// 说明当前位置为0需要进行反转ans;flag^1;}System.out.println(ans);}}pythonimportsys datasys.stdin.read().split()mint(data[0])alist(map(int,data[1:m1]))ans0# 反转flag0foriinrange(m):# 异或 之后 1 0 才是正确stateflag^a[i]ifstate1:continue# 说明当前位置为0需要进行反转ans1flag^1print(ans)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(...line.trim().split(/\s/));});rl.on(close,(){letindex0;constmNumber(input[index]);consta[];for(leti0;im;i){a.push(Number(input[index]));}letans0;// 反转letflag0;for(leti0;im;i){// 异或 之后 1 0 才是正确conststateflag^a[i];if(state1){continue;}// 说明当前位置为0需要进行反转ans;flag^1;}console.log(ans);});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varmintfmt.Fscan(in,m)a:make([]int,m)fori:0;im;i{fmt.Fscan(in,a[i])}ans:0// 反转flag:0fori:0;im;i{// 异或 之后 1 0 才是正确state:flag^a[i]ifstate1{continue}// 说明当前位置为0需要进行反转ansflag^1}fmt.Fprintln(out,ans)}