STEP BY STEP
题目意思是给出2条直线，然后判断其是否相交，平行，还是重合。刚开始以为是判断2条线段的关系，用了黑书的模板写了，发现连样例都过不了。后面改了很多才过了。先判断2条直线所在的向量是否平行，这个可以判断这2个向量的叉积是否为0，然后再判断线段是否重合，可以选3点判断叉积是否为0。如果向量不平行的话，直接求交点。求交点的公式是用了黑书里面的方法，先求出2个叉积代表2个三角形的有向面积，然后根据定比分点的关系（面积的比例等于交点分其中一条线段的比例）可以推出计算公式。
有叉积和点积这2个工具确实能方便的解决很多问题。
代码如下：
1 | #include <stdio.h> |
这是一个计算几何的题目。题意是，按顺序给一系列的线段，问最终哪些线段处在顶端。只需要穷举判断，当前的线段会与哪些线段有交点即可。也就是暴力求解，但是线段数目N有10的5次方，平方算法是不能过的。这个题能过的原因是题目描述里面说了，top的stick不会超过1000个。那么修改下暴力的方式题目就能过了。
从小到大枚举每个棍子，判断它是否与后面的棍子相交，如果相交直接把当前棍子的top属性置为false，然后break内层循环。这样就不会超时了，暴力也是需要技巧的，这句话说的很对啊。
判断2条线段是否相交的算法直接按照黑书上的模板代码写了，那个模板代码还不错吧。。。
代码如下：
1 | #include <stdio.h> |
这个题不错，居然需要在dfs里面写bfs。题意类似于图像识别里面，搜索一张图像里面的某个指定区域里面有几个斑点，题意里面的斑点是指色子。
1 | #include <stdio.h> |
这是一个貌似很麻烦的题，题目要求是将一颗用ascii码绘画出来的树，转换为其一种字符串表示，这种字符串表示好像是叫做什么广义表什么的。
比如，
A
|
B C D
| |
E F G 对应的字符串表示 **(A(B()C(E()F())D(G())))**
</div>
比较纠结的是如何读取数据，如何递归，如果建立树的话，也麻烦，因为还是颗不定叉的树。最主要的是如何方便地递归。最后知道了一个比较巧妙的方法，先一次性把一组数据读入字符串数组里面，再在这个字符串数组上进行递归处理。这样的话，就能很方便的找到树里面节点
的关系了。
而一次读一个字符就想进行递归是没办法确定节点的关系的，不递归估计更很难写，完全没头绪。。。
代码如下：
1 | #include <stdio.h> |
这个题目的意思是要计算一些c语言表达式的值。这些表达式有+-还有++，—操作符与a-z这些变量组合而成。a-z的权值是1-26。比如，表达式 c+f—+—a，得出值是9，其它变量的值也需要计算出来。
这个题目感觉比较麻烦，刚开始一点思路也没有，还写了个错误的方法，浪费了时间。后面我的思路是 （+，-） （—，++）（变量）（—，++），这个匹配式子的意思是先处理二元操作符，然后处理前置，再处理变量，再处理后置，如果发现没有后置操作符，则把读取的数据重新写回数据流里面，下次再处理。
代码如下：
1 | #include <stdio.h> |
题意是用字符串描述的一棵四叉树，读取字符串获得最终叶子节点的颜色。输入是2个字符串，根据这2个字符串建立2个四叉树。然后对于，指定位置的叶子节点，如果2颗树的叶子颜色其中一个为黑色，那么ans++，输出的就是ans。
类似树形结构的东西，直接一个函数递归求解即可。函数参数，一般是字符串地址，当前位置，然后还有其它在递归时候需要用到的东西。
代码如下：
1 | #include <stdio.h> |
这也是一个数学题，刚开始还真以为好难的样子，需要用到什么数论的理论啊。其实，只要去找规律就行了。
题意是给出一个进制，一个数字的最低位，和另外的一个数字，比如10进制，第一个数字的最低位是7，第二个数字是4，根据这些信息，和规则（XXXXX7 4 = 7XXXXX，例子: 179487 4 = 717948 ）求出第一个数字的最小长度。这个规则的意思是乘积是把第一个数字的最低位移动到最高位上去就行了。
貌似很难的样子，其实用笔在纸上求一下XXXXX7 4 = 7XXXXX就会发现。XXXXX7的每一位都是能够确定的，当然顺序是从最低位到最高位开始。因为知道最低位，所以次低位一定是最低位第二个数%base。以此类推，递归下去即可。最终条件是，没有进位了，而且乘积+原来的进位==最低位。
我用的递归完全可以改成循环的形式，这样速度应该会快些。
代码如下：
1 |
|
这是一个很神的数学题吧。基本上过这个题的很多都会wa10多次，而且这个题好像简单的枚举其中的一个指数值都能过，可能是数据量比较小。
但是，这个题还是有数学的解法的。但是，即使找到了这个正确的解法，过题的话，也是一件很困难的事情。题意大致如下：一只猫，高度为H，戴了一个帽子，帽子里面有N只猫（N是常数，且未知），同样帽子里面的猫也戴了帽子，但是这些猫的高度变成了H / (N + 1)，会向下取整。以此递归下去，直到最后的猫的高度都为1为止。现在，给出H和高度为1的猫的数量。要求的是高度大于1的猫的数量，以及所有猫的高度之和。
很别扭吧。通过上面的信息，得出2个式子。假设one代表为高度为1的猫的数量。one = N的n次。H >= (N + 1)的n次。注意第二个式子不一定取等号，因为很多时候都是不能整除的。现在要求N和n。2个方程解2个未知数，应该能解出来。但是，注意的是其中一个还是不等式。。。
指数关系很多时候会转换为对数的关系。所以，继续求对数，有lgH >= n lg(N + 1)。其中，由第一个式子可以得到n = lg(one) / lg(N)。那么最终转换为：lgH >= (lg(one) / lgN) lg(N + 1)。换个形式就是lgH / lg(One) >= lg(N + 1) / lgN。现在，已经很清晰了。因为，函数lg(N + 1) / lg(N) 是单调递减的。看到单调的函数，马上就会知道可以二分了。意思是，我们可以二分出一个N让lg(N + 1) / lgN 最接近lgH/lg(One)，而且是小于lgH / lg(One)的。剩下的工作就只是求和而已了。
写二分的时候，有一个地方可以注意一下。因为 lg(N + 1) / lgN 可能会出现除数为0的情况，所以可以进一步转换为lgH lgN >=lg(N + 1) lg(one)。 也是求一个N让上面那个不等式2边的值最接近，而且右边小于左边。能很快写对这个题真不是件容易的事情。。。
代码如下：
1 | #include <stdio.h> |
这是一个几何题。题意是给出一系列点，点最多才15个，求一个这里面的三个点组合出来的三角形，其面积是最大的，而且没有任何其它的点在这个三角形的内部和边界上。求三角形的面积，题目上面已经给了公式，也可以用0.5|a||b|sin(a,b)求，这里的a和b指的是2条边代表的向量。
现在就剩下一个问题了，怎么判断一个点在三角形的内部和边界上。在边界上，比较好判断，判断是否共线，然后再点是在线段的内部。
具体说明下，判断一个点在三角形内部的思路。我用的还是线性规划的思想。*如果该点在三角形的内部，那么任取三角形的一条边，该内部点和剩余的三角形的一个顶点必定在三角形的那条的边的同一侧。这个方法也可以推广到N边的凸多边形，证明的话很简单，因为线性规划一直在划分区域。所以，划分到最后围起来的区域就是凸多边形的内部了。
至于写代码的话，由于是第一次写这种几何题，写得很凌乱。
1 | #include <stdio.h> |
这也算一个数学类的杂题吧。题目本身比较有意思，解题的思路很需要猜想。题目的意思用+和-去替代式子(? 1 ? 2 ? … ? n = k)中的？号，对于指定的K，求最小的n。For example: to obtain k = 12 , - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。
这个题，我的思路大致如下。首先，K可能是正的也是负的，而且显然负的情况，有相应的正对应情况。那么考虑所有k为正的情况。由于k一定小于等于n(n+1)/2的，所以可以先求出这样的最小n。这个可以二分搜索，或者直接用解不等式方程(不过这种方法一直wa了)。
然后就剩下的是第二点了，假设a + b = n(n+1)/2, a - b = k。可以得到 n(n+1)/2 - k = 2 b。意思是，必须满足 n(n+1)/2和k的差为偶数。假如满足了，这样的n是不是一定OK了？？？
答案是肯定的，这一点就是需要猜想的地方了。因为，仔细观察下，1到n的数字可以组合出任意的1到 n(n+1)/4之间的数字，这个数字即是b。至于证明，可以用数学归纳法从n==1开始证明了。。。至此已经很简单了。
由于求n存在2种不同的方法，而且我开始用解一元二次不等式的方法求的N，出现了浮点误差，一直WA了。后面改成二分才过了。。。
代码如下：
1 | #include <stdio.h> |