Codeforces Round 1091 (Div. 2) and CodeCraft 26

B&D 思维 问题转化

B题k=1
连续的可以统一处理 化成一个数
把x化成0 要去掉的数就是1
发现消掉一个1 需要两步 也可以两边同时消掉也是两步

voidsolve(){intn,k;cin>>n>>k;vector<int>a(n+1);a[0]=-1;intp;forr(i,1,n)cin>>a[i];cin>>p;intx=a[p];intfg=1;forr(i,1,n)if(a[i]!=a[p]){fg=0;break;}if(fg)returncout<<0<<endl,void();vector<int>b;b.push_back(0);intnp=0;forr(i,1,n){if(a[i]!=a[i-1])// 连续的可以统一处理b.push_back(a[i]^x);if(i==p)np=b.size()-1;}p=np;n=b.size()-1;intlcnt=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 可以两边配对消掉 cost=2*(max(lcnt, rcnt)-min(lcnt, rcnt))+2*min(lcnt, rcnt)=2 * max(lcnt, rcnt) */cout<<2*max(lcnt,rcnt)<<endl;}

D k>=1
用包含special index的区间把两边的1消掉，可以把special index看作区段端点，去掉区段中的1

voidsolve(){intn,k;cin>>n>>k;vector<int>a(n+1),p(k+1);a[0]=-1;forr(i,1,n)cin>>a[i];forr(i,1,k)cin>>p[i];intx=a[p[1]];intfg=1;forr(i,1,n)if(a[i]!=x){fg=0;break;}if(fg)returncout<<0<<endl,void();vector<int>b;b.push_back(-1);intid=1;vector<int>np;forr(i,1,n){if(a[i]!=a[i-1])// 连续的可以统一处理b.push_back(a[i]^x);if(id<=k&&i==p[id]){np.push_back(b.size()-1);id++;}}np.erase(unique(np.begin(),np.end()),np.end());n=b.size()-1;np.push_back(n);vector<int>preb(n+1,0);forr(i,1,n)preb[i]=preb[i-1]+b[i];/* 目标：消掉每个special index之间的1 就是让每个seg_i=0 op1：一个/两个位置seg_i -1代价为2 op2：三个位置seg_i -1 代价为3 mx<=sm-mx 只用op1就能消掉:mx和sm-mx两两消掉 剩下sm-2*mx - sm偶数 cost=mx*2+2*(sm-2*mx)/2=sm - sm及数 如果用op2 sm-3=2k 改变奇偶性cost=mx*2+2*(sm-3-2*mx)/2+3=sm mx>sm-mx 只用op1 两两消掉后 mx剩下mx-(sm-mx)=2mx-sm而且只在一个位置 cost=2*(sm-mx)+2*(2*mx-sm)=2*mx */vector<int>segb;forr(i,0,np.size()-1){if(i==0)segb.push_back(preb[np[i]]);elsesegb.push_back(preb[np[i]]-preb[np[i-1]]);}intsm=0,mx=0;for(autoi:segb)sm+=i,mx=max(mx,i);// cout << sm << ' ' << mx << endl;if(mx*2>sm)cout<<2*mx<<endl;elsecout<<sm<<endl;// 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;cin>>n>>m>>a>>b;if((__gcd(n,a)==1&&__gcd(m,b)==1)&&__gcd(n,m)<=2)yes;/* 走偶数步走到原来格子 x轮 n|ax=>n|x m|bx=>m|x lcm(n,m)|x gcd(n,m)=1 x_max=n*m gcd(n,m)=2 奇数步不会走到原来格子 会遍历完 */elseno;}