欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

week3作业

程序员文章站 2022-07-09 18:53:13
...

题目一 选数问题

题目描述

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

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

output 1

4

做法与思路

一个比较典型的深搜问题,但值得注意的是如果单纯深搜会引起重复问题,如样例可能会出现1 4 5和4 5 1当做两种情况,实质上它们选择的数据是一样的。我们注意到按照深搜标准,如果已经达到了4作为第一个所选数的时候,那么1 4,2 4,3 4在之前必然已经出现过,所以选择的n个数应是递增关系,这样就可以保证某组数的唯一性。我这里额外声明了一个dana变量来记录当前所选数字,保证后面的数字都要比它大,从而去重。
关于终止条件,如果和大于给定值,跳出。所选数超过定值数目,跳出。等于给定值时所选个数不等于给定数目,跳出。这一点比较好判断。

代码

#include <iostream>
#include <cstring>
using namespace std; 
int a,b,c;//数据长度、选择数量、和 
int numble;//记录种类数 
int d[1000];
bool vis[1000];
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void dfs(int sum,int x,int dana)//当前的和及选择数量 
{
	if(sum>c)
	return ;
	if(sum==c)
	{
		if(x==b)
			numble++;
		return ;
	}
	if(x>b) return;
	for(int i=dana;i<a;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;
			dfs(sum+d[i],x+1,i+1);
			vis[i]=0;
		}
	}
}
int main(int argc, char** argv) {
	int tnumble;
	cin>>tnumble;
	for(int i=0;i<tnumble;i++)
	{
		memset(vis,0,sizeof(vis));
		numble=0;
		cin>>a>>b>>c;
		for(int j=0;j<a;j++)
		{
			cin>>d[j];
		}
		dfs(0,0,0);
		cout<<numble<<endl;
	}
	return 0;
}

题目二 区间选点

题目描述

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

input

第一行1个整数N(N<=100)
第2~N+1行,每行两个整数a,b(a,b<=100)

output

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

example

input 1

2
1 5
4 6

output 1

1

input 2

3
1 3
2 5
4 6

output 2

2

做法与思路

由于上课时已经介绍过做法,所以并没有花费多少时间。
我们要选最少的点,所以要尽可能让每个点覆盖最多的区间。首先将所有区间按照右端点进行排序,把点在不离开区间的情况下尽可能的放在右边。直到下一个区间的左端点在点的右侧时(此时不得不增加新点),在新区间的右端放置新端点即可.

代码

#include <iostream>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct range{
	int a,b;
	range()
	{
		a=0;b=0;
	}
};
bool bijiao(range t1,range t2)
{
	return t1.b<t2.b;
}
int main(int argc, char** argv) {
	int numble_of_range;
	int numble=0;//选点的个数 
	cin>>numble_of_range;
	int judge=0;
	range t[100];
	for(int i=0;i<numble_of_range;i++)
	{
		int x,y;
		cin>>x>>y;
		t[i].a=x;
		t[i].b=y;
	}
	sort(t,t+numble_of_range,bijiao);
	for(int i=0;i<numble_of_range;i++)
	{
		if(t[i].a>judge)
		{
			judge=t[i].b;
			numble++;
		}
	}
	cout<<numble;
	return 0;
}

题目三 区间覆盖

题目描述

数轴上有 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

example

input 1

3 10
1 7
3 6
6 10

output 1

2

做法与思路

某种程度上与第二题有些类似,要使每个区间尽可能覆盖多的点。如对于线段上某数值为i的点,我们要在左端点小于等于i的区间中挑选出一个右端点最大的区间(不妨设右端点为b),新的起始点就变成了b,再以同样的贪心策略进行即可。如果中间出现断层,即所有区间的左端点都大于i,那么无法覆盖。
先根据区间的左端点对区间进行排序,以方便后来寻找可挑选的区间。

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct range{
	int a,b;
	range()
	{
		a=0;b=0;
	}
	range(int m,int n)
	{
		a=m;b=n;
	}
};
bool bijiao(range m,range n)
{
	return m.a<n.a;
}
range t[25000];
int main(int argc, char** argv) {
	int numble_of_range,finally;
//	cin>>numble_of_range>>finally;
	scanf("%d%d",&numble_of_range,&finally);
	for(int i=0;i<numble_of_range;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		t[i]=range(a,b);
	}
	sort(t,t+numble_of_range,bijiao);
	int judge=0;//记录上个区间的尾 
	int sum=0;
	int j=0;//记录上次搜索到的区间 
	while(judge<finally)
	{
		int maxium=judge;//记录右侧最远点 
		for(int i=j;i<numble_of_range;i++)
		{
			if(t[i].a<=judge+1)//两个区间必须相邻 
			{
				maxium=max(t[i].b,maxium);//第二个区间里选一个右侧最远的
				j=i; 
			}
			else break;
		}
		if(maxium<=judge)//没找到更远的右侧点
		{
			printf("-1");
			return 0;
		}
		judge=maxium;
		sum++;
	}
	printf("%d",sum);
	return 0;
}







上一篇: week3 作业

下一篇: week3作业C