【每日一题】—— B. Deja Vu（Codeforces Round 907 (Div. 2)）（暴力枚举、队列）

编程入门行业动态更新时间:2024-10-25 16:17:29

【每日一题】—— B. Deja Vu（Codeforces Round 907 (Div. 2)）（暴力枚举、<a href=https://www.elefans.com/category/jswz/34/1771257.html style= 队列）"/>

【每日一题】—— B. Deja Vu（Codeforces Round 907 (Div. 2)）（暴力枚举、队列）

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

题目大意：

给你一个长度为 n n n 的数组 a a a ，由正整数组成，和一个长度为 q q q 的数组 x x x ，也由正整数组成。
一共有 q q q 个修改。关于 i i i （ 1 ≤ i ≤ q 1 \leq i \leq q 1≤i≤q ）的修改，对于每个 j j j ( 1 ≤ j ≤ n 1 \leq j \leq n 1≤j≤n )，使得 a j a_j aj 可以被 2 x i 2^{x_i} 2xi 整除，那么就把 2 x i − 1 2^{x_i-1} 2xi−1 加到 a j a_j aj 。注意 x i x_i xi ( 1 ≤ x i ≤ 30 1 \leq x_i \leq 30 1≤xi≤30 ) 是个不超过 30 的正整数。
完成所有修改查询后，需要输出最终数组。

题目链接：

B. Deja Vu（Codeforces Round 907 (Div. 2)）

二.思路分析

主要讲解代码一的思想，代码二就当做一种技巧吧，知道就好，不详细解释了。

首先需要根据题目推出背后的性质：如果一个数是 2 x 2^{x} 2x的倍数，那么它就可以写成k* 2 x − 1 2^{x-1} 2x−1，然后转换成2k* 2 x − 1 2^{x-1} 2x−1，加上 2 x − 1 2^{x-1} 2x−1,就变成了(2k+1) 2 x − 1 2^{x-1} 2x−1,那么肯定不能整除 2 x 2^{x} 2x，而变成了 2 x − 1 2^{x-1} 2x−1的倍数，所以数据经过操作之后会降级：从原来整除 2 x 2^{x} 2x变成整除 2 x − 1 2^{x-1} 2x−1；
首先需要先将数组a里的元素预处理，将其分类，分到对应能整除的次方下，用队列存储下标，存储下标的好处就是，我们可以通过下标直接修改元素值；
然后枚举数组x，这边有一个重要的点， 2 x 2^{x} 2x能够整除 2 x 2^{x} 2x， 2 x + 1 2^{x+1} 2x+1也能整除 2 x 2^{x} 2x，所以能整除大于 2 x 2^{x} 2x的数也需要+ 2 x − 1 2^{x-1} 2x−1，操作完之后将其从原来的队列里出列，进行降级处理，放入 2 x − 1 2^{x-1} 2x−1对应的队列里

最后就是对数据进行一些简单的处理，详细内容见代码一。

三.代码展示

代码一（队列+预处理思想）

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;int a[200020];
int x[200020];
deque<int>heap[31];//表示2的0次方到30次方void solve()
{int n,q;cin>>n>>q;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<q;i++){cin>>x[i];}for(int i=0;i<n;i++)//预处理数组a，将其放入对应的次方{for(int j=1;j<=30;j++){if(a[i]%(1<<j)!=0){heap[j-1].push_back(i);//队列一般都是存下标,通过下标直接修改原数组的值break;}}}for(int i=0;i<q;i++){for(int j=30;j>=x[i];j--)//一个数可能能除以比它大的次方，操作完之后会降级{while(heap[j].size()){int tmp=heap[j].front();//保存下标heap[j].pop_front();//修改数组中的值a[tmp]+=(1<<(x[i]-1));heap[x[i]-1].push_back(tmp);}}}for(int i=0;i<n;i++){cout<<a[i]<<" ";}for(int i=0;i<=30;i++){heap[i].clear();}cout<<"\n";
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

代码二（暴力模拟）

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;int mp[31]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};
int flag[31]={0};
int s[200020];void solve()
{memset(flag,0,sizeof(flag));int n,q;cin>>n>>q;for(int i=1;i<=n;i++){cin>>s[i];}for(int i=0;i<q;i++){int x;cin>>x;if(flag[x]==1){continue;}flag[x]=1;for(int i=1;i<=n;i++){if(s[i]%mp[x]==0){s[i]+=mp[x-1];}}}for(int i=1;i<=n;i++){cout<<s[i]<<" ";}cout<<"\n";
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}