Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hhc0716","updateTime":1695358107000,"title":"20230921 OI Daily Record","dislikeCnt":0,"content":"# **20230921 疯狂刷题**\n\n### **Day:20230921**\n\n### **Total Problems:16**\n\n## **上午**\n\n共五道题。\n\n### **A**\n\nTOO MUCH WATER.\n\n**综合:Class 1**\n\n**少量思维**\n\n**无算法**\n\n**无数据结构**\n\n**无细节**\n\n先考虑无限硬币的情况。\n\n显然,需要 $\\lfloor \\frac{S}{N} \\rfloor$ 个 $N$ 元硬币加上 $S \\bmod N$ 个 $1$ 元硬币。\n\n所以说,只要出现这种情况并且硬币都足够,就是 ```YES```。\n\n但是有时候 $N$ 元硬币不够(设有 $R$ 个),那么剩下的 $\\lfloor \\frac{S}{N} \\rfloor - R$ 个缺失的 $N$ 元硬币需要拆成 $1$ 元硬币。\n\n所以,如果拆完硬币后 $1$ 元硬币不够,就输出 ```NO```;否则就是 ```YES```。\n\n$O(1) + O(1)$。\n\n### **B**\n\n有点麻烦。\n\n**综合:Class 1+**\n\n**少量思维**\n\n**少量算法**\n\n**无数据结构**\n\n**微量细节**\n\n多解题目,但是两种解法都是简单贪心。\n\n#### **单冲法**\n\n每次找到一个最小的数,然后尽可能把这个数往前移。\n\n不加优化 $O(n^2)+O(N)$,加了链接数组优化是 $O(N)+O(N)$。\n\n#### **双冲法**\n\n##### **这里要感谢 [周盛椿](https://vjudge.csgrandeur.cn/user/of_course) 提出这个方法,[王老师](https://vjudge.csgrandeur.cn/user/beyoursven) 证明正确性。**\n\n这种方法放分两轮:\n\n**冒泡阶段**\n\n从后往前扫一遍整个数组,并将交换过后会更优的元素交换。\n\n相当于将数组分成一个一个以该段最小值结尾的段。\n\n**补全阶段**\n\n按任意顺序扫描一遍数组,将能交换并且交换过后会更优的元素交换。\n\n这一阶段稳定了这个方法的正确性。\n\n$O(N)+O(N)$。\n\n### **C**\n\n开始麻烦了起来。\n\n**综合:Class 2+**\n\n**中量思维**\n\n**少量算法**\n\n**无数据结构**\n\n**中量细节**\n\n两种方法,这里只讲一种。\n\n首先贪心铺完平台,然后余数分配。\n\n$O(M)+O(N)$。\n\n### **D**\n\nTOO MUCH WATER.\n\n**综合:Class 0+**\n\n**微量思维**\n\n**无算法**\n\n**无数据结构**\n\n**微量细节**\n\n将字符串按照字符分段(相同的一段),有段长为奇数的字符就一定不会坏。\n\n$O(|S|) + O(1)$。\n\n### **E**\n\nWATER。\n\n**综合:Class 1**\n\n**微量思维**\n\n**无算法**\n\n**无数据结构**\n\n**微量细节**\n\n“任意交换一对字符”意味着我们可以打散所有的1,重新分配。\n\n分类讨论:\n\n当没有长度为奇数的串时,如果有奇数个1答案就是 $N-1$,否则答案就是 $N$;\n\n当有长度为奇数的串时,答案一定是 $N$。\n\n于是我们就统计1的个数和长度为奇数的串的个数就行了。","threadId":168671,"likeCnt":0,"createTime":1695285575000,"isWorkbook":false,"viewCnt":138,"openness":2,"fav":false,"id":4087,"trustable":false}