[综合] 紫书 例题8-7 UVa 11572（滑动窗口）

滑动窗口这个方法名字非常形象， 先是窗口的右指针尽量往右滑，滑不动了就滑窗口的左指针，滑到右指针又可以开始滑动为止。 这道题是要记录滑的过程中最大的窗口长度，限制条件是窗口中不能出现重复的值。 重复的值有两种判断方法。 一种是set，其实就是开个vis数组，但是数据有1...

[综合] 紫书 例题8-8 UVa 1471 （用set实现动态二分）

设切割的区间为（j，i），注意两边都是开区间。 然后可以预处理出以i为起点的最长连续递增的长度和以j为终点的最长连续递增的长度。 大致思路就是枚举i，右边这一侧的最优值就知道了，然后这道题的关键就是就是j取哪里。 （1）去掉干扰元素，这一步非常的关键，设题目给的数组为a，g（i）表示...

[综合] 紫书 例题8-9 UVa 1451 （数形结合）

这道题用了数形结合，真的牛逼，完全想到不到还可以这么做 因为题目求的是平均值，是总数除以个数，这个时候就可以联系 到斜率，也就是说转化为给你一堆点，让你求两点之间的最大斜率 要做两个处理 （1）去掉上凸点，因为上凸点是无论如何都不会为最优解的 （2）...

[综合] 紫书 例题8-11 UVa 10954 （优先队列）

解法和合并果子是一样的，每次取最小的两个，更新答案，加入队列 #include<cstdio> #include<queue> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;intmain() ...

[综合] 紫书 例题8-13 UVa 11093 （反证法）

这道题发现一个性质就解决了 如果以i为起点，然后一直加油耗油，到p这个地方要去p+1的时候没油了，那么i，i+1，……一直到p，如果以这些点 为起点，肯定也走不完。 为什么呢？ 用反证法， 假设以q（i<q<=p）这个点为起点可以走完的话，那么i...

[综合] 紫书 例题8-14 UVa 1607 （二分）

题意非常难理解…… #include<cstdio> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMAXN=212345; structnode {inta,b,w; }g[MAXN]...

[综合] 紫书 例题8-15 UVa 12174 （滑动窗口）

这道题就是给你一n长序列，然后把这个序列按顺序分成很多段，每段长s（最前面可以小于s，只有第一段的后半段，最后面也同样，只有最后一段的前半段），然后要求是每一段里面没有重复的数，问你有几种分法 实际上看到连续s个数，就可以想到滑动窗口，可以提前初始化所给序列的每一段里面有没有重复的数，然后再枚举第一...

[综合] 紫书 例题8-17 UVa 1609 （构造法）（详细注释）

这道题用构造法，就是自己依据题目想出一种可以得到解的方法，没有什么规律可言，只能根据题目本身来思考。 这道题的构造法比较复杂，不知道刘汝佳是怎么想出来的，我想的话肯定想不到。 具体思路紫书上讲得非常清楚了，就不讲了。代码有详细注释 #include<cstdio> #include&...

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

从左往右扫描一遍，得从每个位置往右伸长不会碰到天花板的高度，右往左一样，取最小，然后就是可以放“水”的高度了 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) us...

[综合] 紫书 例题8-19 UVa 12265 （扫描法+单调栈）

首先可以用扫描法处理出一个height数组，来保存从当前行开始，每一个格子可以向上延伸的最大长度。 这种“延伸”的问题用扫描法，因为往往这个时候可以利用前一次的结果来更新当前的值 然后这道题的关键就是是维护一个单调栈，栈顶的元素就是当前状态所求的答案。 这个单调栈满足的性质是：c从小到大增加，h从...

[综合] 紫书 习题 8-1 UVa 1149（贪心）

排序之后，尽量最小和最大的放在一个背包，放不下就放最大的。 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintM...

[综合] 紫书 习题 8-2 UVa 1610 （暴力出奇迹）

这道题我真的想的非常的复杂，拿草稿纸一直在找规律，推公式，然后总有一些特殊的情况。 然后就WA了N次。无奈之下看了别人的博客，然后就惊了。直接暴力枚举两个相邻字符串 里面的所有可能就可以了……真的是暴力出奇迹！ #include<cstdio> #include<iostream...

[综合] 紫书 习题8-4 UVa 11491 （贪心）

题意：给你一个数，要求删去一些数字，使得剩下的数字最大。 这道题用贪心解决。 大家想一想，两个数比较大小，肯定先比较第一位的数，然后依次比较第二位，以此类推。 既然我们要保证最后的数字最大，那么一定要先保证第一位数的最大，然后保证第二位数最大，以此类推。 所以贪心策略就是在能删除的范围内选择最大的数...

[综合] 紫书 习题8-8 UVa 1612 （贪心+精度）

这道题我很快就写出来了，但是一直WA，然后发现是精度，这坑了我一个小时…… （1）贪心。每次就尽量分数高，可以保证最后分数最高 （2）神tm精度问题。记住判断大于小于和等于的时候要用EPS（1e-6） a==bfabs(a-b)<EPS a!=...

[综合] UVa 11137 （背包计数）

相当于给你容量，然后有价值为1，体积为立方数的背包，问你方案数。 f[i][j]=f[i-1][j]+f[i][j-i*i*i] 因为i只与上一行有关，所以可以用滚动数组 还有记得全部初始化为1，然后算的时候就不用算1的情况了。 #include<cstdio> #defineREP(i...

[综合] 紫书 习题8-11 UVa 1615 （区间选点问题）

这个点就是贪心策略中的区间选点问题。 把右端点从大到小排序，左端点从小到大排序。 每次取区间右端点就可以了，到不能覆盖的时候就ans++，重新取点 ps：这道题不考虑精度也可以过 要着重复习一下区间相关问题了，包括前面没有例题的知识点的部分 #include<cstdio> #inclu...

[综合] 区间相关问题（贪心）

摘自紫书第八章 突破口一般是区间包含的时候怎么选，以及怎么排序 （1）选择不相交区间 问题：有n个开区间（ai，bi）选择尽量多的区间，使这些区间两两没有公共点。 按照b从小到大排序（这种情况a无所谓，得出结果一样） 一定选第一个区间，然后，把所有和区间1相交的区间排除在外，然后不相交就选下一个...

[综合] 紫书 习题 8-13 UVa 10570 （枚举+贪心）

我看到数据范围只有500，第一反应枚举所有的可能，然后求出每种可能的最小次数。 但是不知道怎么求最小次数。我想的是尽量让一次交换可以让两个不在应该在的位置的数字 到原来应该在的位置的数字，这样可以消除两个差异，否则就交换到该到的地方，消除一个差异。 但是怎么实现？？我想了很久都只是有这样一个思...

[综合] 紫书 习题 8-15 UVa 1617 （贪心）

先排序，然后每个线段先放右端点，然后往下放，如果不能放就整体往左移动，当不能往左移动的时候就ans++ 开始下一个整块。判断能不能向左移动要用一个变量储存每个已经放了的区间中线段与左端点距离的最小值。 #include<cstdio> #include<algorithm> ...

[综合] 紫书 习题 8-16 UVa 1618 （中途相遇法）

暴力n的四次方，然而可以用中途相遇法的思想，分左边两个数和右边两个数来判断，最后合起来判断。 一边是n平方logn，合起来是n平方logn（枚举n平方，二分logn） （1）两种比较方式是相反的，所以第二次可以直接把数组倒过来做，代码可以省很多。 （2）我们现在来讨论3142这种情况（1最小，2次小...