Codeforces Round #131 (Div. 2)

A. System of Equations

  • \(a\)的范围在\(\sqrt n\)内,所以暴力枚举即可。

B. Hometask

  • 需要被2、5整除,所以末位必然为0,如果0没有出现,则直接返回-1。
  • 在不考虑被3整除的情况下,为了凑出最大数,必然是从9到0的顺序填数。
  • 设位数和模3的值为\(sum\),如果\(sum=0\),显然当前数即答案,否则考虑去除一些数使得数被3整除。
  • 因为\(sum \ne 0\),所以\(sum=1\ or\ sum = 2\),显然去除的数不会超过2个。优先考虑去除一个数\(x\),需要满足\(x \% 3 = sum\),且越小越好;去除两个数时\((x, y)\),需要满足\((x+y)\%3=sum\),且两个值越小越好。

C. Game

  • 游戏顺序必然是\(\cdots \to 1 \to 2 \to 3 \to 1 \to \cdots\)
  • 那么只要枚举起点,取最小值即可。

D. Numbers

  • \(f(i,j)\)表示由前i个数凑成长度为j的方案数。
  • 每次转移时,当前数的个数需要大于等于\(a[i]\)。
  • 由于不能有前导0,所以填0时需要去掉首位这个位置。

E. Relay Race

  • \(dp(i,j,k)\)表示走了i步后,第一个人的横坐标为j,第二个人为k的最大值。
  • 转移时需要判断两个人是否在同一格子,即\(j==k\)。
上一篇:Codeforces Round #539 (Div. 2) 异或 + dp


下一篇:Codeforces Round #260 (Div. 1) A - Boredom DP