首页 > 其他分享 >CF1854E Games Bundles 题解

CF1854E Games Bundles 题解

时间:2023-10-25 10:44:47浏览次数:46  
标签:题解 Bundles 60 Games CF1854E dp

乱搞题

设个 \(dp[i]\) 表示和为 \(i\) 的子序列个数,那么转移是容易的, \(dp[j]+=dp[j-i]\) ,然后就判下 \(dp[60]+dp[60-i]\) 是否大于 \(m\) ,发现这样子搞对于比较大的数可能达不到 \(m\) 的限制,因为这样子转移,默认的是一个数只选一次,但是我们可以重复选,这启发我们需要设定一个值 \(P\),让每个数选 \(P\) 次。直觉判断这题答案解很多,所以我们把 \(P\) 在 \([1,60]\) 范围随机一下,一直到 \(dp[60]==m\) 的时候就找到了答案。

时间复杂度,发现随机次数不会太大,或者你也可以穷举,上界是 \(O(60^3)\)

然后不知道为什么就过了。

仅供参考,训练意义不大

标签:题解,Bundles,60,Games,CF1854E,dp
From: https://www.cnblogs.com/blueparrot/p/17786570.html

相关文章

  • 题解 CF903G【Yet Another Maxflow Problem】
    加边\(A_n\stackrel{0}{\to}A_{n+1}\),\(B_0\stackrel{0}{\to}B_1\)。称形如\(A_i\toA_{i+1}\)的边为左部边,形如\(B_j\toB_{j+1}\)的边为右部边,形如\(A_i\toB_j\)的边为中间边。根据最大流最小割定理,将最大流问题转化为最小割问题求解。显然,至少存在一组最小割,包含恰好......
  • CF1777D题解
    分析首先看到那个\(10^{100}\)再加上样例,我们就能意识到在不是特别多的操作次数后这颗树上的值就会全变成\(0\)。因为没有子节点在一次操作后显然就会变成\(0\),然后第一次叶节点就会变成\(0\),然后下一次子节点中只有叶节点的就会变成\(0\),以此类推,理论上最多操作\(n\)......
  • CF1878B题解
    CF1878BAleksaandStack题目翻译给定\(n\),试构造一个长度为\(n\)的严格上升正整数序列\(a_1,a_2,a_3,...,a_n\)使得\(\foralli\in[3,n],(a_{i-1}+a_{i-2})\nmid3a_i\)。单个测试点内包含多组测试数据。思路拿到题目,发现不好一个数一个数地构造,考虑......
  • 华科新生赛题解
    因为学校里面写代码的条件不足,比如教学楼里面使用键盘就会被盯着看。感觉有点点自闭。早知道退学了。不知道现在退学是不是算晚。昨天好兄弟车昱辉说你是在学习又不是在打游戏,但是我还是很羞涩。Abfs,需要把已经搜到的点在枚举1到n的时候去掉,所以可以使用并查集。或者链表......
  • CF1777C题解
    分析看到题面里面的子序列觉得很恶心,如果是子段感觉就会比较好做。如果直接填上子序列中间的空隙就可能会取一些比必须要取的数更大或者更小的数,影响我们的答案。那么就可以直接排序,使得子序列中间的空隙的数必然\(\geq\)左端且\(\leq\)右端,不会影响我们的答案(因为极差只......
  • [题解]CF1223F Stack Exterminable Arrays
    CCF出的原题观摩一下。思路首先可以用一个Trie来维护。在这里对本文中的一些变量做一下说明。\(p\)表示当前维护的Trie中,指向的元素编号。\(t_i\)表示在Trie中编号为\(i\)的元素在原序列中的值。\(f_i\)表示在Trie中编号为\(i\)的元素在Trie中的父......
  • CSP-S 2023 题解
    CSP-S2023题解游记打得非常烂。。。也是一个经验的总结吧:T1.密码锁(lock)似乎也没什么好讲的,直接模拟枚举每一种情况即可。放上我的考场代码。#include<bits/stdc++.h>usingnamespacestd;intn,a[10][8],b[2][90][8],ans=0,len,l;intread(){intx=0,f=1;char......
  • Codeforces 1862G 题解
    传送门题解因为有这个操作:将序列\(a\)加上\(\{n,n-1,\cdots,1\}\),考虑差分。那么显然每次操作会将差分数组中的每个元素减去\(1\),如果差分数组中有\(0\),就会把\(0\)删除。所以可以发现差分数组中剩下的一定是操作前的最大值。由于操作后最大值还是最大值,最小值仍......
  • CF1777A题解
    分析发现操作2不会改变数的奇偶性,故无视。那么操作就是单纯删一个数。对于一个连续出现\(x\)个奇偶性相同的数的序列,需要删\(x-1\)个数(因为只剩下一个数就不会和相邻的数奇偶性相同了)。觉得找序列太麻烦,观察到连续出现\(x\)个奇偶性相同的数的序列有\(x-1\)个不......
  • CF1523D Love-Hate 题解
    抽象化题意:一共有\(m\)个元素,给定\(n\)个集合,每个集合的元素不超过\(15\)个,求出一个元素个数最多的集合\(S\)是至少\(\lceil\dfrac{n}{2}\rceil\)个集合的子集。其中$p$$(1\len\le2\cdot10^5,1\lep\lem\le60)$我们先假设\(limit=\lceil\dfrac......