2022.10.05考试总结

得分：\(280/400\)

总结：今天考试题目比较简单，第一，二题都是结论题，第三题在考场上因为没有考虑到有五十位导致挂了\(50\)分，第四题想到了正解，但是考试的时候实现的方法有点问题

T1

题目大意：给定平面上 \(n\) 个整点，问从中选出 \(3\) 个使得组成的三角形的重心也是整点的有多少个。

得分：\(100/100\)

总结：这道题目其实感觉出题人没有考虑三个点共线或者共点的情况

首先我们先默认三个点如果共点或者共线的话也算三角形

有一个结论

设三个点的坐标分别为\((x1,y1),(x2,y2),(x3,y3)\)

那么重心的坐标为\((\frac{x1+x2+x3}{3},\frac{y1+y2+y3}{3})\)

根据上述式子，按照对于\(3\)的余数分类，然后计数即可

T2

题目大意：给定序列\(x1...xn\)与序列\(y1...yn\)

可以交换\(x\)序列中任意两个值的位置

最小化\(\sum_{i=1}^n x_i \times y_i\)

要求输出最小值

得分:\(100/100\)

不难发现，我们把\(x\)从小到大排序，\(y\)从大到小排序即可，正确性易证

T3

题目大意：

你有一组非零数字(不一定唯一)。你可以在其中插入任意个 \(0\) ,这样就可以产生无限个数(无前导零)。

例如，\(\{1,2\} \Rightarrow \{12,21,102,120,210....\}\)

给定一个数，问在这个数之前有多少个数

得分:\(50/100\)

总结：注意，这道题有可能会爆\(long\ long\)

我们可以首先求位数比这个数小的数的数个数

然后再求位数相同并且比这个数小的数的个数，考虑用数位\(DP\)解决

T4

题目大意：
给定一个字符矩阵，\(-\)表示平地，\(X\)表示障碍，\(@\)表示起点，\(+\)表示绿洲。
从起点出发，每天可以像四周 8 个方向移动，当然需要是合法移动。然而每天还有一个风向，
若你出发时是逆风而行，则需要 3 天才能到达目的地，否则只需一天就能到达目的地。
你虽然不知道未来的风向如何，但幸运的是风向是确定的，也就是说它不会根据你的决策而改变。问最坏情况下，你要多久才能到达绿洲

得分：\(30/100\)

总结：

设\(d[i][j]\)表示当前在\((i,j)\),还需多久才能走到绿洲。
我们可以观察到，因为求的是最坏情况下的解，那么每个状态的决策只有两种
第一种是选择最优的一个相邻状态\(x\)，并用\(x+3\)更新答案，第二种是使用
次优的相邻状态\(x'\)，用\(x'+1\)更新答案。
这类似与经典的最短路问题，只是是倒着推的。
因为长,宽\(\leq 50\),具体实现可以采用\(bellman-ford\)。