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;
}
