总之先开坑
Counter：95
新队员专题分类：
0、搜索 1、Tire树 2、矩阵乘法 3、最短路 4、概率DP、期望、高斯消元
5、最大团、稳定婚姻问题 6、二分图匹配 7、网络流 8、数学
9、树状数组 10、线段树 11、差分约束、2-SAT、拓扑排序 12、KMP、Manacher 13、强连通分量
14、分块 15、数位DP 16、函数变换 17、分治 18、斜率优化
upd 6.26
2.1 POJ3070 裸矩乘，根据题目中给的公式对矩阵{1,1,1,0}求n次幂。
2.2 HDU1575 先求A的K次幂，累加Ans.s[i][i](1<=i<=n)并取模即可。
2.3 POJ3233 分治做。分奇偶讨论：
K为偶数，由S(K/2)=A+A^2+...+A^(K/2),则S(K)=S(K/2)+A^(K/2)*S(K/2);
K为奇数，S(K)=S(K/2)*A^(K/2+1)+S(K/2);
upd 6.27
2.4 HDU2604 考虑最后一个字母为m或者f，容易得到F(n)=F(n-1)+F(n-3)+F(n-4).
2.5 HDU1757 同HDU2604（但是不理解为什么我用F(1)-F(10)来算是错的，而且有个数据我觉得标程有问题啊）
upd 6.28
0.0 HDU1072 如果能重复回到一个地方，那么只有当此时的爆炸时间比原来长了才是有意义的。用vis标记当前离炸弹爆炸的时间。
0.5 HDU1253 三维BFS 注意要看清题目，判时间是否超过了魔王到达的时间。
0.7 HDU1728 对每个点记录到达时候的已转弯次数k和当前面对的方向fx，如果下一个位置方向与当前不同，则转弯次数k++.
最后遍历0-k，以及四个方向fx，看终点是否vis。
upd 6.29
0.6 HDU1495 预处理 m<n<s，则当m=0，n==s/2且 N和S中相等时可以等分。对S、M、N互倒的六种情况进行BFS即可。
0.1 HDU1175 思路同0.7逃离迷宫，坑点是起点和终点一样以及中间路过的必须是0。但是不能仅仅mp[nx][ny]!=0 要注意还可以nx==ex&&ny==ey；也就是当前路过的点是终点也行。我写成了mp[nx][ny]==mp[ex][ey]。要知道路上也是一样的mp[ex][ey]就完了。
0.3 HDU1181 就是对于单词首尾相同的连边，因为字母才26个。floyed判闭包即可。
0.4 HDU1242 注意r有多个，从a开始搜。然后对于x的处理，第一次是进入，第二次再杀掉守卫并重新进入队列。这样可以防止杀x后+2导致出队的node不是时间最小的node导致错误。
upd 6.30
0.2 HDU1180 对于梯子最好的策略是直接通过，或者等一回合然后通过。梯子方向由步数的奇偶数确定。其他同普通BFS。
0.9 HDU1429 状态压缩+BFS 十把钥匙十扇门对应(1<<10) 每次只需将state|=(1<<x)即加上第x把钥匙，当state&(1<<x)不为0时即能打开第x扇门。
0.8 HDU1254 样例都过不了……好奇怪啊 求救。。。
upd 7.1
3.5 3.8 HDU2544 最短路模板题……直接套板子就好。
3.6 HDU2066 对于相邻的S个城市建立一个超级源点，建边长为1。对终点T个城市也是建立超级汇点，边长也都为1.这样最后计算超级源点到超级汇点的距离，再减去2就是答案。
upd 7.2
3.4 HDU1869 floyed 算出点对点路径，只要所有的路径都<=7就Yes不然就No
3.7 HDU2112关键在于把字符串和数字一一对应起来，转化成数字后容易用SPFA。那么我们可以用map<string,int>，如果当前字符串在map内就不用操作，不在则添加，编号tot++。
3.9 HDU2680 和3.6一样的方法，设置超级源点，然后做单源最短路即可。
upd 7.3
3.1 HDU1217 floyed,用map处理地名。
3.13 HDU3790 做最短路的时候同时维护花费。（路程第一关键字，花费第二关键字）
3.2 HDU1224 保证有路的情况下做DP。dp[i]=dp[j]+v[i] (mp[j][i]==1&&j<i) 输出用fa[j]=i记录路径，类似DP的路径倒序输出即可。
3.12 HDU3339 没过样例，留坑。
鉴于我没有毅力持续写专题的博客QAQ…… 我决定 之后做完一个专题后集中将一个专题的内容 合在一起写出来，这样也更系统更容易自己复习。
upd 1.13 寒假开始…… Bless all！
upd 2.12 近期离线写的记录。
寒假快结束了，总结下专题的情况。
已完成：0、1、3、9、12。
已基本完成+待完成：2.7、6.6、7.6、7.7、13.7、15.5、15.6
期望完成：4、5、8、10、11
寒假结束前补完待完成，校赛选拔前补完期望完成。
3.11后期望剩下专题：14、16、17、18. 有余力可选择完成1-2道。
评论 (0)
