题解

题面描述

给定$n$个字符串集合，每个集合$S_i$包含$A_i$个字符串。对于每个集合$S_i$，需要找到另一个集合$S_j$（$j \neq i$），使得$S_i$与$S_j$的交集中字符串的数量最多。如果存在多个满足条件的$S_j$，则选择序号最小的那个。如果$S_i$与任何其他集合的交集都为空，则选择序号最小的$S_j$（$j \neq i$），并输出交集的字符串数量为$0$。

思路

1. 数据结构选择：

   • 使用vector<set<string>>来存储所有的字符串集合。set可以自动去重，并且支持高效的查找操作（$O(\log n)$时间复杂度）。

2. 读取输入：

   • 首先读取集合的数量$n$。
   • 对于每个集合$S_i$，读取其包含的字符串数量$A_i$，然后将这些字符串存入对应的set中。

3. 计算交集：

   • 对于每个集合$S_i$，遍历所有其他集合$S_j$（$j \neq i$），计算$S_i$与$S_j$的交集大小。
   • 具体实现上，遍历$S_i$中的每个字符串，检查它是否存在于$S_j$中，如果存在，则计数加一。

4. 选择最优集合：

   • 对于每个$S_i$，记录与之交集最大的$S_j$的序号和交集大小。
   • 如果有多个$S_j$的交集大小相同，则选择序号最小的$S_j$。
   • 如果所有$S_j$与$S_i$的交集大小都为$0$，则选择序号最小的$S_j$（$j \neq i$），并输出交集大小为$0$。

5. 处理边界情况：

   • 当$n=1$时，只有一个集合，按照题意此时不会出现，因为$1 < n \leq 100$。
   • 当某个集合$S_i$与所有其他集合的交集都为空时，确保选择序号最小的$S_j$（$j \neq i$）。

cpp

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

int main(){
    int n; // 集合的数量
    cin >> n;
    // 使用vector存储每个集合，集合内部使用set以便快速查找
    vector< set<string> > sets(n);
    
    // 读取每个集合的字符串
    for(int i=0; i<n; i++){
        int Ai; // 第i个集合中的字符串数量
        cin >> Ai;
        for(int j=0; j<Ai; j++){
            string s;
            cin >> s;
            sets[i].insert(s); // 将字符串插入到第i个集合中
        }
    }
    
    // 对于每个集合Si，寻找与其交集最大且序号最小的Sj
    for(int i=0; i<n; i++){
        int max_common = -1; // 当前最大的交集大小
        int chosen_j = -1; // 选择的集合Sj的序号（1-based）
        for(int j=0; j<n; j++){
            if(j == i) continue; // 跳过与自身比较
            // 计算Si与Sj的交集大小
            int common = 0;
            for(const auto &s : sets[i]){
                if(sets[j].count(s)) common++;
            }
            // 如果当前交集大小大于之前的最大值，更新max_common和chosen_j
            if(common > max_common){
                max_common = common;
                chosen_j = j+1; // 序号从1开始
            }
            // 如果当前交集大小等于最大值，并且j的序号更小，则更新chosen_j
            else if(common == max_common && (chosen_j == -1 || (j+1) < chosen_j)){
                chosen_j = j+1;
            }
        }
        // 如果所有交集大小都是0，选择序号最小的集合Sj（j≠i）
        if(max_common == 0){
            chosen_j = 1;
            if(chosen_j == i+1 && n >1){
                chosen_j = 2;
            }
        }
        // 输出结果：Sj的序号和交集大小
        cout << chosen_j << " " << (max_common >0 ? max_common : 0) << "\n";
    }
    return 0;
}

python

# 读取集合的数量
n = int(input())

# 用来存储每个字符串对应的集合索引
string_to_sets = {}

# 存储每个集合的字符串元素
sets = [0]  # sets[0]不使用，集合编号从1开始

# 读取每个集合的信息
for i in range(1, n + 1):
    ai = int(input())  # 当前集合的元素数量
    current_set = {input() for _ in range(ai)}  # 当前集合的字符串元素
    sets.append(current_set)  # 将当前集合添加到集合列表中

    # 更新每个字符串所在的集合索引
    for string in current_set:
        if string not in string_to_sets:
            string_to_sets[string] = []
        string_to_sets[string].append(i)

