翻译
初始时你有一个空序列,共 \(m\) 次操作,每次操作读入两个数 \(t_i\),\(v_i\),分为以下两种操作:
- 当 \(t_i=1\) 时,在空序列中加入 \(2^{v_i}\) 这一元素。(此时 \(0 \le v_i \le 29\))
- 当 \(t_i=2\) 时,询问是否存在:取当前序列的某些元素,使它们的的和等于 \(v_i\)(此时 \(0 \le v_i \le 10^9\))。若存在输出
YES
,否则输出NO
。
思路
学过倍增求 LCA 的人都知道,每次倍增向上跳时的,会选择从大到小跳。在本题中,当判断是否存在时,从大到小判断选择的数,与倍增求 LCA 有异曲同工之妙。
最开始本来打算用一个数组 \(q\) 存值,然后每次询问时从大到小暴力查询,假设当前数组中有 \(k\) 个数,则单次复杂度为 \(O(k)\),明显复杂度不够优秀(吃了一发 TLE)。
转变思路,对于每个操作一,考虑用 \(q\) 存 \(v_i\) 的数量。再通过前面的小结论,每次查询时,通过查询出当前 \(v_i\) 可减去的最大 \(x \times 2^j\),\(j\) 表示当前枚举到的幂次,\(x\)(\(1 \le x \le q_j\))表示对应的倍数。
然后自信提交后又 TLE 了。
再次发现虽然幂次只有 \(30\)。但 \(q_j\) 可能会很大,单次枚举任然有极高的复杂度,所以这里直接使用二分枚举。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define mod 998244353
#define ll long long
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
//priority_queue <ll> q;
//priority_queue <ll , vector<ll> , greater<ll>> q;
inline ll QuickPow(ll a , ll b)
{
if(a == 1 || b == 0)
{
return 1;
}
ll k = QuickPow(a , b >> 1);
if(b & 1)
{
return k * k * a;
}
return k * k;
}
ll m , opt , x;
ll q[100005] , top;
ll max_num;
signed main()
{
// freopen("in.in" , "r" , stdin);
// freopen("out.out" , "w" , stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m;
while(m--)
{
cin >> opt >> x;
if(opt == 1)
{
q[x]++;
max_num += QuickPow(2 , x);
}
else
{
if(x > max_num)
{
cout << "NO" << '\n';
continue;
}
fo(i , 29 , 0)
{
if(!q[i])
{
continue;
}
ll l = 0 , r = q[i] , ans = 0;
ll mid;
ll now = QuickPow(2 , i);
while(l <= r)
{
mid = (l + r) / 2;
if(now * mid > x)
{
r = mid - 1;
}
else
{
ans = mid;
l = mid + 1;
}
}
x -= now * ans;
if(x <= 0)
{
break;
}
}
if(x == 0)
{
cout << "YES" << '\n';
}
else
{
cout << "NO" << '\n';
}
}
}
return 0;
}
标签:opt,le,题解,ll,Game,num,Multiset,include,复杂度
From: https://www.cnblogs.com/xhqdmmz/p/18126513