2023首届大学生算法大赛——补题_算法大赛cff 第一届 赛题

1. 拿饼干

内存限制：128Mb

时间限制：1s

题目描述

小明今天外出野炊。他的母亲为他制作了M种他喜欢的饼干，共有N块。每块饼干都被标了编号，从1一直标到N。第i块饼干的重量是W[i]。饼干种类的编号是T[i]，从1一直到M。小明想尽可能拿到最大总重量的饼干，但每种饼干只拿一块，而且他的背包的最大承重不能超过C。请帮助小明进行选择，别忘了要确保每种饼干至少拿一块。

输入

第一行包含三个整数N,M,C，之间用一个空格隔开。N代表饼干总数，M代表饼干种类数，C代表小明的背包的总重量。

第二行包含包含N个整数，W[1], W[2], …, W[i], …, W[N]，之间用一个空格隔开，标明了每块饼干的重量。

第三行包含N个整数，T[1], T[2], …, T[i], …, T[N] ，之间用一个空格隔开，标明了每块饼干的类型。

输出

显示小明的背包拿足了饼干后的重量。

样例输入

复制

5 3 50
10 3 23 13 21
1 2 2 1 3

样例输出

复制

37

提示

约束条件

1 <= M <= N <= 500

1 <= C <= 10000

1 <= W[i] <= 50

1 <= T[i] <= M

输入样例 1

5 3 50

10 3 23 13 21

1 2 2 1 3

输出样例 1

37

输入样例说明1

小明可以这样选择饼干：

1. 重量为13的第1种饼干；

2. 重量为3的第2种饼干；

3. 重量为21的第3种饼干；

因此总重量为13 + 3 + 21 = 37，未超过背包的最大承重。

输入样例 2

3 2 10

11 12 13

1 2 1

输出样例 2

0

输入样例说明2

小明无论怎么拿都超过了背包最大承重量，因此无法拿走任何一块饼干。

题解 ：

分析：典型的分组背包，为确保每种饼干至少拿一块，所以要做标记。

#include<iostream>
#include<cstring>
using namespace std;
int n,m,c;
int s[501],t[501],w[501][501];
int dp[10003],vis[10003],vis2[10003];
 
int main(){
	cin>>n>>m>>c;
	for(int i=1; i<=n; i++) cin>>t[i];
	for(int type,i=1; i<=n; i++){
		cin>>type;
		w[type][++s[type]]=t[i];
	}
	for(int i=1; i<=m; i++){
		for(int j=1;j<=c;j++) vis[j]=vis2[j];
		memset(vis2, 0, sizeof(vis2));
		for(int j=c; j>=1; j--){
			for(int k=1; k<=s[i]; k++){
				if(j>=w[i][k]&&(i==1||vis[j-w[i][k]])){
					if(dp[j-w[i][k]]+w[i][k]>dp[j]){
						dp[j]=dp[j-w[i][k]]+w[i][k];
						vis2[j]=1;
					}
				}
			}
		}
	}
	cout<<dp[c];
	return 0;
}

2. 村庄

内存限制：64Mb

时间限制：1s

题目描述

很久很久以前, 在一个国家里有N个村庄。起初，这N个村庄相互之间通过M座桥梁相连，桥梁从1到M进行编号。第i座桥在第Ai​个村庄和第Bi​个村庄之间进行连接。因此人们可以在任意两个村庄之间利用这些桥梁进行通行。

为了阻止人们相互联络，入侵者决定一个接一个地毁坏这些桥梁。从第1座桥开始，依次摧毁，直至第K(1 <= K <= M)座桥。

村庄a和村庄b组成一个村庄组合(a, b)(a < b)，当第一座桥到第K座桥被依次摧毁后，计算到底有多少个 (a, b)(a < b)这样的村庄组合不能通过剩余的一座或多座桥梁进行来往通行。

输入

第一行包含三个整数N, M, K,分别表示村庄总数、桥梁总数和被摧毁的桥梁数目。

接着有M行，每一行包含两个整数ai, bi，表示由第i座桥梁连接着的两个村庄的编号。

输出

打印出在第一座桥到第K座桥被摧毁后相互不能通行村庄组合的数目。

样例输入

复制

4 5 3
1 2
2 3
3 4
4 1
1 3

样例输出

复制

3

提示

数据范围：

       2 <= N <= 10^5

       1 <= K <= M <= 10^5

       1 <= ai < bi <= N

       所有的村庄组合(ai, bi) 各不相同。

题解： 

分析：这道题跟图论不占边，考的是并查集的算法。

#include<iostream>
using  namespace std;
int n,m,k;
int pre[100003],num[100003];
 
int find(int x){
	if(x==pre[x]) return x;
	return pre[x]=find(pre[x]);
}
 
void join(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		pre[fx]=fy;
	}
}
 
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) pre[i]=i;
	for(int x,y,i=1;i<=m;i++){
		cin>>x>>y;
		if(i>k){
			join(x,y);
		}
	}
	for(int i=1; i<=n; i++){
		num[find(i)]++;
	}
	long long ans=0;
	for(int i=1; i<=n; i++){
		if(num[i]){
			for(int j=i+1; j<=n; j++){
				if(num[j]) ans+=num[i]*num[j];
			}
		}
	}
	cout<<ans;
	return 0;
}

3. 幸运数字

内存限制：64Mb

时间限制：1s

题目描述

数字8、2、6、9是大多数中国人中最喜欢的幸运数字。这几个数字的组合也被视为幸运数字，例如88。

小龙非常喜欢幸运数字。他认为只有满足以下条件的正整数才算是好的整数：

8、2、6、9中的每个数字至少在这个整数中出现一次，而且没有除了这四个之外的其他数字。

小龙想知道在1和N（含N）之间有多少个满足这一条件的整数。

输入

输入一个整数N。

输出

打印输出1到N（含N）之间幸运数字的总数量。

样例输入

复制

5673

样例输出

复制

6

提示

数据范围：

       1 <= N < 10^12

样例说明：

       有6个不大于5673的幸运数字：2689、2698、2869、2896、2968、2986

题解： 

分析：DFS。（学习了此人的博客）2023首届大学生算法大赛——正式赛 5、7（DFS）_panjyash的博客-CSDN博客

#include<iostream>
using namespace std;
typedef long long LL;
LL n,ans;
 
void dfs(LL u,bool f2,bool f6,bool f8,bool f9){
	if(u>n) return ;
	if(f2&&f6&&f8&&f9) ans++;
	dfs(u*10+2,1,f6,f8,f9);
	dfs(u*10+6,f2,1,f8,f9);
	dfs(u*10+8,f2,f6,1,f9);
	dfs(u*10+9,f2,f6,f8,1);
}
 
int main(){
	cin>>n;
	dfs(0, 0, 0, 0, 0);
	cout<<ans;
	return 0;
}