CSU Monthly May 2012 小结

关键句：我还是弱爆了，又是这种感觉，无助的感觉。

其实这个结果也算是意料之中，毕竟我和队友还是没有一起做过一次Contest，各方面都很欠缺。

开始回顾历史：

A. 很水的一道题，直接模拟即可，当时很快就A了，貌似是全场第一个气球。。

B.一道dp题，把二维最长公共子序列上升到了三维，其实状态转移基本没变，于是也很快1Y了。

C.看了下，英文题，比较长，于是我先放了，让队友读。后来队友描述题意是，给定N个人，N个开关，初始时开关都是0，每个人能够改变一些开关的值（具体开关的编号由数据给出），问使得所有的开关都变成1的最少的人数组成的操作序列（1,2,3表示第一个人先操作，第二个人接着操作，第三个人最后操作）（赛后据说是用高斯消元。。没明白）

D.名字叫做一道水题（其实不很水，需要处理的细节很多），题意是给定一个三角形的三个端点，再给一条线段的两个端点，判断线段经过三角形内部的长度，当时的想法就是，把线段和三角形边的直线方程写出来，然后去解方程，把线段所在直线和三角形边所在直线的交点求出来，然后判断交点是否在线段和三角形边上(记做合法交点)，如果存在两个合法交点，那么就输出他们之间的距离，如果只有一个合法交点，那么说明线段的另外一个端点在三角形内部，这样距离就是三角形内部的线段端点和该合法交点的距离，如果没有合法交点，又要分成两种情况，第一种是线段的两个端点都在三角形内部，那么距离就是线段长度，第二种是线段在三角形外部，那么距离时0，最后还要讨论线段和三角形边重合的情景，这里又要分成3种情况，如果线段与边没有交点，距离是0，如果线段的一个端点在边上，那么距离时该端点到边的一个端点的距离就是解，如果线段的两个端点都在边上，那么解就是线段的长度。（貌似讨论的比较完备了，当时就是这么想得，现在也是这么想得） 然后交了几次WA了，于是在查错无果之后，人崩溃了。。

E, 给定一个长度为N的序列（值在-1000000000-1000000000之间），在给定一个长度为操作符序列由‘+’，‘-’组成，要求把序列还原成N+1的序列，N+1的序列和N的序列的关系是

a0 op a1 = b0

a1 op a2 = b1

......

an op an+1 = bn

求出还原结果的总数（ai 是正整数）

通过这个题我总结出自己不好的习惯，就是不喜欢用符号来抽象出题目中给出的关系（即上面的a,b等式），然后老是空想+暴力枚举+乱想，最后得出了一些乱七八糟的算法，整个就是悲剧。大体的思路还是有了，就是确定一个ai那么剩下的都可以确定了。

其实抽象出题目给的关系以后，很容易得出递推式，

a0 = b0 -op a1

a1 = b1 -op a2

....

an-1 = bn-1 -op an

an = bn -op an+1

那么a0-an都可以化成an+1和一个常数的表达式

以

3 -1 7

+ - +

为例

a2 = 7-a3

a1 = -1+a2 = -1+7-a3 = 6-a3

a0 = 3-a1 = 3-6+a3 = -3+a3

由于题目限定ai是正整数，那么a0>=1 a1>=1 a2>=1 a3>=1 可以得出不等式组

-3+a3 >= 1

6-a3 >= 1

7-a3 >= 1

a3 >= 1

可以得出a3的范围：1<=a3<=2 ，如果不存在an+1不存在上限，那么就有无穷多组，如果an+1上限小于等于0，那么无解，其他的就是上限-下限+1、

F.超级恶心搜索题，我还没读懂啥意思。

G.经典贪心问题，一个时间轴上安排N个任务，每个任务有开始时间和结束时间，每段时间内只能做一个任务，要求在能够做得任务数最多，按照任务的结束时间升序排序，如果结束时间相同，按照起始时间降序排序。 1Y

H.没读明白题目意思。

其实E题是个很大的教训！！！！！！！以此为戒！！！！！！