Virtual NOIP 2018 Day5 总结

## 上午 ### T1 购买板凳 $100$分：使用差分数组进行区间加法、单点查询。 ### T2 马拉松路径 $30$分：对每一个$C$点计算最短路即可。 $40$分：考虑$C=n$的情况，直接输出最短的边长即可。 $70$分：考虑树的情况，进行树上$\text{dp}$。 $100$分： 这道题要求的是图上多起点、多终点的最短路，考虑添加超级源点和超级汇点。 但是一个$C$点不能回到它自己，因此要避免出现$s\rightarrow c_1\rightarrow x \rightarrow c_1 \rightarrow e$这样的路径。解决办法有以下两种： 1. 考虑将所有$C$点分为$A$和$B$两组，源点只向$A$连边，只有$B$中的点才向汇点连边，求一次最短路，就能求出所有$A$中的$C$点到$B$中$C$点的最短路。 我们如何分组，才能计算完所有$C$点对之间的最短路呢？ 考虑二进制拆分。如果两个数不同，那么它们至少有一个二进制位不同。因此我们考虑枚举二进制位，将某一位为$0$的点分到$A$组，为$1$的点分到$B$组，这样就能枚举完所有的可能$C$点对了。 2. 在计算$s$到$e$的最短路时，保留最短路和次短路，即保证最短路的“来源”不同，最后选择来源正确的最短路值即可。 ### T3 起飞 $40$分：暴力$\text{dp}$。 $100$分：考虑使用数据结构优化。因为是在$a-k$到$a-1$的范围内选择状态进行转移，因此这道题是不是可以用单调队列解决呢？但是树高不同，怎么办呢？ 考虑到树高不同，因此我们可以试着使用单调栈套单调队列。 单调栈套单调队列的代码如下： ```cpp #include <cstdio> #include <cctype> #include <algorithm> #define MAXN 1000005 #define INF 1000005 using namespace std; typedef int io_t; io_t uread(void); //读入优化 int a[MAXN]; //树的高度 int h[MAXN]; //单调不减数组，记录每一个体力值对应的范围内最高的树高 int fst[MAXN]={0},nxt[MAXN],fore[MAXN],tl[MAXN]={0}; //记录每一个点单调队列的队头、下一个元素、上一个元素和队尾 int f[MAXN]; //跳到每一棵数上的最小体力值花费 bool cmp(const int lhs,const int rhs); //离散化 int min(int a,int b); int max(int a,int b); int main(void){ int n; n=uread(); for (int i=1;i<=n;i++){ a[i]=uread(),nxt[i]=i; //这里使用nxt数组是为了节省空间 } //离散化 sort(nxt+1,nxt+n+1,cmp); for (int i=1;i<=n;i++){ a[nxt[i]]=i;//离散化（逆映射） } int q; q=uread(); while (q--){ int k; int head=0,tail=0; //单调栈栈底、栈顶（超尾）指针 //实际上这个单调栈也会出现弹出栈底的现象（如果栈底的所有元素都过期了，就需要弹出栈底） k=uread(); for (int i=0;i<=n;i++) tl[i]=fst[i]=0,h[i]=INF; //初始化每个栈节点的队头和队尾 fst[0]=tl[0]=1; //将1加入单调栈 h[0]=a[1]; fore[1]=nxt[1]=0; f[1]=0; tail=1; for (int i=2;i<=n;i++){ int tf=INF; //tf计算当前元素的f值 //删除已经无效的元素(i-k-1) if (i-k-1>0){ int deletep=i-k-1; if (f[deletep]<tail && fst[f[deletep]]==deletep){ //这个节点还在数据结构中，需要删除 fst[f[deletep]]=nxt[deletep]; //队头由下一个继承 if (!fst[f[deletep]]){ //如果这个队已经空了 tl[f[deletep]]=0; //注意一定要把tail也清空 if (f[deletep]>head) //如果这个元素之前还有元素，即不是栈底 h[f[deletep]]=h[f[deletep]-1]; //为了不影响二分搜索，我们把这个位置的h值设为体力值稍小的一个位置的h值，这样这个位置不会被使用 else h[f[deletep]]=0,head++; //栈底被弹出，head++ } else { fore[fst[f[deletep]]]=0; //否则把这个栈位置的队头的fore信息维护好 h[f[deletep]]=a[fst[f[deletep]]]; //更新这个栈位置的h值 } } } //在h数组中二分，计算f[i] int lst=lower_bound(h+head,h+tail,a[i])-h; //找到比i高的、范围内的、消耗体力值最小的树 if (lst<tail) //lst==tail是找不到的标志 tf=min(tf,lst); tf=min(tf,head+1); //也可以考虑从当前体力值最小的树（比i矮）消耗1体力值跳到i上 f[i]=tf; //更新f[i] //将i插入到数据结构中 if (tf>=tail){ //要压入栈顶 tail=tf+1; //tail是超尾 h[tf]=a[i]; //压入 fst[tf]=tl[tf]=i; //更新fst和tl fore[i]=nxt[i]=0; //没有相邻的元素 } else { while (tl[tf] && a[tl[tf]]<a[i]) //单调队列基本操作 tl[tf]=fore[tl[tf]]; //弹掉比i早、又比i矮的树 if (tl[tf]){ //如果还剩有元素 nxt[tl[tf]]=i; fore[i]=tl[tf],nxt[i]=0; tl[tf]=i; } else { //不剩元素了，i作为队头 tl[tf]=fst[tf]=i; h[tf]=a[i]; fore[i]=nxt[i]=0; } } } printf("%d\n",f[n]); } return 0; } inline int min(int a,int b){ return a<b?a:b; } inline int max(int a,int b){ return a>b?a:b; } bool cmp(const int lhs,const int rhs){ if (a[lhs]==a[rhs]) //如果高度相同，按出现顺序正序排列 return lhs<rhs; else return a[lhs]<a[rhs]; } io_t uread(void){ char ch; io_t ans=0; ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)){ ans=ans*10+(ch-'0'); ch=getchar(); } return ans; } ``` 这个办法很麻烦，因为要手动维护每个栈节点的队列，而且必须用链表模拟队列。 有什么简单的方法吗？ 事实上，我们只需要维护一个单调队列，单调队列中记录范围内的体力值的最小值，每次都从队头元素转移即可。 为什么可以这样呢？ 如果用队头元素转移，设队头体力值为$x$那么转移出来的体力值为$x$或$x+1$。现在假设有另一个不在队头的状态，使得可以不消耗体力值转移，设这个状态的体力值为$y$，那么转移出来的体力值也为$y$。 然而，由于$y$不在队头，一定有$x<y$，由此知$y\ge x+1$，因此从队头转移不会变劣，证明完毕。 ## 下午 ### T1 鳕鱼 $100$分：解方程$x+y=n,x-y=k$，解得$x=\frac{n+k}{2},y=\frac{n-k}{2}$，因此当$n>k$且$n\equiv k\pmod{2}$时，这一群鳕鱼还可以被分成$\frac{n+k}{2}$和$\frac{n-k}{2}$两组，递归计算即可。 ### T2 一样远 $30$分：对于每一次询问，都分别以起点和终点为根计算每一个点的深度，最后计算深度相同的点的个数。 $40$分：对于$a=b$的情况，直接输出$n$即可。 $100$分：树上的题目要抓住$\text{LCA}$这个关键点来解。我们讨论这两个点与$\text{LCA}$的距离。 如果这两个点到$\text{LCA}$的距离相等，那么$\text{LCA}$及$\text{LCA}$以上的部分都是合法的。 如果这两个点到$\text{LCA}$的距离不相等，且这两个点之间的距离为偶数，那么以这两个点的路径的中点为根的子树中的点都满足要求。 如果这两个点间的距离为奇数，那么答案为$0$。 注意，如果树的形态是一条链，不能通过递归$\text{dfs}$，否则会导致$\text{Stack Overflow}$；必须手写栈。 $\text{dfs}$遍历树时，要递推计算点的深度和直接父亲；遍历后要递推计算$2^x$层祖先和以$i$为根的子树大小（可以按照深度从大到小的顺序计算）。 ### T3 配对方案 $30$分：$\text{O}(2^{2n})=\text{O}(4^n)$直接记忆化搜索即可。 $100$分：我们考虑队列的形态。最后一位一定是女生，否则那一位男生就没有办法匹配女生了。如此我们发现，每一位男生身后的女生数量一定至少比男生数量多$1$。 接着我们考虑一位男生可以和哪一位女生配对。如果他身后只有一位女生（这样他当然就是最后一位男生），那么他就只能和这一位女生配对；如果他身后有多位女生，那么他可以选择其中的一位女生配对，这样会产生不同的状态，即有后效性，不便$\text{dp}$，且由于$n$的范围很大，几乎不可能用撞鸭$\text{dp}$。 还记得[小奇挖矿](https://www.luogu.org/problemnew/show/P1412)吗？在那道题中，是否采矿和是否维修对接下来的状态有很大影响，于是我们采用逆向$\text{dp}$，从后往前计算。 这道题同样可以逆向$\text{dp}$。由于每位男生都只能选择和自己身后的女生配对，因此对于最后一位男生（序号为$i$），他身后的女生数目$f[i]$即为他能选择的方案数。 对于$i$前面的一位男生，设他身后的女生数量为$x$，那么他能选择的方案数是$x-1$（其中一位已经和男生$i$配对）。以此类推，如果某一位男生身后有$x$位女生和$y$位男生，那么他能够配对的选择数是$x-y$。 于是我们可以计算将上述$x-y$的值用$f[i]$数组递推计算，最后把所有男生的$f$值乘起来取模即得答案。