2016-C02-team1

从 Trac 迁移的文章

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

原文章内容如下：

jtjl

== 流水账 ==

== 总结 ==

== 题解 ==

=== A. Lobby [JTJL] ===

签到

=== B. Cameras [JTJL] ===

签到

=== C. Robot [JTJL] ===

SGU472/POI1999有一个类似的推箱子题，是求最短路。赖陆航在20100326的ppt中给出了一个有趣的O((n+m)^3^)的做法。[[BR]]
本题的数据范围是1000。考虑只需要判断是否联通，只需要求出双联通的情况。考虑对于图中每个格子，当箱子在该点上时，能否在箱子附近的四个格子中移动。只有当该点为割点时才会造成无法到达的情况，所以跑一遍Tarjan求出这个，然后用f[i][j][k]表示箱子在(i,j)，k表示robot在箱子的哪个方向，bfs一遍即可。[[BR]]

=== D. Laser Game [JTJL] ===

先求出射线间的交点, 删除射线端点到第一个交点的线段，然后对每个点上的线段极角排序之后，建原图的对偶图。显然对偶图的点和边的数量都是n^2^，判定s和t的区域之后跑一遍最短路即可[[BR]]

=== E. Billboard [JTJL] ===

枚举子矩阵的左右边界，然后枚举下边界的同时用平衡树维护上边界的移动即可，复杂度为O(n^3^logn)[[BR]]
~~听说好像set或者heap就可以啦~~[[BR]]

=== F. Funfair [JTJL] ===

考察i和j放置的先后顺序，可以得到L*(1-P)/(P*A)越大的放在前面越有利。所以按照这个顺序排序之后就可以打牌了。[[BR]]

=== G. Beehive [JTJL] ===

剪切变换到直角坐标系，预处理所有点的坐标后加加减减即可。[[BR]]

=== H. DNA Sequencing [JTJL] ===

数据范围比较小，直接用set维护当前答案集，从后往前枚举删除情况，发现合法并不在答案集合中加入即可。由于越长的合法字符串一定比短的优，所以贪心是正确的。[[BR]]
~~刚开始有点手抽写了Trie，然后在上面dp，大概也是能过的~~[[BR]]

=== I. Cafebazaar [JTJL] ===

最大费用流，用负INF边来强制选择即可，不需要上下界[[BR]]

=== J. Fence [JTJL] ===

凸包上的点是关键点[[BR]]

== 补题 ==

=== JTJL ===

 * 口胡: C D E

jtjl

流水账

总结

题解

A. Lobby [JTJL]

签到

B. Cameras [JTJL]

签到

C. Robot [JTJL]

SGU472/POI1999有一个类似的推箱子题，是求最短路。赖陆航在20100326的ppt中给出了一个有趣的O((n+m)³)的做法。

本题的数据范围是1000。考虑只需要判断是否联通，只需要求出双联通的情况。考虑对于图中每个格子，当箱子在该点上时，能否在箱子附近的四个格子中移动。只有当该点为割点时才会造成无法到达的情况，所以跑一遍Tarjan求出这个，然后用f[i][j][k]表示箱子在(i,j)，k表示robot在箱子的哪个方向，bfs一遍即可。

D. Laser Game [JTJL]

先求出射线间的交点, 删除射线端点到第一个交点的线段，然后对每个点上的线段极角排序之后，建原图的对偶图。显然对偶图的点和边的数量都是n²，判定s和t的区域之后跑一遍最短路即可

E. Billboard [JTJL]

枚举子矩阵的左右边界，然后枚举下边界的同时用平衡树维护上边界的移动即可，复杂度为O(n³logn)

听说好像set或者heap就可以啦

F. Funfair [JTJL]

考察i和j放置的先后顺序，可以得到L*(1-P)/(P*A)越大的放在前面越有利。所以按照这个顺序排序之后就可以打牌了。

G. Beehive [JTJL]

剪切变换到直角坐标系，预处理所有点的坐标后加加减减即可。

H. DNA Sequencing [JTJL]

数据范围比较小，直接用set维护当前答案集，从后往前枚举删除情况，发现合法并不在答案集合中加入即可。由于越长的合法字符串一定比短的优，所以贪心是正确的。

刚开始有点手抽写了Trie，然后在上面dp，大概也是能过的

I. Cafebazaar [JTJL]

最大费用流，用负INF边来强制选择即可，不需要上下界

J. Fence [JTJL]

凸包上的点是关键点

补题

JTJL

• 口胡: C D E