小学学校网站建设方案,ui设计难吗,百度网址大全免费下载,wordpress摘要过滤时间安排
7:40–7:50 读题#xff0c;T1 貌似是签到#xff0c;T2,T4 DP,T3看起来很不可做。 7:50–8:00 T1,差分一下然后模拟就行了。 8:00–10:20 T2,注意到值域很小#xff0c;可以考虑状压#xff0c;想到一个状压状态数较少的 dp #xff0c;然后挂得彻底。发现有一…时间安排
7:40–7:50 读题T1 貌似是签到T2,T4 DP,T3看起来很不可做。 7:50–8:00 T1,差分一下然后模拟就行了。 8:00–10:20 T2,注意到值域很小可以考虑状压想到一个状压状态数较少的 dp 然后挂得彻底。发现有一些情况没考虑到那就不得不增加状态维度可这样的话状态数就非常大。想了好久没有想到什么更小的表示于是就硬着头皮写了。可以拿到 70 分左右。 10:20–12:00 T4,考虑怎么 dp 为了不重那么就要尽可能少的操作问题在于对于一个状态我压根不知道最少的操作是什么。分讨一下发现情况非常复杂不知道怎么 dp 。写了个dfs 暴力。
回顾反思
T2: 基本思路和正解差不多不过赛时做法复杂度较劣主要有两点。 一是 dp 转移设计上题目要求划分为若干个子段于是我每次都要枚举最后一段的左端点。但实际上一段的信息非常好维护于是可以考虑直接在 dp 状态里加入当前未结束的段的信息对于一个新元素考虑是另起一段还是加入当前段就行了。 二是状压状态数上直接暴力枚举状压的状态复杂度很大但是显然很不满通过 bfs 处理出有用的状态发现只有 100 多个非常少于是复杂度就对了。 对于这种一段的信息非常简单的可以考虑在 dp 时直接维护当前未结束段的信息。 状压的状态数很大时一定要想想是不是每个状态都真的有用去 bfs/dfs 一下会发现有用的状态往往很少。 T3: 貌似很高深。 T4: 比赛的时候压根不知道从何下手设计 dp 。是否必要操作操作的先后没法确定等一系列问题。 由于本题操作的一些优秀性质发现对于一个结束态有些区间如果要操作必然是最后几次操作将其去掉后剩下的也能如此划分。于是划分出若干个块每个块若要操作与相邻的块有一定依赖关系于是就有了操作的先后关系枚举相邻的几个块是否操作了根据分讨依赖关系就可以得到当前块操作是否是必要的。 已知操作后的最终序列考虑将操作序列映射到原序列。比如本题可以先把对应操作区间划分出来讨论区间之间的依赖关系。
