十一月月赛题解

Kruskal 2020-11-02 14:21:24

1001. 国庆假期

(签到题) 输出37

1002. 较大值

(签到题) 输出max(a,b)

1003. NBA

(数学题)胜场数和负场数分别为k,n-k, 答案为k/(n-k+1)向上取整。 当然也可以用二分的方法

1004. 比例数组

(动态规划) 当a[i] 为偶数时,才能作为比例的中间数,对应的方案数为左边a[i]/2次数乘以右边3a[i]/2的次数。 做法:前后扫描数组 并统计每个数字出现次数,直接用map比较方便, 由于所有数据在[-100000,100000]内,可以加固定值只统计非负数的次数。注意结果要用long long。

1005. 禁着点

(深度优先搜索) 对每个空点进行判断,如果改成黑棋,黑棋会死且不能吃掉任何一块白棋,那么就是禁着点。

  1. 黑气会死可以通过在dfs中能否找到气判断。
  2. 如果能吃一块白棋,那么这块白棋一定在这个空点旁边。判断这块白棋有没有气就好。

1006. 裁剪数字

(找规律+动态规划) 假设n对应答案为ans,且n的位数为k。

  • 那么对于 10n+x,如果删除的数字不包括最后一位的x, 这部分总和为 10ans+xk(k+1)/2
  • 如果删除包括最后一位,假设这部分总和为add,sum为n的各位数字和。可以推出来add*10加上sum就是下一个add,需要额外维护前缀和sum。
  • n=123 ,x=4时 add1=123+12+1+0
  • n=1234 ,x=5 时 add2=1234+123+12+1+0 = 10*add1+4+3+2+1
  • n=12345 ,x =6 时 add3=12345+1234+123+12+1+0 = 10*add2+5+4+3+2+1

共 2 条回复

Leiyuxuan
[已删除]
Jack_Kasluo

[已删除] (doge)

AMAZE UI
Hello world!