2024北京市赛补题

原题链接
好难…用的技巧和算法很多

K 贪心 桶

直观想 每次最小的乘二 乘二就是左移 每次把最高位最小的乘二
枚举二进制位 把所有数整到一个最高二进制位上 如果还有剩的k就同步变大 用桶维护最高二进制位 2e5*30

vector<int>b[40];voidsolve(){intn,k;cin>>n>>k;vector<int>a(n+1);// ,b(n+1,0);forr(i,1,n){cin>>a[i];}forr(i,1,n){inttp=a[i],cnt=0;while(tp){cnt++;tp>>=1;}b[cnt].push_back(a[i]);}intans=0,sm=0;forr(i,0,30){sort(b[i].begin(),b[i].end());if(b[i].size()==n){inttm=k/n;k%=n;intpsm=0,ssm=0;forr(j,0,k-1)(psm+=b[i][j]%mod)%=mod;forr(j,k,b[i].size()-1)(ssm+=b[i][j]%mod)%=mod;(ans+=(psm*qpow(2,tm+1)%mod+ssm*qpow(2,tm)%mod)%mod)%=mod;break;}for(autox:b[i]){if(k>0)b[i+1].push_back(x<<1),k--;elseb[i+1].push_back(x);}if(k==0){forr(j,i+1,30){for(autox:b[j])(ans+=x%mod)%=mod;}break;}}cout<<ans<<endl;/* int ans=0,pre=0,id=n; forr(i,1,n-1){ int dis=b[i+1]-b[i]; cout<<dis<<' '<<k<<endl; (ans+=a[i])%=mod; if(dis>0){ int sft=min(k,dis*i); k-=sft; (ans*=qpow(2,sft))%=mod;// 合并成一块了 不知道其中如何分配 } if(k==0){ id=i; break; } } forr(i,id,n)ans+=a[i]; (ans*=qpow(2,k))%=mod; cout<<ans<<endl; */// int ans=0,psm=0,ssm=0;// forr(i,1,k)(psm+=a[i])%=mod;;// forr(i,k+1,n)(ssm+=a[i])%=mod;// ans= (qpow(2,tm+1)*psm%mod+qpow(2,tm)*ssm%mod)%mod;// cout<<ans<<endl;}

D LCA找两点之间的路径 判断点是否在路径上

如果本次点在相邻两点的路径上 那么这个点不是目标经典
用LCA找两点间路径

constintN=2e5+10,M=1e5;constdoublePI=acos(-1),eps=1e-7;constlonglongmod=1e9+7,inf=2e18;intn,m,q;intfa[N][35],dep[N];intb[N];vector<int>g[N];voiddfs(intnow,intf){// O(nlogn)fa[now][0]=f;dep[now]=dep[f]+1;for(inti=1;(1<<i)<=dep[now];i++){fa[now][i]=fa[fa[now][i-1]][i-1];}for(autox:g[now]){if(x==f)continue;dfs(x,now);}}intLCA(intx,inty){if(dep[x]<dep[y])swap(x,y);reforr(i,0,20){if(dep[fa[x][i]]>=dep[y])x=fa[x][i];}if(x==y)returnx;reforr(i,0,20){if(fa[x][i]!=fa[y][i]){x=fa[x][i],y=fa[y][i];}}returnfa[x][0];}boolisanc(intx,inttar){// 确定tar是否为x的祖先reforr(i,0,20){if(dep[fa[x][i]]>=dep[tar])x=fa[x][i];// x上跳}returnx==tar;}boolcheck(intp){// 判断now是不是目标景点 是1 不是0/* now是目标景点：不在相邻两点的路径上 */if(p==1||p==m)return1;// 不是两边都有点 不能确定是路过的点 那就算作目标景点intlp=b[p-1],rp=b[p+1],now=b[p];// 看now是否在lp rp的路上intf=LCA(lp,rp);if(dep[f]>dep[now])return1;//now比f深度浅 now不可能在路上// dep[f]<=dep[now] now可能在路上// lp rp 通过f连成一条路 如果now在路上 now是lp或rp的一个祖先if(isanc(lp,now)||isanc(rp,now))return0;elsereturn1;}voidsolve(){cin>>n>>m>>q;forr(i,1,n-1){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);forr(i,1,m)cin>>b[i];intans=0;forr(i,1,m)ans+=check(i);while(q--){intp,w;cin>>p>>w;// 一个点和相邻两点状态相关// 消除原来的状态if(p-1>=1)ans-=check(p-1);if(p+1<=m)ans-=check(p+1);ans-=check(p);//添加新的状态b[p]=w;if(p-1>=1)ans+=check(p-1);if(p+1<=m)ans+=check(p+1);ans+=check(p);cout<<ans<<endl;}}