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

理念

天行键,君子以自强不息;地势坤,君子以厚德载物!

马上就要有大的挑战,学习功课闲暇时还要抽时间刷题,刷题闲暇时还要玩游戏,玩游戏闲暇时还要努力睡觉,睡觉闲暇时还要发博,厄……连锁的链式反应就是可怕,没办法,好多事其实是一件事,慢慢做,不怕做不完