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