赴京赶考

from Gromah

大家好，我是 Gromah，大家赴京赶考的路上是不是都是骑的果弱马去的呢。。？（雾）

算法零

$n,m \le 100, q \le 10$ 的话，直接给网格中的每一个格点都建一个点，然后该怎么最短路就怎么最短路，该怎么并查集+BFS就怎么并查集+BFS。

复杂度 $O(qnm)$，可以拿下前30分。

算法一

$n\le 10^5, m = 1, q\le 10^5$ 的话，我们可以直接预处理出 $(1,1)-(1,i)$ 的距离以及 $(1,i)-(1,n)$ 的距离，然后就枚举走的方式 $i-j$ 或者 $j-n-1-i$ 就可以啦。

复杂度 $O(n + q)$，结合算法零可以拿下50分。

算法二

$n,m\le 10^5, q\le 10^5$ 的话，我们发现我们可以突破维度的界限，把每一维拆开分别考虑，最后的答案就是每一维的答案的和。

这为啥是对的呢？

对于 $a_i \neq a_{i+1}$，无论 $b_j$ 取啥值，你从 $(i,j)$ 穿越到 $(i+1,j)$ 的时候，都必然会花费等待时间；否则如果 $a_i = a_{i+1}$ 的话，就必然不会花费等待时间。所以一条路线的总等待时间可以拆分成各个维度的等待时间的和。

然后这个问题就变成一维问题啦，直接用算法一的搞法就可以了。

复杂度 $O(n + m + q)$，可以拿下100分。

Q&A

Q：为什么这个题这么水？

A：因为 Gromah 是一匹送莘莘学子赴京赶考的果弱马。

Q：你都送考去了怎么出的题？

A：VFK 大法好。。。

赛事回顾

膜一血爷 alpq654321 以及众线段树爷。。

决战圆锥曲线

from jiry_2

大家好这里是JRY！这次出了一道不是生成树的良心大水题> <。

虽然题目叫做圆锥曲线但是和圆锥曲线一点关系都没有啦..

算法一

所有操作都大暴力，时间复杂度$O(nm)$，期望得分10分。

算法二

当$a=0$且$c=0$的时候，询问就相当于询问一个区间的$y$坐标最大值，这个可以直接用线段树来维护，时间复杂度$O(m\log n)$，期望得分30分。

算法三

当$c=0$的时候，很显然答案肯定在这个区间的凸包上，我们可以用线段树来维护区间的上凸壳。

因为数据时随机的，所以长度为$n$的区间的凸包大小是$O(\log n)$的，所以在线段树update的时候可以直接暴力合并左右孩子的凸包，所以修改操作都是单次$O(\log^2 n)$的。要注意的是因为存在操作R，所以同时还要维护区间的下凸壳。

至于询问操作我们可以暴力扫每一个子区间的凸包上的所有的点，带入式子中得到最优值。询问操作单次也是$O(\log^2 n)$的。

所以总的时间复杂度是$O(m\log^2 n)$，结合算法一二期望得分50分。

算法四

当$c \neq 0$的时候，答案是不在上凸壳上的，比如三个点$(0,3),(1,1),(3,0)$，$xy$的最大值就取在点$(1,1)$上，而这个点显然不在上凸壳上。

可以发现对于一个点$(x_i,y_i)$，如果存在一个点$(x_j,y_j)$满足$x_i \leq x_j$且$y_i \leq y_j$，那么第$i$个点对答案是一定没有影响的。因为数据随机，所以可以证明题目中一个长度为$n$的区间对答案有影响的点的个数是$O(\log n)$的，证明如下：

如果点$i$对答案有影响当且仅当对于所有$j > i$都有$y_i > y_j$，所以第$i$个点对答案有影响的概率是$\frac{1}{n-i+1}$，所以对答案有影响的点期望是$\sum_{i=1}^n \frac{1}{i}=O(\log n)$的。

所以我们可以用线段树来维护一个区间内对答案有影响的点集（一个台阶状物体），同样也是要维护向上的台阶以及向下的台阶。时间复杂度$O(m \log^2 n)$，结合算法一二期望得分70分。

