【作业向】程序设计思维与实践 Week3 作业

♔A 选数问题

♔Problem

Given nn positive numbers, ZJM can select exactly KK of them that sums to SS. Now ZJM wonders how many ways to get it!

♔Input

The first line, an integer T<=100T<=100, indicates the number of test cases. For each case, there are two lines. The first line, three integers indicate nn, KK and SS. The second line, nn integers indicate the positive numbers.

♔Output

For each case, an integer indicate the answer in a independent line.

♔Example

♔Input

1
2
3

1
10 3 10
1 2 3 4 5 6 7 8 9 10

♔Output

♔Note

Remember that k<=n<=16 and all numbers can be stored in 32-bit integer

♔解题思路

由题意得，本题可以使用dfs的方式枚举，dfs有三个参数x,p,sum；x表示当前应该选第x个数，p表示当前判断到了第p个数，sum表示当前选中的前x-1个数的和。在每次dfs时，首先判断如果p>s表示已经选择了s个数，则判断sum的值是否等于k，如果等于则方案数cnt加一；当p<=s时，从第p个数到第n个数开始执行dfs(x+1,i+1,sum+a[i])。当dfs结束后输出cnt即可。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int T,n,s,k,cnt;
int a[20];

void dfs(int x,int p,int sum)
{
	if(x>s)
	{
		if(sum==k) cnt++;
		return;
	}
	if(sum>=k) return;
	for(int i=p;i<=n;i++)
	{
		dfs(x+1,i+1,sum+a[i]);
	}
}

int main()
{
	int i,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&s,&k);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		cnt=0;
		dfs(1,1,0);
		printf("%d\n",cnt);
	}
	return 0;
}

♔B 区间选点

♔Problem

数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）

♔Input

第一行1个整数N（N<=100）
第2~N+1行，每行两个整数a,b（a,b<=100）

♔Output

一个整数，代表选点的数目

♔Examples

♔Input 1

1
2
3

2
1 5
4 6

♔Output 1

♔Input 2

♔Output 2

♔解题思路

由题意可知，这是一道贪心题，我们需要用最少的点来覆盖尽可能多的点。

那么我们的贪心策略是将区间按右端点升序排序，右端点相同的按左端点降序排序（其实没必要），然后从第一个区间开始，选择该区间的右端点，然后遍历剩下的节点，若遇到未被当前节点选择的区间，则选择该区间的右端点，节点数加一并将当前节点设置为该点，继续遍历，直到遍历完所有的节点为止。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
struct data
{
	int x,y;
}line[105];
int n,cnt,pre;

int wly(data a,data b)
{
	if(a.y<b.y) return 1;
	if(a.y==b.y)
	{
		return a.x<b.x;
	}
	return 0;
}

int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&line[i].x,&line[i].y);
	sort(line+1,line+1+n,wly);
	for(i=1;i<=n;i++)
	{
		if(pre>=line[i].x && pre<=line[i].y) continue;
		cnt++;
		pre=line[i].y;
	}
	printf("%d",cnt);
	return 0;
}

♔C 区间覆盖

♔Problem

数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]（ 1<=t<=1,000,000）。
覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)。
不可能办到输出-1

♔Input

第一行：N和T
第二行至N+1行: 每一行一个闭区间。

♔Output

选择的区间的数目，不可能办到输出-1

♔Examples

♔Input

♔Output

♔解题思路

这一题也是一个很经典的区间问题的贪心题目，贪心的策略是首先读入的时候排除掉完全在区间 [1, t]之外的区间，然后将剩下的区间按照左端点进行升序排序。先将所选择的区间能够覆盖道的最远点x设为0，然后从第一个区间开始，如果该区间的左端点小于等于x+1，那么选择该区间，并当区间的左端点小于等于x+1时进行循环，求出被覆盖的区间能够覆盖到的最远点maxx，选择的区间数cnt+1，并将x设为maxx然后继续遍历各个区间。当循环结束后判断x若大于等于T则输出cnt，否则不能覆盖 [1, t]，输出-1。

ps：这一题wa了好几发，坑点在于最开始没有说是覆盖离散的点，意识到这个问题之后就A了

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
struct data
{
	int x,y;
} line[1000005];
int n,cnt=0,bac,maxn,T;

int wly(data a,data b)
{
	return a.x<b.x;
}

int main()
{
	int i,j;
	while(scanf("%d%d",&n,&T)!=EOF)
	{
		for(i=1; i<=n; i++)
		{
			scanf("%d%d",&line[i].x,&line[i].y);
			if(line[i].y<1 || line[i].x>T) i--,n--;
		}
		sort(line+1,line+1+n,wly);
		bac=0;
		cnt=0;
		for(i=1; i<=n; i++)
		{
			if(line[i].x<=bac+1)
			{
				maxn=line[i].y;
				while(line[i].x<=bac+1)
				{
					maxn=max(maxn,line[i].y);
					i++;
					if(i>n) break;
				}
				i--;
				bac=maxn;
				cnt++;
			}
			if(bac>=T) break;
		}
		if(bac>=T) printf("%d\n",cnt);
		else printf("-1\n");
	}
	return 0;
}