文章目录BD 思维 问题转化C 数论 同余原题链接BD 思维 问题转化B题k1连续的可以统一处理 化成一个数把x化成0 要去掉的数就是1发现消掉一个1 需要两步 也可以两边同时消掉也是两步voidsolve(){intn,k;cinnk;vectorinta(n1);a[0]-1;intp;forr(i,1,n)cina[i];cinp;intxa[p];intfg1;forr(i,1,n)if(a[i]!a[p]){fg0;break;}if(fg)returncout0endl,void();vectorintb;b.push_back(0);intnp0;forr(i,1,n){if(a[i]!a[i-1])// 连续的可以统一处理b.push_back(a[i]^x);if(ip)npb.size()-1;}pnp;nb.size()-1;intlcnt0,rcnt0;reforr(i,1,p-1)if(b[i]1)lcnt;forr(i,p1,n)if(b[i]1)rcnt;/* 每次消掉一个1 需要2次操作 eg.01 可以两边配对消掉 cost2*(max(lcnt, rcnt)-min(lcnt, rcnt))2*min(lcnt, rcnt)2 * max(lcnt, rcnt) */cout2*max(lcnt,rcnt)endl;}D k1用包含special index的区间把两边的1消掉可以把special index看作区段端点去掉区段中的1voidsolve(){intn,k;cinnk;vectorinta(n1),p(k1);a[0]-1;forr(i,1,n)cina[i];forr(i,1,k)cinp[i];intxa[p[1]];intfg1;forr(i,1,n)if(a[i]!x){fg0;break;}if(fg)returncout0endl,void();vectorintb;b.push_back(-1);intid1;vectorintnp;forr(i,1,n){if(a[i]!a[i-1])// 连续的可以统一处理b.push_back(a[i]^x);if(idkip[id]){np.push_back(b.size()-1);id;}}np.erase(unique(np.begin(),np.end()),np.end());nb.size()-1;np.push_back(n);vectorintpreb(n1,0);forr(i,1,n)preb[i]preb[i-1]b[i];/* 目标消掉每个special index之间的1 就是让每个seg_i0 op1一个/两个位置seg_i -1代价为2 op2三个位置seg_i -1 代价为3 mxsm-mx 只用op1就能消掉:mx和sm-mx两两消掉 剩下sm-2*mx - sm偶数 costmx*22*(sm-2*mx)/2sm - sm及数 如果用op2 sm-32k 改变奇偶性costmx*22*(sm-3-2*mx)/23sm mxsm-mx 只用op1 两两消掉后 mx剩下mx-(sm-mx)2mx-sm而且只在一个位置 cost2*(sm-mx)2*(2*mx-sm)2*mx */vectorintsegb;forr(i,0,np.size()-1){if(i0)segb.push_back(preb[np[i]]);elsesegb.push_back(preb[np[i]]-preb[np[i-1]]);}intsm0,mx0;for(autoi:segb)smi,mxmax(mx,i);// cout sm mx endl;if(mx*2sm)cout2*mxendl;elsecoutsmendl;// int lcnt 0, rcnt 0;// reforr(i, 1, p - 1) if (b[i] 1) lcnt;// forr(i, p 1, n) if (b[i] 1) rcnt;// /*// 每次消掉一个1 需要2次操作 eg.01// 可以两边配对消掉// */// // cout lcnt rcnt endl;// cout 2 * max(lcnt, rcnt) endl;}C 数论 同余参考ImALAS 的题解dalao写的太好了谢谢大佬voidsolve(){intn,m,a,b;cinnmab;if((__gcd(n,a)1__gcd(m,b)1)__gcd(n,m)2)yes;/* 走偶数步走到原来格子 x轮 n|axn|x m|bxm|x lcm(n,m)|x gcd(n,m)1 x_maxn*m gcd(n,m)2 奇数步不会走到原来格子 会遍历完 */elseno;}