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

理念

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

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