Virtual NOIP II Day 5 总结

## 联考 ### T1 信息学奥赛 ~~信息学奥赛主要算法：模拟。 ——题解~~ 简单的暴力字符串题，直接读入暴力匹配（不区分大小写）即可。但是读入极坑！而且数据中还有Windows风格换行符`'\r'`，可能会干扰。 注意名字不能转换为小写，还有就是数组**开大了不多收钱**。 ### T2 拥堵的道路 一道不算是很难的图论题。 $30$分：数据范围非常诡异，通常的数据范围都是给的$\le$，但是这里为什么是$b[i]-a[i]\ge 500000$呢？原来，可以证明，在不考虑限制的情况下，从$s$到$t$的最短路长度$<500000$，因此输出$1$即可。 $100$分：题目求的是速度的最小值，而且答案满足单调性，于是考虑二分。 对于一个给定的速度$v$，如果$s$到某个点的最短路长$l$满足$t>\frac{l}{v}$，那么这个点就可以到达，我们就可以对这个点的邻点做松弛操作。根据这个性质，我们就可以用$\text{Dijkstra}$求出在$v$下到达每个点的最短时间，进行判断。 当然，为了避免浮点误差，我们也可以化除为乘，改为判断$l<vt$。 但是要注意一个问题：设二分范围为$(l,r]$，那么$r$的初始值一定要设为$\text{dis}(t)+1$（$\text{dis}(t)$表示不考虑限制的距离）。为什么呢？考虑$b[t]-a[t]=1$的情形，此时所需时间必须小于$1\text{s}$，因此速度必须大于最短路长。比赛时我因为没有考虑到这个问题被卡掉了$20$分，因此今后在不影响整体复杂度、数组不越界的前提下可以稍稍加大二分范围。 最后，这道题是不可能输出$-1$的，用$-1$骗分的同学要注意了。就像$\text{fstqwq}$神犇说的，题目可以不认真看，但起码要认真看数据范围嘛！ ### T3 花朵涂色 看来今后看题要更留心了，看错题目是会死掉的，比$\text{SPFA}$死得都要惨呢。 比赛时我看错了这题的题目，以为是每一朵花必须且仅能给其中一个花瓣涂色。然而，这题每个花瓣都是可以涂色或不涂色的。 $30$分：考虑$a[i]=b[i]=1$的情况，这时每一朵非根节点的花的花瓣的贡献都为$1$，于是答案为$4(n-1)$。不会爆$\text{long long}$。 尽管我在考试时看错了题目，但是由于写了数据分治，我还是得了$30$分。因此，按数据分治是不可缺少的，尤其在对自己的做法正确性不是特别确定的情况下。 $100$分：注意到每一种花瓣的涂色方案是独立的，因此我们对每一个花瓣求期望，再利用期望的线性性质相加即可。 容易发现答案即为所有非根节点的花瓣的贡献之和。我们把答案统计移到子节点（题目中是父节点）上，那么答案就是根据子节点和父节点花瓣颜色的关系计算的。 由于每个点都是平等的，因此不管父亲是谁，花瓣颜色相同或不相同的概率都是$\frac{1}{2}$，于是这个节点的第$i$个花瓣对答案的贡献就是$\frac{1}{2}(a_i+b_i)$。因为所有非根节点的花瓣都有贡献，所以第$i$个花瓣的总期望就是$\frac{1}{2}(n-1)(a_i+b_i)$。上式对$i$求和即得到最终答案。 不知道为什么题解写得那么复杂，难道重制过题目吗？ $2^{-1}\equiv \lfloor \frac{p+1}{2} \rfloor \pmod{p}$（$p$是奇质数）。利用这个结论就可以不需要`exgcd`或`kasumi`求$2$的逆元了。 ## 咕咕月赛 ### T1 [终于结束的起点](https://www.luogu.org/problemnew/show/P4994) 求斐波那契数列在$\mod{m}$意义下的循环节长度。 实际上，在数据范围内，循环节长度不会超过$10^7$。直接暴力递推计算即可。 在考试时如果对算法不自信，可以造尽可能多的随机数据进行计时，会发现这个方法是满足要求的。 ### T2 [跳跳！](https://www.luogu.org/problemnew/show/P4995) 首先看数据范围，$n\le 300$，可能是$\text{O}(n^3)$的动态规划。 但是，这道题的状态难以设计，我们必须记录跳过了哪些石头，这样就需要状态压缩，而$300$又超过了通常状态压缩的数据范围。 怎么办呢？我们先研究跳的策略吧。由于是平方，我们应该让每一次跳的距离尽可能大，于是我们猜想，每次应该跳到当前没跳过的，且与当前位置高度差最大的石头上。 上述策略如何实现呢？把$0$加入到高度数组中，对其进行排序，然后按照$0,n-1,1,n-2,2,n-3,\cdots$进行跳跃即可。 如何证明呢？~~我也不知道呢~~ 应该是用数学归纳法吧！ 总之，$\text{OI}$中的贪心证明通常采用感性理解法、显然法（逃。 ### T3 [咕咕咕](https://www.luogu.org/problemnew/show/P4996) 题意：给定一个$2^n$个点的图，点分别编号为$0,1,\cdots,2^n-1$，其中$m$个点有点权。图中有有向边$x\rightarrow y$当且仅当$x\subset y$。一条路径的权指这条路径上的所有点的点权之和。求所有$0$到$2^n-1$的路径的权之和。 $70$分：考虑递推。设$f[i]$表示所有$0$到$i$的路径的权值之和，那么$f[i]=\text{method}[i]w[i]+\sum_{j\subset i} f[j]$，其中$\text{method}[i]$表示从$0$到$i$的路径条数，可以递推得到。由于要枚举子集的子集，时间复杂度是$\text{O}(3^n)$。 $100$分：我们考虑优化上面的递推。优化分为优化$\text{method}$的计算和优化答案的计算两方面。 首先考虑$\text{method}$的计算方法。“$\text{method}[i]$表示从$0$到$i$的路径条数”，那么由于$i$的各个二进制位之间都是平等的，$\text{method}[i]$应该只与$i$的二进制表示中$1$的个数有关。设$i$的二进制表示中$1$的个数为$\text{cnt}[i]$，那么我们只需对$[0,n]$的每一个$\text{cnt}$求出其$\text{method}$即可。 就像$70$分算法中的那样，考虑枚举$x$的子集。但是我们已经知道，$\text{method}[x]$的值只与$\text{cnt}[x]$有关，因此我们可以把相同元素个数的子集合并起来算。设$\text{cnt}[x]=c$，那么，$x$（一个$c$元集合）的$c'$元子集有多少？答案是$\text{C}_{c}^{c'}$。所有这些$c'$元子集都可以转移到$x$上，并且转移到这些子集的路径数都是$\text{method}[c']$。因此我们得到，$\text{method}[c]=\sum_{0\le c'<c}\text{method}[c']\times \text{C}^{c'}_{c}$。这样我们就在$\text{O}(n^2)$的时间内计算出了$\text{method}$。 接下来考虑优化答案的计算。 我们转而考虑每个点对答案的贡献，即计算有多少条$0\rightarrow 2^n-1$的路径经过了$i$。 把所有$0\rightarrow i\rightarrow 2^n-1$的路径拆成$0\rightarrow i$和$i\rightarrow 2^n-1$两部分，那么根据乘法原理，总路径数就是这两种路径数的乘积。根据我们之前的计算，$0\rightarrow i$的路径数就是$\text{method}[\text{cnt}[i]]$。取图的反图，运用逆向思维，我们发现，$i\rightarrow 2^n-1$的路径数就是$\text{method}[n-\text{cnt}[i]]$，即$i$中$1$的个数所对应的$\text{method}$值！ 这样，我们就在$\text{O}(2^n)$或$\text{O}(n^2+m)$的时间内解决了问题。 --- 注释：请注意上述做法和[$\text{FMT}$](https://sweetlemon.blog.luogu.org/Note-day4)的区别：$\text{FMT}$计算的是$x$所有子集的点权之和，即$\text{FMT}$求和的是一个“常量”数组，在求和开始后不会改变；而这道题求和的是一个递推变化的数组。