Xorex

前言： 其实在最开始接触贪心的时候就知道这种背包问题了，然后我就死想贪心思路，但是根本想不到好吧，然后觉得这种背包问题真的是好厉害，世界上一定没有什么方法来解决背包问题了吧，但是只从我开始学了DP之后就明白了，原来这么简单QAQ 背包问题模板：0/1背包问题方法： 倒着逐步选择更新 代码：123456for(int i=1;i<=Things;i++){ cin>>Weight>>Value; for(int j=Bag_weight;j>=Weight;j--) f[j]=max(f[j],f[j-Weight]+Value[i]);} 完全背包问题方法： 0/1背包的基础上进行正序更新 代码：123456for(int i=1;i<=Things;i++){ cin>>Weight>>Value; for(int j=Weight;j<=Bag_weight;j++)//循环方式和0/1是反的 f[j]=max(f[j],f[j-Weig ...

资源分配DP 资源分配千万不能套模板，本人有亲身经历，写了几道题之后以为资源分配就是这种类型的于是就开始敲，敲出来了常规类型的三维动态规划，虽然也AC了这道题，但是和学长的二维算法比起来，慢了4倍…… 有P1266这道题，也是超级魔性，竟然和题目中的数据范围结合在了一起，不禁让我想起来了寒假的时候老师给我们模拟赛的一道题，也是规定了数据中数的大小是小于100的，很小，这就可以提示我们进行数组记录出现次数，来进行10000000的数据范围的处理，而这道题是数据大小小于450，然后就可以开一个100*450大小的数组进行处理每一种可能出现的情况……真的是丧心病狂…… 双重爆炸 总之，现在的我对DP的方法理解就是根据题意和数据范围，然后猜测记录下来哪一些状态，然后想他的状态是取决于前面哪些状态的哪些因素…… 我还是太弱了啊，DP方程蒙蔽，月考爆炸，一本线都过不了，要好好学习了QAQ ……然后就亮出三道比较好的题目吧！ P1265花店橱窗题目描述： 设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架 ...

感言：最近LIS真是把我搞得身心俱疲，尤其是加强版的LIS，整整两节课才调试完……表示心塞心塞心塞……像我这样的弱鸡和刘神澜神差距还是太大了 (；′⌒`)，难怪一直被吊着打，不过这样默默地提高自己的代码能力吧，与其为了刷题量而刷题，不如去用心做一些有用的题，还能提高自己的代码能力……（个人感觉代码能力很重要很重要……如果没有代码能力，就算知道算法，不一定能敲出来对的……很有可能就是因为等号大于小于的判断导致大规模丢分，而且这些错误超级难找到……比如加强版LIS） 不过总算写了这三道题，A掉的人还是比较少的，所以很开心……对于求LIS这类型的题，可以使用二分进行优化，这样可以将速度提高很多很多 LIS 最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。 二分优化LIS题目描述： 给定N(n<=300000)个数，求这N个数的最长上升子序列的长度。 输入： 输入两行，第一行N，第二行N个数； 输出： 输出一行，这N个数的最长上升子序列的长度。 题解：首先这道题因为数据量是300000所以 ...

感言： 瑟瑟发抖的萌新好不容易A掉了这道14个人才过掉的题，然而被杨树神无情抢沙发，仅仅慢了十几分钟……已经哭晕在厕所…… 为什么要拉出来这道题呢，因为刚刚刷完割边割点强连通分量，所以就写写这道题试一试，而且发现了一些新的技巧，神奇的缩点和最后答案的判断…… 最受欢迎的牛题目描述： 每头牛都有一个梦想：成为一个群体中最受欢迎的名牛！在一个有N(1<=N<=10,000)头牛的牛群中，给你M(1<=M<=50,000)个二元组(A,B),表示A认为B是受欢迎的。既然受欢迎是可传递的，那么如果A认为B受欢迎，B又认为C受欢迎,则A也会认为C是受欢迎的，哪怕这不是十分明确的规定。你的任务是计算被所有其它的牛都喜欢的牛的个数。 输入： 第一行，两个数，N和M。第2～M+1行，每行两个数，A和B，表示A认为B是受欢迎的； 输出： 一行，最受欢迎的奶牛的数量…… 题解：这道题用到了tarjan算法，用这个算法来求出所有的联通分量，为什么要求联通分量呢，因为每一个连通分量中，因为我喜欢你，你也喜欢我，那么我们两个就可以看成一个点，这样就可以吧五万个点缩成不同的连通分量 ...

目标 所以说这就是我未来好几个月要努力的东西了…… 1.动态规划入门 2.动态规划的基础和动机 3.资源分配类 4.背包问题 5.双进程类问题 6.区间动态规划 7.二维动态规划 8.动态规划深入讨论 总结动态规划书上的东西道是搞完了，但是还有很多比较高深的东西QAQ，以后慢慢学，希望在OI的路上越走越远

写在前面： 无良学姐瞎写讲稿，毁我青春，还好有刘神相助，改了错误的地方，不然要栽在书上了……首先说割点，割点的意义在于切掉这个点，就，就不连通了，这个图就毁了，那么这个点就是一个割点，所以说我们在求割点的时候，需要注意一种东西，那就是你搞得图，不一定是联通的，所以你需要遍历所有的联通图……因为P1230就是这个坑，超级大坑，这个图是不连接的，所以你需要求出所有图的所有割点…… 关于割点割点概念： 在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。 求出割点然后说如何求出割点，首先我们需要建图，然后开两个数组，一个是dfn，另一个是low，而dfn表示的是DFS的访问时间，low表示的是这个点能回到的最靠前的点。我们建立一个DFS树，按照顺序DFS得到一个树，这个树来说，对于一个树，我们要看他的边，如果这个边是链接下面的点的话，他就是正常边，如果这个边链接上面的点，那么这就不是一个正常的边，我们称作为返祖边，对于返祖边我无话可说，一旦遇到这种返祖边，也就意味着这个返祖边（u，v），dfn[v]&l ...

反思 首先我要对最近写的题进行一下，反思，首先最近做P1698和P1225这两道题的时候，Debug的时间太长了，消耗我不少时间。所以我觉得是我的做题方式出了问题，我应该在拿到一道题之后，去认真的想，然后思考，大致规划出怎么写，代码实现思路需要详细一些，然后去仔细理解，明白每一个步骤是干什么后，想一想会不会出什么bug，或者特别情况，所有的东西都想清楚了之后，再去认真的把它敲出来，一边敲一边打表Debug，确保自己写的每一步都是对的才行。 并查集并查集我也是刚刚学会的，所以总结一下。 并查集就是利用father数组来记录下来和每一个点联系的点，然后经过压缩路径之后，所有有关系的点都会指向同一个点，那么这就是一个集合，并查集来寻找两个点是否在同一个集合里面是非常快的。 并查集代码递归版本：12345678int Getfather(int x){ if(father[x]==x) return x; int p=Getfather(father[x]); Num_Start[x]+=Num_Start[father[x]]; father[x]=p; ...

错误总结： 好久没有这么爽的A一道题了，这个爽代表着无数次Debug和最后的恍然大悟，然后AC。很有成就感的说，比作数学题爽得多…… 首先总结一下最近写图论的时候犯的一些小错误： 1.更新a[i].point=a[i].point，说白了就是 j 打成 i …… 2.没有考虑到不去赋初值对程序的影响 3.数组名打错……比如Link1打成Link什么的…… 4.两个链表运用的时候a，b搞混 5.没有小小的证明就开始乱搞，比如这道题 NOIP2009最佳贸易题目描述： C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人century来到 C 国旅游。当他从strork处得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商 ...

具体规划1.学会Floyd算法 2.学会Dijkstra算法 3.学会Bellman-ford算法 4.学会SPFA算法 5.学会最小生成树Prim算法 6.同样的最小生成树Kruskal算法 7.学会拓扑排序Topsort算法 8.割点、割边与强连通分量 9.学会Hash-哈希表的应用（跪求刘神快点给我们讲！！） 10.学会并查集查找 感言赶完一个就划掉一个，我已经发现在图论里面，我是机房同等级最慢的一个。其实很大原因就是寒假偷懒了，要抓紧补回来。 文化课，一天六七节课都翘掉是不能了，每天规定时间：副课、下午最后一节自习、晚自习、中午可以来机房，剩下的时间都要在班里面，一定要把学习指导和活页完成，其次是英语，每天要背单词了，一定要背，绝对的！ 加油吧！！！

Flyed算法代码：12345for(i=1;i<=n;i++) for(k=1;k<=n;k++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; 代码讲解：这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。 K循环作用也就是说，最外层的循环每次枚举的是中间点k，然后下面两个循环不停地枚举通过另外两个点，如果这两个点能够通过k这个点更新掉 i 到 j 的最短路，那么就开始更新，其实我在最开始接触Floyd的时候，有一点很是不理解，那就是为什么k在最外层循环，因为k代表的是 i 和 j 中间的点，为什么k不能在第二层循环或者是第三层循环呢，找了很久的资料之后我才弄明白这个算法中k为什么在最外层，顺便感悟到了这个算法的真正的魅力和神奇。 代码运行开始算法之前，首先介绍一下这个算法是如 ...