算法五

如果要用线段树来维护台阶的话记录的信息太多了，肯定没有办法在更低的时间复杂度里解决这个问题。所以要找到一种记录的信息更少且一样可以达到目的的方法。

我们可以对于线段树上每一个区间记录这个区间的$y$坐标的最大值和最小值（对，就是框矩形）。这样修改操作都很简单，可以在$O(\log n)$的时间内完成。而对于询问操作，考虑这样的算法：

令变量$ans$为当前得到的最大值，$calc(x,y)$为点$(x,y)$带入$ax+by+cxy$后得到的答案，$\max(l,r)$表示区间$[l,r]$的纵坐标的最大值。假设当前我们递归到的区间为$[l,r]$，它的左儿子为$[l,mid]$，右儿子为$[mid+1,r]$。如果$calc(r,\max(mid+1,r))>ans$，则递归进入右儿子。等到右儿子判断（递归）结束后，如果$calc(mid,\max(l,mid))>ans$则递归进入左儿子。当递归到叶子节点的时候，更新$ans$。

可以发现这个算法的复杂度是$O(\log^2 n)$的，因为我们递归到一个孩子意味着这个孩子所表示的区间中一定至少存在一个对答案有影响的点（这个区间的纵坐标的最大值一定比我们之前递归得到的所有区间的纵坐标的最大值大），所以每一次递归一定在一个对答案有影响的点结束，因为对答案有影响的点的个数是$O(\log n)$的，所以每次询问的时间复杂度是$O(\log^2 n)$的。

到此我们解决了这个问题，期望得分100分。

总结

其实这题数据真的很难造QAQ因为数据是随机的所以绝大部分情况下最优值是取在凸包上的。用随机+对拍大法勉强卡掉了六七八三个点，之后怎么也找不到新的数据了。最后第九个点和第十个点开头是和第七个点一样的，直到出现了凸包算法WA的询问后才重新开始随机QAQ。

然后这个算法也是可以拓展的，只要询问的函数$f(x,y)$在$x_i \leq x_j$且$y_i \leq y_j$的时候有$f(x_i,y_i) \leq f(x_j,y_j)$就可以在数据随机的情况下使用这个算法，而且因为只要维护区间的最大值和最小值所以像区间翻转这种不影响随机性质的操作都是可以加上去的。

总之这题也是不怎么难，程序也好写好调，差不多就二十分钟的工作量吧，希望大家水的愉快。

为信息学献一利器，看出题人再造数据。

宿命多项式

from jcvb

为了方便，我们把限制由$1\le f(i)\le c_i$改为$0\le f(i) < c_i$。这样只需把常数项减去1，不会影响答案。

算法一

对于第1个数据，$n=1$。那么就是 \begin{align*} 0\le a_0< c_0 \\ 0\le a_0+a_1 < c_1 \end{align*}

固定$a_0$后，$a_1$有$c_1$种选择，所以答案是$c_0\cdot c_1$。

可以获得10分。

算法二

对于第2个数据， \begin{align*} 0\le a_0< c_0 \\ 0\le a_0+a_1+a_2 < c_1 \\ 0\le a_0+2a_1+4a_2 < c_2 \end{align*} 因为$c_0$比较小，可以枚举$a_0$，然后算此时$a_1,a_2$的取值方案。这里要求平面上多边形内整点个数，应该还是很可做的。

可以获得20分。

算法三

枚举$f(0),f(1),\cdots,f(n)$的值，然后根据这个方程组解出$a_0,a_1,\cdots,a_n$，如果这些值都是整数，那么给答案加一。然而这样太低效了。

每次解方程组时，未知数前系数都是不变的，变的只是右边的常数。于是我们可以把这个系数矩阵的逆矩阵求出来，然后会发现逆矩阵中的元素的分母都很小。

于是我们只要枚举$f(1),\cdots,f(n)$在模其对应的分母意义下的值，判断对应的系数是否是整数即可。

这个做法的复杂度是$O((n!(n-1)!(n-2)!\cdots 1!)^2 \cdot n)$。

可以获得60分。

算法四

