Virtual NOIP II Day 9 总结

## 模板级题目测试 ### T1 单峰排列 看一下数据范围，$n\le 2\times 10^9$，显然是$\text{O}(1)$或者$\text{O}(\log n)$好题嘛！ 仔细观察单峰排列的定义式，我们发现，其中有一个元素非常特殊：最大的元素一定在排列的“中间”，即它把排列分割成了单调增和单调减的两份。其余元素只要选定了是在这个元素的左边和右边，位置也就确定下来了；即最大元素左边的元素和右边的元素分别构成两个集合，这两个集合里面的元素的顺序已经确定。 因此，这题其实就是问，这两个集合有多少种选取方式。由于$[1,n-1]$中的每一个整数都可以选择是在左边还是在右边，因此选择方式有$2^{n-1}$种。 答案就是$2^{n-1} \mod{1234567}$。使用$\text{Kasumi}$计算即可。 ### T2 连接格点 一道最小生成树的简单题目。我们把给定的边连接起来，再建图跑一遍最小生成树即可。 建图有优化技巧。如果两个点已经相连，就无需加入这条边，这样可以减少排序的时间。另外，如果在建图前整个图就已经连通，就无需建图。 ### T3 [无序字母对](https://www.luogu.org/problemnew/show/P1341) 丢人，居然忘了欧拉路怎么写了。 请注意并不是对于所有的起点都有欧拉路，如果图中有两个奇点，欧拉路就只能以奇点为起点。另外，到达一个点后，也不是任意选一个相连的点走过去就一定能构成欧拉路，因此需要一定的回溯。 以字母为顶点，字母对为无向边。建图时统计每个点的度数，从字典序最小的奇点（如果有$2$个奇点）或偶点（如果没有奇点）开始$\text{dfs}$，将顶点存入栈中，经过一条边就把这条边删去；如果当前经过的边数达到$n-1$，就把栈中的顶点按照入栈顺序输出。 ## 模板题目测试 ### 线段树 写线段树的时候卡了半天……如果在考场上这样会不会死掉啊…… 注意两点： 1. $l$和$r$不要手抖写错！ 2. 请注意`query`和`add`函数中，在递归调用`LC(root)`和`RC(root)`时，不要盲目更改范围。 这种写法是正确的： ```cpp void add(int root,int nl,int nr,ll v){ if (nl<=L(root) && nr>=R(root)){ SUM(root)+=(R(root)-L(root)+1)*v; ADD(root)+=v; return; } //这里使用逗号表达式是因为三元运算符两边的类型必须匹配 //但是我没法写出一个类型为void的常量 ADD(root)?(push_down(root),0):(0); if (nl<=MID(root)) add(LC(root),nl,nr,v); if (nr>MID(root)) add(RC(root),nl,nr,v); SUM(root)=SUM(LC(root))+SUM(RC(root)); } ``` 而这种写法是错误的： ```cpp void add(int root,int nl,int nr,ll v){ if (nl<=L(root) && nr>=R(root)){ SUM(root)+=(L(root)-R(root)+1)*v; //上面的L和R写反了 ADD(root)+=v; return; } ADD(root)?(push_down(root),0):(0); if (nl<=MID(root)) add(LC(root),nl,MID(root),v); if (nr>MID(root)) add(RC(root),MID(root)+1,nr,v); //上面两个递归调用可能扩大区间加的范围 //试仔细体会区别 SUM(root)=SUM(LC(root))+SUM(RC(root)); } ```