首页 > 其他分享 >CF1913C Game with Multiset 题解

CF1913C Game with Multiset 题解

时间:2024-04-10 17:48:44浏览次数:27  
标签:opt le 题解 ll Game num Multiset include 复杂度

翻译

初始时你有一个空序列,共 \(m\) 次操作,每次操作读入两个数 \(t_i\),\(v_i\),分为以下两种操作:

  1. 当 \(t_i=1\) 时,在空序列中加入 \(2^{v_i}\) 这一元素。(此时 \(0 \le v_i \le 29\))
  2. 当 \(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

相关文章

  • CF1913B Swap and Delete 题解
    翻译给定一个字符串\(s\),你有两种操作:删除一个字符。(花费一枚金币)交换某两个字符的位置。(不花费金币)假设经过若干次操作后得到的字符串为\(t\)。\(t\)是好的当且仅当对于任意的\(i\)(\(1\lei\le|t|\),\(|t|\)为字符串\(t\)的长度),均满足\(t_i\nes_i\)。(\(s\)是......
  • CF1907B YetnotherrokenKeoard 题解
    比较简单,建议评橙。题面。思路对于每个给定的字符串,用两个大根堆来分别记录小写字母与大写字母,注意这里记录时不要记录大写的B和小写的b。每当出现一个B时,从记录大写字母的大根堆中取出目前最后录入的大写字母的位置,标记,接着弹出堆顶元素,标记。小写字母同理。以上操作在......
  • CF1891B Deja Vu 题解
    建议凭橙,思路橙,码量红到橙。题面。思路一,暴力直接依照题意模拟,复杂度\(O(tqn^2)\),看一眼数据范围,妥妥T飞,倒在第三个点。二,逐步优化看一眼数据发现,虽然\(q\)很大,但实际上\(x\)只有三十个值,因此首先预处理出从\(2^1\)到\(2^{30}\)的所有值,摘掉一个\(n\),复杂度\(O......
  • P9750 [CSP-J 2023] 一元二次方程 题解
    题面。直接依照题意模拟即可,注意细节。细节第一注意输出分式时分母为\(1\)不输出,分子为\(0\)直接输出零且不带正负号。第二约分时,\(gcd\)内的两个数应该都是非负实数。第三可以单独输出符号,注意别有多余的符号。第四当方程有两根且均是有理数时,要根据\(2a\)的正......
  • CF1815A Ian and Array Sorting 题解
    题面。直接进入主题吧。思路题目要求非递减序列,很明显,由题目给的操作,一定可以将这个序列的前\(n-1\)项能够满足是非递减序列,最后只需要比较第\(n\)项是否大于等于第\(n-1\)项即可。解释一下为什么。对于序列\(a\),从\(a_1\)开始到\(a_{n-1}\)结束,每次对\(a_i\)......
  • CF1909C Heavy Intervals 题解
    一种似乎更快抽象的解法?题面正文看这道题,给定序列\(l,r,c\),要求重构\(l,r,c\)使得\(\sum_{i=1}^n(r_i-l_i)\timesc_i\)最小。首先可以想到的就是尽量让小的\(r_i-l_i\)乘上大的\(c_i\)。这样子看来\(c_i\)几乎不需要更多的处理,仅需从小到大(或从大到小)排个序。来......
  • GitHub问题解决新突破,复旦大学MAGIS框架大幅超越GPT-4
    获取本文论文,请关注公众号【AI论文解读】回复:&nbsp;论文解读引言:GitHub问题解决的挑战与LLMs的潜力在软件开发的演进过程中,解决GitHub仓库中出现的问题是一个复杂的挑战。这不仅涉及到新代码的加入,还要维护现有功能的稳定运行。大型语言模型(LLMs)在代码生成和理解方......
  • Air Conditioner 题解
    [AirConditioner]题意简述题目链接。给定一个整数\(n\),每秒钟可以选择使\(n\)增加\(1\)或减少\(1\)或不改变,有\(M\)个询问,对于第\(i\)个询问,给定\(t_i,l_i,r_i\),表示询问在第\(t_i\)秒时,是否有\(n\in[l_i,r_i]\)。如果能满足所有的询问,输出YES,否则输出NO。......
  • Codeforces-182E 题解
    Vasyahasrecentlyboughtsomelandanddecidedtosurrounditwithawoodenfence.Hewenttoacompanycalled"Woodenboard"thatproduceswoodenboardsforfences.Vasyareadinthecatalogofproductsthatthecompanyhasatitsdisposal\(......
  • 20240410每日一题题解
    20240410每日一题题解Problem一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半,又贪嘴多吃了一个;接下来的每一天它都会吃剩余的桃子的一半外加一个。第\(n\)天早上起来一看,只剩下\(1\)个桃子了。请问小猴买了几个桃子?输入一个正整数\(n\),表示天数。输出小猴买了多......