0%

题意描述

洛谷链接

LibreOJ 链接

公元 2044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n1 条双向航道,每条航道建立在两个星球之间,这 n1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

阅读全文 »

又来记流水账了 QWQ

Day 0

由于成都疫情一直在家,复习了一下初赛,然后继续刷题。由于现在基本等于停课状态准备算比较充分。

今年是线上考,事先试了一下设备。刷了一套初赛题之后就在洛谷上刷其它题去了(逃 还是复赛题有意思

补了几集《四月是你的谎言》就睡觉了。

阅读全文 »

题意描述

洛谷链接

大会的规则如下:每位参赛的选手可以得到 n 种材料,选手可以自由选择用满式或是汉式料理将材料当成菜肴。

大会的评审制度是:共有 m 位评审员分别把关。只要参赛者能在这两种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。

但大会后来发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的参赛者最多只能通过部分评审员的审查而不是全部,所以可能会发生没有人通过考核的情形。

所以大会希望有人能写一个程序来判断,所选出的 m 位评审,会不会发生没有人能通过考核的窘境,以便协会组织合适的评审团。

阅读全文 »

题意描述

洛谷链接

根据宪法,Byteland 民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是,由于某些党派代表之间的不和睦而使得这件事存在障碍。 此委员会必须满足下列条件:

  • 每个党派都在委员会中恰有 1 个代表。
  • 如果 2 个代表彼此厌恶,则他们不能都属于委员会。

每个党在议会中有 2 个代表。代表从 1 编号到 2n。 编号为 2i12i 的代表属于第 i 个党派。

任务:写一程序读入党派的数量和关系不友好的代表对,计算决定建立和平委员会是否可能,若行,则列出委员会的成员表。

对于 100% 的数据,1n80000m200001a<b8000

阅读全文 »

题意描述

洛谷链接

小 C 最近学了很多最小生成树的算法,Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:如果最小生成树选择的边集是 EM,严格次小生成树选择的边集是 ES,那么需要满足:(value(e) 表示边 e 的权值) eEMvalue(e)<eESvalue(e)

这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。

对于 100% 的数据, N105M3×105,边权 [0,109],数据保证必定存在严格次小生成树。

阅读全文 »

题意描述

洛谷链接

首先村落里的一共有 n 座房屋,并形成一个树状结构。然后救济粮分 m 次发放,每次选择两个房屋 (x, y),然后对于 xy 的路径上(含 xy)每座房子里发放一袋 z 类型的救济粮。

然后深绘里想知道,当所有的救济粮发放完毕后,每座房子里存放的最多的是哪种救济粮。

对于 100% 测试数据,保证 1n,m1051a,b,x,yn1z105

阅读全文 »

题意描述

洛谷链接

LibreOJ 链接

对于一个序列,定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入,在本题中请以题面中给出的定义为准。

一开始给定 n 个长度不一的正整数序列,编号为 1n,初始序列可以为空。这 n 个序列被视为存在,其他编号对应的序列视为不存在。

q 次操作,操作有以下类型:

  • 1 x y:在 x 号序列末尾插入数字 y。保证 x 号序列存在,且 1x,yn+q
  • 2 x:删除 x 号序列末尾的数字,保证 x 号序列存在、非空,且 1xn+q
  • 3 m x1 x2 xm:将 x1,x2,,xm 号序列顺次拼接,得到一个新序列,并询问其众数。如果不存在满足上述条件的数,则返回 1。数据保证对于任意 1imxi 是一个仍然存在的序列,1xin+q,且拼接得到的序列非空。注意:不保证 x1,,xm 互不相同,询问中的合并操作不会对后续操作产生影响。
  • 4 x1 x2 x3:新建一个编号为 x3 的序列,其为 x1 号序列后顺次添加 x2 号序列中数字得到的结果,然后删除 x1,x2 对应的序列。此时序列 x3 视为存在,而序列 x1,x2 被视为不存在,在后续操作中也不会被再次使用。保证 1x1,x2,x3n+qx1x2、序列 x1,x2 在操作前存在、且在操作前没有序列使用过编号 x3

假定 Cl=li 代表输入序列长度之和,Cm=m 代表所有操作 3 需要拼接的序列个数之和;对于所有测试数据,保证 1n,q,Cm,Cl5×105

阅读全文 »