0%

题意描述

洛谷链接

LibreOJ 链接

Sylvia 是一个热爱学习的女孩子。

前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。

Sylvia 所在的方阵中有 \(n \times m\) 名学生,方阵的行数为 \(n\),列数为 \(m\)

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中 的学生从 \(1\)\(n \times m\) 编上了号码。即:初始时,第 \(i\) 行第 \(j\) 列 的学生的编号是 \((i-1)\times m + j\)

然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天 中,一共发生了 \(q\) 件这样的离队事件。每一次离队事件可以用数对 \((x,y) (1 \le x \le n, 1 \le y \le m)\) 描述,表示第 \(x\) 行第 \(y\) 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达 这样的两条指令:

  1. 向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条 指令之后,空位在第 \(x\) 行第 \(m\) 列。

  2. 向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条 指令之后,空位在第 \(n\) 行第 \(m\) 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后, 下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 \(n\) 行 第 \(m\) 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学 的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后 方阵中同学的编号可能是乱序的。

阅读全文 »

题意描述

Codeforces 链接

Alice 和 Bob 玩游戏,游戏中有 \(n\) 张标有 \(1 \sim n\) 数字卡牌(\(n\) 为偶数),开局时 Alice 和 Bob 均有 \(\frac{n}{2}\) 张。在每一轮中,其中一人先打出自己一张卡牌,然后另一人再打出自己的一张卡牌。若后手无法打出比前一人打出卡牌数字大的卡牌,则后手输;否则进入下一轮。该轮的后手为下一轮的先手。若卡牌打完则平局。在这个游戏中,Alice 为第一轮的先手。假设双方均按最优策略出牌,求 Alice 赢、Bob 赢和平局的情况数。答案对 \(998244353\) 取模。

阅读全文 »

题意描述

洛谷链接

LibreOJ 链接

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 \(m\) 条赛道。

C 城一共有 \(n\) 个路口,这些路口编号为 \(1,2, \cdots , n\),有 \(n − 1\) 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 \(i\) 条道路连接的两个路口编号为 \(a_i\)\(b_i\),该道路的长度为 \(l_i\)。借助这 \(n − 1\) 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 \(e_1, e_2, \cdots , e_k\),满足可以从某个路口出发,依次经过道路 \(e_1, e_2, \cdots , e_k\)(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的 \(m\) 条赛道中长度最小的赛道长度最大(即 \(m\) 条赛道中最短赛道的长度尽可能大)。

阅读全文 »

题意描述

洛谷链接

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 的物流公司完成阶段性工作所需要的最短时间是多少?

阅读全文 »

又来记流水账了 QWQ

Day 0

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

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

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

阅读全文 »

题意描述

洛谷链接

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

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

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

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

阅读全文 »

题意描述

洛谷链接

根据宪法,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\)

阅读全文 »

题意描述

洛谷链接

小 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]\),数据保证必定存在严格次小生成树。

阅读全文 »