[综合] 紫书 习题 8-17 UVa 11536 （滑动窗口）

这道题说连续子序列，马上就想到滑动窗口。 注意窗口里面的元素中小于等于k的才是有效元素。记录窗口里面有效元素的个数，满足了之后开始 缩短窗口，如果左端点不是有效元素或者即使窗口中存在这个元素的个数大于1，即使删去还是满足 窗口内有1到k这些元素的时候，左端点就删去。就...

[综合] 紫书 习题8-18 UVa 11536 （扫描法）

这道题貌似可以用滑动窗口或者单调栈做，但是我都没有用到。 这道题要求连续子序列中和乘上最小值最大，那么我们就可以求出每一个元素， 以它为最小值的的最大区间的值，然后取max就ok了。那么怎么求呢？ 我可以初始化出一个第一个小于当前元素的的元素的位置，也就是说初始...

[综合] 紫书 习题 8-20 UVa 1620 （找规律+求逆序对）

这道题看了半天没看出什么规律，然后看到别人的博客，结论是当n为奇数且逆序数为奇数的时候 无解，否则有解。但是没有给出证明，在网上也找到详细的证明……我也不知道是为什么…… 求逆序对有两种方法，树状数组和归并排序，当然这道题数据很小可以直接暴力，我三种都写了。 暴力 ...

[综合] 紫书 习题 8-22 UVa 1622 （构造法）

这道题的构造法真的复杂……要推一堆公式……这道题写了几天了……还是没写出来…… 一开始简单的觉得先左右来回，然后上下来回，然后把剩下的执行完了好了，然后就WA。 然后换了个思路，觉得是贪心，觉得只要保证当前留下的最多就ok了，然后又WA。 这里不能每一步贪心，因为当前最优不能保证以后是最优的。 然后...

[综合] 紫书 习题 8-23 UVa 1623 （set妙用 + 贪心）

这道题我是从样例中看出思路了 24 0011 看这组数据，输出的是No，为什么呢？因为两个1之间没有神龙喝水，所以一定会有水灾。 然后就启发了我，两次同一个湖的降水之间必须至少有一次神龙喝水，否则就会有水灾。 如果是第一个湖的话那么就看作在第0次有一次降水。 ...

[综合] 紫书 习题 8-24 UVa 10366 （构造法）

又是一道非常复杂的构造法…… #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMAXN...

[综合] 紫书 例题 11-1 UVa 12219 （表达式树）

这道题看了刘汝佳的代码真的是天秀，很值得学习。 具体看代码 #include<cstdio> #include<iostream> #include<cctype> #include<map> #defineREP(i,a,b)for(inti=(a)...

[综合] 紫书 例题 11-2 UVa 1395（最大边减最小边最小的生成树）

思路：枚举所有可能的情况。 枚举最小边，然后不断加边，直到联通后，这个时候有一个生成树。这个时候，在目前这个最小边的情况可以不往后枚举了， 可以直接更新答案后break。 因为题目求最大边减最小边最小，在最小边确定的情况下，要使得差值最小，就要使得最大边最小，那么排序之后加边后 的第一个生成树一定是...

[综合] 紫书 例题 11-3 UVa 1151 （有边集的最小生成树+二进制枚举子集）

标题指的边集是说这道题的套餐，是由几条边构成的。 思路是先做一遍最小生成树排除边，因为如果第一次做没有加入的边，到后来新加入了很多权值为0的边，这些边肯定排在最前面，然后这条边的前面的那些边肯定都要再扫一遍，也就是这条边无论如何都不会选。 那么后来就是二进制枚举套餐，从头开始，加入套餐中的边然后权值...

[综合] 紫书 例题11-4 UVa247 （Floyd判断联通）

Floyd联通，然后为了输出联通分量而新建一个图，让互相可以打电话的建立一条边，然后dfs输出联通分量就ok了。 #include<cstdio> #include<iostream> #include<cstring> #include<string>...

