洛谷 P2680 运输计划

Description:

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

洛谷 P3258 [JLOI2014]松鼠的新家

Description:

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。可是这样会导致维尼重复走很多房间,懒惰的维尼不停地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。

维尼是个馋家伙,立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

洛谷 P3128 [USACO15DEC]最大流Max Flow

Description:

Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ($2 \leq N \leq 50,000$), conveniently numbered $1 \ldots N$. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ($1 \leq K \leq 100,000$). For the $i$th such pair, you are told two stalls $s_i$ and $t_i$, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_i$ to $t_i$, then it counts as being pumped through the endpoint stalls $s_i$ and $t_i$, as well as through every stall along the path between them.

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道,隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线,第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力,你需要计算压力最大的隔间的压力是多少。

LibreOJ #2332. 「JOI 2017 Final」焚风现象

Description:

焚风是是由于空气作绝热下沉运动时,因温度升高湿度降低而形成的一种干热风。焚风常出现在山脉背风坡,由山地引发的过山气流在背风坡下沉,使过山气流变得干热的一种风。在高压区,空气下沉也可产生焚风。

IOI 王国永远刮着海风。风从地点 $0$ 依次吹到地点 $1$,地点 $2$ ……直到地点 $N$,共 $N+1$ 个地点。JOI 君住在地点 $N$。地点 $0$ 的海拔 $A_0=0$,地点 $i(1\leqslant i\leqslant N)$ 的海拔为 $A_i$。
地表风的温度随海拔升降而变化。地点 $0$ 在海边,温度为 $0$ 度;对于任一地点 $i(0\leqslant i<N)$,从地点 $i$ 吹到地点 $i+1$ 的风的温差仅取决于两地的海拔差。具体来说:

  • 如果 $A_i=A_{i+1}$,风的温度不变;
  • 如果 $A_i<A_{i+1}$,风每爬升 $1$ 米,温度就会下降 $S$ 度;
  • 如果 $A_i> A_{i+1}$,风每下沉 $1$ 米,温度就会升高 $T$ 度。

IOI 国的地壳运动很强烈。你得到了 $Q$ 天来地壳运动的数据。在第 $j$ 日 $(1\leqslant j\leqslant Q)$,地点 $L_j, L_j+1, \ldots, R_j (1\leqslant L_j\leqslant R_j\leqslant N)$ 的海拔升高了 $X_j$,注意 $X_j$ 可能是负数。
你的任务是,计算每天地壳运动后 JOI 君住所的温度。

洛谷 P1083 借教室

Description:

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。

我们需要处理接下来$n$天的借教室信息,其中第$i$天学校有$r_i$个教室可供租借。共有$m$份订单,每份订单用三个正整数描述,分别为$d_j,s_j,t_j$,表示某租借者需要从第$s_j$天到第$t_j$天租借教室(包括第$s_j$天和第$t_j$天),每天需要租借$d_j$个教室。

我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供$d_j$个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第$s_j$天到第$t_j$天中有至少一天剩余的教室数量不足$d_j$个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

CodeForces GYM 102012 2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest

A. Rikka with Minimum Spanning Trees

Description:

Hello everyone! I am your old friend Rikka. Welcome to Xuzhou. This is the first problem, which is a problem about the minimum spanning tree (MST). I promise you all that this should be the easiest problem for most people.
A minimum spanning tree, or minimum weight spanning tree, is a subset of edges from an edge-weighted undirected graph, which forms a tree with the minimum possible total edge weight that connects all the vertices together without any cycles.
In this problem, Rikka wants you to calculate the summation of total edge weights through all MSTs for a given graph, which obviously equals to the product of the total edge weight in an MST and the total number of different MSTs. Note that two spanning trees are different if the sets of their edges are different. In addition, a disconnected graph could have no MSTs, the number of whose different MSTs is zero.
To decrease the size of the input, Rikka provides an edge-weighted undirected graph via a random number generator with given random seeds, denoted by two integers $k_1$ and $k_2$. Supposing the number of vertices and edges in the graph are $n$ and $m$ respectively, the following code in C++ tells you how to generate the graph and store the $i$-th edge between the vertex $u[i]$ and $v[i]$ with weight $w[i]$ in corresponding arrays. You can use the code directly in your submissions.

