当前位置: 首页 > news >正文

2/12考试总结

时间安排

8:30–8:50 读题,T1 不知道是个啥,T2是个dp ,T3可能也是 dp 之类的。
8:50–9:30 T1,读了好几遍才理解了题意,对于部分分有爆搜。考虑正解,想到预处理后O(1) 查询,问题是如何由已知的信息得到所有可能询问的答案,想了几种 子集dp 之类的东西,都不太对。
9:30–10:20 T2,看了一眼发现有 70 分是送的。正解貌似可以前缀和优化一下什么的。仔细分析了一下发现不好维护,暴力前缀和预处理的话时间空间都不允许,尝试着化简式子看看能不能 O(1) 做,貌似做不了。
10:20–11:13 T3,分析题目可以找到一些性质,然后根据这个建图,部分分可以暴力在图上跑。考虑能不能推广,需要快速知道图上的信息,猜了好几个结论都是假的。
11:13–12:00 瞪T1,T3。
12:00–13:00 瞪T1 。

回顾反思

T1:
正解是 dfs 搜索,或者使用状压做类似过程,复杂度是 n2nn2^nn2n 的。
比赛时一开始读题理解题意耽误了一点时间。
题目中有 ∃∀\exist \forall∃∀ 两种逻辑运算,将 ∃\exist 当做限制,问题是如何预处理出一个限制是否被满足。考场上,我局限于先以某种方式钦定一个限制,然后考虑在限制下的所有可能状态的解,那么这样复杂度就是枚举限制的复杂度与枚举状态复杂度的积,是不能通过的。但是实际上,根本不需要事先钦定某个限制,可以直接将限制的钦定融进状态的枚举中,考虑直接一位一位枚举状态,对于某一位,讨论是采取限制 1 还是限制 2 ,然后得到在此限制下下一位的合法状态,递归进入下一位。这样,递归进入某一位是,之前的所有位的信息都能被有效利用,而非再次搜索产生冗余。
这道题,我在最开始题意的理解上出现了一些偏差,绕了一些弯子;其次,我局限于钦定限制然后找状态,但是实际上可以枚举状态然后讨论限制,边枚举边做;再者,我对 dfs 的复杂度没有信心,没有仔细去计算 dfs的实际复杂度。
要认真分析复杂度,一般的 dfs 会有很多不必要的冗余,若能够做到最大化利用每一段递归公共的部分减少重复冗余操作,其复杂度会极大的降低。
T2:
思路基本和正解相同,考虑组产生的分界,但是角度又略有不同。正解主要考虑是 A 组先满还是 B 组先满,而我则是考虑在给定的 K 的关键点内 B 组是否满了。这两种角度对于部分分计算的复杂度是一样的,但是我涉及的组合数整体的分布不如正解的 “亲近” ,比较难以优化计算;其次,正解的式子几乎只涉及了值域为 n 的 i 以及种数为 n\sqrt nn 的 K,那么枚举 K 对 i 暴力预处理就行了,而我还涉及到另一个值域为 n 的变量 xk ,于是预处理也很困难。于是进行不下去了。
还是要尝试多种角度的思考问题,不仅是这种思路能走多远的问题,更直接的,不同的角度会对式子产生不同的影响。
对于具体的计算方法,
对于每个询问涉及到某种分布或者某段的组合数的计算,直接计算或者预处理都不好做,可以考虑优化暴力,将询问对应的区间离线下来,对相应数值跑莫队,这样可以做到根号。
对于正解,其计算难点在于出现了以 k 为参数的式子,这个 k 值域是 1->n ,若对于每个 1-> n 都预处理是不现实的。但是注意题目条件 ∑k≤2∗n\sum k\leq 2*nk2n ,那么不同的 k 的种数最多只有 n\sqrt nn 级别,于是将 k 离线下来只对这根号个 k 预处理就可以了。
很多题目都涉及了对 ∑k≤lim\sum k\leq limklim 这个条件性质的利用,如该题中 k 种类数不超过根号、虚树等。

T3:
想到建图了,建了图,但是对于图的性质没有剖析完全,模型中出现了许多冗余边。具体的,正解的建图是若干条链,相邻的链连边,而我对于一条链与许多不相邻的链也连了边,但实际上这些边即使不加,也存在相应的等价的路径。于是我的图模型不像题解那样简洁,比较乱,也没有规律可循。
这种建模题,连边时要谨慎,考虑到这条边是否有加的必要,是否不需要这条边也能表现出相应的等价关系,精简模型,透露本质。
题目有充要性质:相同的 ai 对应的 pi 递减,且对于一个 pi 大于 i 之前最近的一个满足 aj=ai-1 的 pj 。由此建图,是若干条相连的链。
这个图比较简单,信息可以直接递推处理。

三道题都没有涉及什么比较复杂的算法和数据结构,T1是暴力题,T2是经典套路题,T3难度也不算很高,其实都在个人可控范围内,T1,T2都是应该 AC 的题目,理想分数应该在 250+ 以上。

http://www.lryc.cn/news/4419.html

相关文章:

  • 第三章虚拟机的克隆,快照,迁移删除
  • 华为OD机试 - 任务总执行时长(Python)| 真题含思路
  • LeetCode 热题 C++ 114. 二叉树展开为链表
  • Spring的事务控制-基于AOP的声明式事务控制
  • SSO(单点登陆)
  • 线程和QObjects
  • 最新中文版FL Studio21水果软件下载安装图文教程
  • pandas数据分析35——多个数据框实现笛卡尔积
  • 【C语言学习笔记】:数组倒序排列,数组倒置
  • sni+tomcat漏洞复现
  • Linux ALSA 之十:ALSA ASOC Machine Driver
  • Spring 面试题(一):Spring 如何处理全局异常?
  • Threadlocal为何引发内存泄漏问题
  • 如何写好 Python 的 Lambda 函数?
  • 大数据技术架构(组件)32——Spark:Spark SQL--Execute Engine
  • Leetcode.1138 字母板上的路径
  • 一个自动配置 opengrok 多项目的脚本
  • JAVA同步代码块 同步方法
  • 分享111个助理类简历模板,总有一款适合您
  • Allegro如何更改临时高亮的颜色设置操作指导
  • 知识图谱嵌入技术研究综述
  • Scratch少儿编程案例-水果忍者-超完整
  • 练 习
  • Urho3D整体结构
  • 大数据技术之Hudi
  • libxlsxwriter条件格式
  • nodejs+vue+elementui在线求助系统vscode
  • 电子技术——BJT差分输入对
  • [MySQL教程②] - MySQL介绍和发展史
  • 多表查询--实例