CF1601B Frog Traveler

题目大意

有一只青蛙掉到了井底,这口井被划分为 $n+1$ 个位置,井口是 $0$ ,井
底是 $n$ 。

现在这只青蛙想跳出这口井,假设它当前在位置 $i$,则它可以向上跳 $0$ 到 $a_i$ 的任意整数距离。

又因为井口很滑,所以如果青蛙跳到了位置 $j$,则它会往下滑 $b_j$ 个位置。

给定 $n, a, b$,你需要求出青蛙最少跳多少次才能跳出井(跳到位置 $0$ ),并给出方案。

$1 \leq n \leq 3 \times 10^5$

CF1419F Rain of Fire

显然这题答案具有单调性,现在我们考虑给定一个$T$怎么check

枚举答案,对于$(i,j)(i<j)$,若$i<j$且$i+j$是完全平方数,则从$i$向$j$连一条边

然后跑最小路径覆盖(可以参照LOJ 6002)

方案输出也类似上一题

1.建立两个集合$x$和$y$

2.如果有一条边$<u,v>$,则从$x$集合中的$u$点连向$y$集合的$v$点,容量为$inf$

3.从$s$向$x$中每一个点连边,从$y$中每一个点向$t$连边,容量为$1$

和LOJ #6004圆桌聚餐很像

建模:

1.从源点向每道试题$x_i$连一条容量为$1$的边

2.从每种类型$y_i$向汇点连一条容量为该类型需求数量的边

3.如果试题$x_i$属于类型$y_i$则从$x_i$向$y_i$连一条容量为$1$的边

然后跑裸的网络最大流,如果最大流$\not=$需求试题总数则无解

方案:

对于每种类型,它连出的所有满流量边即为该类型所对应的试题

建模:

1.从源点向每个单位$x_i$连边,容量是该单位的人数

2.从每张餐桌$y_i$向汇点连边,容量是该餐桌能容纳的人数

3.从每个单位$x_i$向每张餐桌$y_j$连边,容量为$1$

如果最大流量等于所有单位人数之和,则有解,否则无解。

方案:

对于每个单位$x_i$,该单位向$y$集合连出的所有满流量边即为该单位人员的安排情况(证明显然

很简单的网络流

对于每个正飞行员,从源点向它连一条容量为$1$的边

对于每个副飞行员,从它向汇点连一条容量为$1$的边

对于每一对可以配对的正/副飞行员,从正飞行员向副飞行员连一条容量为$1$的边

「算法笔记」Dijkstra

前言

  • $SPFA​$算法由于它上限 $O(NM) = O(VE)​$的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:$dijkstra​$.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×