img

Also, to decrease the size of the output, your code should output the answer modulo $(10^9 + 7)$.
If you have already learned how to handle that, start your show and omit all the rest of the statement.
To make sure everyone knows how to solve this problem, here Rikka would like to provide for you all an effective practice which can solve the problem and help you all get Accepted!
The first one you need to know is the Kirchhoff’s matrix tree theorem. Given an undirected graph $G$ with $n$ vertices excluding all loops, its Laplacian matrix $L_{n \times n}$ is defined as $(D - A)$, where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. More precisely, in the matrix $L$ the entry $l_{i, j}$ ($i \ne j$) equals to $-m$ where $m$ is the number of edges between the $i$-th vertex and the $j$-th vertex, and $L_{i, i}$ equals to the degree of the $i$-th vertex. Next, construct a matrix $L^{*}$ by deleting any row and any column from $L$, for example, deleting row $1$ and column $1$. The Kirchhoff’s matrix tree theorem shows that the number of spanning trees is exactly the determinant of $L^{*}$, which can be computed in polynomial time.
Now let me explain an algorithm that counts the number of MSTs. The algorithm breaks up the Kruskal’s algorithm for MST into a series of blocks, each of which consists of a sequence of operations about adding edges in a same weight into a multigraph (where a multigraph is a graph, two vertices of which may be connected by more than one edge) whose vertices are components that have been built through the previous block of operations.
Precisely speaking, let’s label the multigraph that has been built after the $i$-th block of operations as $G_i$. Without loss of generality, let’s consider the $0$-th block which has no operation and let $G_0$ be an empty graph with $n$ isolated vertices. The $i$-th block of operations squeezes vertices in $G_{i - 1}$ connected by edges in this block into a single vertex. The result is exactly the graph $G_i​$.
If you know the cardinal principle of Kruskal’s algorithm pretty well, you may find that the number of MSTs is the product of the numbers of spanning trees in every component of the graph for each block-defining weight. Actually, the number of edges for a certain weight is fixed in all MSTs, based on the greedy-choice strategy in Kruskal’s algorithm. Finally, the Kirchhoff’s matrix tree theorem helps you compute the numbers of spanning trees for graphs.

Aizu 1309 The Two Men of the Japanese Alps

Description:

Two experienced climbers are planning a first-ever attempt: they start at two points of the equal altitudes on a mountain range, move back and forth on a single route keeping their altitudes equal, and finally meet with each other at a point on the route. A wise man told them that if a route has no point lower than the start points (of the equal altitudes) there is at least a way to achieve the attempt. This is the reason why the two climbers dare to start planning this fancy attempt.

The two climbers already obtained altimeters (devices that indicate altitude) and communication devices that are needed for keeping their altitudes equal. They also picked up a candidate route for the attempt: the route consists of consequent line segments without branches; the two starting points are at the two ends of the route; there is no point lower than the two starting points of the equal altitudes. An illustration of the route is given in Figure E.1 (this figure corresponds to the first dataset of the sample input).

img

Figure E.1: An illustration of a route

The attempt should be possible for the route as the wise man said. The two climbers, however, could not find a pair of move sequences to achieve the attempt, because they cannot keep their altitudes equal without a complex combination of both forward and backward moves. For example, for the route illustrated above: a climber starting at p1 (say A) moves to s, and the other climber (say B) moves from p6 to p5; then A moves back to t while B moves to p4; finally A arrives at p3 and at the same time B also arrives at p3. Things can be much more complicated and thus they asked you to write a program to find a pair of move sequences for them.

There may exist more than one possible pair of move sequences, and thus you are requested to find the pair of move sequences with the shortest length sum. Here, we measure the length along the route surface, i.e., an uphill path from (0, 0) to (3, 4) has the length of 5.

洛谷 P3649 [APIO2014]回文串

Description:

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s,求所有回文子串中的最大存在值。

|