题解

题面描述

米小游有$n$个由小写字母组成、长度均为$m$的字符串。我们定义两个字符串$p, q$的差异值为

其中方括号 $[p_i \neq q_i]$ 为艾弗森括号，若 $p_i \neq q_i$，该处取 1，否则取 0。也就是说，差异值就是对应位置上不同字符的个数。

如果两个字符串的差异值小于等于 $k$，我们就说这两个字符串属于同一个团，或者说它们之间连一条“边”。

我们想知道，是否可以将这$n$个字符串都放到同一个“完整的团”里。根据给出的样例以及结果分析，这里的“完整的团”并不是指图论中“完全子图”，而是指所有字符串在一张无向图中处于同一个连通分量，换言之，对于任意两个字符串，我们都可以通过若干次跳转(沿着差异值 $\le k$ 的边)从一个字符串到达另一个字符串。

• 如果所有字符串本身就能处于同一个连通分量(无需删除任何字符串)，则输出：

  YES
  

• 否则输出：

  NO
  x
  

  其中 (x) 是最少需要删除的字符串数目，使得剩余的那些字符串在图中恰好位于同一个连通分量中。

思路分析

这道题的核心是将给定的字符串看作图中的节点，若两个字符串的差异值小于等于 (k)，则在它们之间建立一条边，最终要判断这些字符串是否能被归为一个连通的团。如果所有字符串能形成一个连通分量，则直接输出“YES”；如果无法形成一个连通分量，则输出“NO”并给出最少需要删除的字符串数目，这个数目等于总字符串数减去最大连通分量的大小。通过DFS（深度优先搜索）或并查集方法，分别计算图中的连通分量，并找到最大的连通分量，从而确定需要删除的最少字符串数。

1. 建图：

   • 将每个字符串看作图中的一个顶点，共 $n$ 个顶点。
   • 比较任意两条字符串的差异值，若差异值 $\le k$，则在它们之间连一条无向边。
   • 这样我们会得到一张无向图。

2. 判断图的连通性：

   • 如果这张无向图只有一个连通分量，说明所有顶点（字符串）都能通过若干条边互相到达，直接输出 YES。
   • 否则，图会分成若干个连通分量。我们希望通过删除最少的顶点，使得剩余顶点只包含在同一个连通分量里。由于删除顶点不会产生新的边，因此只可能让某些连通分量被直接“丢弃”。

3. 最少删除顶点数：

   • 若图有多个连通分量，则只需保留其中最大的那个连通分量对应的所有顶点即可，因为那个连通分量里本身已经满足了“互相可达”的要求。
   • 因此，需要删除的字符串数目 = $n - \max\_component\_size$，其中 $\max\_component\_size$ 表示连通分量中顶点数目的最大值。

4. 时间复杂度分析：

   • 我们需要进行差异值比较的次数是 $\mathcal{O}(n^2)$。
   • 每次比较两个字符串，需要 $\mathcal{O}(m)$的时间来统计差异值。
   • 整体复杂度 $\approx \mathcal{O}(n^2 \cdot m)$。在 $n\le 500, m\le 500$ 的限制下，合理实现可在可接受时间内完成。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

// 计算两个字符串的差异值
int diffValue(const string &a, const string &b) {
    int diff = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] != b[i]) {
            diff++;
        }
    }
    return diff;
}

// 在图中进行DFS，求连通分量大小
int dfs(int start, vector<bool> &visited, const vector<vector<int>> &adj) {
    stack<int> st;
    st.push(start);
    visited[start] = true;
    int count = 0;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        count++;
        // 遍历u的所有邻居
        for (auto &v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                st.push(v);
            }
        }
    }
    return count;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<string> strs(n);
        for(int i = 0; i < n; i++){
            cin >> strs[i];
        }

        // 建图: 邻接表
        vector<vector<int>> adj(n);

        // O(n^2 * m) 判断差异值是否<=k
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(diffValue(strs[i], strs[j]) <= k){
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }

        // 判断图的连通性 & 寻找最大连通分量
        vector<bool> visited(n, false);
        int maxCompSize = 0;
        int compCount = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                compCount++;
                int csize = dfs(i, visited, adj);
                maxCompSize = max(maxCompSize, csize);
            }
        }

        if (compCount == 1) {
            // 图已经是连通的
            cout << "YES\n";
        } else {
            // 不连通，最少删除 = n - 最大连通分量大小
            cout << "NO\n";
            cout << n - maxCompSize << "\n";
        }
    }
    return 0;
}

