【总结】2019南京网络赛小结
The Preliminary Contest for ICPC Asia Nanjing 2019 (即 ICPC2019 南京网络赛)部分总结
A - The beautiful values of the palace
题目大意
整块 n * n 的地区,每个坐标都有自己的权值。权数值由中间到外围螺旋状减小(如下例),权值等于权数值的数位总和。在这片地区有 m 座城堡,对于 q 次询问,询问一个矩形范围内的城堡占点的权值和。
对于 n = 3 和 n = 5 的情况,点权分布情况为:
1 |
|
其中,左下角为(1, 1)
,右上角为(n, n)
。T 组数据。
数据范围:T <= 5; n <= 1e6; m, p <= 1e5
。
题目思路
将数据离散化后仍然需要 1e5 * 1e5 的大小来存储数据,不可行。
将二维问题化为一维问题,将所有数据存储到同一个结构体中,按 x 轴排序后根据 y 轴大小维护一个树状数组。
其中地图信息和询问信息全部离线到数组中统一处理,对于坐标重合的数据,将地图信息排在询问的前边。最后扫描统一处理。
参考写法
1 |
|
B - super_log
题目大意
求 a 的 b 个 a 次幂模 m 的值,即:
$$
\begin{equation}
\underbrace{a^{a^{a^{…}}}}_{b\ times} (mod\ m)
\end{equation}
$$
题目思路
使用欧拉定理递归降幂,需要特判 a 和 m 不互质的情况。
欧拉函数会很快迭代到 1,可以提前退出,速度很快。
扩展欧拉定理:
F - Greedy Sequence
题目大意
对于 n 个数字,k 的搜索半径,一个长度为 n 的字典池。要求以 1 到 n 为序列首位,构造 n 个序列。
对于每个序列,每次以当前最后一位为原点,选择字典池中半径为 k 的最大值,直到无法选择。
如对于 n = 7, k = 2, dic[] = {3, 1, 4, 6, 2, 5, 7}
,构造的七个序列分别为:
1 |
|
求构造的 n 个序列的长度,如上述样例,输出为1 1 2 3 2 3 3
。
题目思路
简单的 DP,字典序最大,则每次只选择能选择的最大值,找到后 break 即可。
参考写法
1 |
|
H - Holy Grail
题目大意
你的英灵的宝具是一个带负权有向图(?)。你需要在指定的六个位置依次连接六条此位置允许的最小边,使不出现负权环,否则你会被圣杯吞噬(?)。数据保证答案存在。
题目思路
要使不出现负权环,则需要在指定位置创建零权环。要在 x -> y 连边创建零权环,则所需权值为 y -> x 最短路的相反数。每次跑一下最短路并连接新边即可。
参考写法
1 |
|