ABC321题解

news/发布时间2024/5/17 5:23:02

A

从低位到高位判断是否递增就行了。

B

直接暴力枚举。

C

深搜一下,答案最多 1023 个,然后要开 long long !!!

D

从小到大枚举 a 的同时从大到小枚举 b,然后前缀和优化一下就行了。

E

考虑把这棵树分成两部分,分界线为从 1 到 n 的路径。

然后在路径上从下往上dp出长为 \(k\) 的路径条数,对于其他的完全二叉树,路径条数要么是 \(2^k\) 要么是0。

然后从 \(x\) 开始一路向上走,答案累计 \(x\) 对面的另一颗子树(x xor 1)。注意要加上 \(x\) 这颗子树的答案。

大概就是令 \(f_{i,j}\) 为路径上端为 \(i\),长度为 \(j\) 的条数,然后

\(Ans=[deep > k] + f_{x,k} + \sum\limits_{i=0}^{deep}f_{(i\ \text{Rsh}\ i) \text{xor} 1,k-i-2}\)

F

对于 + 操作,普通的背包就行了。

对于 - 操作,注意到对于背包来说,物品的顺序是不重要的,那么把要删除的物品提到最前面来,然后反着做一次背包就行了。

G

状压dp。

\(f_i\) 表示 \(i\) 内的点构成了一个连通块的方案数。

容斥一下就出来了。

更新答案的时候就乘上可能的连边方案数累加进答案里就行了。

那么一种连边方式的贡献显然会被每个连通块分解并分别算入答案。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ulsteruni.cn/article/88868206.html

如若内容造成侵权/违法违规/事实不符,请联系编程大学网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

python字典批量删除多个键值对(连续)

搜不到字典批量删除多个键值对的方法,换了个搜索姿势,批量取N个元素,那么组合一下,就出来了!新建一个字典dict; 目标:去掉key为c,d,e的键值对。最常见的就是直接删除,但是这样有个弊端,要删除的个数多的话就尴尬了。 解决方法:(2:5→索引2,3,4) 当然,这种情…

在Visual Studio2019中使用C#语言连接Sql Server数据库

1、首先在visual studio里面创建好自己的表 服务资源管理器-->连接数据库:然后选择sql server数据库文件,并自定义数据库名称,显示不存在点击创建即可; 2、创建自己的程序对应的字段的表3、连接数据库操作 1、引入连接数据库需要使用的using关键字2、编写Connection代码…

umich cv-1

UMICH CV Image Classification---KNN 在本节课中,首先justin老师为我们介绍了图像分类了基础概念以及其用途,这里就不多涉及了 接着我们思考图像分类问题,如果我们想要直接通过某种算法来实现图像分类,显然是比较棘手的,于是引入了机器学习的思想,即用数据驱动,用数据去…

针对简历可能提到的问题

目录C/C++C和C++的区别关键字continue和break的用法return的含义goto的含义Volatile的用法const可以和volatile一起使用吗union和struct的区别union和struct的内存对齐问题为什么要内存对齐?union判断大小端大小端转换空的structstruct在C和C++的区别struct和class的区别enum的…