BestCoder Round #84

2016年7月24日1,3822

1001 Aaronson

对n做二进制拆分,注意m对30取min


1002 Bellovin

直接输出F,显然是字典序最小的方案


1003 Colmerauer

用单调栈预处理下每个点向左/右第一个小等于它的元素,向上/下第一个大等于它的元素(一开始我用set预处理结果TLE)。

然后计算每个元素对答案的贡献,若设四个方向第一个使得其不能成为鞍点的数与其的距离分别为L,R,U,D

则其对答案的贡献为L*R*U*D*(L+R+1)*(U+D+1)/4


1004 Dertouzos

注意到满足题设条件的数一定是d的倍数kd,且k不大于d的最小因子,k*d小于n,且k是素数,预处理素数表后在其中二分即可

 

  • 就是张威2016年7月24日 下午3:19 回复

    黄学长 03的贡献为什么是L*R*U*D*(L+R+1)*(U+D+1)/4

    #1  
    • hzwer2016年7月27日 下午7:27 回复
      admin

      其实就是求包含一个点的子矩形面积和对吧
      可以行列分开,算完乘起来
      对于左侧的L个格子,右端点可以是R个格子中的一个
      那么右侧的贡献就是(1+2+…+R)*L = (R+1)*L/2
      左侧类似,算一下加起来就行咯

      #11