本文从WordPress迁移而来, 查看全部WordPress迁移文章
A.题意:每个物品有一个价值w[i],如果用机器人左臂去拿最左边的物品,每个物品还要wl,如果用机器人右臂去拿则wr,如果用左臂连续拿了几个物品,那么从第2个物品开始每个物品要附加一个权值ql;如果连续 用右臂拿物品从第2个物品开始每个物品附加一个权qr;取完所有物品花费最小
一开始想到DP,后来想清楚了,主要是用左臂拿还是右臂拿的问题,无论怎么拿,假设最后拿走的物品是第m个物品,那么可知 ,1到m-1号物品一定都是左臂拿的,因为拿东西只能从端点拿,m号是最后拿走的,那么之前它一直存在,1到m-1号的物品是不可能通过右臂拿到的,同理,m+1到n号的物品一定是通过右臂拿到的,至于m号物品,最后只剩下它,可以左臂或者右臂拿,枚举一次即可。另外1到m-1号是左臂拿的,m+1号到n号是右臂拿的,具体怎么拿,那肯定是错开开,左边拿一个,右边拿一个,这样才能最大限度地避免因为连续拿物品而产生的附加花费,但即便是错开拿,有些情况下还是要连续拿物品的(因为左边和右边的物品数不一定相同) 做法就是枚举最后拿的物品m,m把线段分成左右两部分,左边一定是左臂拿,右边一定右臂拿,另外枚举m是哪个臂拿,再计算连续拿东西产生的花费
1 |
|
1 | INF = 2000000000 |
C.题意:给出一个序列,给一个值k,序列的每个元素都可以减少k以内的数字,通过适当地调整,使得整个序列的gcd最大,输出最大点的gcd
每个数字能减少k以内的数字,转而想表达的意思是,假设有一个数字G,序列中每个元素都满足 ai % G <= k,那么这个G就是一个可行的gcd,因为每个ai都可以通过减少数值使得自己可以被G整除
找出序列中的最小值mina
若 mina <= k+1 , 那么D答案就是mina,因为G = mina <= k+1 , ai % G < G <= k+1,即 ai % G <= k
若 mina > k+1 , 一个显然的事实是,G <= mina,那么就暴力枚举答案,从 mina—>k+2 枚举答案,不过不能暴力检验(ai%G<=k),要利用性质
假设G是 一个可行的gcd,那么对于 所有ai都满足 ai % G <= k,换言之,ai一定落在数轴的 [G,G+k] , [2G,2G+k] , [3G,3G+k] …… [mG,mG+k]里面,那么我们只要统计一下这些区间里面一共有多少个ai,如果数目是n个,表示全部命中,G是可行解
上面一个小细节是m最多是多少,m = maxa / G
所以我们先统计区间[G,G+k],利用二分,看看序列中多少数字在里面
接着统计区间[2G,2G+k],二分
……..
[mG,mG+k],二分
代码中人肉写了两个二分查找,不过学会了两个STL,lower_bound,upper_bound,能达到两个二分查找的效果
1 |
|