Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hhc0716","updateTime":1696741242000,"title":"20230922 OI Daily Record","dislikeCnt":0,"content":"# **20230922 疯狂刷题**\n\n## **Day:20230922**\n\n## **Total Problems:7**\n\n## **上午**\n\n共五道题。\n\n### **A**\n\nTOO MUCH WATER\n\n**综合:Class 0**\n\n**无思维**\n\n**无算法**\n\n**无数据结构**\n\n**无细节**\n\n三重循环不行吗?\n\n### **B**\n\n有一点点麻烦。\n\n**综合:Class 1**\n\n**少量思维**\n\n**无算法**\n\n**无数据结构**\n\n**少量细节**\n\n由于可以重排,只需要统计上下左右做的次数,在特判一直向左(右,上,下)再一直向右(左,下,上)的情况即可。\n\n### **C**\n\n一道获得了“最水 C 题奖”的题目,我甚至觉得这题比上一道题目(一道 B 题)还要简单。\n\n**综合:Class 0+**\n\n**无思维**\n\n**少量算法**\n\n**无数据结构**\n\n**无细节**\n\n双指针。\n\n一开始初始化右端点,如果遇到不合法的字符 break。\n\n### **D**\n\n开始麻烦了起来。\n\n**综合:Class 2+**\n\n**中量思维**\n\n**少量算法**\n\n**无数据结构**\n\n**少量细节**\n\n能够好好讲讲的一道多解题。\n\n#### **“神虎牌删犇法”**\n\n##### **名字取自某洛谷剪贴板上的“神虎牌删犇器”。**\n\n##### **个人原创,并证明正确性**\n\n假设我们有一个序列,并将这个序列分成了一个一个“极长上升子段”。\n\n这里,“极长上升子段”是指,加入左边的数或右边的数(假设都有)都会使这个子段变成非上升子段的上升子段。\n\n先将答案设为所有子段的长度的最大值;\n\n然后,对于每一个分出来的子段:\n\n如果子段长度是1,那么删掉这个子段的唯一一个元素可能会使得两边的极长上升子段合并成一个,此时更新答案。\n\n其他情况:\n\n删中间的数会使这个“极长上升子段”的长度减去1,但是两边不能合并还是不能合并;\n\n删左边的数虽然会使这个上升子段(注意用词)的长度减去1,但是可能会使得左边的上升子段和这个上升子段合并,此时更新答案;\n\n删右边的数同理。\n\n于是我们不用任何算法就 A 了这道题。\n\n#### **正常的 dp**\n\n很显然上一种方法的“先将答案设为所有子段的长度的最大值”这句话是无法避免了(因为不删也是一种方案)。\n\n考虑删了一个数会造成什么影响:\n\n这个数左边的数属于的上升子段可能会与这个数右边的数属于的上升子段合并,又或者是不合并。如果合并,更新答案即可。\n\n算法也能 A 了这道题。\n\n### **E**\n\n今日新闻:唐纳德·希尔的棺材板出现剧烈震动,随后供奉唐纳德·希尔的人迅速逃离。\n\n所幸并无人员有生命危险。\n\n**综合:Class 2**\n\n**少量思维**\n\n**中量算法**\n\n**无数据结构**\n\n**无细节**\n\n其实这个题就是让我们模拟一遍一轮希尔排序的过程。\n\n由于插入会 T 飞,所以用 sort。\n\n### **F**\n\n看看这题解区,乱成了啥样?\n\n**综合:Class 2**\n\n**中量思维**\n\n**少量算法**\n\n**无数据结构**\n\n**少量细节**\n\n首先暴力肯定会 T 飞对不对?\n\n然后题目的式子好像有点儿不可推。\n\n但是我要声明,这题确实可以推式子。\n\n$$\n首先定义 \\ f(x) \\ 为 \\ x \\ 的最大平方因数.\n$$\n\n$$\n那么就可以将 \\ i,j \\ 表示为 \\ i \u003d p \\times f(i), j \u003d q \\times f(j).\n$$\n\n$$\n那么 \\ i,j \\ 是完全平方数 \\iff p \\times f(i) \\times q \\times f(j) 是完全平方数。\n$$","threadId":168709,"likeCnt":0,"createTime":1695363209000,"isWorkbook":false,"viewCnt":158,"openness":2,"fav":false,"id":4090,"trustable":false}