首页 > 其他分享 >[CF1854E] Game Bundles

[CF1854E] Game Bundles

时间:2023-10-04 21:22:20浏览次数:35  
标签:le int 30 Bundles game 60 Game CF1854E dp

题目描述

Rishi is developing games in the 2D metaverse and wants to offer game bundles to his customers. Each game has an associated enjoyment value. A game bundle consists of a subset of games whose total enjoyment value adds up to $ 60 $ .

Your task is to choose $ k $ games, where $ 1 \leq k \leq 60 $ , along with their respective enjoyment values $ a_1, a_2, \dots, a_k $ , in such a way that exactly $ m $ distinct game bundles can be formed.

输入格式

The input is a single integer $ m $ ( $ 1 \le m \le 10^{10} $ ) — the desired number of game bundles.

输出格式

The first line should contain an integer $ k $ ( $ 1 \le k \le 60 $ ) — the number of games.

The second line should contain $ k $ integers, $ a_1, a_2, \dots, a_k $ ( $ 1 \le a_1, a_2, \dots, a_k \le 60 $ ) — the enjoyment values of the $ k $ games.

首先对于一个选择的集合,大于 30 的数最多只会选择一次。

所以考虑随机一个只由小于等于 30 的数组成的数列,然后在后面增加大于 30 的数。

首先想到到不断在后面增加小于等于 30 的数。每增加一个就是一下可不可以跑出来答案。

怎么试呢?定义 \(dp_i\) 为组成 \(i\) 的方案数,那么增加某一个大于 30 的数 \(x\) 增加的方案数是 \(dp_{60-x}\)。把所有的 dp 值从大到小排序后,能选就选。

然后发现这种方式凑出来的 \(m\) 不能超过 \(10^8\),但是正确率很高。

考虑为什么凑出来方案数太少,这是因为小于 30 的数重复的太少。

枚举一个 \(lim\),然后新增的时候强制序列中的数不超过 \(lim\),就能过了。

#include<bits/stdc++.h>
using namespace std;
int a[65],id[65];
long long n,m,dp[65];
int T,fl;
mt19937 gen(time(0));
int cmp(int x,int y)
{
	return dp[x]>dp[y];
}
int main()
{
	scanf("%lld",&n);
	while(1)
	{
		for(int j=30;j;j--)
		{
			memset(dp,0,sizeof(dp));
			dp[0]=1;
			for(T=1;T<=60;T++)
			{
				a[T]=gen()%j+1;
				for(int i=60;i>=a[T];i--)
					dp[i]+=dp[i-a[T]];
				if(dp[60]>n)
					break;
				m=n-dp[60],fl=T;;
		//		printf("%d\n",m);
				for(int i=0;i<=29;i++)
					id[i]=i;
				sort(id,id+30,cmp);
				for(int i=0;i<=29;i++)
				{
					while(fl<=60&&m>=dp[id[i]])
						a[++fl]=60-id[i],m-=dp[id[i]];
				}
				if(!m&&fl<=60)
				{
					printf("%d\n",fl);
					for(int i=1;i<=fl;i++)
						printf("%d ",a[i]);
					exit(0);
				}
			}
		}
	}
}

标签:le,int,30,Bundles,game,60,Game,CF1854E,dp
From: https://www.cnblogs.com/mekoszc/p/17742764.html

相关文章

  • AtCoder Grand Contest 056 D Subset Sum Game
    洛谷传送门AtCoder传送门考虑若\(n\)是奇数怎么做。枚举Alice第一次选的数\(a_i\),然后考虑把剩下的数两两结成一个匹配,若Bob选了其中一个,Alice就选另一个。容易发现排序后奇数位和它右边的偶数位匹配最优。那么设奇数位的和为\(A\),偶数位的和为\(B\),此时Alice获胜......
  • CF1875B Jellyfish and Game
    思路题意大概是两人都有一组数,奇数轮,第一个人可以选择和第二个人交换一个数字也可以不换,偶数轮,第二个人可以选择和第一个人交换一个数字也可以不换。首先可以猜测,我们每次都应该选择交换对方的最大值和自己的最小值,如果自己的最小值都比对方大的话就不交换。应该比较好想,这里感......
  • UTPC 2021 L Maze Game
    洛谷传送门AtCoder传送门若图中存在点使得删去它后\(S,T\)不连通,那么A可以一步获胜。否则,双方都不会删去一个点使得删去它后会产生一个点使得删去它后\(S,T\)不连通。那么到最后图上会剩下两条\(S\toT\)的不交路径。此时一方无论如何操作都会使得另一方获胜。因......
  • Galgame封包逆向入门
    Galgame封包逆向入门这里就简单聊一下封包逆向分析的一些注意点吧,其实也是初入逆向的注意点了,本质差不多。正向基础语言基础:ASM、C、C++平台基础:Win32、PE、GDI、DirectX引擎基础:游戏引擎架构虽然说的逆向,其实和正向的水平、见识、经验是强相关的,如果你没写过相关的程序又......
  • GameFi链游系统开发应用
      GameFi软件的开发是结合了区块技术,它是将游戏的元素移动到上链上,让游戏变得独立,这就符合了用户的娱乐方式。该软件项目还具有一定的投资价格,GameFi系统开发的应用可以带来更多的创新和价值。  GameFi的软件开发应用程序是让用户更好的管理自己的资产,有助于游戏的稳定,持......
  • CF1882C Card Game
    某种程度上的抽卡游戏?有这样一个结论:一个后缀中\([i+1,n]\)中所有的正数都可以被取到,所以维护一个正数后缀和\(s_i\),枚举每个位置\(i\),如果\(i\)为奇数,答案对\(a_i+s_{i+1}\)取\(\max\),否则对\(s_{i+1}\)取\(\max\)。下面证明这个结论:先依次取掉\([i+1,n]\)中的奇......
  • Strategic game POJ - 1463 树的最小点覆盖,树形dp
    题意:树的最小点覆盖,选择最少的点覆盖所有边。分析:状态:f[u][0/1]表示不选/选编号u的点的最优解转移:不选u,则一定选u的儿子v,即f[u][0]+=f[v][1]选u,则可以选,也可以不选u的儿子v,即f[u][1]+=min(f[v][0],f[v][1]);目标:ans=min(f[rt][0],f[rt][1]);点击查看代码#inc......
  • Python游戏开发:Pygame库入门
    Pygame是一个开源的Python库,用于开发2D游戏。它提供了许多功能,如游戏开发、音频处理和事件处理。安装Pygame库您可以通过以下命令在终端中安装Pygame库:pipinstallpygame创建游戏窗口要创建一个游戏窗口,您可以使用以下代码:importpygamepygame.init()#设置窗口尺寸window_......
  • [CF235D] Graph Game
    GraphGame乌克兰逃兵在线发题解。好像要用期望去推,但是像我这种看到序列的期望题只想得到线性性的弱鸡只能感理了。我们把点分治过程当成点分树,y能在x被爆时做贡献当且仅当y为x的子树。先考虑树的情况。考虑把遍历t的次数分到单个点上发现仅当x为x->y路径上......
  • Precomputed Radiance Transfer(games202)
    PrecomputedRadianceTransfer(games202)关于BRDF可以看看这篇文章基于物理着色:BRDF物体在不同光照下的表现不同,PRT(PrecomputedRadianceTransfer)是一个计算物体在不同光照下表现的方法。光线在一个环境中,会经历反射,折射,散射,甚至还会物体的内部进行散射。为了模拟具有真实......