CF549B Looksery Party

    • 30通过
    • 55提交
  • 题目来源 CodeForces 549B
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    Looksery 公司由 $n$ 名员工所组成,每个员工都有自己的电话和联系人列表。

    最近,公司打算举办一场大型派对,每位到场的员工,都会向他的联系人发送消息,来说明这场派对有多炫酷。由于每个人都想花尽量多的时间来享受派对时光,他们会不假思索地向所有联系人发送消息,甚至包括他们自己。

    Looksery 公司的开发者 Igor 和 Max 就每个人收到了多少条消息展开了争论. Igor 钦点了 $n$ 个数字,其中第 $i$ 个数字表示 Igor 认为第 $i$ 个人收到的消息条数。如果 Igor 猜到了至少 $1$ 个数字就算他胜利,否则 Max 胜利。

    作为 Max 的支持者,你需要根据员工的联系人列表,确定是否存在 Igor 会输的情况。具体来说,你需要确定哪些人应该参加派对,使得派对结束后,任意一个人收到的消息条数与 Igor 所给出的不同。

    输入输出格式

    输入格式

    第一行一个正整数 $n(1 \le n \le 100)$ ,表示 Looksery 公司的员工数量。

    接下来 $n$ 行描述了所有员工的联系人列表,每行为一个长度为 $n$ 的字符串。若第 $i$ 行的第 $j$ 个字符为 $1$ ,则第 $j$ 名员工在第 $i$ 名员工的联系人列表中,否则就不在。特别地,第 $i$ 个人总是在自己的联系人列表中。

    最后一行 $n$ 个由空格隔开的数字 $a_1,a_2,...,a_n(0 \le a_i \le n)$ ,表示 Igor 所认为的每个员工会收到的消息数量。

    输出格式

    第一行一个整数 $m$ 表示参加派对的人数。

    第二行 $m$ 个正整数,表示参加派对的员工的编号。

    如果有多种方案满足条件,输出其中任意一种即可。

    如果 Igor 无论如何都会赢,输出 $-1$ 。

    感谢@悠悠我昕 提供翻译

    题目描述

    The Looksery company, consisting of $ n $ staff members, is planning another big party. Every employee has his phone number and the phone numbers of his friends in the phone book. Everyone who comes to the party, sends messages to his contacts about how cool it is. At the same time everyone is trying to spend as much time on the fun as possible, so they send messages to everyone without special thinking, moreover, each person even sends a message to himself or herself.

    Igor and Max, Looksery developers, started a dispute on how many messages each person gets. Igor indicates $ n $ numbers, the $ i $ -th of which indicates how many messages, in his view, the $ i $ -th employee is going to take. If Igor guesses correctly at least one of these numbers, he wins, otherwise Max wins.

    You support Max in this debate, so you need, given the contact lists of the employees, to determine whether there is a situation where Igor loses. Specifically, you need to determine which employees should come to the party, and which should not, so after all the visitors send messages to their contacts, each employee received a number of messages that is different from what Igor stated.

    输入输出格式

    输入格式:

    The first line contains a single integer $ n $ ( $ 1<=n<=100 $ ) — the number of employees of company Looksery.

    Next $ n $ lines contain the description of the contact lists of the employees. The $ i $ -th of these lines contains a string of length $ n $ , consisting of digits zero and one, specifying the contact list of the $ i $ -th employee. If the $ j $ -th character of the $ i $ -th string equals 1, then the $ j $ -th employee is in the $ i $ -th employee's contact list, otherwise he isn't. It is guaranteed that the $ i $ -th character of the $ i $ -th line is always equal to 1.

    The last line contains $ n $ space-separated integers: $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=n $ ), where $ a_{i} $ represents the number of messages that the $ i $ -th employee should get according to Igor.

    输出格式:

    In the first line print a single integer $ m $ — the number of employees who should come to the party so that Igor loses the dispute.

    In the second line print $ m $ space-separated integers — the numbers of these employees in an arbitrary order.

    If Igor wins the dispute in any case, print -1.

    If there are multiple possible solutions, print any of them.

    输入输出样例

    输入样例#1: 复制
    3
    101
    010
    001
    0 1 2
    
    输出样例#1: 复制
    1
    1 
    
    输入样例#2: 复制
    1
    1
    1
    
    输出样例#2: 复制
    0
    
    
    输入样例#3: 复制
    4
    1111
    0101
    1110
    0001
    1 0 1 0
    
    输出样例#3: 复制
    4
    1 2 3 4 
    

    说明

    In the first sample Igor supposes that the first employee will receive $ 0 $ messages. Since he isn't contained in any other contact list he must come to the party in order to receive one message from himself. If he is the only who come to the party then he will receive $ 1 $ message, the second employee will receive $ 0 $ messages and the third will also receive $ 1 $ message. Thereby Igor won't guess any number.

    In the second sample if the single employee comes to the party he receives $ 1 $ message and Igor wins, so he shouldn't do it.

    In the third sample the first employee will receive $ 2 $ messages, the second — $ 3 $ , the third — $ 2 $ , the fourth — $ 3 $ .

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。