2018-team11-006

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题解 ==
A
题意：给一个h*w(1000*1000)的迷宫，每个格子到其他任意格子仅有一条路径，在格子中按顺序选择m(m<=10000)个，问总路程
做法：转成树，两点路径长度求lca用深度随便算
B
题意：给出两个圆分别是蓝圆与红圆，给两个点为起点与终点，红圆区域不能走，问起点到终点最短距离
'''保证红圆被蓝圆包含，起点到终点直线路径一定经过红圆'''
做法：sb几何，从起点与终点对圆作切线，两条路径算完取较小的。都怪'''sbsg'''给我讲题意把约束条件给漏了
C
题意：n(<=1e3)个点m(<=5e3)条边DAG，有正边权，问从任意点出发到任意点结束路径最大边权和
做法：枚举每个点为起点，dp随便搞
D
题意：给出金字塔的第n(<=1e6)层（有n个数），问这层可以有多少不同情况得到
做法：第一个数确定就能确定整个序列，同时第一个数+1相当于奇数位都+1，偶数位都-1；先假定第一位为0，计算出每一位在第一位为0时的情况，然后每一位根据限制调整，计算出第一位的最大和最小值
E
题意：将分子分母均为实数的分数化为分子分母都为质数的分数，不能输出impossible
做法：去掉小数点当成整数约分成最简分数，如果1/1输出2/2；如果分子分母有一个为合数即impossible
F
题意：给n(<=1e5)个数，问能否选出两个数互相减，当一个数小于0以后另一个数为1
做法：找n个数中有无斐波那契数列的相邻两项
G
题意：牛逼几何我不会
H
题意：

题解

A

题意：给一个h*w(1000*1000)的迷宫，每个格子到其他任意格子仅有一条路径，在格子中按顺序选择m(m<=10000)个，问总路程

做法：转成树，两点路径长度求lca用深度随便算

B

题意：给出两个圆分别是蓝圆与红圆，给两个点为起点与终点，红圆区域不能走，问起点到终点最短距离

保证红圆被蓝圆包含，起点到终点直线路径一定经过红圆

做法：sb几何，从起点与终点对圆作切线，两条路径算完取较小的。都怪sbsg给我讲题意把约束条件给漏了

C

题意：n(<=1e3)个点m(<=5e3)条边DAG，有正边权，问从任意点出发到任意点结束路径最大边权和

做法：枚举每个点为起点，dp随便搞

D

题意：给出金字塔的第n(<=1e6)层（有n个数），问这层可以有多少不同情况得到

做法：第一个数确定就能确定整个序列，同时第一个数+1相当于奇数位都+1，偶数位都-1；先假定第一位为0，计算出每一位在第一位为0时的情况，然后每一位根据限制调整，计算出第一位的最大和最小值

E

题意：将分子分母均为实数的分数化为分子分母都为质数的分数，不能输出impossible

做法：去掉小数点当成整数约分成最简分数，如果1/1输出2/2；如果分子分母有一个为合数即impossible

F

题意：给n(<=1e5)个数，问能否选出两个数互相减，当一个数小于0以后另一个数为1

做法：找n个数中有无斐波那契数列的相邻两项

G

题意：牛逼几何我不会

H

题意：