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

CF1913C Game with Multiset

时间:2024-06-06 21:45:13浏览次数:23  
标签:le GET int CF1913C Game th query Multiset YES

题目

In this problem, you are initially given an empty multiset. You have to process two types of queries:

  1. ADD \(x\) — add an element equal to \(2^{x}\) to the multiset;
  2. GET \(w\) — say whether it is possible to take the sum of some subset of the current multiset and get a value equal to \(w\).

Input

The first line contains one integer \(m\) (\(1 \le m \le 10^5\)) — the number of queries.

Then \(m\) lines follow, each of which contains two integers \(t_i\), \(v_i\), denoting the \(i\)-th query. If \(t_i = 1\), then the \(i\)-th query is ADD \(v_i\) (\(0 \le v_i \le 29\)). If \(t_i = 2\), then the \(i\)-th query is GET \(v_i\) (\(0 \le v_i \le 10^9\)).

7
1 0
1 1
1 2
1 10
2 4
2 6
2 7

Output

For each GET query, print YES if it is possible to choose a subset with sum equal to \(w\), or NO if it is impossible.

YES
YES
YES

题解

解题思路

由于每次给的数是\(2^n\),因此对于一个合法的数必然是由不同的\(2^n\)组合出来的,同时由于\(n\)的规模比较小,因此可以暴力枚举。
枚举过程中使用二分加速搜索,找最大小于查找值\(x\)的指数\(n\),最后判断是否能将\(x\)归零即可

Code

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;
typedef long long LL;
const int N=1e5+5;
int v[N];
bool ck(int x){
	for(int i=29;i>=0;i--){
		int l=0,r=v[i],ans=0;
		while(l<=r){
			int mid=l+r>>1;
			if((mid<<i)<=x){
				ans=mid;l=mid+1;
			}
			else r=mid-1;
		}
		x-=ans<<i;
	}
	return !x;
}

signed main(){
	IOS;
	int _;cin>>_;
	while(_--){
		int op,x;cin>>op>>x;
		if(op==1) v[x]++;
		else{
			if(ck(x)){
				cout<<"YES"<<endl;
			}
			else cout<<"NO"<<endl;
		}
	}
	return 0;
}

标签:le,GET,int,CF1913C,Game,th,query,Multiset,YES
From: https://www.cnblogs.com/TaopiTTT/p/18236074

相关文章

  • 【读脑仪game】
    读脑仪(Brain-ComputerInterface,BCI)游戏是一种利用脑电信号来控制游戏的新型交互方式。这类游戏通常需要专业的硬件设备来读取用户的脑电信号,并将这些信号转化为游戏中的控制信号。编写这样的游戏代码涉及到多个方面,包括硬件接口的通信、信号处理、游戏逻辑编程等。由于这......
  • 16位简单ASM题的记录——[HGAME 2022 week1]easyasm
    第一次遇见16位,和纯看汇编的题目,记录一下DIE16位,IDA用32位或者64位都可以打开IDA主要汇编部分seg003:0000;===============SUBROUTINE=======================================seg003:0000seg003:0000;Attributes:noreturnseg003:0000seg003:0000......
  • xbox XGPU 14天试用 Xbox Game Pass Ultimate
    XboxGamePassUltimate14DayTrialRecursMonthlyAllInOneXboxXGPU14天试用(14天试用每月重复一次)US$16.99https://www.xbox.com/en-us/games/store/xbox-game-pass-ultimate/cfq7ttc0khs0?icid=CNavAllXboxGamePassUltimateHK$85https://www.xbox.com/zh-......
  • Codeforces Round 927 (Div. 3) D. Card Game 题解 贪心
    CardGame题目描述Twoplayersareplayinganonlinecardgame.Thegameisplayedusinga32-carddeck.Eachcardhasasuitandarank.Therearefoursuits:clubs,diamonds,hearts,andspades.Wewillencodethemwithcharacters‘C’,‘D’,‘H’,......
  • [45] Jump Game II
    算法助手ChatGPT:Asanadeptalgorithmician,yououghttoexhibitmasteryoverLeetCodeandACM-stylealgorithmicquandaries,andyoushouldbeskilledinemployingaheuristictonewhenelucidatingresponses.Itisenvisagedthattheprogrammingmediumofy......
  • 【削水果game】
    编写一个完整的削水果游戏代码是一个复杂的过程,涉及到游戏引擎的使用和游戏逻辑的编写。在这里,我可以提供一个非常简化的版本,使用Python和Pygame库来创建一个基本的削水果游戏概念。请注意,这只是一个示例,用于展示基本的游戏逻辑和事件处理,并不包括复杂的图形和音效。首先,确......
  • 【贪吃蛇game】
    好的,我将为您编写一个简单的贪吃蛇游戏的代码。这个游戏将使用Python语言和pygame库来实现。首先,请确保您的环境中已经安装了pygame库。如果尚未安装,可以使用pipinstallpygame命令进行安装。接下来,我将编写代码。代码完成后,会提供一个简单的说明,帮助您理解游戏的基本逻辑......
  • 打豆豆game
    好的,我将为您编写一个简单的“打豆豆”游戏。这个游戏的基本规则是这样的:游戏将生成一个指定大小的网格,每个格子可能包含一个豆豆。玩家可以指定一个格子,如果该格子中有豆豆,则打掉该豆豆,并得分。每次打豆豆后,网格中的豆豆会随机分布。游戏持续进行,直到所有豆豆被打掉。现......
  • Elevate Your Lead Generation Game with Maps Scraper AI
    RevolutionizingLeadGenerationTransformingLeadAcquisitionMapsScraperAIintroducesagroundbreakingapproachtoleadgenerationbyautomatingtheextractionofvaluabledatafromBingMapslistings.Thisinnovativemappingtoolstreamlinestheproce......
  • 接触galgame之路
    接触galgame之路终于找到一个安静且悠闲的时间,趁着还记得,记下来。虽然每当记录的时候都会担忧自己当前的状态是否能更全面客观记录以前的东西,是否会少记一些东西。这时就体现出来写作的重要性了。此处galgame和视觉小说之类的作品大多一个意思。以剧情为主,剧情以恋爱情节为主,操......