10月7日

· · 个人记录

上午

问题 A: Sightseeing Cows

题目描述

Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time.

Fortunately, they have a detailed city map showing the L (2 <= L <= 1000) major landmarks (conveniently numbered 1.. L) and the P (2 <= P <= 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction.

While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values F_i (1 <= F_i <= 1000) for each landmark i.

The cows also know about the cowpaths. Cowpath i connects landmark L1_i to L2_i (in the direction L1_i -> L2_i) and requires time T_i (1 <= T_i <= 1000) to traverse.

In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off.

Help the cows find the maximum fun value per unit time that they can achieve.

给定一张 L 个点、P 条边的有向图，每个点都有一个权值 ，每条边都有一个权值

。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

输入

第一行包含两个整数 L 和 P。

接下来 L 行每行一个整数，表示 f[i]。

再接下来 P 行，每行三个整数 a，b，t[i]，表示点 a和 b之间存在一条边，边的权值为 t[i]。

输出

输出一个数表示结果，保留两位小数。

题解：

spfa跑n遍。

问题 B: 升降梯上

题目描述

开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。 Nescafé 之塔一共有N 层，升降梯在每层都有一个停靠点。手柄有M 个控制槽，第i个控制槽旁边标着一个数Ci，满足C1<C2<C3<...<CM。如果Ci>0，表示手柄扳动到该槽时，电梯将上升Ci 层；如果Ci<0，表示手柄扳动到该槽时，电梯将下降-Ci 层；并且一定存在一个Ci=0，手柄最初就位于此槽中。注意升降梯只能在1~N 层间移动，因此扳动到使升降梯移动到1 层以下、N 层以上的控制槽是不允许的。 电梯每移动一层，需要花费2 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费1 秒钟时间。探险队员现在在1 层，并且想尽快到达N 层，他们想知道从1 层到N 层至少需要多长时间？

输入

第一行两个正整数N、M。 第二行M 个整数C1、C2...CM。

输出

输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1。

题解：

dij最短路

问题 C: 银河英雄传说

题目描述

公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经展开，银河的历史又翻过了一页……

输入

第一行有一个整数T（1 <= T <= 500,000），表示总共有T条指令。 以下有T行，每行有一条指令。指令有两种格式：

  1. M i j ：i和j是两个整数（1 <= i , j <= 30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
  2. C i j ：i和j是两个整数（1 <= i , j <= 30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

    输出

    你的程序应当依次对输入的每一条指令进行分析和处理： 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息； 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

    题解：

    并查集

问题 D: 导弹防御塔

题目描述

Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。 所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。 现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。

输入

第一行五个正整数N,M,T1,T2,V。 接下来M行每行两个整数，代表入侵者的坐标。 接下来N行每行两个整数，代表防御塔的坐标。

输出

输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。

题解：

二分查找+二分图

问题 E: 搭配购买(buy)

题目描述

Joe 觉得云朵很美，决定去山上的商店买一些云朵。商店里有 n 朵云，云朵被编号为 1，2，…...，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。 但是 Joe 的钱有限，所以他希望买的价值越多越好。

输入

第1 行 n，m，w，表示 n 朵云，m 个搭配，Joe 有 w 的钱。 第2~n+1 行，每行 ci，di 表示 i 朵云的价钱和价值。 第n+2~n+1+m 行，每行 ui，vi，表示买 ui 就必须买 vi，同理，如果买 vi 就必须买 ui。

输出

一行，表示可以获得的最大价值。

题解：

并查集背包

问题 F: 最优乘车(travel)

题目描述

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。 一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达 S 公园。 现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。 写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到 S 公园的过程中换车的次数最少。

输入

第一行有两个数字 M 和 N(1<=M<=100 1<N<=500），表示开通了 M 条单程巴士线路，总共有 N 个车站。从第二行到第 M 刊行依次给出了第 1 条到第 M 条巴士线路的信息。其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。

输出

只有一行。如果无法乘巴士从饭店到达 S 公园，则输出"N0"，否则输出你的程序所找到的最少换车次数，换车次数为 0 表示不需换车即可到达。

题解：

floyd找最短路即可

下午

问题 A: [TJOI2013]松鼠聚会

题目描述

草原上住着一群小松鼠，每个小松鼠都有一个家。时间长了，大家觉得应该聚一聚。但是草原非常大，松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点 (x,y)表示,两个点的距离定义为点 (x,y)和它周围的 8个点 (x−1,y)，(x+1,y)，(x,y−1)，(x,y+1)，(x−1,y+1)，(x−1,y−1)，(x+1,y+1)，(x+1,y−1) 距离为 1。

输入

第一行是一个整数 N，表示有多少只松鼠。接下来 N 行，第 i 行是两个整数 x和 y，表示松鼠 i 的家的坐标。

输出

一个整数，表示松鼠为了聚会走的路程和最小是多少。

题解：

切比雪夫距离转成曼哈顿距离\ 公式：\ 切比雪夫：max(|xi-xj|,|yi-yj|)\ 曼哈顿：|xi-xj|+|yi-yj|

曼哈顿转切比雪夫：\ |xi-xj|+|yi-yj|\ =max(xi-xj,xj-xi)+max(yi-yj,yj-yi)

=max(xi-xj+yi-yj,xj-xi+yi-yj,xi-xj+yj-yi,xj-xi+yj-yi)

=max(|xi+yi-xj-yj|,|xi-yi-xj+yj|)

所以将x转换为x+y，y转化为x-y后的坐标的切尔雪夫距离等同于原坐标的曼哈顿距离

上面那段证反了，但我懒得删了

切尔雪夫转曼哈顿：\ max(|xi-xj|,|yi-yj|)\ =(||xi-xj|+|yi-yj||-||xi-xj|-|yi-yj||)/2

=|(xi+yi）-（xj+yj)|/2+|(xi-yi）-（xj-yj)|/2

所以将x转换为(x+y)/2，y转化为(x-y)/2后的坐标的切尔雪夫距离等同于原坐标的曼哈顿距离

然后前缀和求曼哈顿距离，每次效率O（1）

问题 B: [TJOI2013]拯救小矮人

题目描述

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。

对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。

如果我们利用矮人1，矮人2，矮人3,。。。矮人k

搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就不能再搭人梯了。

我们希望尽可能多的小矮人逃跑，问最多可以使多少个小矮人逃跑。

第一行一个整数N， 表示矮人的个数，

接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）

输入

第一行一个整数N， 表示矮人的个数，

接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）

输出

一个整数表示对多可以逃跑多少小矮人

题解：

贪心+dp

问题 C: [TJOI2013]最长上升子序列

题目描述

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

输入

第一行一个整数N，表示我们要将1到N插入序列中。

接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

输出

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

题解：

这道题可以用treap，也可以用树状数组和线段树维护区间最大值

用treap就边输入边维护（~~我不会~~）

我的写法是倒序插入查找最后的位置，再顺序更新当前的最大子序列长度

但是，它WA了

于是我改用线段树（向黑恶势力低头）

然后就AC了