求Codeforces 1761C Set Construction问题的正确解法及代码修正

问题要求 #

给定n×n二进制矩阵b，构造n个集合A₁到Aₙ（元素为1到n的整数），满足：

• 每个集合非空且互不相同
• 若b[i][j]=1，则Aᵢ是Aⱼ的真子集
• 若b[i][j]=0，则Aᵢ不是Aⱼ的子集

原代码问题分析 #

1. 输入逻辑错误：嵌套循环中每次调用Console.ReadLine()读取单个元素，实际题目输入是每行n个空格分隔的整数，导致读入数据混乱。
2. 循环变量错误：多处使用j++、k++修改循环控制变量，导致循环跳过元素、逻辑混乱。
3. 构造逻辑错误：集合元素的添加/删除逻辑完全不符合题目要求，无法满足子集关系的约束。

正确算法思路 #

核心构造方法：

• 对于每个集合Aᵢ（对应代码中0-based索引i，实际为题目中的i+1）：
  1. 首先将i+1加入集合（保证集合非空，且每个集合有唯一标识元素）
  2. 遍历所有k（0-based），若b[k][i] = 1（即题目中b[k+1][i+1] = 1，表示A_{k+1}是A_{i+1}的真子集），则将k+1加入A_{i+1}
• 该构造满足所有条件：
  • 非空且互不相同：每个集合都包含唯一的i+1，因此不可能为空或重复
  • 真子集约束：若b[i][j]=1，则Aᵢ的所有元素都会被包含在Aⱼ中，且Aⱼ包含j+1（Aᵢ不包含），满足真子集要求
  • 非子集约束：若b[i][j]=0，则Aᵢ包含i+1，而i+1不在Aⱼ中（否则会推出b[i][j]=1），因此Aᵢ不是Aⱼ的子集

修正后的C#代码 #

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int t = int.Parse(Console.ReadLine());
        for (int caseNum = 0; caseNum < t; caseNum++)
        {
            int n = int.Parse(Console.ReadLine());
            int[,] b = new int[n, n];
            
            // 读入n行，每行n个整数
            for (int i = 0; i < n; i++)
            {
                int[] row = Console.ReadLine().Split().Select(int.Parse).ToArray();
                for (int j = 0; j < n; j++)
                {
                    b[i, j] = row[j];
                }
            }
            
            List<HashSet<int>> sets = new List<HashSet<int>>();
            for (int i = 0; i < n; i++)
            {
                HashSet<int> currentSet = new HashSet<int>();
                // 添加自身对应的元素（1-based）
                currentSet.Add(i + 1);
                
                // 加入所有k+1，其中b[k][i] = 1（即A_{k+1}是A_{i+1}的真子集）
                for (int k = 0; k < n; k++)
                {
                    if (b[k, i] == 1)
                    {
                        currentSet.Add(k + 1);
                    }
                }
                
                sets.Add(currentSet);
            }
            
            // 输出每个集合的元素（按题目要求格式）
            foreach (var set in sets)
            {
                Console.WriteLine(string.Join(" ", set.OrderBy(x => x)));
            }
        }
    }
}

代码说明 #

1. 输入处理：每行读取完整的一行，分割为整数数组，正确填充n×n矩阵。
2. 集合构造：严格按照算法思路构建每个集合，确保满足所有约束条件。
3. 输出格式：将集合元素排序后输出（题目未要求顺序，但排序后更清晰，符合常规输出习惯）。

内容的提问来源于stack exchange，提问作者Game of HB - YT