客户网站建设洽谈方案,如何建设网站兴田德润可以吗,物流公司响应式网站建设,成都网络推广中联无限上期周赛因为最后一题出现bug#xff0c;再加上都是经典的模板题#xff0c;问哥就懒得写题解了。 本期也是有两道考过的题目#xff0c;不过最后一题因为考到了背包问题的特殊类型#xff0c;还是值得拿出来记个笔记。 第一题#xff1a;传奇霸业 传奇霸业#xff0c;是… 上期周赛因为最后一题出现bug再加上都是经典的模板题问哥就懒得写题解了。 本期也是有两道考过的题目不过最后一题因为考到了背包问题的特殊类型还是值得拿出来记个笔记。 第一题传奇霸业 传奇霸业是兄弟就来干。小春(HP a)遇到了一只黄金哥布林(HP x)。小春每次能对哥布林造成b点伤害哥布林每次能对小春造成y点伤害。作为玩家的小春怎么可能随便让哥布林打死呢他有治疗神药每次能恢复c点HP。HP无上限。小春需要操作多少次才能打死哥布林治疗攻击 输入描述第一行输入a,b,c。(1a,b,c1000)。第二行输入x,y。(1x1000,0yc) 输出描述输出最小操作次数。 示例 示例输入11 6 100 12 5输出2分析
模拟。但本题出得不是特别好因为对游戏的流程没有说清楚。不管有没有玩过游戏读完此题都会有一定程度的迷惑是先攻击怪物哥布林还是先受攻击是回合制还是即时制在被攻击前可以无限吃药问哥一开始以为是即时制所以最初的思路是一旦自己的HP小于怪物的攻击力就不断吃药直到大于怪物攻击力。。。然后无法通过才发现原来是回合制。修正思路为如果自己的HP大于怪物的攻击力或怪物的HP小于自己的攻击力一击毙命没必要浪费回合回HP则发动一次攻击否则就吃一次药恢复HP。然后轮到怪物发动一次攻击自己的HP减去怪物的攻击力然后循环直到怪物HP小于等于0。最后循环的次数就是答案。
参考代码
a, b, c map(int, input().strip().split())
x, y map(int, input().strip().split())
res 0
while x 0: # 循环直到怪物体力小于等于0if a y or b x: # 如果自己的HP大于怪物的攻击力或者怪物的HP小于自己的攻击力x - b # 选择攻击else:a c # 选择吃药回复HPres 1 # 回合加一a - y # 自己受到怪物的攻击HP减少
print(res) 第二题严查枪火 X国最近开始严管枪火。像是“ak”,“m4a1”,“skr”。都是明令禁止的。现在小Q查获了一批违禁物品其中部分是枪支。小Q想知道自己需要按照私藏枪火来关押多少人。只有以上三种枪被视为违法 输入描述第一行输入整数n.(1n10000)表示携带违禁物品的人数。以下n行表示违禁物品的名称。 输出描述输出需要按照私藏枪火来关押的人。 示例 示例输入3 Dsd ak 232asd输出 1 分析
第6期考过的老题以前也写过题解。
没什么好分析的就是依次检查列表中的字符串是否等于这三种枪火所代表的字符串最后输出相等的个数即可。
参考代码
n int(input().strip())
res 0
for _ in range(n):temp input().strip()if temp in {ak, m4a1, skr}:res 1
print(res) 第三题蚂蚁家族 小蚂蚁群是一个庞大的群体在这个蚂蚁群中有n只小蚂蚁 为了保证所有蚂蚁在消息传送的时候都能接收到消息需要在他们之间建立通信关系。就是要求小蚂蚁都可以通过多只或者直接联系到其他人。已知几条小蚂蚁之间有通信关系请问还需要再新建至少多少条关系 输入描述第一行输入整数nmn为小蚂蚁总数m为关系数。(1n,m1000)。以下m行每行m对整数xy。(代表x与y有联系) 输出描述输出最少需要新建关系数。 示例 示例输入4 3 1 2 2 3 3 4输出 0 分析
第12期考过好像并不遥远可以参考以前写的题解。
官方很喜欢考并查集问哥当初解这道题的时候是靠着测试用例的缺陷骗分过了。后来又自己琢磨了使用集合的方法不过这次再次遇到就可以用已经熟悉的并查集模板来解了。
算法原理还是一样先定义并查集的查集函数find()再把每次输入边的顶点合并在一起都指向同一个“祖先”最后统计祖先的个数就表示了现在已存在的连通子图的个数要把它们连在一起只需要个数减一条边就可以了。
参考代码
n, m map(int, input().strip().split())
ants list(range(n1))
def find(i):if ants[i] i: return iants[i] find(ants[i])return ants[i]
for _ in range(m):a, b map(int, input().strip().split())ants[find(a)] find(b)
result set()
for i in ants[1:]:j find(i)result.add(j)
print(len(result)-1)
不过比赛中本题的数据有坑有一个测试数据的节点编号超过了 n于是在查集的时候报了下标越界的错误 所以上面的代码要稍微修改一下。只要增加一个节点最后再判断该节点有没有边即可。 第四题运输石油 某石油公司需要向A、B两地运输石油。两地的需求量不同而一辆车只能装载一定量的石油。经过计算A地需要a辆车B地需要b辆车运输才能满足需求。现在一共有n辆车分布在各地每辆车前往A、B两地运输石油均可以获得一定不等的利润。现在请你安排a辆车前往A地b辆车前往B地运输石油使得在满足A、B两地石油需求的前提下获得最大的利润。每辆车只能前往一地运输石油。 输入描述输入第一行包含三个整数nab分别表示公司的车辆数量和AB两地车辆所需数量保证abn。(1n1000)。接下来有n行每行两个正整数xy分别表示该车完成A地任务的利润和B地任务的利润。 输出描述输出仅包含一个正整数表示最大获得的利润和。 示例 示例输入5 2 2 4 2 3 3 5 4 5 3 1 5输出18分析
题目本身不太难难的是对测试数据的优化。
从题干来看还是背包问题的一个扩展子类三维背包问题。也就是存在两个背包A地和B地两地需要的车的数量类似于普通背包的容积怎样分配物品n辆车类似于体积才能得到最优解最大价值。
既然是背包问题就存在状态转移。我们可以用 的三维数组来表示 辆车中有 辆去往A地 辆去往B地的最大价值。那我们如果增加了一辆车也就是检查第 辆车的时候 的值怎样得到呢这时我们有三个选择
不派这辆车那么 派这辆车去A地那么 因为这辆车去了A地那么前面 辆车里就少派一辆去A地的车派这辆车去B地那么 同上因为这辆车去了B地那么前面 辆车里就少派一辆去B地的车
很显然最终 的值就等于这三项最大值。于是可以得到状态转移方程如下 如果熟练掌握了基础背包问题这里很容易就可以看出因为在状态转移时只用到了 所以可以类似01背包使用循环数组降低空间复杂度减去一维。但是同样地状态转移的时候需要逆序更新。
降维后的转移方程如下 所以到这里我们关于这道题的解法已经很清楚了代码整理如下
参考代码一
n, a, b map(int, input().strip().split())
dp [[0]*(b1) for _ in range(a1)]
for i in range(1, n1):profit_a, profit_b map(int, input().strip().split())for j in range(a, -1, -1): # 因为使用了滚动数组优化空间需要逆序更新for k in range(b, -1, -1): # 同上if j 0: dp[j][k] max(dp[j][k], dp[j-1][k]profit_a)if k 0: dp[j][k] max(dp[j][k], dp[j][k-1]profit_b)
print(dp[a][b])
这里要注意边界问题也就是当 或 时无须从 或 的状态更新过来。
然鹅上面的代码是无法pass这道题的。原因就在于测试数据范围太大而我们的算法时间复杂度是 其中 而测试数据的范围在 1e4计算量级相当于1e12 ()。必须考虑优化。
优化
不幸的是关于三维背包问哥并不知道是否存在能够优化时间复杂度到 甚至更低的算法。但是上面的状态转移过程中很显然存在很多无意义的计算也就是派往A地和B地的车的数量存在 的限制。于是可以通过剪枝来进行一定的优化。
在下面两行代码里、 分别代表派往A地和B地的车的数量而这两个数量的范围使用了 和 。
for j in range(a, -1, -1): for k in range(b, -1, -1):
不难发现当我们只有 辆车的时候
如果 我们最多只能派 辆而不是 辆车去往A地如果 我们最多也只需要派 辆车去A地。
所以我们派往A地的车辆数量的上限是 。
同样地因为我们在 辆车里选择了 辆去A地那么我们最多只能派 辆车去往B地。所以派往B地车辆数量的上限是 。
我们再来看范围的下限。常识里下限应该是0也就是一辆都不派但真的是这样吗
本题所谓的下限也就是在 辆车里最少派多少辆车到两地。以A地为例因为题目要求一定要派 辆车到A地那么我们在 辆车里最少要派的 辆车加上剩下的最多能派往A地的车必须要等于 。剩下的 辆车里最多也只能派 辆车也就是全部派往A地所以最小的 要满足 。显然如果也就是说剩下的车辆数量大于等于 的话 的最小值是 0。于是可以得到 的下限是 。
再来看B地。同样的道理题目要求一定要派 辆车到B地也就是说我们在 辆车里最少要派的 辆车加上剩下的最多能派往B地的车必须要等于 。但是考虑到剩下的车里至少要保留 辆会派往A地所以剩下能派往B地的车数量最多只有 辆。于是最小的 要满足 。展开可以得到 的下限是 。
而在此上下限范围之外的数据我们是压根不需要计算的。因为逻辑不合理它们对最终结果不会产生影响于是我们可以进行剪枝。 更新代码最终得到pass代码如下
参考代码二
n, a, b map(int, input().strip().split())
dp [[0]*(b1) for _ in range(a1)]
for i in range(1, n1):aa, bb map(int, input().strip().split())for j in range(min(i, a), max(0, a-ni)-1, -1):for k in range(min(i-j, b), max(0, b-nai-j)-1, -1):if j 0: dp[j][k] max(dp[j][k], dp[j-1][k]aa)if k 0: dp[j][k] max(dp[j][k], dp[j][k-1]bb)
print(dp[a][b])
由此可见虽然算法的渐进时间复杂度没有改变但是通过剪枝还是可以通过测试用例说明测试数据中存在许多干扰的无用数据想必这也是考点之一吧。 文章转载自： http://www.morning.kgsws.cn.gov.cn.kgsws.cn http://www.morning.zmnyj.cn.gov.cn.zmnyj.cn http://www.morning.hpggl.cn.gov.cn.hpggl.cn http://www.morning.mqnbm.cn.gov.cn.mqnbm.cn http://www.morning.qcwck.cn.gov.cn.qcwck.cn http://www.morning.ydfr.cn.gov.cn.ydfr.cn http://www.morning.nzmqn.cn.gov.cn.nzmqn.cn http://www.morning.hlhqs.cn.gov.cn.hlhqs.cn http://www.morning.nqlx.cn.gov.cn.nqlx.cn http://www.morning.rtlrz.cn.gov.cn.rtlrz.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.fwdln.cn.gov.cn.fwdln.cn http://www.morning.rtbx.cn.gov.cn.rtbx.cn http://www.morning.qkxt.cn.gov.cn.qkxt.cn http://www.morning.ptmgq.cn.gov.cn.ptmgq.cn http://www.morning.zrks.cn.gov.cn.zrks.cn http://www.morning.rfldz.cn.gov.cn.rfldz.cn http://www.morning.zcnfm.cn.gov.cn.zcnfm.cn http://www.morning.ykrss.cn.gov.cn.ykrss.cn http://www.morning.simpliq.cn.gov.cn.simpliq.cn http://www.morning.rgrz.cn.gov.cn.rgrz.cn http://www.morning.gyxwh.cn.gov.cn.gyxwh.cn http://www.morning.drnjn.cn.gov.cn.drnjn.cn http://www.morning.rscrj.cn.gov.cn.rscrj.cn http://www.morning.fbmjl.cn.gov.cn.fbmjl.cn http://www.morning.wxwall.com.gov.cn.wxwall.com http://www.morning.nqrfd.cn.gov.cn.nqrfd.cn http://www.morning.gltmz.cn.gov.cn.gltmz.cn http://www.morning.pmbcr.cn.gov.cn.pmbcr.cn http://www.morning.wtrjq.cn.gov.cn.wtrjq.cn http://www.morning.fnpmf.cn.gov.cn.fnpmf.cn http://www.morning.ktpzb.cn.gov.cn.ktpzb.cn http://www.morning.mnnxt.cn.gov.cn.mnnxt.cn http://www.morning.qgfkn.cn.gov.cn.qgfkn.cn http://www.morning.nqypf.cn.gov.cn.nqypf.cn http://www.morning.pmjw.cn.gov.cn.pmjw.cn http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.lmpfk.cn.gov.cn.lmpfk.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn http://www.morning.xkbdx.cn.gov.cn.xkbdx.cn http://www.morning.nqrdx.cn.gov.cn.nqrdx.cn http://www.morning.snygg.cn.gov.cn.snygg.cn http://www.morning.zwznz.cn.gov.cn.zwznz.cn http://www.morning.bsrp.cn.gov.cn.bsrp.cn http://www.morning.tkrpt.cn.gov.cn.tkrpt.cn http://www.morning.ctrkh.cn.gov.cn.ctrkh.cn http://www.morning.ljjph.cn.gov.cn.ljjph.cn http://www.morning.djbhz.cn.gov.cn.djbhz.cn http://www.morning.clqpj.cn.gov.cn.clqpj.cn http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.ctpfq.cn.gov.cn.ctpfq.cn http://www.morning.yhwyh.cn.gov.cn.yhwyh.cn http://www.morning.tyklz.cn.gov.cn.tyklz.cn http://www.morning.mqfhy.cn.gov.cn.mqfhy.cn http://www.morning.wflsk.cn.gov.cn.wflsk.cn http://www.morning.jfbrt.cn.gov.cn.jfbrt.cn http://www.morning.ntzfj.cn.gov.cn.ntzfj.cn http://www.morning.jhzct.cn.gov.cn.jhzct.cn http://www.morning.ffdyy.cn.gov.cn.ffdyy.cn http://www.morning.syglx.cn.gov.cn.syglx.cn http://www.morning.znqfc.cn.gov.cn.znqfc.cn http://www.morning.lqlhw.cn.gov.cn.lqlhw.cn http://www.morning.bwfsn.cn.gov.cn.bwfsn.cn http://www.morning.qggxt.cn.gov.cn.qggxt.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.xbdrc.cn.gov.cn.xbdrc.cn http://www.morning.fnwny.cn.gov.cn.fnwny.cn http://www.morning.kwqwp.cn.gov.cn.kwqwp.cn http://www.morning.cfnht.cn.gov.cn.cfnht.cn http://www.morning.wbqt.cn.gov.cn.wbqt.cn http://www.morning.sgcdr.com.gov.cn.sgcdr.com http://www.morning.rnmc.cn.gov.cn.rnmc.cn http://www.morning.gbyng.cn.gov.cn.gbyng.cn http://www.morning.kzcfr.cn.gov.cn.kzcfr.cn http://www.morning.sdecsd.cn.gov.cn.sdecsd.cn http://www.morning.rfrxt.cn.gov.cn.rfrxt.cn http://www.morning.pttrs.cn.gov.cn.pttrs.cn http://www.morning.rmkyb.cn.gov.cn.rmkyb.cn http://www.morning.btpll.cn.gov.cn.btpll.cn http://www.morning.cttti.com.gov.cn.cttti.com
