POJ3667线段树

题目解答

裸的线段树,线段树能解决的问题很多,这道题目是非常典型的线段染色问题。有三种状态,无色(空),满色(有人),杂色。主要考察的也就是实现线段树的惰性,即懒操作。修改颜色时不是一改到底的,在适当粒度的区间做好标记,当出现更细粒度(小于某个区间)的操作时再下放。例如:区间[1,10]标记为客满,同时区间[1,2]标记为空是可以在某些时刻共存的,想想为什么。

Read More

USACO 3.1.4 Rect1

题目解答

刚一读题,第一反应就是朴素染色,但是因为较大的数据,染色法绝对行不通。因为我们没有必要重复覆盖某个点,包括计算面积我们不需要统计,而是直接用坐标计算。所以可以考虑使用面向矩形整体的方法:

  1. 二维线段树或者离散化 + 线段树:这种方法的弊端是要么过于复杂,要么MLE,所以牛刀还是用来屠牛吧
  2. 我具体论述一下矩形切割:首先通过分析我们知道凡是在后面覆盖过的绝对不会被前面的覆盖,因此假设我们覆盖第N个矩形,那么第(N-1)个一定在它的下面,由此知道要倒序染色(1),这样可以省去很多的操作;而两个矩形相交如何处理呢?我们知道:如果两个矩形相交,他们的交集必定是一个矩形,记录一个矩形只需两个对角坐标,处理方便,所以我们要对每次的覆盖进行切割(2);

Read More

NOI2004郁闷的出纳员

题目解答

这是一道考察数据结构的题目,理论上使用静态的会更好,不见得动态的就快,但是我是使用Treap AC的。原理很简单,就是需要额外再用一个delta来记录差量,避免Treap退化,所以在加入一个节点时 ,要减去这个差量,最后输出时加上即可。然后’S’、’A’操作只改变delta,剩下的就是实现了。

Read More

USACO 2.3.3 Cowtour

题目解答

这道题目是图论问题,首先用floyd求出每对点的最短路,然后再找出单独每个点的可连接的最远的点(直径),接下来就是计算两个分离牧区的直径。首先遍历所有不连通的点对,然后用这两点的距离加上两点原来的直径。如果更小,则更新直到结束。
但是还有一种特殊情况:“包含”。如果一个牧场恰好包含另一个,且大的牧场直径比计算出的要长一些,则结果应该是更大的那个才对。(参考图片:红色表示最终连接的结果,蓝色表示大牧场的直径,显然蓝色的才正确)

Read More

NOIP2001Car的旅行路线

题目解答

新年第一题:这道题目很值得一说,首先这是一个比较典型的计算几何转化为图论去做,同时也是需要结合两者的不错的题目。大体思想是首先用向量法计算出第4个点,因为第4个点是现有的3个点中的作为现有RT三角形的一个对角点,所以先要确定直角点,用点积为0判定,剩下的很简单了。接着要建模为一张图,然后计算最短路径。大体就是这样。

关于计算最短路径:我的想法是先求出所有点对的最短路径,然后遍历A市与B市的飞机场选出一个最短的,但是这样似乎麻烦而且时效低,所以我介绍一下官方的强大方法:首先对于A市和B市,把他们的铁路价格都改为0,这样无论选择两个城市中的哪个机场,都不用额外花费铁路价格,把城市封装为一个整体,意味着A、B的机场任意。做一遍Dijkstra即可。

Read More

CSAPC09 质均数

题目解答

  1. 直接找规律,第一个是5,第二个就是下一个质数7,以此类推……
  2. 发现关系后用规律去做:关系是任何一个质数(>=5)都可以被两个质数相加除以2得到。(仅为猜想,没有证明),然后就直接有了一个直接找规律

Read More

USACO 2.3.4 Money

题目解答

这道题目有必要解释一下我写的DP,a[j]=a[j]+a[j-k] (0<=j<=n),其中k为当前面值,思想是这样的:f[j]是用j面值可组成钱的方案数,事实上就是先降维后记忆化搜索的背包,原来的方程是:f[i,j]=f[i-1,j]+f[i,j-k]因为选中k后还可以再次选择(01背包只能选一次)所以第二个式子是i而不是i-1。

Read More

USACO 2.3.5 Concom

这道题过了,但是这道题就不贴时间和程序的全部了,因为我原来用超级复杂的邻接表做的,最后的一个数据没有过(第9个),后来发现邻接矩阵这么简单,于是此刻我充分感受到了KISS原则的宝贵,毕竟usaco的第二章不会考到多么精尖的算法,与其用2、3个小时编写一个0s的程序,倒不如用40min写一个0.1s的程序的性价比高!!!

Read More