Codeforces Round 907 (Div. 2) B. Deja Vu
思路:
预处理31位的 \(2^x\) 存在\(tmp_i\)
对于输入\(a_i\),通过查找最后一个二进制1位置,存在\(x0_i\)
由题意可知,对于输入的\(x\),如果有\(a_i\)可整除\(x\),则会使\(a_i\)加上\(2^{x-1}\)
所以之后除非是\(x-1\),否则无效,因此把输入\(x\)保存降序部分在vector
\(x\)从后往前,将\(2^{x_i}\)后缀和存在sum
对于\(a_i\),二分查找在\(x\)的第一个小于等于\(x0_i\)的位置
\(a_i\)加上后缀和
#define int long long
#define ld long double
#define pb push_back
#define pf push_front
using namespace std;
int t;
int tmp[32];
int a[100010];
int x0[100010];
vector<int>x;
deque<int>sum;
void ini()
{
tmp[0] = 1;
for (int i = 1; i <= 31; i++)
{
tmp[i] = tmp[i - 1] * 2LL;
}
}
void ss(int f, int i)
{
int cnt = 0;
while (f)
{
if (f & 1)
{
x0[i] = cnt;
return;
}
cnt++;
f >>= 1;
}
}
int check(int f)
{
int l = 0, r = x.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (x[mid] > f)
{
l = mid + 1;
}
else r = mid;
}
return sum[r];
}
void solve()
{
x.clear();
sum.clear();
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ss(a[i], i);
}
for (int i = 1; i <= q; i++)
{
int z;
cin >> z;
if (!x.size() || x[x.size() - 1]>z)
{
x.pb(z);
}
}
for (int i = x.size()-1; i>=0; i--)
{
if (i == x.size() - 1)
{
sum.pf(tmp[x[i]-1]);
}
else
{
sum.pf(tmp[x[i] - 1] + sum.front());
}
}
for (int i = 1; i <= n; i++)
{
if (x0[i]>=x[x.size()-1])
{
a[i] += check(x0[i]);
}
cout << a[i] << " ";
}
cout << endl;
}
signed main()
{
ini();
//t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
标签:tmp,907,int,sum,Codeforces,mid,Vu,define,size
From: https://www.cnblogs.com/ikunhuaji/p/17804124.html