acm基础题java输入输出



一、本周周赛总结

二、 4494. 吃饭

• 1. 题目描述
• 2. 思路分析
• 3. 代码实现

• 三、4495. 数组操作

• 1. 题目描述
• 2. 思路分析
• 3. 代码实现

• 四、4496. 吃水果

• 1. 题目描述
• 2. 思路分析
• 3. 代码实现

• 六、参考链接

acm基础题java输入输出

一、本周周赛总结

• 第一次打acwing，一共三题，难度跳跃挺大。
• acwing python竟然不支持from math import comb,震惊！还得自己实现。

二、 4494. 吃饭

链接: 4494. 吃饭

1. 题目描述

2. 思路分析

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

3. 代码实现

三、4495. 数组操作

链接: 4495. 数组操作

1. 题目描述

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. 代码实现

四、4496. 吃水果

链接: 4496. 吃水果

1. 题目描述

2. 思路分析

组合数学。

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

3. 代码实现

六、参考链接

• 无

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/19579.html