[综合] 紫书 例题 11-5 UVa 10048 （Floyd求最大权值最小的路径）

这道题是Floyd的变形 改成d[i][j]=min(d[i][j],max(d[i][k],d[k][j]))就好了。 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);...

[综合] 紫书 例题 11-6 UVa 658 （状态压缩+隐式图搜索+最短路）

这道题用到了很多知识点，是一道好题目。 第一用了状态压缩，因为这里最多只有20位，所以可以用二进制来储存状态（要对数据范围敏感），然后 涉及到了一些位运算。 第二这里是隐式图搜索，和之前有一道bfs倒水的有点像，就是题目和图论没有半毛钱关系，但是却可以自己建 图来做，把状态看...

[综合] 二分模板

二分分为二分查找和二分答案。 二分查找。实际上就是一个有序数列中有一个解，然后搜一遍求这个解。而直接for循环暴搜一遍的话时间复杂度是O（n），而用二分查找可以降低时间复杂度，为O（logn）；而数组形象化出来的话就是0000010000000（0为无解，1为有解），二分就是要找中间的1，即为唯...

[综合] 紫书 例题11-7 UVa 753 （网络流最大流）

设一个源点，到所有设备连一条弧，容量为1，然后设一个汇点，所有插座到汇点连弧，容量为1，然后 转换器也连一条弧，容量为1。最后最大流就是答案。其中注意节点数要开大一些。 #include<cstdio> #include<queue> #include<...

[综合] 紫书 例题11-8 UVa 11082（网络流最大流）

这道题的建模真的非常的秀，非常牛逼。 先讲建模过程。源点到每一行连一条弧，容量为这一行的和减去列数，然后每一列到汇点连一条弧，容量为这一列 的和减去行数，然后每一行和列之间连一条弧，容量为19。然后求最大流，最后矩阵中每一个元素的值就是其所在 列和行所连的弧的...

[综合] 紫书 例题11-9 UVa 1658 （拆点+最小费用流）

这道题要求每个节点只能经过一次，也就是结点容量为1，要拆点，拆成两个点，中间连一条弧容量为1，费用为0. 因为拆成两个点，所以要经过原图中的这个节点就要经过拆成的这两个点，又因为这两个点的 边的容量为1，所以只能经过一次，就等价于原图中的点只能经过一次。 拆点的时候...

[综合] 紫书 例题11-10 UVa 1349 （二分图最小权完美匹配）

二分图网络流做法 （1）最大基数匹配。源点到每一个X节点连一条容量为1的弧，每一个Y节点连一条容量为1的弧，然后每条有向 边连一条弧，容量为1，然后跑一遍最大流即可，最大流即是最大匹配对数 （2）最小（大）权完美匹配（每个点都被匹配到）。和最大基数匹配类似，只是有...

[综合] 紫书 例题11-11 UVa 12661 （dihkstra变形）

这道题主要比较权值的时候要改变一下，其他地方基本一样。 比较权值的时候要考虑边的时间与a，b 可以设相对于当前边的时间now，则now=d[u]%（a+b），也就是当前这个边进行到整个a和b的循环 的哪个地方了。然后我们分类讨论。 （1）当t>a的时候，这种边在输入的时候就可以去掉了，因为不...

[综合] 紫书 习题 11-1 UVa 821 （Floyd）

水题，Floyd一遍就完了。 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMAXN=101; intd[...

[综合] 紫书 习题 11-2 UVa 1001 （Floyd）

这道题只是在边上做一些文章。 这道题起点终点可以看成半径为0的洞，我是直接加入了洞的数组。 边就是两点间的距离减去半径，如果结果小于0的话，距离就为0，距离不能为负 然后我看到n只有100，范围很小，虽然这道题只是单源最短路， 但是Floyd代码比较短，而又不会超时，所以我就写了Floyd。 #in...