python

def diff_value(s1, s2):
    """
    计算两个等长字符串的差异值
    """
    diff = 0
    for c1, c2 in zip(s1, s2):
        if c1 != c2:
            diff += 1
    return diff

def dfs(start, adj, visited):
    """
    从 start 出发进行 DFS，返回该连通分量包含的顶点数量
    """
    stack = [start]
    visited[start] = True
    count = 0
    
    while stack:
        u = stack.pop()
        count += 1
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                stack.append(v)
    return count

def solve():
    import sys
    input_data = sys.stdin.read().strip().split()
    T = int(input_data[0])
    index = 1
    
    results = []
    for _ in range(T):
        n = int(input_data[index]); index+=1
        m = int(input_data[index]); index+=1
        k = int(input_data[index]); index+=1
        
        strs = input_data[index:index+n]
        index += n
        
        # 建图
        adj = [[] for _ in range(n)]
        
        for i in range(n):
            for j in range(i+1, n):
                if diff_value(strs[i], strs[j]) <= k:
                    adj[i].append(j)
                    adj[j].append(i)
        
        visited = [False]*n
        max_comp_size = 0
        comp_count = 0
        
        for i in range(n):
            if not visited[i]:
                comp_count += 1
                csize = dfs(i, adj, visited)
                if csize > max_comp_size:
                    max_comp_size = csize
        
        if comp_count == 1:
            results.append("YES")
        else:
            results.append("NO")
            results.append(str(n - max_comp_size))
    
    print("\n".join(results))

if __name__ == "__main__":
    solve()

Java

import java.util.*;

public class Main {
    
    // 计算两个字符串的差异值
    public static int diffValue(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
            }
        }
        return diff;
    }
    
    // DFS 返回连通分量顶点数
    public static int dfs(int start, List<List<Integer>> adj, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;
        int count = 0;
        
        while (!stack.isEmpty()) {
            int u = stack.pop();
            count++;
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }
        return count;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            sc.nextLine(); // 读掉换行符

            String[] strs = new String[n];
            for (int i = 0; i < n; i++) {
                strs[i] = sc.nextLine();
            }

            // 构建邻接表
            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }

            // O(n^2 * m)比较差异值
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (diffValue(strs[i], strs[j]) <= k) {
                        adj.get(i).add(j);
                        adj.get(j).add(i);
                    }
                }
            }

            boolean[] visited = new boolean[n];
            int maxCompSize = 0;
            int compCount = 0;
            
            // 找最大连通分量
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    compCount++;
                    int csize = dfs(i, adj, visited);
                    if (csize > maxCompSize) {
                        maxCompSize = csize;
                    }
                }
            }

            if (compCount == 1) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
                System.out.println(n - maxCompSize);
            }
        }
        sc.close();
    }
}

题目内容

米小游有 $n$ 个长度为 $m$ 且仅由小写字母组成的字符串。

定义两个字符串 $p,q$ 的差异值为$\sum_{i=0}^m[p_i≠q_i]$，其中表达式中的括号为艾弗森括号，表达式成立时为 $1$ ，否则为 $0$。

若两个字符串的差异值小于等于 $k$ ，那么两个字符串属于一个团。

现在请你帮助米小游计算能否将这 $n$ 个字符串归为一个完整的团，若可以输出“$YES$”，否则输出“$NO$”，再输出需要删除多少个字符串。

输入描述

第一行一个整数 $T(1 ≤ T ≤ 100)$，表示单个测试文件的数据组数。

对于每一组数据格式为：

第一行三个整数 $n,m,k(1≤n≤500,1≤k≤m≤500)$

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，输入仅由小写字母组成。

单个测试文件保证 $\sum n≤500$ 。

输出描述

对于每一组数据，若可以归为一个团，若可以输出"$YES$"，否则输 "$NO$"，再输出需要删除多少个字符串。

样例1

输入

2
3 2 1
ab
ba
bc
3 2 1
ab
ba
bb

输出

NO
1
YES