XenonWZH's Blog

卷了个寂寞？

0%

发表于 更新于 分类于 ， Disqus：

题意描述

洛谷链接

LibreOJ 链接

公元 \(2044\) 年，人类进入了宇宙纪元。

L 国有 \(n\) 个星球，还有 \(n - 1\) 条双向航道，每条航道建立在两个星球之间，这 \(n - 1\) 条航道连通了 L 国的所有星球。

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

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

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

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

阅读全文 »

发表于 更新于 分类于 ， Disqus：

又来记流水账了 QWQ

Day 0

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

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

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

阅读全文 »

发表于 分类于 ， Disqus：

题意描述

洛谷链接

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

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

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

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

阅读全文 »

发表于 分类于 ， Disqus：

题意描述

洛谷链接

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

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

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

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

对于 \(100\%\) 的数据，\(1 \leq n \leq 8000\)，\(0 \leq m \leq 20000\)，\(1 \leq a < b \leq 8000\)。

阅读全文 »

发表于 分类于 ， Disqus：

题意描述

洛谷链接

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

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

对于 \(100\%\) 的数据， \(N\le 10^5\)，\(M\le 3\times10^5\)，边权 \(\in [0,10^9]\)，数据保证必定存在严格次小生成树。

阅读全文 »

发表于 分类于 ， Disqus：

题意描述

洛谷链接

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

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

对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

题意描述

洛谷链接

LibreOJ 链接

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

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

有 \(q\) 次操作，操作有以下类型:

  • \(1 \ x \ y\)：在 \(x\) 号序列末尾插入数字 \(y\)。保证 \(x\) 号序列存在，且 \(1 \le x, y \le n + q\)。
  • \(2 \ x\)：删除 \(x\) 号序列末尾的数字，保证 \(x\) 号序列存在、非空，且 \(1 \le x \le n + q\)。
  • \(3 \ m \ x_1 \ x_2 \ x_m\)：将 \(x_1, x_2, \ldots, x_m\) 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 \(-1\)。数据保证对于任意 \(1 \le i \le m\)，\(x_i\) 是一个仍然存在的序列，\(1 \le x_i \le n + q\)，且拼接得到的序列非空。注意：不保证 \(\boldsymbol{x_1, \ldots, x_m}\) 互不相同，询问中的合并操作不会对后续操作产生影响。
  • \(4 \ x_1 \ x_2 \ x_3\)：新建一个编号为 \(x_3\) 的序列，其为 \(x_1\) 号序列后顺次添加 \(x_2\) 号序列中数字得到的结果，然后删除 \(x_1, x_2\) 对应的序列。此时序列 \(x_3\) 视为存在，而序列 \(x_1, x_2\) 被视为不存在，在后续操作中也不会被再次使用。保证 \(1 \le x_1, x_2, x_3 \le n + q\)、\(x_1 \ne x_2\)、序列 \(x_1, x_2\) 在操作前存在、且在操作前没有序列使用过编号 \(x_3\)。

假定 \(C_l = \sum l_i\) 代表输入序列长度之和，\(C_m = \sum m\) 代表所有操作 \(3\) 需要拼接的序列个数之和；对于所有测试数据，保证 \(1 \le n, q, C_m, C_l \le 5 \times {10}^5\)。

阅读全文 »