A - 选数问题
Given n positive numbers, ZJM can select exactly K of them that sums to S. Now ZJM wonders how many ways to get it!
Input
The first line, an integer T<=100, indicates the number of test cases. For each case, there are two lines. The first line, three integers indicate n, K and S. The second line, n integers indicate the positive numbers.
Output
For each case, an integer indicate the answer in a independent line.
**Example **
Input
1
10 3 10
1 2 3 4 5 6 7 8 9 10
Output
4
思路
首先，将数组排序，这样可以保证剪枝，然后利用DFS从根节点向后扩展，当达到K层时即停止，若总和为S则总数+1，最后输出总数即可。在DFS过程中，可以根据SUM进行剪枝，若SUM已经大于S则不用扩展到K层。
DFS部分
void dfs(int a[],int k,int s,int l){
if(k==0&&s==0) {
c+=1;
return;
}
if(l>=n) return;
if(k==0||k<0||s<0) return;
dfs(a,k,s,l+1);
dfs(a,k-1,s-a[l],l+1);
}
B - 区间选点
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）
Input
第一行1个整数N（N<=100）
第2~N+1行，每行两个整数a,b（a,b<=100）
Output
一个整数，代表选点的数目
Examples
Input
2
1 5
4 6
Output
1
Input
3
1 3
2 5
4 6
Output
2
思路
通过贪心算法，按照b给区间从大到小排序，当b相同时，按照a从大到小排序，再遍历得到的区间，首先取第一个区间的b作为r，若r不属于当前区间，则取当前区间的b作为r，以此得到选点的数目。
区间的遍历
while(heap.size()){
tmp = heap.top();
if(lastEnd<tmp.a||lastEnd>tmp.b){
result+=1;
lastEnd = tmp.b;
}
heap.pop();
}
C - 区间覆盖
数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]（ 1<=t<=1,000,000）。
覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)。
不可能办到输出-1
输入
第一行：N和T
第二行至N+1行: 每一行一个闭区间。
输出
选择的区间的数目，不可能办到输出-1
样例输入
3 10
1 7
3 6
6 10
样例输出
2
思路
根据贪心算法，首先将[s,t]以外的部分切掉，若互相包含，则将小区间舍弃，将区间按照a从小到大排序，区间1的起点不是1则无解。选择区间[ai,bi]后的七点设置为bi，并切掉bi之前的部分。
首先，构建结构体myPair ，其中cut函数，用于对区间进行切割。
typedef struct myPair{
int a;
int b;
int length;
void cut(int x,int y){
if(x>this->a) this->a = x;
if(y<this->b) this->b = y;
this->length = this->b-this->a;
}
void out(){
cout<<a<<","<<b<<endl;
}
}myPair;
然后将区间按照贪心准则排序，再对区间遍历。在每一次遍历过程中，若自当前区间开始，假设目标区间已改为[s,t]，则选择所有a值<=s+1的区间并将其排序，此即为相互交叉的区间，从中选择最大的，将此区间的b值定为s，直到s=t或遍历完成为止。
代码如下
for(int i=1;i<n&&(last.b!=t);i++){
in = false;
list<myPair> pl;
while((l[i].a<=s+1)&&i<n){
in = true;
l[i].cut(s+1,t);
pl.push_back(l[i]);
i++;
}
if(in) i-=1;
pl.sort(cmp2);
myPair mf = pl.front();
s = mf.b;
last = mf;
result+=1;
}
踩过的坑：
在内部选择相互交叉区间时一直不懂含义，以为只有左区间相等时才能选择最大的区间。