首页 > 其他分享 >CF DP 题乱做(续更)

CF DP 题乱做(续更)

时间:2023-11-03 20:11:58浏览次数:40  
标签:gcd CF 枚举 DP 考虑 题乱 转移 dp log

CF566F

$1500$

容易考虑到 $n^2$ 做法:设 $dp_i$ 为第 $i$ 个数选的答案,对于排好序的序列,枚举前面的数 $a_j$,如果 $a_j|a_i$ 就转移,时间复杂度易知 $O(n^2+n\log n)$。

由于 $a$ 至于很小,延续刚才的思路,设 $dp_i$ 为选为 $i$ 的答案。那么她可以更新她的所有倍数,枚举倍数即可。

考虑到 $a_i$ 互不相同(我也不知道怎么知道这个条件的,但是不去重直接算能过),那么极端情况就是 $\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor = n \log n$ 所以可以通过。

CF264B

$1500$

容易写出 $dp_i$ 记录选第 $i$ 个数的答案,可以由 $j$ 满足 $\gcd(a_i,a_j)>1$ 转移过来。

但这太慢了,考虑我提前搜出来每个数的因数,同时维护一个 $f_i$ 表示因数为 $i$ 能得到的最大贡献,这样大大减少了枚举数量,可以通过此题。

有转移:

$dp_i = \max{f_j}+1$

CF474D

$1700$

设计 $dp_i$ 为长度为 $i$ 的方案数,那么她要么是 $0$,要么是 $1$,如果是 $0$,那么她的上一位就没限制,所以从 $i-1$ 转移过来;是 $1$,那么前 $k$ 位就都得是 $1$,所以在此区间只有一种方案,所以应从 $i-k$ 转移过来。

有:$dp_i = dp_{i-1} + dp_{i-k}\times[i\ge k]$

初始化 $dp_0 = 1$

前缀和一下即可。

CF580D

$1700$

看数据范围可知是状压,考虑 $dp_{S,i}$ 为吃了 $S$ 集合里的,最后吃的是 $i$。

枚举集合 $S$,记录 $popcount$,如果刚好是 $m$,统计一轮答案。如果比 $m$ 小,则有转移:

$$
dp_{S+i,i}= \max{dp_{S+i,i},dp_{S,j}+a_i+c_{j,i}}
$$

枚举 $i$ 是接下来要吃的,$j$ 是刚刚吃完的。

时间复杂度 $O(n22n+n+k)$ 可以通过此题。

CF1635D

$1800$

考虑把这些数当做二进制处理,对 $1e5$ 的 $p$ 来讲更加友善。

那么对于她讲的这两个操作,本质就是要么在二进制末尾添加一个 $1$,要么就在后面添加两个 $0$。

那么得到转移 $f_i = f_{i-1} + f_{i-2}$,总方案数就是求和,那么就是求一个 $fib$ 部分和。

考虑多算了一些东西,就是有可能一个大数是可以由一个小数变化而来的,那么就不应该计算她,因为是重复的。考虑从小到大排完序后,每次暴力的去模拟往前找,如果找到了一个已经存在的,说明她是可以被前面的变化过来的,就把她删了好了。

最后数一数她有多少位,加起来就好了。时间复杂度 $O(n+p+n\log n)$,当然我知道,$fib$ 前缀和可以做 $\log p$,在此不赘述,毕竟 $1e5$ 没必要。

CF41D

$1900$

考虑设 $dp_{i,j,k}$ 为到 $(i,j)$ 时能否收集 $k$ 个豌豆。

那么就有转移方程:

$$
dp_{i,j,k} = dp_{i+1,j-1,k-a_{i,j}} \text{ or } dp_{i+1,j+1,k-a_{i,j}}
$$

初始化 $dp_{n+1,i,0} = 1$。

从大到小枚举倍数,找可以达成的位置,找到了从下到上输出方案即可。

CF1627D

$1900$

$\gcd(\gcd(a,b),c) = \gcd(a,b,c)$,所以我生成了一个 $\gcd$ 后,拿着她去跟别的生成的 $\gcd$ 就是她们本身全体的 $\gcd$,由此,问题被简化成了在这个序列里乱选一些数,能得到多少个不同的 $\gcd$。当然,肯定不会同一个数选择多次,因为这样不会有贡献。

那么考虑直接暴力计算那些数是可以被若干次 $\gcd$ 凑出来的。我们发现一个数的若干个倍数的 $\gcd$ 可能是她本身(当然也有可能是她的倍数),那我们就枚举她的已经存在的倍数,全 $\gcd$ 起来,判断是不是她本身且她不在原有集合里就可以记录答案,因为调和级数是 $\log$,所以时间复杂度 $O(n\log n)$。

CF295C

$2100$

考虑设 $dp_{i,j,k}$ 记录第 $i$ 轮划船岸上有 $j$ 个 $100$ 斤, $k$ 个 $50$ 斤 的方案数。

显然,若某一时刻 $dp_{i,0,0}$ 有值,那么就输出。

转移为:枚举一次运输了 $a$ 个 $100$ 斤,$b$ 个 $50$ 斤

对于去:

