1011

ZRC 签到

题意：

一个动态开点线段树的build环节，如果是在1-n上build，当区间长度小于等于k就return的话，要开多少点。

解：

考场上时刚开始觉得大家过得这么快肯定是什么打表随便看的东西，就没仔细想直接打表找规律了。看了好长时间之后得到结论：当$k\cdot 2^x=n$时，答案是$2^{x+1}-1$,$k\cdot 2^x<n<k\cdot 2^{x+1}$时，答案是$min{ 2^{x+1}-1+2\cdot (n-k\cdot 2^x),2^{x+2}-1 }$

这样复杂度一个log即可判断。

实际上不打表的方法也是显然的。对于每种长度记忆化搜索。对于每个输入最多只有$\lg n$层，所以就最多只有大约$O(\lg n)$级别种不同长度的区间。对他给的代码随便改改即可。

1007

ZRC&WD 无脑签到

1004

LYF 博弈论

1003

WD ntt字符串匹配

1009

题意：

n100的方阵，从左上角走到右下角，每一步只能向右或者向下。每个格子有a,b两个属性1e6，保证数据随机，问最终路径上a的和*路径上b的和的最大值是多少。

ZRC&LYF解：

首先感受到退火对这道题貌似很不稳定，貌似局部爬山的峰都很小，比较难找到正确的峰。考虑A*。估值随便按局部最优解估，更重要的是如何剪枝。LYF想出了可以预处理当前点到终点的a+b的和的最大值，剪枝时利用这个最大值求出一个从当前状态走到终点时的答案的上界，与当前答案比较。跑得飞快。

题解：

设计一个状态$f[i][j][x]$表示走到i,j位置且a的和为x时的b的最大值。则对于同一个i,j位置，可能发展为最优解的x和f的值是具有单调性的。因此最多只有$n^2\cdot(有效的x)$个状态，而随机数据下有效的x大约是几千个。