看到 $ n \le 10^5$,就知道这题不是纯模拟。
又看到了 $ 0 \le d < 2^{16}$,发现特殊的地方,于是就考虑使用二进制。
具体地,我们对两种操作分类讨论(题目中的字符打不出来,用 \(l\) 代替)。
操作一
在二进制下,将二进制数左移一位相当于将原数乘 \(2\)。不过由于数据范围很大,我们暂时先将其放在一边。
操作二
不难想到,可以直接在二进制下做高精度加法,复杂度也是可以接受的。现在要将其与操作一结合。
结论
每做一次加法,后面可能还要做若干次乘法。设做完某一次加法后还要做 \(p\) 次乘法,相当于要在本次操作后左移 \(p\) 位。那么我们可以反向思维,提前计算好最后的位置(从右往左第 \(p+1\) 位为最低位),直接在最后的位置做加法。那么,乘法操作就可以忽略了。
时间复杂度 \(O( n \log d)\),代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
int n,a[1000001],T,x[1000001],y[1000001],now,cnt,k,pd;
int main()
{
cin >> T;
while( T -- )
{
pd = 1;
now = 1;
a[now] = 0;
cin >> n;
for( int i = 1 ; i <= n ; i ++ )
{
a[i] = 0;
cin >> x[i];
if( x[i] == 2 )
cin >> y[i];
else
y[i] = 0;
}
for( int i = n + 1 ; i <= n + 1000 ; i ++ )
a[i] = 0;
for( int i = n ; i >= 1 ; i -- )
if( x[i] == 1 )
now ++,pd ++;
else
{
k = pd;
do
{
a[k] += y[i] % 2;
a[k+1] += a[k] / 2;
a[k] %= 2;
y[i] /= 2;
k ++;
}
while(y[i]);
while( a[k] > 1 )
{
a[k+1] += a[k] / 2;
a[k] %= 2;
k ++;
}
}
for( int i = 1 ; i <= n + 1000 ; i ++ )
{
a[i+1] += a[i] / 2;
a[i] %= 2;
}
cnt = n + 1000;
while( a[cnt] == 0 && cnt > 1 ) cnt --;
for( int i = cnt ; i >= 1 ; i -- )
cout << a[i];
cout << endl;
}
return 0;
}
标签:int,++,LG9155,pd,加法,--,now
From: https://www.cnblogs.com/-lilong-/p/17976891