/ BZOJ

BZOJ 省队十连测第一场

Claris出题。BZOJ Begin 3738,3739,3740。

试题难度一高,我这样的蒟蒻当然是一道题都做不出来的。考试5个小时前3个小时水掉了,最后两个小时半个小时拿去吃饭,一个半小时打暴力,混了个60分。

  • shopping 0
  • highway 30
  • sailing 30

T1输入输出文件名写成了“highway"……下次模拟赛的时候要注意了。

shopping

考虑没有消费限制的话,直接插板就好了。允许为空,所以共n+kn+k个球n+k1n+k-1个空,nn个盒子n1n-1块板;所以

Ans=Cn+k1n1Ans=C_ {n+k-1}^{n-1}

我知道接下来应该枚举某一些商店必然超限,但是没有想到应该怎么统计答案。如果在每个枚举必定超限的商店先消费这个商店的限额加1的钱数,剩下的再随便分配,那么可以转为和上面一样的问题。

Ans=AM(1)ACn+k1iA(wi+1)n1Ans=\sum_ {A\subset M} (-1)^{\left | A\right |} C_ {n+k-1-\sum _{i\in A}(w_ i+1)}^{n-1}

如果用深搜枚举的话,时间复杂度为O(2m)O(2^m),有70分。

因为对答案真正有贡献的只是一些组合数的加减,而每个组合数的大小只和w\sum w有关系,所以只要算出要加减多少个w\sum w就可以了。设f[i][j]f[i][j]为前ii个有限制的商店中Cn+k1(w+1)n1C_ {n+k-1-\sum (w+1)}^{n-1}对答案贡献的系数。

  • 如果第ii个商店不超过限制,那么f[i][j]+=f[i1][j]f[i][j]+=f[i-1][j]
  • 如果第ii个商店超过限制,根据容斥,贡献要变成负的,那么f[i][j]=f[i1][jw1]f[i][j]-=f[i-1][j-w-1]

时间复杂度O(mw2)O(mw^2),这在m300,w300m\leq 300,w\leq 300的情况下竟然要跑进一秒,只能说评测机太快了。

highway

区间问题,考虑区间数据结构或者分块。这题可以用线段树来做。每个区间维护区间内最小生成树用的边,因为这题的结点数量是比较小的,n100n\leq 100,所以边数n1n-1并不大。合并区间信息的时候,大区间的最小生成树的边只可能来自两个小区间的最小生成树的边;如果两个子区间都按从小到大存好了最小生成树的边,只要做一次归并,就可以得到大区间内边权从小到大的顺序,来一次Kruskal即可。单次询问O(logmnα(n))O(\log m\cdot n\alpha(n))。这解法十分巧妙而编码不会太复杂,我完全没有想到,实在是佩服。

sailing

这题的直接广搜没什么好说的。题解是对可行性判断和最终统计答案时可覆盖的地方的数量的计算用FFT优化。

把地图连接成一个串,就是第二行开头连接到第一行末尾,第三行开头连接到第二行末尾……然后分别处理出两个01串,一个表示石头的位置(设为S),一个表示舰队的位置(T)。把他们写成两行,那么舰队的横向移动就是±1\pm 1,纵向就是±m\pm m,01串的相对移动时。不可能要求循环01串,因为一旦有船跑出了模板边界,船也就跑出地图了。

在BFS的时候,我们想知道一个位移是否合法。那么就是要检查经过这个位移之后的01串是否存在一个位置使得两个串都是1。把T串倒过来,其实就是检查STS\cdot T后某一位是否为0啦。

BFS过后知道哪些位移合法,再来一次类似的卷积,判断某个位置是否为0就可以知道地图上的对应位置是否能被覆盖到。

时间复杂度O(nmlog(nm))O(nm\log(nm))

关于快速傅立叶变换,我另外写了一篇文章来总结:链接