网站建设与网络营销,珠海室内设计学校,广州怎么建设一个网站,辽宁智能网站建设推荐时间安排
8:30–8:50 读题#xff0c;T1 不知道是个啥,T2是个dp #xff0c;T3可能也是 dp 之类的。 8:50–9:30 T1#xff0c;读了好几遍才理解了题意#xff0c;对于部分分有爆搜。考虑正解#xff0c;想到预处理后O(1) 查询#xff0c;问题是如何由已知的信息得到所有…时间安排
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*n∑k≤2∗n 那么不同的 k 的种数最多只有 n\sqrt nn 级别于是将 k 离线下来只对这根号个 k 预处理就可以了。 很多题目都涉及了对 ∑k≤lim\sum k\leq lim∑k≤lim 这个条件性质的利用如该题中 k 种类数不超过根号、虚树等。
T3: 想到建图了建了图但是对于图的性质没有剖析完全模型中出现了许多冗余边。具体的正解的建图是若干条链相邻的链连边而我对于一条链与许多不相邻的链也连了边但实际上这些边即使不加也存在相应的等价的路径。于是我的图模型不像题解那样简洁比较乱也没有规律可循。 这种建模题连边时要谨慎考虑到这条边是否有加的必要是否不需要这条边也能表现出相应的等价关系精简模型透露本质。 题目有充要性质相同的 ai 对应的 pi 递减且对于一个 pi 大于 i 之前最近的一个满足 ajai-1 的 pj 。由此建图是若干条相连的链。 这个图比较简单信息可以直接递推处理。
三道题都没有涉及什么比较复杂的算法和数据结构T1是暴力题T2是经典套路题T3难度也不算很高其实都在个人可控范围内T1,T2都是应该 AC 的题目理想分数应该在 250 以上。
