普转提Day1
T1
给定一个长度为N的序列,去掉其中连续的一部分使得剩下的部分没有重复元素。
很显然可以发现去掉的一部分只有三种情况:开头、中间、最后。
那么我们只需要枚举Hash就可以了。复杂度O(N^2).
不过这题也可以用O(N)的做法,类似一个双指针的做法就可以了。
T2
给出两个数N,M,求小于等于N的自然数内,M的倍数的个位数字之和。
数学题,求出循环节进行计算即可。
T3
将N个物品放进最大承重量为S的背包内,每个物品有一个规定的放入时间和拿出时间,且有它的重量、价值和该物品的承重量。在同一个时刻放入多个物品时可以按任意次序放入,物品可以选择不放入。求最大的价值。
对于每个物品的放入时间和拿出时间,仔细思考会发现有一个性质:将拿出时间为第一关键字非严格单调递增排序,放入时间为第二关键字非严格单调递减排序后,对于一个物品i就不用再去考虑i之前放入的物品,即i之前放入的物品都是合法的。
有了这个性质之后,很显然就可以dp了。设f[i][j]表示枚举到第i个物品时在这个物品上面的承载量不超过j时的最大价值,然后我们通过这个物品进出的时间段内的阶段对这个状态进行转移。
不妨设目前已经放好了前i-1个物品,那么对于第i个物品,我们要考虑有三个问题,一是从哪些状态转移,二是这个物品的承重,三是如何转移。 因为根据上述的性质,我们不用考虑i之后的状态会对i产生影响,所以我们只需通过i之前的状态转移而来。那么承重超了怎么办,我们设的状态就是第i个物品以上承重量不超过j的最大价值,而且一个个物品都是一个类栈的形式,当前枚举到的i一定是最外面的一层,而在i外面的物品还在后面的状态(可以由排序时的性质可得),通过这个思路我们也可以用递归来写,不过常数偏高。在转移的时候我们只枚举第i个物品进出的时间,用一个数组记录从这个i放入的时间起到当前枚举到的时间时的最大价值,那么当前状态就可以由这个价值加上从该时间起到拿出时间的状态(因为是栈的形式,所以这个物品时间内部的物品的状态一定已经被计算)。时间复杂度(N^2*S).
T4
给出n个数和m组数,每组数中又有ki个数。求将所有数or起来后为1的方案数,对1e9+7取模。比如说有三个数,有三组数分别为1,3、2,3、1,2.那么1,2和1,3与了之后1,2,3就都有了,是一种方案。同,2,3&1,2和1,3&2,3和1,2&1,3&2,3都是其中的一种方案,所以共有4中方案。
假设每一组数中都包含了每一个数,那么总方案就是2^m。但是其中存在有一个数没包含的情况,两个数没包含的情况,三个数没包含的情况……所以设cnt[i]表示i的方案数,根据容斥原理,答案应该是2^cnt(s)-2^cnt(s-1)+2^cnt(s-2)-...即simga(2^cnt(s)*(-1^(n-|s|)),其中s表示枚举的子集。那么cnt数组可以表示成一个高维前缀和,也就是说cnt[i]表示i所以子集的cnt之和。
for (int i = 1; i <= m; ++ i)
for (int j = 0; j < 1 << m; ++ j)
if (j & (1 << i - 1))
cnt[j] += cnt[j - (1 << i - 1)], cnt[j] %= Mod;
之后我们就可以用cnt对i进行转移了。复杂度为O(M*2^M).
最新文章
- 基于jquery的bootstrap在线文本编辑器插件Summernote
- CSS基础-插曲
- plsqldevloper + orcal环境搭建
- South - 在 Django 中 Migrate Database
- Eleven scrum meeting 2015/11/5
- Android 工程在4.0基础上混淆
- poj 3264 Balanced Lineup (RMQ算法 模板题)
- Mysql在php5中的应用
- 后缀.aspx.cs是什么软件的生成的
- 《个人-GIT使用方法》
- python selenium+phantomjs alert()弹窗报错
- win快捷键
- spring boot + easypoi两行代码excel导入导出
- 关于kubernetes使用私有仓库一点说明
- SAP MM 物料主数据采购视图中的字段&#39;Var. OUn&#39;的作用?
- AAndroid Studio的\drawable还是mipmap
- 常用.net反编译替换正则表达式
- JAVA反射机制_获取字节码文件对象
- 2_C语言中的数据类型 (七)类型限定
- Ubuntu12.04 64bit 下安装VNC server