# 对每个集合进行交集大小的计算
for i in range(1, n + 1):
    intersection_count = [0] * (n + 1)  # 用来统计每个集合与集合i的交集大小

    # 统计与集合i有交集的其他集合
    for string in sets[i]:
        for set_idx in string_to_sets[string]:
            intersection_count[set_idx] += 1

    # 排除集合i本身和计数器的初始化值
    intersection_count[i] = intersection_count[0] = -1

    # 输出与集合i交集最大的集合序号和交集大小
    print(intersection_count.index(max(intersection_count)), max(intersection_count))

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取集合的数量
        int n = Integer.parseInt(scanner.nextLine());

        // 用来存储每个字符串对应的集合索引
        Map<String, List<Integer>> stringToSets = new HashMap<>();

        // 存储每个集合的字符串元素
        List<Set<String>> sets = new ArrayList<>();
        sets.add(new HashSet<>());  // sets[0]不使用，集合编号从1开始

        // 读取每个集合的信息
        for (int i = 1; i <= n; i++) {
            int ai = Integer.parseInt(scanner.nextLine());  // 当前集合的元素数量
            Set<String> currentSet = new HashSet<>();
            for (int j = 0; j < ai; j++) {
                String str = scanner.nextLine();
                currentSet.add(str);  // 当前集合的字符串元素
            }
            sets.add(currentSet);  // 将当前集合添加到集合列表中

            // 更新每个字符串所在的集合索引
            for (String str : currentSet) {
                stringToSets.putIfAbsent(str, new ArrayList<>());
                stringToSets.get(str).add(i);
            }
        }

        // 对每个集合进行交集大小的计算
        for (int i = 1; i <= n; i++) {
            int[] intersectionCount = new int[n + 1];  // 用来统计每个集合与集合i的交集大小

            // 统计与集合i有交集的其他集合
            for (String str : sets.get(i)) {
                for (int setIdx : stringToSets.get(str)) {
                    intersectionCount[setIdx] += 1;
                }
            }

            // 排除集合i本身和计数器的初始化值
            intersectionCount[i] = -1;
            intersectionCount[0] = -1;

            // 输出与集合i交集最大的集合序号和交集大小
            int maxIntersection = -1;
            int maxSetIdx = -1;
            for (int j = 1; j <= n; j++) {
                if (intersectionCount[j] > maxIntersection) {
                    maxIntersection = intersectionCount[j];
                    maxSetIdx = j;
                }
            }

            System.out.println(maxSetIdx + " " + maxIntersection);
        }

        scanner.close();
    }
}

题目内容

两个集合$A$和$B$的交集指的是，所有属于集合$A$目属于集合$B$的元素所组成的集合。

给定$n$个字符串集合，每个字符串集合$si(1 <=i<=n)$中字符串数目为$Ai$，对每个字符串集合$Si$，请找到序号最小的$j(j≠i)$满足$Sj$与$Si$的交集中字符串个数最多，并输出与交集中的字符串个数。如果$Si$与任何其他集合的交集都为空。

我们认为交集个数全部为$0$，输出其他集合中序号最小的即可。例如样例$1$中S4输出的是$1\ 0$；例如$S1$与其他集合交集全为空，则输出$2\ 0$.

输入描述

第一行一个数$n$，表示字符串集合的数量;从第二行开始，共分为$n$个部分:

第$i$部分第一行一个数$Ai$，表示该字符串集合$Si$中的字符串数量;下接$Ai$行，代表$Si$内的所有字符串。

约束:

$1、1 <n <=100$

$2、0 <Ai <= 100$

$3$、单个字符串的长度为$len, 0 < len <= 100$

字符串中只包含大小写字母与数字

输出描述

输出共$n$行，每行两个数字$j$和$x$，分隔符为$1$个空格；$j$代表与$Si$交集中字符串个数最多的是$Sj$；$x$代表$Si$与$Sj$交集中的字符串个数。

样例1

输入

4
3
123
456
789
3
234
345
4567
5
123
456
789
0123
4567
1
6789

输出

3 3
3 1
1 3
1 0

说明

1.对于字符串集合$S1${"$123$","$456$","$789$}，与$S3$的交集中字符串个数最多，它俩的交集中有$3$个字符串，即{"$123$","$456$","$789$"}

$2$.对于字符串集合$S2${"$234$","$345$'',"$4567$"}，与$S3$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$4567$"}

$3$.对于字符串集合$S3${"$123$","$456$","$789$","$0123$","$4567$”}，与其$S1$的交集中字符串个数最多，它俩的交集中有$3$个字符串，即{"$123$","$456$","$789$"}

$4$.对于字符串集合$S4${"$6789$"}，与$S1、S2、S3$的交集全部为空，序号最小的是$S1$,输出$1\ 0$。

样例2

输入

3
2
123
678
3
728
8888
1000
2
123
728

输出

3 1
3 1
1 1

说明

$1$.对于字符串集合$S1${"$123$","$678$"}，与$S3$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$123$"}

$2$.对于字符串集合$S2$ {"$728$","$8888$","$1000$"}，与$S3$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$728$"}

$3$.对于字符串集合$S3${"$123$","$728$"}，与$S1$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$123$"}