2025/03/09训练

2025/03/09训练

L3-001 凑零钱

n,m = map(int,input().split())
num = list(map(int,input().split()))
num = [0] + num
num.sort(reverse = True)
ans = []
dp = [[0 for _ in range(m+1)]for _ in range(n+1)]
dp[0][0] = True
for i in range(1,n+1):
    for j in range(m+1):
        dp[i][j] = dp[i-1][j]
        if j >= num[i] and dp[i-1][j-num[i]]:
            dp[i][j] = True
if dp[n][m] == False:
    print("No Solution")
else :
    for i in range(n-1,0,-1):
        if m - num[i] >= 0:
            if dp[i-1][m-num[i]]:
                ans.append(num[i])
                m -= num[i]
for i in range(0,len(ans)-1):
    print(ans[i],end = ' ')
print(ans[len(ans)-1])

L2-005 集合相似度

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,k;
	cin>>n;
	set<int>num[55];
	for (int i=1;i<=n;i++)
	{
		cin>>m;
		for(int j=1;j<=m;j++)
		{
			int l;
			cin>>l;
			num[i].insert(l);
		}
	}
	cin>>k;
	for (int i=1;i<=k;i++)
	{
		int a,b;
		cin>>a>>b;
		int count = 0;
		int aa = num[a].size();
		int bb = num[b].size();
		set<int>::iterator iter;
		for (iter = num[a].begin();iter!=num[a].end();iter ++)
		{
			if (num[b].find(*iter)!=num[b].end())
			{
				count ++;
			}
		}
		printf("%.2f%%\n",count*1.0/(aa+bb-count)*100);
	}
	return 0;
}

n = int(input())
sets = []
for _ in range(n):
    line = list(map(int,input().split()))
    M = line[0]
    current_set = set(line[1:])
    sets.append(current_set)
k = int(input())
for _ in range(k):
    i,j = map(int,input().split())
    set1 = sets[i - 1]
    set2 = sets[j - 1]
    intersection_count = len(set1.intersection((set2)))
    union_count = len(set1.union(set2))
    similarity = (intersection_count / union_count) * 100
    print(f"{similarity:.2f}%")