test 10.13
| 考试策略与过程 |
|---|
看T1。考虑枚举左端点，发现右端点单调递增，秒了。看T2。开始题意有很多地方不明确，浪费了20min。理解题以后，第一问秒了，第二问预处理往前，王后的最长子段 down[i] 和 up[i] 后，就是枚举 \(i\) ，求 \(\max\{down(j)\}\;(j<i-1,a(j)<a(i))\) ，条件则是二维偏序，第一个顺序枚举就可以做到，第二个用树状数组求 \(\max\) + 离散化就好。看T3。猜如果可以划分为两个 MST ，无论怎么划分都是合法的，对拍发现错了。考虑不合法的条件也不行。看T4。看到概率就傻了。写了30部分分，但是后面挂了。T1，T2 30min 写完，但是T2没有注意可以不删区间，挂了10分。写T3。看到 \(n,m\) 很小，想到状压。枚举第一颗生成树所用的 \(n-1\) 条边，这里可以钦定从小往大枚举剪枝，过程中可以用启发式可撤销并查集判断是否合法剪枝，再加个Kruskal就好了，70分。 |
| 经验教训 |
| 这次考试发挥较好，只挂了40分。数论方面及其不熟练，连扩欧都打不出来！以后有数论专题时再补。T3充分显现出了暴力的重要性，暴力不能丢！ |
| 能力分 | 实际分 | 失分原因 | 改进办法 | |
|---|---|---|---|---|
| T1 | 100 | 100 | 无。 | 套路：区间 \(\Rightarrow\) 前缀和，差分，单调性，双指针，二分。考虑暴力（枚举），优化某些量的计算过程。 |
| T2 | 100 | 90 | 题意不清。 | 套路：考虑将要求的东西转化，找出其中性质，也就是什么情况一定不会出现，一定不优。善用数据结构优化。 |
| T3 | 70 | 70 | 思维不够。 | 思路不够开阔，还是做题做少了。 |
| T4 | 30 | 0 | 知识点（数论）及其不熟练！ | 正解反正不可能想到，暴力就要补一补数论！ |