2019 ICPC南京站部分官方题解
A. A Hard Problem
在这些数字中，在这些n个数字中，在这n个数字中，在这些n个数字中（注意：此处可能需要进一步优化表达）
随后，在其中选取足够多的数量（即\lceil \frac{n}{2}\rceil 个），当我们在这些未被选中的数字中选取最大值时（即选取\lceil \frac{n}{2}\rceil 个），此时对于每个数字b来说，在剩下的未被选中的数字中必定存在一个与之最接近并能整除它的数字\frac{b}{2}。因此选出这么多数量是不可能成立的。
综上，答案为\lceil \frac{n}{2} \rceil +1。
B. Chessboard
首先，我们可以观察到如下几个不难证明的性质：
- 两个被染上颜色的格子之间的计算方式始终采用曼哈顿距离。
- 一个方案合法即任何时间点每行或每列被染色的格子要么不存在要么形成一段连续区间。
- 若当前所形成的区域是一个矩形则最后填充的那个点必定位于该矩形的一个顶角位置。
接下来，可以手玩一些例子：
符号#与符号表示已经被着色的那一块区域；符号标识着最后一块着色的位置；符号.则表明那些尚未着色的位置
....
....
##$.
###.先随便走一步
....
..$.
###.
###.这时，受到命运的指引，我们接下来必须扩充一行。为什么呢？
如果接下来的一天里我的计划不是前往A点而是选择其他地方游玩的话。（比如：我们用ABC分别标注这三个未被涂色的区域）
.B..
CA$.
###.
###.染色A是否意味着我必须先到达B或C中的某一个格子呢？担心如果此时染色可能会出现什么问题。
因此，我下一步必须 去 A，下下步必须 去 C。
于是，可以得出以下结论：
当所染色的区域为一个r(r \geq 2)行c(c \geq 2)列的矩形时，在下一步操作中必须选择将其扩展为r+1行c列或者r行c+1列的形式，并且这种选择是唯一的。这是因为当前状态下最后一个被染色的格子必然位于某个特定角的位置上
由单个元素组成的 1×1 矩阵可以通过不断扩展的方式逐步发展至 n×m 矩阵。总共需要进行 n + m − 2 次扩展操作，在这其中会有 n−1 次是用于扩展行的数量。因此相应的决策数量为组合数 \binom{n+m-2}{n-1} 种。具体来说这种模式下的方案总数则为4乘以组合数 \binom{n+m-2}{n-1}
Corner case: n=1 或者 m=1，小心特判掉即可。
C. Digital Path
定义dp[i][j][k]为以点(i,j)结尾且长度为k的路径中无法向左延伸的情况下的方案数量。其中k的最大取值为4。我们通过设置所有长度为1且无法向左延伸的路径对应的初始状态，并根据格子权值从低到高排序后进行动态规划处理更为合理。特别地，在计算总方案数时需要确保所考虑的所有路径均能够向右延伸。
D. Hole
-
定义 p(k,x,y) 为从起点，随机游走 k 步后在 (x,y) 的概率，P(x,y)=\sum_{k=0}^{+\infty} p(k,x,y)，
-
定义 e(k,x,y) = p(k,x,y) * k，E(x,y)=\sum_{k=0}^{+\infty} e(k,x,y)
-
那么对每个洞 (x,y), \frac{E(x,y)}{P(x,y)} 即为答案。
-
定义 out(x,y) 为 (x,y) 的出度，设走一步能到达 (x,y) 的 q 个点为 (x'_1, y'_1),....(x'_q,y'_q)。那么当 k \geq 1 时，有
- p(k,x,y) = \sum_{i=1}^{q}\frac{p(k-1,x_i',y_i')}{out(x_i',y_i')}，
- \frac{e(k,x,y)}{k} = \sum_{i=1}^{q}\frac{e(k-1,x_i',y_i')}{(k-1)out(x_i',y_i')}
- 对以上两个式子，的等式最右边，分别将 k 从 1 到正无穷进行累和，分别可以得到关于 P(x,y), E(x,y) 的两个线性方程组。
-
P(x,y) 和 E(x,y) 均可利用高斯消元法进行求解，在涉及 O(nm) 个变量的情况下（其中每个变量对应着一个方程），其计算复杂度达到了 O(n^3m^3) 的水平。
-
观察到所有变量均可表示为"棋盘中每行第一个从起点能到达的点对应的变量"这一特定模式下的线性组合关系。这种模式的应用使得我们能够将原本数量达到 O(n) 的独立方程组数目减少至 O(n) 个（即每个方程组仅包含一个独立未知数），从而使得整个系统的计算复杂度降至 O(n^3) 的水平。
I. Space Station
f(c[]) 作为基于'权值为i的点已有c[i]个被访问过的状态'的函数，在遍历所有节点时有多少种可能的路径。
- 当 \sum_{i=1}^{m}ic[i] \geq m 时，剩下的点可以任意次序访问。
当满足\sum_{i=1}^{m}\mathit{ic}[i]
K. Triangle
首先确定点P所在的边并采用向量叉乘与点乘的方法进行判断。若已知点P位于AB边上，则需要计算平分线PE的长度。假设点P距离A较近，则端点E必定位于BC边上。以上情况为例进行说明；其余情况类推
外部链接的图片无法正常上传至平台，请您按照以下步骤操作：首先将需要上传的图片保存到本地设备上；其次确保您的浏览器已启用图库上传功能；最后尝试重新提交图片文件。建议您在上传前检查网络连接状况以避免重复提交同一张图片导致资源耗尽的问题。
解法1:
运用向量叉乘来计算面积的方法下，在等式|BA|\times|BC|\times sinB\times 0.5=|BP|\times|BE|\times sinB的基础上直接得出线段BE的长度之后就可以确定点E的位置
外部链接中的图片无法正常存储，请您将图片保存后重新尝试上传（建议您在本地先保存该图片文件后复制粘贴到目标位置进行上传）。具体操作可参考以下步骤：1. 在您的浏览器中找到并点击该外链链接；2. 等待页面加载完成后找到并点击相关按钮；3. 按照提示完成图片上传操作）。
解法2:
取AB边的中点为D，则连接C点与D所得的线段CD即为此三角形的一条平分线。接着连接P和C两点，并将此连线延伸至BC边上一点E的位置。接着过D作DE平行于PC，并延长交BC于E。那么PE即为此三角形的另一条平分线。
证明：其中那两个红色三角形的面积相等；进而得到PEB三角形与BCD三角形的面积相等。