定义下降幂$x^{\underline{k}}=x(x-1)(x-2)\cdots (x-k+1) \,\,(k\ge 0)$。

一个整系数多项式可以唯一地表示为一个下降幂的级数形式，反之亦然： $$ f(x)=a_n x^n+a_{n-1}x^{n-1}+\cdots + a_0= q_n x^{\underline{n}}+q_{n-1} x^{\underline{n-1}}+\cdots + q_0 $$

所以我们只需用下降幂的形式考虑即可。

以$n=3$为例，有 \begin{align*} f(0)&=q_0\\ f(1)&=q_1+q_0\\ f(2)&=2q_2+2q_1+q_0\\ f(3)&=6q_3+6q_2+3q_1+q_0 \end{align*}

也就是说 \begin{align*} 0&\le q_0 < c_0\\ 0&\le q_1+q_0 < c_1\\ 0&\le 2q_2+2q_1+q_0 < c_2\\ 0&\le 6q_3+6q_2+3q_1+q_0 < c_3 \end{align*}

观察最后一行，如果$q_2,q_1,q_0$已经固定，我们就有$-C\le 6q_3 < c_3-C$，于是合法的$q_3$的数量为 \begin{align*} \left \lfloor c_3/6 \right \rfloor \,\,\,\,\,\,\,\,C \bmod 6 \ge c_3 \bmod 6 \\ \left \lfloor c_3/6 \right \rfloor +1 \,\,\,\,C \bmod 6 < c_3 \bmod 6 \end{align*} 为了计算$C \bmod 6$，我们需要知道$q_1 \bmod 2$和$q_0 \bmod 6$，因为$C=6q_2+3q_1+q_0$。

一般地，我们枚举$r_0=q_0 \bmod n!,r_1=q_1 \bmod (n-1)!,\cdots, r_{k-2}=q_{k-2}\bmod 2!$。利用第$i$个不等式 $$ 0\le f(i)=i^{\underline{i}}q_i+i^{\underline{i-1}}q_{i-1}+\cdots + i^{\underline{0}}q_0 < c_i $$ 来计算合法的$q_i$的数量。将$q_i$写作$(k-i)!\cdot t+r_i$，那么 $$ 0\le i!(k-i)!t+i^{\underline{i}}r_i+i^{\underline{i-1}}q_{i-1}+\cdots + i^{\underline{0}}q_0 < c_i $$ 现在要计算合法$t$的数目。和刚才一样，我们要计算$(i^{\underline{i}}r_i+i^{\underline{i-1}}q_{i-1}+\cdots + i^{\underline{0}}q_0) \bmod i!(n-i)!$，它等于$(i^{\underline{i}}r_i+i^{\underline{i-1}}r_{i-1}+\cdots + i^{\underline{0}}r_0) \bmod i!(n-i)!$，因为$i!(n-i)!$是整除$i^{\underline{j}}(n-j)!$的。把得数和$c_i\bmod i!(n-i)!$比较就可以了。最后把这些结果相乘。

这个做法的复杂度是$O(n\cdot n!(n-1)!\cdots 1!)$。

可以获得90分。

算法五

我们刚才在$0\sim n!-1$范围内枚举了$r_0$，我们考虑如何避免这层枚举。注意这个枚举过程中，$(i^{\underline{i}}r_i+i^{\underline{i-1}}r_{i-1}+\cdots + r_0) \bmod i!(n-i)!$在不断地增加1然后归零这样循环下去，在值$\ge c_i\bmod i!(n-i)!$时不加一，小于时加一。于是在一个周期内变化两次，总共有$n!/i!(n-i)!=\binom{n}{i}$个周期，那么有$2\binom{n}{i}$个变化点。那么对于所有$i$，共有$\sum 2\binom{n}{i}=2^{n+1}$个变化点。在相邻两个变化点之间，对答案的贡献是不发生变化的。

这样我们就做到了$O((n-1)!\cdots 1! \cdot 2^{n+1}\log 2^{n+1})$。

这个排序的 $\log$ 可以用计数排序的办法去掉。但是不能每次都调用计数排序，而是应该离线的做，等待排序量足够大的时候统一排序。

可以获得100分。