[acwing周赛复盘] 第 60 场周赛20220716

[acwing周赛复盘] 第 60 场周赛20220716

    • 一、本周周赛总结
    • 二、 4494. 吃饭
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 三、4495. 数组操作
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 四、4496. 吃水果
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 六、参考链接

一、本周周赛总结

  • 第一次打acwing,一共三题,难度跳跃挺大。
  • acwing python竟然不支持from math import comb,震惊!还得自己实现。
  • [acwing周赛复盘] 第 60 场周赛20220716_第1张图片
    [acwing周赛复盘] 第 60 场周赛20220716_第2张图片

二、 4494. 吃饭

链接: 4494. 吃饭

1. 题目描述

[acwing周赛复盘] 第 60 场周赛20220716_第3张图片

2. 思路分析

定级Easy。
签到题,明显只要m和k同时大于等于n即可。

3. 代码实现

import io
import os
import sys
from collections import deque

if os.getenv('LOCALTESTACWING'):
    sys.stdin = open('input.txt')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

if __name__ == '__main__':
    n, m, k = map(int, input().split())
    if n <= m and n <= k:
        print('Yes')
    else:
        print('No')

三、4495. 数组操作

链接: 4495. 数组操作

1. 题目描述

[acwing周赛复盘] 第 60 场周赛20220716_第4张图片

2. 思路分析

还挺难的,主要我差分没怎么学过,当场研究。

  • 由于要找最小数,我们可以把a排序,最左边的非0数就是每次的答案。
  • 但是每次又要对数组中所有非0数据减去一个数值,这种区间操作就想到了是否可以lazy,只记录最前边的值,然后联想到这就是差分的方法。
  • a排序后建立差分数组diff,diff[0]=a[0],其它位置都代表a[i]比前一位置大几。
  • 那么我们只需要diff中找到第一个非0元素x,由于x前边一定是0,因此a[i]=diff[i],也就是第一次操作的答案x。
  • 同时后边的数的都要减去x,让diff[i]=0即可。
  • 后续答案继续找第一个非0的数,如果找不到,返回0.

3. 代码实现

import io
import os
import sys
from collections import deque

if os.getenv('LOCALTESTACWING'):
    sys.stdin = open('input.txt')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    diff = [a[0]]
    for i in range(1, n):
        diff.append(a[i] - a[i - 1])
    j = 0
    for _ in range(k):
        while j<n and diff[j] == 0:
            j += 1
        if j >= n:
            print(0)
        else:
            print(diff[j])
            diff[j] = 0

四、4496. 吃水果

链接: 4496. 吃水果

1. 题目描述

[acwing周赛复盘] 第 60 场周赛20220716_第5张图片

2. 思路分析

组合数学。

  • 题意说忽略最左边的小朋友,但是他可以选m种水果,先把ans初始化成m。
  • 然后在除了排头的位置,选k个位置变水果种类,C(n-1,k)种选法。
  • 每次变水果,有m-1种方法,(m-1)^k。
  • 最烦的是acwing python3竟然不能引入math.comb,因此要自己写组合数公式

3. 代码实现

import io
import os
import sys
from collections import deque
from math import factorial

if os.getenv('LOCALTESTACWING'):
    sys.stdin = open('input.txt')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD = 998244353
if __name__ == '__main__':
    n, m, k = map(int, input().split())
    def comb(m,r):
        return factorial(m)//(factorial(r)*factorial(m-r))
    ans = m*comb(n-1,k)*((m-1)**k)

    print(ans % MOD)

六、参考链接

你可能感兴趣的