【cf261X】Codeforces Round #160 (Div. 1)

2015年6月25日1,6823
A. Maxim and Discounts
挑要求最小的优惠方案啦,最贵的那几个显然要花钱买,赠品当然也是选最贵的。。。恩变成了子问题

B. Maxim and Restaurant

f(i,j,k)表示前i个人,选了j个,消耗为k的方案数

然后枚举选的人数+组合数学,注意不重复统计答案

C. Maxim and Matrix

发现第m+1行的和就是2^(m二进制1的个数+1)

则t是2的幂次才有解,求<=n的ans数量

从大到小枚举每一位,如果n的这一位为1

1.这一位ans放0,则剩下的1在ans的低位任意放,排列组合

2.这一位ans放1,变成一个子问题

D. Maxim and Increasing Subsequence

t大于max(maxb,n)是没有意义的。。。

t取个min然后由于n*maxb有限制就变成了最长上升子序列裸题,可以用树状数组水

这题有比较特殊的地方

考虑1-n的ans数组每个位置最多增加t次,所以可以暴力QAQ

E. Maxim and Calculator

找出从l到r中x的数量,满足x的任意一个分解式\(\prod^t_{i=1}k_i\)中\(maxk+t<=p\)

显然x不能有一个质因子大于p,写个搜索发现1到10^9符合条件的只有300w

把这些数排序后放在a数组,做个100*300w的dp

f(i,j)表示使用<=i的因子,第j个数的最少因子个数,只要\(i+f(i,j)<=p\) a[j]就符合条件

\(f(i,j)=f(i-1,pos[a[j]/i])\);

对于每个i,\(pos[a[j]/i]\)是递增的,所以可以不hash。。。

 

  • sunzeyu2015年6月28日 下午5:30 回复

    实测D题暴力第11个点会炸

    #1  
  • sunzeyu2015年6月28日 下午5:42 回复

    还有D题真的是树状数组吗?树状数组一般会出现i&(-i)这样的东西啊
    感觉更像是前缀和^_^

    #2  
    • hzwer2015年6月29日 上午9:20 回复
      admin

      我写的并不是啊。。。

      #21