由于种种原因回去再写了下USACO……
看来,USACO Training题目也有更新……以前的题满水的……虽然虐我这种蒟蒻还是easy……T_T
Chapter 3.4
Heritage:很基础的二叉树遍历
Fence9:因为三角形内的点连续,最初想随机出第i行某个成立的点,然后左右二分,后来发现随机不合适……
算法①令y-i=0 i为行数 枚举i 求出 该直线与三角形其余三条直线的交点,取出在相应取值范围内的点,减一下 然后累加即可。
算法②pick定理 s=a+b/2-1 直接算面积s 当然如果非要体现自己貌似很NB的话可以用海伦公式 接下来很神的可以证明,一条直线((0,0),(n,m))上的格点数等于n与m的最大公约数+1。即b=gcd(n,m)+1. gcd(n,m)为n与m的最大公约数。然后代入 求解 注意重复除去的点(三角形顶点)
Rockers:简单的动态规划,类似于01背包
Chapter 4.1
Nuggets:推一下可得答案不超过65024,然后上水DP (两互质数上限a1a2-a1-a2)
Fence8: dfsid 二分+搜索+剪枝
Fence6: Floyd 求最小环……最初的想法有些漏洞 果然我还是太嫩了么~~