$$
dp_{i,j,k} = \sum calc(x,a,y,b)\times dp_{i-1,j-a,k-b}
$$

对于回:

$$
dp_{i+1,j,k} = \sum calc(x,a,y,b)\times dp_{i,j+a,k+b}
$$

我们有函数 $calc(x,a,y,b) = \dbinom{x}{a}\dbinom{y}{b}$

CF1650F

$2200$

考虑 $0-1$ 背包,考虑到数据范围,我们设时间为价值,百分比为容量,那么容量就从 $0\sim200$,对于每个任务做背包,然后看在规定时间内能否完成任务,即是否有 $100%$ 以上有值。按常规套路输出方案即可。

有状态转移:$dp_{i,j} = \min{dp_{i,j},dp_{i+1,j-p_i} + t_i}$

这个题细节比较多,尤其注意初始化时不要用 memset,否则会超时。

标签:gcd,CF,枚举,DP,考虑,题乱,转移,dp,log
From: https://www.cnblogs.com/yanxinyi-cpp/p/17808321.html

相关文章

  • 无法获得锁 /var/lib/dpkg/lock-frontend。锁正由进程 3701(unattended-upgr)持有 N: 请
    当用apt-get时遇到无法获得锁/var/lib/dpkg/lock-frontend。锁正由进程3701(unattended-upgr)持有N:请注意,直接移除锁文件不一定是合适的解决方案,且可能损坏您的系统。E:无法获取dpkg前端锁(/var/lib/dpkg/lock-frontend),是否有其他进程正占用它?问题时sudorm/var/cache/ap......
  • CF1866M Mighty Rock Tower 题解
    Problem-1866M-CodeforcesMightyRockTower-洛谷先考虑一个\(O(n^2)\)的dp设计状态:\(dp_i\)表示搭\(i\)层的期望转移:\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j=i}^{n-1}dp_j\timesP_{j+1}^{j-i+1}\times(1-P_{j+1})\),显然是有后效性的,但我们展开......
  • vcftools 快速安装日志
     下载https://vcftools.github.io/examples.htmltar-xvfvcfools.0.X.XX.tar.gzexportPERL5LIB=/path/to/your/vcftools-directory/src/perl/cdvcftools/先执行./autogen.sh报错autoreconf找不到,执行yuminstall autoreconf./configure 如果这一步执行报错,缺少c++......
  • linux服务器安装python curl_cffi
    """在windows或mac上,直接pip3installcurl_cffi就能使用,但是在linux中,可能会缺少证书以下是Linux中的安装步骤:"""#安装第三方库pip3installcurl_cffi​#下载证书wgethttps://curl.se/ca/cacert.pem​#将证书添加到site-packagesmvcacert.pem/usr/local/lib/python3.8/si......
  • 棱镜七彩兼容CCF版开源漏洞信息描述规范COSV Schema 1.0
    CCF版开源漏洞信息描述规范COSVSchema1.0(以下简称“COSVSchema1.0”)已于前期正式发布,棱镜七彩作为COSVSchema1.0制定工作的重要成员积极响应规范内容,目前公司产品与漏洞推送服务已经实现COSVSchema1.0兼容。开源软件在现代软件开发中占据着重要作用,因此开源软件中存在的开源......
  • CF练习题18
    这次的题都是什么怪物!!!ShortColorfulStrip因为\(n=m\),所以最终的形态一定是\(n\)的一个排列。根据题意,发掘几个性质:一个区间染色,一定最先对其中颜色最小的染色。染色要求覆盖的点颜色完全相同。对于第一次来说,先找到颜色为\(1\)的点,位置是\(p\)。染色的区间是\([......
  • CF1837E
    这是一道非常有意思的题。设\(n\)为当前队伍数量。下面对于每个队伍的“数值”不是编号,而是能力。(比如说这时编号为\(1\)的队伍能力为\(n\))。思路清晰的,我们发现在初始状态下,每两格一组,每组之间是互相独立的。然后我们当前已经确定了一些队伍的位置,只知道这些发现很难去计......
  • CF1861D
    废话:VP时T3思路不清晰,写了很久,然后这题没时间做了,赛后五分钟AC了(还好不是正赛,不然我会气死的)。所以做题前思路一定要清晰且严谨!思路:观察这个问题,发现如果\(l\)到\(r\)不是单调的,那么完全没必要一起乘。那么本题中的操作将会一整段一整段的进行,我们肯定会让段数尽可......
  • [MDP.NetCore] 開發一個從GitHub持續佈署到Azure Container Apps的Web站台
    開發一個從GitHub持續佈署到AzureContainerApps的Web站台程式碼簽入GitHub之後,啟動GitHubAction流程,編譯並部署程式到AzureContainerApps,是開發系統時常見的功能需求。本篇範例協助開發人員使用GitHub與Azure,逐步完成必要的設計和實作。操作步驟1.註冊並登入AzurePortal......
  • 解决远程连接(rdp)遇到的小问题
    远程连接Windows服务器时提示:“出现身份认证错误,要求的函数不受支持,CredSSP加密数据库修正”解决方法:以下代码保存为1.reg双击运行导入即可WindowsRegistryEditorVersion5.00[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP......