Virtual NOIP II Day 6 总结

### T1 图形变换 简单模拟题，直接暴力进行每次变换即可。 有没有更好的方法呢？ 注意到，表格的尺寸只有$(n,m)$和$(m,n)$两种状态，对于每一种状态，行和列都分别只有翻转和未翻转两种状态。因此，整个图像的不同状态只有$8$种，这$8$种状态构成一个置换群。因此，我们可以把整个输入字符串进行处理，计算出最终状态是这$8$种状态中的哪一种，再输出即可。 ### T2 分班 此题题意十分不清晰，干扰做题！ 请注意，第一个班一定要在第一个教室，类似地，第$i$个班一定要在第$i$个教室。 $20$分：直接爆搜枚举分割点即可。 $30$分：我们考虑$\text{dp}$。 设$f[i][j]$为第$i$个班恰在第$j$个学生处结束的所有分班方案的最小评价值。 为什么不把状态设计成“$f[i][j][k]$表示当前考虑到第$i$个学生，他在第$j$个班，这个班有$k$个学生”呢？因为在状态转移时可能没有发生“分班”这一关键决策，会导致状态严重冗余。因此状态的设计一定要考虑到“什么时候发生决策”，尽量避免出现“不发生决策”的垃圾状态。这里可以参考[绝美的挣扎 搜索部分](https://www.luogu.org/blog/Taki/solution-struggle)，即为什么是写`dfs(x+k[x]+1);`而不是`dfs(x+1)`。 接下来，我们能够写出状态转移方程：$f[i][j]=\min(f[i-1][j-k]+(\text{sval}[j]-\text{sval}[j-k])\times g[i]),a\le k\le b$，其中$\text{sval}[i]$表示$(\mu-x_i)^2$的前缀和。 直接按照状态转移方程计算，就是$\text{O}(nm^2)$的，可以得到$30$分。 $100$分：上面的方法在计算$\min$时有比较大的时间浪费，我们考虑优化$\text{dp}$。 $k$是有转移范围的，我们想到单调队列优化$\text{dp}$。我们按$i$建立$n$个单调队列，分别维护$[j-b,j-a]$区间内的最小转移值（即$f[i-1][j-k]+(\text{sval}[j]-\text{sval}[j-k])\times g[i]$），即可加速计算。 这题的数据很大，答案最大可能达到$10^{17}$，因此要开$\text{long long}$。考试时我的代码由于$\text{INF}$只调到了$10^{14}$，因此$\text{WA}$了所有的大数据；并且在调试时我没有发现这个问题，浪费了数小时。因此，在考试时，$\text{INF}$的取值一定要认真计算和斟酌，在不爆炸的前提下尽量开大一些。 ### T3 关于女朋友~~，不存在的~~ ~~好虐狗的题目！~~ 在考试时，我因为在$\text{T2}$的题意理解上花费了过多的时间，所以没能仔细思考这题的做法，其实这道题还是可做的。 $40$分：首先计算出所有点到$n$的最短路。读入$x$时，计算出所有点到$x$的最短路，再从$1$开始沿着最短路走，枚举分手点（我很恶毒呢）即可。由于不停地计算最短路，此算法效率很低。 $100$分：上述算法耗时最多的恐怕是不停计算最短路这一步。我们能否只求一次最短路呢？~~当然可以啊，用Floyd就行~~ 由于到$x$的最短路唯一，我们考虑建立以$1$为根的**最短路树**，即以$1\rightarrow y$中$y$的前驱作为树上$y$的父亲。这样我们只要沿着树边，从$x$往上走就能枚举所有的分手点了。 可是最短路树不一定是平衡的，它有可能退化成链，因此这样做的复杂度仍是$\text{O}(nq)$的。 如何保证稳定的$\text{O}(q \log n)$复杂度呢？回顾我们的问题，我们想要求的的是$x$点往上一段中**到$n$距离的最小值**，也即树上一段中的最小值。 在树上求值，我们考虑用树上倍增（就是$\text{LCA}$用的那玩意儿）。我们除了记录$2^k$层父亲之外，还要记录$x$的$[1,2^k]$层父亲中到$n$距离的最小值。这样我们在往上倍增的时候就能求出走过这一段到$n$的最小值了。 这里注意程序实现上的一个细节。下面的做法是十分危险的： ```cpp #define MAXLG 19 #define MAXN 100005 int mind[MAXLG][MAXN]; for (int l=MAXLG;l>=0;l--) //Do something ``` 这样写下表严重越界，轻则$\text{RE}$，严重的会输出随机值，十分难以调试。因此今后在写倍增的题目时，循环上界应另定义一个变量，如： ```cpp #define MAXLG 19 #define MAXJUMP 15 #define MAXN 100005 int mind[MAXLG][MAXN]; for (int l=MAXJUMP;l>=0;l--) //Do something ``` 如果直接使用`MAXLG`，当然就`gg`啦~ 本次考试中和考试后，我在程序调试上出了很大问题，浪费了许多时间。因此今后要努力提高代码调试水平，提高调试速度！