自从暑假里偶然做到了 PKU 3525 之后，我就发现自己在几何题方面还有一定的欠缺。于是我又开始学了一些东西，比如 O(N logN) 求凸包、旋转卡尺（ROTATING CALIPER）以及多边形

我想UVA 11275这道题一定会令我很难忘。因为它不仅让我因为一个错的算法栽进去了三天，而且它还带领我走进了三维几何题的大门。题意很简单，给出两个三维空间中的三角形（也就是一个平面上用三条边包围起来

首先，为了说话方便，列出一些术语： 在启发式搜索中，对于每个状态 x，启发函数 f(x) 通常是这样的形式： f(x) = g(x) + h(x) 其中 g(x) 是从初始状态走到 x 所花的代价；h(x) 是从 x 走到目标状态所需要的代价的估计值。 相对于 h(x)，还有一个概念叫 h*(x)，表示从 x 走到目标状态所需要的实际最小代价（当然，这个值有时我们是事先无法知道的）。 如果在你的启发函数里，能保证 h(x) = h*(x)，也就是说，你不能高估了从 x 走到目标状态所需要的代价，

UVA110 题目要求输入一个整数，然后输出一个pascal的可运行的程序，但程序中只能宥比较，if，else，if else等的语句，在程序中使用了递归算法，写好后觉得这个类似与一个生成1.。。。n的所有数的排列数 #include stdio.h #include stdlib.h #include assert.h #define MAX 9 #define STEP 2 struct meta { int num; int var[MAX]; } Meta; void space(int

如果所有字符串的长度之和是L，则下面介绍的这个算法的平均效率O(L * logL)，但是最坏情况下可能会再乘以O(l)，l是每个字符串的平均长度。 首先对于每个字符串，取出以每个字符开头，到字符串尾的子串。比如字符串 acb ，从中取出的子串有 acb 、 cb 和 b 。如果所有字符串的总长度为L，则总共就有L个子串。我们把这些子串存在一个名为sub的数组中。（注意，最好用C风格的字符，这样可以直接引用每个子串的首地址，不用把这些子串另外转存。） 接下来就是主要花时间的步骤：把这L个子串排序。

1. #include cstdio 2. #include algorithm 3. #include string 4. #define maxn 1000001 5. using namespace std; 6. int d[maxn]={0},a,b,a0,b0; 7. 8. int calc(long long x){ 9. int ret=0; 10. while (x!=1 (x =maxn||!d[x])){ 11. ++ret; 12. if (x 1) x=x+x+x+1;

PKU : 1475 Pushing Boxes 搜索 3023 Submarines 计算几何 3008 Hexer***** Astar 2742 Organize Your Trains 双向BFS 3133 Manhattan Wiring 3135Polygons on the Grid 3137Enjoyable Commutation 1863Subnumber UVA : 10335 Ray inside *** 计算几何 11238 Inumerous Bowling 动态规划

这个问题来自UVA 11109，模型大概是这样的：由于液体对杯壁有一定的附着力，所以既使把杯子倒过来，还是有一定体积（设它为Vr）的液体是流不出来的。因此洗杯子的流程大概是这样（见图1）： 一开始杯子里有Vr体积的咖啡，是怎么也倒不出来的。 1. 加入一定量的水，摇荡均匀，成为稀释的咖啡溶液。 2. 尽量倒出咖啡溶液。最后还是有Vr体积的溶液倒不出，但是杯中咖啡的量已经减少了。 3. 反复做步骤1和2，直到咖啡的量足够少。 图1 洗杯子的示意义图 当然，这只是比较理想化的状态。现实中还有很多别的

如图1所示，这是很多人小时候都玩过的彩色转盘玩具。玩法显而易见就是要把打乱的两个转盘归位到图1所示的目标状态。如果要用搜索的办法解这个问题的话（当然，实际的玩法不是硬搜，而是有一定的规律的，在这里只是举一个搜索的例子），有一个特别的优化方法，就是双向搜索。 图1 很多人小时候都玩过的转盘玩具 有一些搜索问题的目标状态是唯一的，比如这个转盘玩具，目标只有图1所示的这一个状态。对这种问题可以用双向搜索的方法来解，也就是从起点向前搜一段，同时也从目标往回搜一段，如果两边遇到了某个相同的状态，则从起点到

#include stdio.h #include stdlib.h #include assert.h #define LH 1 #define EH 0 #define RH -1 typedef int ElemType; typedef struct BSTNode { ElemType data; int bf; struct BSTNode *lchild, *rchild; } BSTNode, *BSTree; int Equal(ElemType *a, ElemType *b

给定边数，问一共可以有多少种形式的网络。网络分为串联、并联以及它们的组合，网络的边不加区分。如N=3时，有四种情况，分别是：三边串联，三边并联，两边串联后和另一边并联，两边并联后和另一边串联。 这道题比较关键的一点是要发现essentially series network和essentially parallel network的数目是相等的。所谓essentially series network是指从最外面来看，网络是由串联的几部分组成；essentially parallel netwo

什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到。二分图的最大匹配有两种求法，第一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章。所以...

今天做了一道求一个多边形是否存在对称轴的题。主要是要想到一点：如果有对称轴，则对称轴左、右两边的顶点数应该相等，并且两两对称。所以对称轴肯定经过某一顶点或某一条边的中点。具体...

又很久没写了。我在我们那个判题系统中的工作终于暂告一段落，下周的校内选拔赛可以用上了。说实话，这个系统我看来在国际上都占居先进地位。我还没见过更好的。现在主流的PC^2比起我们的...

暂时贴上的是 UVa 10200~10270 这些题目的类型介绍与简单解析 补充中.......

最近写得很少。放假了还写这么少，主要是因为忙，又缺少计划性。 最近没做什么印象深刻的题。唯一记得的是一个求凸多边形重心的算法。下面讲一下。 以前以为三角形的重心是三个顶点坐标的...

（阅读本文之前请先了解二叉搜索树） 红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到...

#include stdio.h #include stdlib.h #include string.h #define MAX 101 int grid[MAX][MAX], f[MAX][MAX], tree[MAX][MAX], path[MAX]; int m, n; int findmin(int i, int j) { // compa...

// http://online-judge.uva.es/p/v104/10440.html #include stdio.h #include stdlib.h #include limits.h #include string.h #define MAX 1441 int arv[MAX], f[MAX], road[MAX]; int ma...

/* * UVa 10465 Homer Simpson Algorithm DP... * 感觉这题很简单， 但是状态转移方程也想了挺长的时间。 * 之前对dp的感觉就是状态转移方程很难设计， 现在决觉的dp和递推关系很密切 * 自...

/* * UVa 10482 Algorithm DP * http://online-judge.uva.es/p/v104/10482.html * 如果他不是分给三个小孩而是分给k个小孩该怎么做呢???? * 不知道, 以我现在的思路就是用k-1dim数组, 那也...

// UVa 574 ac#include stdio.h #include stdlib.h #include string.h #define MAX 15 int n, total, flag, data[MAX], cnt[MAX], used[MAX]; void search(int depth, int sum) { int i, j...

/* * 最近在看线段树放面的资料，好像蛮简单的 * 可是当写代码的时候还是发现了许多的问题，一下代码 * 还没有测试过，因为我还没有找到足够简单的题目来 * 测试这个程序。ft, 终于过了，...