USACO chapter 3 总结

总结

这几天刷了很多USACO的题，最大的感受就是这些题大部分编码难度不是很高，但是思维的要求确实不低，因此在写完之后最好适当的总结一下才能在写完后真正的有收获

最短网络
一眼最小生成树，直接跑Kruscal就可以了 【题目标签直接给出了话说

总分
看到可以多次选一个东西，完全背包可以解决。

丑数
容易想到暴力转移，但是肯定过不了，应该加以优化，方法是记录枚举到的SUM然后减少重复枚举

联系
STL可做的shabi题

邮票
背包问题，注意枚举边界，枚举到不可行的就直接退出

阶乘
最后非零位不会改变，所以不断%即可。因为n是1e3级别，所以保证保留4位即可

二进制数01串
这个不是很好想，【我看了题解
首先，位数是确定的，所以有一定量1的个数的数的个数是可以通过组合数的方式求出来的
那么关键就是找出答案。可以使用二分的方法，对于每一位看看符合条件的数的个数，然后二分。

纺车的轮子
已补坑
其实就是简单的模拟，然后关键在于我只需要模拟360次因为360次以后一定会有相同的状态，而如果此时还没有终止循环的话一定是无解的。所以瞎搞就可以了

饲料调配
爆搜即可，注意判断0和及时终止循环

魔板
【这个玩具可以玩一下……
直接bfs即可，某dalao貌似写了个IDA跪了

香甜的黄油
图论基础题，floyd可过，但是想练习一下别的也未尝不可【比如SPFA的各种优化？

骑马修栅栏
欧拉回路模板题，很简单，注意输出即可

商店购物
已填坑。
因为题目中说种类的数量最多是5，所以可以搞一个5维的背包
QwQ

亚瑟王的宫殿
图论加搜索剪枝待填坑

家的范围
前缀和加暴力可过，正解动规

游戏
长得像对抗搜索的区间动规

闭合的栅栏
计算几何待填坑

美国血统
已填坑
字符串处理就可以了，需要一点图论的基础姿势

电网
利用皮克公式和gcd瞎搞的题

破锣摇滚乐队
三维动态规划,每一位分别表示当前到达的歌曲，CD，以及CD使用的时间。