CSDN 编程竞赛三十二期题解

竞赛总览

CSDN 编程竞赛三十二期：比赛详情 (csdn.net)

竞赛题解

题目1、传奇霸业

传奇霸业，是兄弟就来干。小春（HP为a）遇到了一只黄金哥布林（HP为x）。小春每次能对哥布林造成b点伤害，哥布林每次能对小春造成y点伤害。作为玩家的小春怎么可能随便让哥布林打死呢！他有治疗神药，每次能恢复c点HP。HP无上限。小春需要操作多少次（治疗+攻击）才能打死哥布林？

#include <cstdio>struct role {int hp;int attack;
};int main () {int a, b, c, x, y;scanf ("%d %d %d %d %d", &a, &b, &c, &x, &y);role player, monster;player.hp = a; player.attack = b;monster.hp = x; monster.attack = y;int attack_num = (monster.hp / player.attack) + (monster.hp % player.attack != 0 ? 1 : 0);int attack_monster = monster.attack * (attack_num - 1);int t = 0;while (player.hp + t * c <= attack_monster){t = t + 1;attack_monster = attack_monster + monster.attack;}printf ("%d", attack_num + t);return 0;
}

本题描述上虽然有些即时游戏的感觉，但实际上用的是回合制的规则，类似赛尔号打谱尼。

在本题中，规则被简化了不少，没有技能释放次数（PP）、技能冷却时间（CD）等限制，不需要走位躲避怪物的攻击，怪物也不会回血。

可以直接计算出所需的攻击次数。玩家攻击之后，轮到怪物攻击，可以由此算出怪物对玩家的伤害量。

通常来说，玩家的HP不足以抵挡怪物的总伤害量，在攻击过程中，很大概率需要使用恢复道具。然而，玩过赛尔号的小伙伴应该都知道，使用道具恢复之后，还会被怪物揍一次。因此，吃药的过程需要单独拿出来计算。每次吃完药之后，更新玩家吃药次数和怪物攻击次数，直到初始HP与恢复HP之和超过怪物的总输出为止。

也可以采用另一种贪心的思路来解决此题，能直接干掉BOSS或者血量足以抵挡BOSS一次攻击时，玩家采用攻击策略；否则，玩家必须吃药。这种思路直接无脑循环就行了，可以让程序帮忙把答案算出来，不需要太多的分析。

题目2、严查枪火

X国最近开始严管枪火。像是ak, skr, m4a1。都是明令禁止的。现在小Q查获了一批违禁物品其中部分是枪支。小Q想知道自己需要按照私藏枪火来关押多少人（只有以上三种枪被视为违法）。

#include <cstdio>
#include <iostream>
#include <string>int main () {int result = 0;std::string str, data [] = {"ak", "skr", "m4a1"};while (std::cin >> str) {for (int i = 0; i < 3; i++) {if (str == data [i]) result += 1;}}printf ("%d", result);return 0;
}

本题可以在输入之后直接比较字符串，而且这样做效率更高一些。但是，为了体现出程序自动化的思想，建议将所有符合条件的字符串存入列表中，利用循环自动进行比较。

输入数据比较成功时，对结果进行更新，直到将所有输入数据比较完成之后，输出最终结果。 

题目3、蚂蚁家族

小蚂蚁群是一个庞大的群体，在这个蚂蚁群中有n只小蚂蚁，为了保证所有蚂蚁在消息传送的时候都能接收到消息，需要在他们之间建立通信关系。就是要求小蚂蚁都可以通过多只或者直接联系到其他人。已知几条小蚂蚁之间有通信关系，请问还需要再新建至少多少条关系？

这道题之前也考过一次，可以用并查集算法解决。

题目4、运输石油

某石油公司需要向A、B两地运输石油。两地的需求量不同，而一辆车只能装载一定量的石油。经过计算A地需要a辆车运输、B地需要b辆车运输，才能满足需求。现在一共有n辆车分布在各地，每辆车前往A、B两地运输石油均可以获得一定不等的利润。现在请你安排a辆车前往A地，b辆车前往B地运输石油，使得在满足A、B两地石油需求的前提下，获得最大的利润。每辆车只能前往一地运输石油。

#include <cstdio>int dp [1005][1005];int max (int a, int b, int c) {if (a > b && a > c) return a;if (b > a && b > c) return b;return c;
}int max (int a, int b) {if (a > b) return a;return b;
}int min (int a, int b) {if (a < b) return a;return b;
}int main () {int n, a, b;scanf ("%d %d %d", &n, &a, &b);int award [2];for (int i = 1; i <= n; i++) {scanf ("%d %d", &award [0], &award [1]);for (int x = min (a, i), x_end = max (a - n + i, 0); x >= x_end; x--) {for (int y = min (b, i - x), y_end = max (a + b - n + i - x, 0); y >= y_end; y--) {if (x + y > i) {break;} else if (x == 0 && y == 0) {continue;} else if (x == 0) {dp [x][y] = max (dp [x][y], dp [x][y - 1] + award [1]);} else if (y == 0) {dp [x][y] = max (dp [x][y], dp [x - 1][y] + award [0]);} else {dp [x][y] = max (dp [x][y], dp [x - 1][y] + award [0], dp [x][y - 1] + award [1]);}}}}printf ("%d", dp [a][b]);return 0;
}