2012-0037

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意是：
你所选的文明大国（比如天朝）诞生在m*n（50*50）的方格地图上，其中有一片连通的格子是属于天朝的领土，当然地图上还有其它一些连通的格子是属于其它文明的领土。

现在你要修建一个奇观建筑（比如长城），修建长城需要耗费一定的资源，文明5是回合制游戏，每回合你都能得到一定量的资源，比如每回合产量为20，建造长城需要160资源的话，就需要8回合才能造好


每回合资源总产量为多少，取决于你的领土状况以及本回合如何分配你的工人，所有属于你领土的格子都有一个固定的每回合资源产量，但是必须要有工人在这个格子上工作才能得到这个格子的资源~最开始（回合0）你有一个工人，每过5个回合（比如回合5、回合10）你会得到一个额外的工人。同时每过5回合，你的领土会扩展【一圈】，这个一圈是指凡是和你领土相邻的格子，都会成为你的领土（但是如果已经是其他文明的领土了，则不会被纳入，注意其他文明的领土不会扩张）


注意：工人一旦分配到一个格子上，就不能再离开，格子上的资源有一个最初产量，每被开采一回合，每回合产量就会减1，直至为0，工人从首都走到格子上不需要消耗回合数~同时工人一旦出生就必须在当前回合分配到一个格子，否则会变成游民


此外，地图上的某些格子有远古遗迹（遗迹很稀少，不会超过5个），找到这些遗迹的话可以直接获得一定量的资源，最开始你有一个侦察兵，在首都所在的格子，每回合侦察兵最多可以走两格（上下左右），走到遗迹所在的格子就能获得这些资源，但是不能踏进其他文明的领土


这题其实不难，没有高级的算法和数据结构，就是做几次bfs、dfs即可

做法把几个遗迹提取出来，预处理出它们之间以及它们到首都的最短路径，dfs枚举侦察兵踩遗迹的顺序，踩的过程肯定是走最短路，顺序定了之后，二分所需的回合数，然后每一回合都贪心取总产量最高的格子放工人，当然不二分也可以，只不过二分的话可以O（1）得出一个格子的最终收益比较好计算一点，可以用优先队列来维护产量最高的格子，如果有新的格子纳入版图则塞入优先队列，同时预处理出地图上所有格子需要几回合才能纳入本国领土，这个可以用普通的bfs一次搞定


有一个trick就是侦察兵一个回合可以走两格，所以最好模拟一格一格的走

题目大意是：

你所选的文明大国（比如天朝）诞生在m*n（50*50）的方格地图上，其中有一片连通的格子是属于天朝的领土，当然地图上还有其它一些连通的格子是属于其它文明的领土。

现在你要修建一个奇观建筑（比如长城），修建长城需要耗费一定的资源，文明5是回合制游戏，每回合你都能得到一定量的资源，比如每回合产量为20，建造长城需要160资源的话，就需要8回合才能造好

每回合资源总产量为多少，取决于你的领土状况以及本回合如何分配你的工人，所有属于你领土的格子都有一个固定的每回合资源产量，但是必须要有工人在这个格子上工作才能得到这个格子的资源~最开始（回合0）你有一个工人，每过5个回合（比如回合5、回合10）你会得到一个额外的工人。同时每过5回合，你的领土会扩展【一圈】，这个一圈是指凡是和你领土相邻的格子，都会成为你的领土（但是如果已经是其他文明的领土了，则不会被纳入，注意其他文明的领土不会扩张）

注意：工人一旦分配到一个格子上，就不能再离开，格子上的资源有一个最初产量，每被开采一回合，每回合产量就会减1，直至为0，工人从首都走到格子上不需要消耗回合数~同时工人一旦出生就必须在当前回合分配到一个格子，否则会变成游民

此外，地图上的某些格子有远古遗迹（遗迹很稀少，不会超过5个），找到这些遗迹的话可以直接获得一定量的资源，最开始你有一个侦察兵，在首都所在的格子，每回合侦察兵最多可以走两格（上下左右），走到遗迹所在的格子就能获得这些资源，但是不能踏进其他文明的领土

这题其实不难，没有高级的算法和数据结构，就是做几次bfs、dfs即可

做法把几个遗迹提取出来，预处理出它们之间以及它们到首都的最短路径，dfs枚举侦察兵踩遗迹的顺序，踩的过程肯定是走最短路，顺序定了之后，二分所需的回合数，然后每一回合都贪心取总产量最高的格子放工人，当然不二分也可以，只不过二分的话可以O（1）得出一个格子的最终收益比较好计算一点，可以用优先队列来维护产量最高的格子，如果有新的格子纳入版图则塞入优先队列，同时预处理出地图上所有格子需要几回合才能纳入本国领土，这个可以用普通的bfs一次搞定

有一个trick就是侦察兵一个回合可以走两格，所以最好模拟一格一格的走