CF1891B Deja Vu

2024-02-09 21:28

文章标签 vu deja cf1891b

本文主要是介绍CF1891B Deja Vu，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

You are given an array a of length n , consisting of positive integers, and an array x of length q , also consisting of positive integers.

There are q modification. On the i -th modification ( 1≤i≤q ), for each j ( 1≤j≤n ), such that aj is divisible by $2^x$ , you add $2^{x-1}$ to aj . Note that xi ( 1≤xi≤30 ) is a positive integer not exceeding 30. After all modification queries, you need to output the final array.

给你一个长度为 n 的数组 a，接下来依次进行 q 次修改，第 i 次会给你一个数 x，你需要将 a 中所有是 $2^x$ 的倍数的数加上 $2^{x-1}$ ，最后输出这个序列。共有 t 组数据。

分析

看到 $2^x$ 的倍数，应该不难想到满足条件的数在二进制下的x位一下一定都为0，而加上 $2^{x-1}$ 以后的数，一定不能被 $2^{y}$ （ $y\geq x$ ）整除所以可以把操作序列化简为一个单调下降序列，然后我们将操作合并成 z

再来看操作序列对a的影响，不难发现，若设x位满足a[ i ] 的第0位到第x位都为0的最大值，则只有z的0~x位对a[ i ] 有贡献（因为再大的就不能被a[ i ]整除了）对于求x，可以化简为 a[ i ] 最大能整除的2的整数次幂，可以通过lowbit函数求解对于求z，在已经求出x的情况下就非常好求了，具体见代码

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,T,a[100005];
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);scanf("%d",&x); y=x; z=(1<<(x-1)); //第一个操作特殊处理for(int i=2;i<=m;i++){scanf("%d",&x);if(x<y) y=x,z|=(1<<(x-1)); //求单调下降的贡献 + 更新当前最小值}for(int i=1;i<=n;i++) a[i]+=(((a[i]&(-a[i]))-1)&z);//(a[i]&(-a[i]) 为求a[i]的lowbit//(a[i]&(-a[i])-1 为将满足条件的位子变为1//(a[i]&(-a[i])-1)&z  为去除z的最后x位//有lowbit性质可知，a[i]的后x位一定为0，固可以直接加for(int i=1;i<=n;i++) printf("%d ",a[i]); cout<<"\n";}return 0;
}

这篇关于CF1891B Deja Vu的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！