有2个题目,被卡住了
第一个题目是,给定n个区间，然后找出所有区间里可以整个覆盖其他区间的最大覆盖量，比如：
1 3
2 5
5 8
3 6
2 5
3 8
3 6
3 8
就输出最大4， 因为对应每个输入的区间可以覆盖其他区间的数量就是0, 1, 0, 1, 1, 4, 1, 4
第一个1-3没办法覆盖任何其他，而第二个2-5可以覆盖另外一个2-5，所以是2，
而最后一个可以覆盖另外的3-8,3-6,3-6,5-8,所以就是4
第二题是给定一个一维的棋盘，刚开始棋盘式满的，目的是清空整个棋盘
规则如下：
-在任何情况下都可以去除或者填充第一个格子。
-如果第一个格子是满的那么我们就可以去除或者填满第二个格子(对N>=2也适用)
-若要去除或者填充第3<=K<=N的格子，只有在第K-1个格子是满的并且所有第1到第K-2个格子是空的时候才可以。
给个操作图，刚开始时4个格子
[解决办法]
第一小题:
1. 设置数组 Cnt[n] 存储各个区间能覆盖其它区间的个数,初值为 0;
2. for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (i!=j && 第 i 个区间能覆盖第 j 个区间) Cnt[i]++;
3. 在 Cnt[..] 中寻找最大者
上面算法耗时 O(n*n)
第二小题:
对于当前棋盘,实际上有两个后继状态:1) 首个方格状态取反(若有子,则删除,若无子,则填子) 2) 首个有子的右侧状态取反(若有子,则删除,若无子,则填子).算法如下:
1. 定义集合S,它的初值为 S={<1,....1>};
2. for (i=1;i<=|S|;i++)
3. {
4. 令 P=S[i];
5. Q=P;
6. if (P[0]==1) // 若有子
7. {
8. p[0]=0; // 删除该棋子
9. if (P[0..n-1]全为 0) return 完成; // 可用增加链指针,输出删子步骤
10. }
11. else // 若无子
12. {
13. P[0]=1; // 落子
14. }
15. if (P 不在 S 中) S=S+{P};
16. 在 Q[0..n-1] 中查找首个为 1 的下标,令它是 i;
17. if (i<n-1)
18. {
19. Q[i+1]=1-Q[i+1]; // 右侧状态取反
20. if (Q 不在 S 中) S=S+{Q};
21. }
22. }
23. 返回:无解
算法耗时 O(2^n)
[解决办法]
第一个题目简单，依次遍历
第二个题目，用递归，这个算法有点像汉诺塔和九连环
[解决办法]
include <cstdio>#include <vector>#include <algorithm>std::vector<int> map[10001];int intervals[10000][2] = { {1,3},{2,5},{5,8},{3,6},{2,5},{3,8},{3,6},{3,8}};int n = 8;int main(){ for (int i = 0; i < n; ++i) map[intervals[i][0]].push_back(intervals[i][1]); for (int i = 1; i <= n; ++i) std::sort(map[i].begin(), map[i].end()); int max = 0; for (int i = 0; i < n; ++i){ int b = intervals[i][0], e = intervals[i][1], ct = 0; for (int j = b; j < e; ++j) ct += std::upper_bound(map[j].begin(),map[j].end(),e)-map[j].begin(); if (ct > max) max = ct; } printf("%d\n", max-1); return 0;}
[解决办法]
1. 先排序。x小的排前面。如果x相等的话y大的排前面。然后问题就退化成了，查询某一个区间里y<=某个给定值的区间有多少。这个可以用线段树做出来。
2. 只要弄成了只有N-1填充其他都是空的状态以后，接下来第k步就是移动(k的二进制里最后一个1的位数)这一格。
[解决办法]
懂线段树的话就好说了。
首先把区间排序。排序以后，假设区间a[i]包含区间a[j]，那么根据排序规则必然有j>i。所以要查找a[i]包含了多少区间，只需要看所有起始点在a[i].start到a[i].end之间，并且该区间.end<=a[i].end的区间个数。根据排序规则，起始点在a[i].start到a[i].end之间的所有区间在排序后数组里是连续排列的。因此如果有一个数据结构可以高效解决：给定一个数组v[1]~v[n]，查询v[l]~v[r]之间<=x的元素个数有多少个；这个问题的话，那我们令v[i]=a[i].end，建立数据结构。每当查询一个区间A，先用二分确定l,r使得所有A.start<=a[i].start<=A.end的i都落在[l,r]里。然后用x=A.end查询这个数据结构返回A包含几个区间。
下面就是怎样构造这个数据结构。令一个表示[i,j]区间的线段树节点存储v[i]到v[j]这个子序列的一个有序数组。这个线段树每层的空间需求O(n)，所以总共空间需求是O(nlogn)。父节点可以用两个子节点加上归并排序得出，所以时间也是O(nlogn)。现在如果进来一个查询[l,r]，按照通常线段树的做法把[l,r]分解成若干个[li,ri]的不相交的并，并且每一层至多出现2个这样的子区间。对于每个子区间，用一次二分就可以算出子区间里有多少<=x的元素。加起来就是返回的答案。复杂度的话，第k层有O(n/2^k)个元素，所以第k层上的二分复杂度是O(logn-k)。当k=1加到树的深度的时候，复杂度加起来就是O((logn)^2)……这是单次查询的复杂度。原问题有n次查询所以O(n(logn)^2)搞定。