普转提Day2
T1
给定一个区间,求这个区间中只有一个数字与其他数组不相同的数的个数。
给出的区间范围较大,但是要求的数比较少。所以我的想法是这样的:因为这些数只有一个数字和每个数字都相同的数不同,所以考虑将所有数字都相同的数处理出来(不算0总共有126个)。那么每次枚举这些数,将其中的一个数字改掉,再去判断更改后的数字是否在区间内,是的话就累计一下答案,最后再单独处理*00000...的情况。但是我在预处理数的时候最后一组忘记处理出来了,而且在开头数字没有处理好,得分80.
范围<=1e16
T2
给出一个只包含大写字母的字符串,求ABC的出现次数相同的非空连续子串中的个数。
先求出字符A,B,C出现的前缀和,设为a,b,c。当a[i]-b[i]=a[j]-b[j]且b[i]-c[i]=b[j]-c[j]时,即是一种情况。枚举每个位置i,那么前面有多个j可能与i匹配,那么我们只需要将map的二元组(a[i]-b[i]和b[i]-c[j])存起来,并累计答案即可。注意要讲map的初值0,0赋值为1.然而我觉得只有ABC三种字符,得分20.
字符串长度<=1e6
T3
给出di个数字i,将这些数字和若干个0(0可以不用)组合后被11整除,这个数至少需要多少位。
有一个数学结论:一个数的奇数位之和-偶数位之和能被11整除,那么这个数就能被11整除。
由这个结论出发,考虑数位dp,设f[i][j][k]表示已经用了i个数,余数为j,奇数位上放了k个数的可行性。
f[i][j][k+1]|=f[i-1][(j+num[i])%11][k], f[i][j][k]|=f[i-1][(f-num[i]+11)%11][k].(num[i]要用到的第i个数,也就是将di拆开了)
最后输出时只要找到一个f[n][11][i],那么这个状态对答案的贡献有两种情况,一是奇数位的数与偶数位一样多,那么就是i<<1.如果奇数位多,则是(i<<1)-1.显然不存在偶数位多的情况(因为存在就不可能是最优值).
sigma d[i] <= 100
T4
有n个怪,每个怪有一个生命值hi,有m点能量,每次可以选举如下任意一次操作:1.使其中的一个hi--;2.消耗一点能量,使其中的hi-=2;3.消耗一点能量,是每一个hi--.每次操作完毕后剩下生命值比0打的所以怪物都会造成一点伤害,求受到的伤害最小值。
显然我们要将hi从小到大排序。有一个很明显的贪心策略是有能量一定先把能量用掉,当当前打的这个怪只剩一点生命值或怪的数量大于3时,肯定是用群攻来的更赚;否则就用重击(就是操作2),能力用完后就按照血量值从小到大把怪物一个一个安排就好了。时间复杂度O(NlogN).
n<=1e5,m<=100.
最新文章
- TCP的阻塞和重传机制
- IOS-JSON &; XML解析
- Relax NG 在Odoo中的应用
- Zookeeper3.4.6部署伪分布集群(Apache)
- codevs 4163 hzwer与逆序对
- iOS7 UIKit动力学-碰撞特性UICollisionBehavior 下
- C++拷贝构造函数专题
- php中函数和方法的区别
- Ext JS 6应用程序Build后出现“c is not a constructor return new c(a[0])”的处理
- MySQL 8 新特性之Invisible Indexes
- 网络通信socket连接数上限
- FileProvider 添加二级目录
- oracle排序后的第一条记录
- promise VS future
- Mac生成APP图标和启动图的脚本
- 【翻译】理解 LSTM 网络
- 公司内部搭建git服务器
- Codeforces Round #451 (Div. 2)
- include和application
- Oracle字符集的查看查询和Oracle字符集的设置修改(转)