Beyond the Void

问题简述

能量场中有N个粒子，每个粒子都有一个质量m和结合系数c，两个粒子a,b合并时会产生m_am_b(c_a - c_b)的能量。(1)找出两个粒子相结合，使得产生的能量最大。(2)从中找出任意k个粒子排列成一个环，相邻两个粒子分别合并，使得总能量最大，产生负能量的粒子必须是环上连续的一段。

问题分析

乍一看这个问题的第一问好像很简单，枚举每对粒子即可，但是时间复杂度是O(N²)的，而且难以想到如何优化。第二问则更加困难，搜索、动态规划是肯定不行的，贪心、图论也难以找到建模方式。分析发现这个问题可以归约到一个0/1规划问题，如果没有特殊性将无法解决，而特殊性无非在于能量产生的公式，因此将目光聚焦到这个公式上，对公式进行一些变形：

• m_am_b(c_a - c_b)
• = m_am_bc_a - m_am_bc_b
• = m_ac_am_{b –} m_bc_bm_a
• 设x_i=m_ic_i，y_i=m_i则原式
• = x_a*y_b – x_b*y_a

Read the rest of this entry »

问题简述

平面上有一些笔画，笔画两端为半圆，中部为矩形，笔画可以互相重叠。任务是求平面上笔画的总面积。 Read the rest of this entry »

这道题我的方法是二分判断+计算几何。

首先要找到多边形的边界，可以用四个点分别表示多边形上下左右边界的一个顶点。寻找边界可以用二分的方法。由于已知原点一定在多边形内或边上，寻找左边界就可以从x取值-10000到0之间二分答案，其余边界以此类推。

确定边界后，接着要确定每个每个顶点的位置，由于这是一个凸多边形，而且没有边与坐标轴平行，所以从左界点到下界点之间的一段折线斜率一定是严格单调递增的，类似的相邻两个边界点之间的一段折线的斜率也都是单调的。于是我们可以二分答案，确定折线每条线段的端点。最后在按照极角排序好的顶点顺序求出多边形面积，顺序输出每个顶点坐标。其实再写程序时如果求折线端点的顺序恰当，顶点就是直接排好的。

为了尽量减少询问次数，可以把已经询问过的记录下来，以免重复询问。计算几何题一般来说细节较多，代码量大，很难一次写对。再加上这是一个交互式题，我调了好长时间。由于询问次数的限制，我的程序不能拿到满分，后面有几个点都是8分9分。谁要是能写出满分的程序，我一定拜读。
Read the rest of this entry »

我的计划就从NOI1997开始。NOI1997一共有6道题，分别是[卫星覆盖][积木游戏][竞赛排名][最佳游览][最优乘车][文件匹配]。这一年的6个题难易分布均衡，做完后收获不小。

其中[竞赛排名]和[最佳游览]是两个最简单的题，但是往往细节是容易忽视的。[积木游戏]和[最优乘车]难度属于中等，分别是动态规划和构造最短路径解题。[卫星覆盖]和[文件匹配]属于较难题，用到了[卫星覆盖]离散化或者立体切割的方法，而[文件匹配]是搜索中的难题，需要很多的优化。

做这些题我花了4天的时间，进度还算正常，希望能继续保持下去。今后做题的宗旨是“不求多，不求快，但求精”。

Read the rest of this entry »

很明显，这个题是求连通块的个数。关键在于正确判断两个矩形相交。

我们知道，在一维的数轴上，两个区间[a,b] [c,d] (a<=b)，这两个区间相交的充分必要条件是c<=b。对于题中所述的边平行于坐标轴的矩形，我们需要分别判断x轴方向和y轴方向都相交，那么这个矩形一定相交。

假设我们对于给定的两个矩形A，B，A矩形的左下点坐标为(A.x1,A.y1)，右上点坐标(A.x2,A.y2)，同理B点，判断这两个矩形相交，要分为以下四种情况

• 情况1：A在B左下 (A.x1 <= B.x1 且 A.y1 <= B.y1)
  • 该情况下两个矩形相交的条件是 (B.x1<=A.x2 且 B.y1<=A.y2)

• 情况2：A在B左上 (A.x1 <= B.x1 且 A.y1 >= B.y1)
  • 该情况下两个矩形相交的条件是 (B.x1<=A.x2 且 A.y1<=B.y2)

• 情况3：A在B右下 (A.x1 >= B.x1 且 A.y1 <= B.y1)
  • 该情况下两个矩形相交的条件是 (A.x1<=B.x2 且 B.y1<=A.y2)

• 情况4：A在B左上 (A.x1 >= B.x1 且 A.y1 >= B.y1)
  • 该情况下两个矩形相交的条件是 (A.x1<=B.x2 且 A.y1<=B.y2)

根据以上四种情况分类讨论，可以判断A和B是否相交。但是以上方法会造成一个遗漏，就是按题意如果两个矩形只有一个公共点，不能算作相交。对于这种特殊判断，需要排除只有一个交点的状态。

• 情况1：A在B左下 (A.x1 <= B.x1 且 A.y1 <= B.y1)
  • 该情况下要排除(A.x2==B.x1 且 A.y2==B.y1)的状态

• 情况2：A在B左上 (A.x1 <= B.x1 且 A.y1 >= B.y1)
  • 该情况下要排除(A.x2==B.x1 且 A.y1==B.y2)的状态

• 情况3：A在B右下 (A.x1 >= B.x1 且 A.y1 <= B.y1)
  • 该情况下要排除(A.x1==B.x2 且 A.y2==B.y1)的状态

• 情况4：A在B左上 (A.x1 >= B.x1 且 A.y1 >= B.y1)
  • 该情况下要排除(A.x1==B.x2 且 A.y1==B.y2)的状态

根据以上方法，我们就可以判断每对矩形是否相交了。接下来要求出所有的连通块，由于N多达7000，一般的O(N^2)的广搜会超时，需要用并查集求连通块。

初始时把每个矩形作为单独的一个集合，如果两个矩形相交，合并这两个矩形所属的集合，最后统计剩余的集合数，就是连通块的个数。这样时间复杂度虽然还近似是O(N^2)，但是会减少搜索时许多无用的操作，所以可以解决问题。

Read the rest of this entry »