火眼金睛_搜狗笔试题

cycleof

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int main(){
    int i,j,r,q,n,temp1,temp2;//问题数
    while(cin >> n){
        vector<vector<int> > p;//处理不均衡的数组有效
        vector<int> pp;
        set<int> ppp;//自动去重排序
        int s[1000000] = {0};
        for(i=0;i<n;i++){
            pp.clear();
            cin >> temp1;
            pp.push_back(temp1);
            cin >> temp2;
            pp.push_back(temp2);
            for(j=0;j<temp2;j++){
                cin >> temp1;
                pp.push_back(temp1);
            }
            p.push_back(pp);
        }
        for(i=0;i<p.size();i++){
            int count = 0;
            for(j=2;j<p[i].size();j++){
                int z = p[i][j];
                if(s[z] == -1){//该问题说谎者人数
                    count++;
                }
                if(z == p[i][0])//自己回答自己则不在搜索
                    continue;
                for(q=i+1;q<p.size();q++){
                    if(p[q][0] == z){
                        for(r=2;r<p[q].size();r++){//该问题回答者的提问，该问题提问者是否也回答了，两者都有问题
                            if( p[q][r] == p[i][0] ){
                                s[p[i][0]] = -1;s[z] = -1;
                                ppp.insert(p[i][0]);
                                ppp.insert(z);
                                break;
                            }
                        }
                    }
                }
            }
            if(count >= 2){//超过两个的说谎者回答了该问题，故提问者作弊
                s[p[i][0]] = -1;
                ppp.insert(p[i][0]);
            }
        }
        cout<<ppp.size()<<endl;
        int cc=0;
        for(auto it=ppp.begin();it!=ppp.end();it++){
            if(++cc == ppp.size())
                cout<<*it<<endl;
            else cout<<*it<<" ";
        }
    }
}

发表于 2017-07-25 17:54:19 回复(0)

paragogh

#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
using namespace std;
int main(int argc, char** argv) {
	int N;
	while (scanf("%d", &N) != EOF) {
		map<int, set<int> > m;
		for (int i = 0; i < N; i++) {
			int askId;
			cin >> askId;
			int num;
			cin >> num;
			if (m.find(askId) == m.end()) {
				set<int> tmp;
				for (int j = 0; j < num; j++) {
					int awserId;
					cin >> awserId;
					if (awserId != askId) {
						tmp.insert(awserId);
						//cout << askId << ","<<awserId << " " << endl;
					}

				}
				if (!tmp.empty()) {
					m.insert(make_pair(askId, tmp));
				}

			}
			else {
				for (int j = 0; j < num; j++) {
					int awserId;
					cin >> awserId;
					if (askId != awserId) {
						m[askId].insert(awserId);
						//cout << askId << "," << awserId << " " << endl;
					}

				}
			}


		}
		//cout << "size: " << m.size() << endl;
		set<int> res;
		for (auto it = m.begin(); it != m.end(); ++it) {
			for (auto ite = it->second.begin(); ite != it->second.end(); ++ite) {
				if (m.find(*ite) != m.end()) {
					if (m[*ite].find(it->first) != m[*ite].end()) {
						res.insert(it->first);
						res.insert(*ite);
					}
					
				}
				//cout << *ite << " ";
			}
			//cout << endl;
		}
		int sz = res.size();
		while (1) {
			for (auto it = m.begin(); it != m.end(); ++it) {
				int count = 0;
				for (auto ite = it->second.begin(); ite != it->second.end(); ++ite) {
					if (res.find(*ite) != res.end()) {
						count++;
					}
				}
				if (count >= 2) {
					res.insert(it->first);
				}
			}
			if (sz != res.size()) {
				sz = res.size();
			}
			else {
				break;
			}
		}

		cout << res.size() << endl;
		if (!res.empty()) {
            bool first = true;
			for (auto it = res.begin(); it != res.end();++it) {
                if(first) {
                    cout<<*it;
                    first = false;
                } else {
                    cout <<" "<<*it;
                }
				
			}
			cout << endl;
		}

	}
	return 0;
}

发表于 2016-09-14 18:47:54 回复(0)

Java

猫时雨

ac了，输出注意的地方：

1.第一行为个数，第二行为id，空格分开，最后一个数字后没有空格

2.如果个数为0，不要输出空行直接输下个用例了

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNextLine()) {
            int n = Integer.parseInt(input.nextLine());
            //每个出题者set
            Set<Long> lzs = new HashSet<>(n);
            //每个出题者的回答者set（去重，不包含自己）
            Map<Long, Set<Long>> qs = new HashMap<>();
            for (int i = 0; i < n; i++) {
                String line = input.nextLine();
                String[] all = line.split(" ");
                Long lz = Long.valueOf(all[0]);
                lzs.add(lz);
                Set<Long> set = qs.get(lz);
                if (set == null) {
                    set = new HashSet<>();
                    qs.put(lz, set);
                }
                for (int j = 1; j < all.length; j++) {
                    Long as = Long.valueOf(all[j]);
                    if (as != lz) set.add(as);
                }
            }
            Set<Long> cheater = fun(lzs, qs);
            List<Long> list = new ArrayList<>(cheater);
            Collections.sort(list);
            System.out.println(list.size());
            //如果个数为0，直接进行下个用例
            if(list.size()==0) continue;    
            for (int i = 0; i < list.size(); i++) {
                if (i > 0) System.out.print(" ");
                //数字间空格分开，最后一个后面不要空格
                System.out.print(list.get(i));
            }
            System.out.println();//换行
        }
    }

    public static Set<Long> fun(Set<Long> lzs, Map<Long, Set<Long>> qs) {
        Set<Long> cheater = new HashSet<>();
        //判断第一种情况作弊：互相回答问题
        for (Long lz : lzs) {     
            //对于每一个发问者lz ,找到回答他问题的回答者answers    
            Set<Long> answers = qs.get(lz); 
            if (answers != null) {
                for (Long answer : answers) {
                    Set<Long> answerAsLz = qs.get(answer); 
                    if (answerAsLz != null && answerAsLz.contains(lz)) {
                        //回答者的提问中是否有lz回答的问题 
                        cheater.add(lz);
                        cheater.add(answer);
                    }
                }
            }
        }
        //第二种情况
        boolean flag = false;//是否有新的作弊者加入
        //当有新作弊者加入后要重新检查第二种作弊情况
        do {
            flag = false;
            //对于每一个发问者lz
            for (Long lz : lzs) {     
                //lz已经是作弊者，则跳过
                if (cheater.contains(lz)) continue; 
                //找到回答他问题的回答者answer
                Set<Long> answers = qs.get(lz); 
                int times = 0;
                for (Long cheat : cheater) {
                    if (answers.contains(cheat)) times++;
                    //如果有两个作弊者回答了lz问题，则lz作弊
                    if (times >= 2) break;
                }
                if (times >= 2) {
                    cheater.add(lz);
                    flag = true;//有新作弊者加入
                }
            }
        } while (flag);
        return cheater;
    } 
}

编辑于 2016-09-03 17:02:07 回复(0)

专业维修电脑

import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        while(s.hasNext()){
            int n=s.nextInt();
            int[] a=new int[n];
            int k=0;
            TreeSet<Integer> tl=new TreeSet<Integer>();
            HashMap<Integer,HashSet<Integer>> hm=new HashMap<Integer,HashSet<Integer>>();
            for(int i=0;i<n;i++){
                int t=k++;
                a[t]=s.nextInt();
            	if(hm.get(a[t])==null){
                    HashSet<Integer> al=new HashSet<Integer>();
                    int num=s.nextInt();
                    for(int j=1;j<=num;j++){
                        al.add(s.nextInt());
                    }
                    hm.put(a[t],al);
            	}else{
                    int num=s.nextInt();
                    for(int j=1;j<=num;j++){
                        hm.get(a[i]).add(s.nextInt());
                    }
            	}

            }
            //处理
            for(int i=0;i<n;i++){
            	HashSet<Integer> al = hm.get(a[i]);
                for(int num:al){
            	  if(hm.get(num)!=null){
            		  if(a[i]!=num){
                		  HashSet<Integer> al2=hm.get(num);
              		  		for(int num2:al2){
              		  		if(num2==a[i]){
              		  			tl.add(num2);
              		  			tl.add(a[i]);
              		  			break;
              		  		}
              		  	}
            		  }

            	  }

               }
            }
            //处理2
            for(int i=0;i<n;i++){
            	int count=0;
            	HashSet<Integer> al = hm.get(a[i]);
            	for(int num:al){
            		 for(int num2:tl){
            			 if(num==num2){
            				 count++;
            			 }
            			 if(count>=2){
            				 tl.add(a[i]);
            				 break;
            			 }
            		 }
            		 if(count>=2){
        				 break;
        			 }
            	}
            }
            System.out.println(tl.size());
            for(int num2:tl){
                System.out.println(num2);
            }
            
        }
    }
}

发表于 2016-06-15 16:28:57 回复(0)

李狗蛋爱搬砖

//	先简单说明一下，题目要求ID范围是0-1000000，太大了，直接建立有向图会内存溢出。正确做法是将总人数归一化后建立有向图列表，最后输出时在映射会ID号。
//  这段程序我没有写，直接把数据定死成范围在1030内，最后也可以AC。特此说明。
#include <iostream>
#include <vector>
using namespace std;

#define MaxNum  1030

int main()
{
	int num;
	while (cin >> num)
	{
		vector<vector<int> > vv(MaxNum, vector<int>(MaxNum, -1));
		vector<int> cheat(MaxNum, -1);
		int asker, n, tmp;
		int CheatNum = 0;
		//	建立有向图
		while (num--)
		{
			cin >> asker >> n;
			for (int i = 0; i < n; i++)
			{
				cin >> tmp;
				vv[asker][tmp] = 1;
			}
		}
		//	遍历图，图中带有环的就是作弊者
		for (int i = 0; i < MaxNum; i++)
		{
			for (int j = 0; j < MaxNum; j++)
			{
				if (i != j)
				{
					if (vv[i][j] == 1 && vv[j][i] == 1)
					{
						cheat[i] = 1;
						cheat[j] = 1;
					}
				}
			}
		}

//	遍历图 更新作弊者列表，每行提问者的问题回答有两个以上作弊者的也是作弊者
//	感谢 @Sleepy小迪 现更新方法如下：
//		for (int i = 0; i < MaxNum; i++)  {
		for (int i = 0; i < MaxNum;)  {
			int cnt = 0;

			for (int j = 0; j < MaxNum; j++)
			{
				if (vv[i][j] == 1 && cheat[j] == 1)
				{
					cnt++;
				}
			}

			if (cnt > 1 && cheat[i] != 1)
			{
				cheat[i] = 1;
				i = 0;
			}
			else
			{
				++i;
			}
		}

		for (int i = 0; i < MaxNum; i++)
		{
			if (cheat[i] == 1)
			{
				CheatNum++;
			}
		}
		cout << CheatNum << endl;
		for (int i = 0; i < MaxNum; i++)
		{
			if (cheat[i] == 1)
			{
				if (--CheatNum)
				{
					cout << i << " ";
				} 
				else
				{
					cout << i << endl;
				}				
			}
		}
	}
	return 0;
}

编辑于 2016-08-23 21:31:01 回复(2)

solo哥


//竟然可以AC了，说明：用户ID最大值不超过N 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main45 {
	static List<Integer> getResult(int n,int[][] map)
	{
		ArrayList<Integer> list=new ArrayList<Integer>();
		for(int i=0;i<=n;i++)
		{
			int cnt=0;
			for(int j=0;j<=n;j++)
			{
				if(map[i][j]==1 && map[j][i]==1 && i!=j)
				{
					if(!list.contains(i))
					{
						list.add(i);
						cnt++;
					}
				}
				if(map[i][j]==1 && i!=j && list.contains(j))
					cnt++;
				if(cnt>=2)
				{
					if(!list.contains(i))
					{
						list.add(i);
					}
				}
			}	
		}
		Collections.sort(list);
		return list;
	}
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			/*
			 n:问题个数
			 m[i]:提出问题i的人的编号
			 p[i]:回答问题i的人数
			 map[i][j]=1:j回答了i的问题
			 */
			int n=in.nextInt();
			int m[]=new int[n];
			int p[]=new int[n];
			int map[][]=new int[n+1][n+1];
			for(int i=0;i<n;i++)
			{
				m[i]=in.nextInt();
				p[i]=in.nextInt();
				for(int j=0;j<p[i];j++)
				{
					int num=in.nextInt();
					map[m[i]][num]=1;
				}
			}
			List<Integer> list=getResult(n, map);
			System.out.println(list.size());
			for(Integer i:list)
			{
				System.out.println(i);
			}
		}
	}
}

编辑于 2016-07-18 16:11:11 回复(0)

离疏

try:
    while 1:
        import collections
        N = int(input())
        dict_x = collections.defaultdict(list)
        for i in range(N):
            list_x= list(map(int,input().split()))
            for j in range(2,len(list_x)):
                dict_x[list_x[0]].append(list_x[j])
        ans = []
        for key in list(dict_x.keys()):
            if len(set(ans)&set(dict_x[key]))>=2:#回答者中作弊人数>=2
                ans.append(key)
            for temp in dict_x[key]:#互相回答问题，则都为作弊
                if key in dict_x[temp] and key!=temp:
                    ans.append(key)
                    ans.append(temp)
        ans = set(ans)
        ans = list(ans)
        ans.sort()
        print(len(ans))
        if len(ans)!=0:
            print(' '.join(map(str,ans)))
except EOFError:
    pass

发表于 2018-09-12 13:09:51 回复(0)

VagrantYang

我这样算作弊吗，求大佬解答一下，用了这么多库函数

package com.special.first;

import java.util.*;

/**
 * 搜狗01-火眼金睛
 *
 * 思路：用哈希思想和set来做即可（真实面试的时候不知道让不让用这么多数据结构）
 * 我们的HashMap为问题人的ID对应答题人的ID的set集合
 * 再用另一个TreeSet来存放答题人的ID，即能去重，又能快速访问，最后还能保持有序
 *
 * 我们对于每一个问题下的每一个回答者存放到哈希中
 * 首先看回答者是否与出题者是同一人，若不是，继续处理，若是，跳过
 * 条件1：看回答者有没有回答问题，若没有继续下一步
 * 若回答过问题，我们看他下面的回答者是否有当前问题者，
 * 若有，说明两者是作弊者，放到其结果set中。
 * 条件2：查看当前回答者是否是作弊者，若是count++
 * 这个问题结束后。我们看其count是否大于等于2，若是，则说明问题人是作弊者，存放
 *
 * 注意：1.问题者自己回答自己的问题不算作弊，所以上面的2个条件的处理的前提是回答者Id与出题者id不同
 * 2.若没有作弊者，最后不要输出多余的空行
 * Create by Special on 2018/3/6 14:17
 */
public class Pro045 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            Map<Integer, Set<Integer>> answers = new HashMap<>();
            Set<Integer> cheatId = new TreeSet<>();
            int n = input.nextInt(), questionNo, count, answerNo, cheatCount;
            while(n-- > 0){
                questionNo = input.nextInt();
                if(!answers.containsKey(questionNo)){
                    answers.put(questionNo, new HashSet<>());
                }
                count = input.nextInt();
                cheatCount = 0;
                while(count-- > 0){
                    answerNo = input.nextInt();
                    answers.get(questionNo).add(answerNo);
                    if(answerNo != questionNo) {
                        if (answers.get(answerNo) != null
                                && answers.get(answerNo).contains(questionNo)) {
                            cheatId.add(questionNo);
                            cheatId.add(answerNo);
                        }
                        if (cheatId.contains(answerNo)) {
                            cheatCount++;
                        }
                    }
                }
                if(cheatCount >= 2){
                    cheatId.add(questionNo);
                }
            }
            System.out.println(cheatId.size());
            boolean flag = false;
            for(int item : cheatId){
                System.out.print((!flag ? "" : " ") + item);
                flag = true;
            }
            if(flag) {
                System.out.println();
            }
        }
    }
}

发表于 2018-03-06 14:49:09 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1010; 

int main()
{     int num;     while(cin>>num)     {         vector<vector<int>> vv(MAX, vector<int>(MAX,-1));         vector<int> v(MAX,-1);         int asker,n,t;         int count = 0;                  while(num--)         {             cin>>asker>>n;             for(int i=0;i<n;i++)             {                 cin>>t;                 vv[asker][t] = 1;             }         }         for(int i=0;i<MAX;i++)             for(int j=0;j<MAX;j++)                 if(i!=j && vv[i][j]==1 && vv[j][i]==1)                     v[i] = v[j] = 1;                  for(int i=0;i<MAX;)         {             int cnt = 0;             for(int j=0;j<MAX;j++)                 if(vv[i][j]==1 && v[j]==1)                     cnt++;             if(cnt>1 && v[i]!=1)             {                 v[i] = 1;                 i = 0;             }else                 i++;                     }                  for(int i=0;i<MAX;i++)             if(v[i]==1)                 count++;         cout<<count<<endl;         for(int i=0;i<MAX;i++)             if(v[i]==1)             {                 if(--count)                     cout<<i<<" ";                 else                     cout<<i<<endl;                             }     }          return 0;
}

发表于 2017-12-21 01:07:44 回复(0)

Java

i-i

用队列存储作弊者，然后再用HashSet处理

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int N = scanner.nextInt();
            HashMap<Integer, HashSet<Integer>> answer = new HashMap<Integer, HashSet<Integer>>();
            Queue<Integer> cheatQueue = new LinkedList<>();
            for (int i = 0; i < N; i++) {
                int from = scanner.nextInt();
                int n = scanner.nextInt();
                for (int j = 0; j < n; j++) {
                    int to = scanner.nextInt();
//                  这里神坑，JDK7里面HashMap的put方法，如果是put一个新的结构，<>里必须要填数据类型Integer，而我使用的是JDK8，提交了几次都是编译错误
                    if (!answer.containsKey(to))
                        answer.put(to, new HashSet<Integer>());
//                  这里也非常坑，提问者提出问题而自己回答，不算作弊，因此自己回答自己的情况不需要考虑
                    if (to != from) {
                        answer.get(to).add(from);
                        if (answer.containsKey(from) && answer.get(from).contains(to)) {
//                            用队列存储作弊者，可以有重复，但后面会做处理
                            cheatQueue.add(from);
                            cheatQueue.add(to);
                        }
                    }
                }
            }
//          只要是被作弊者回答的提问者都会加入到cheatAnswer中，因此只要某个作弊者回答的提问者在cheatAnswer中就说明重复出现，因此提问者作弊
//          上面判定作弊的提问者也算作弊者，所以需要加入队列继续处理
            Set<Integer> cheatAnswer = new HashSet<>();
            TreeSet<Integer> cheatSet = new TreeSet<>();
            while (!cheatQueue.isEmpty()) {
                int cheat = cheatQueue.poll();
//              访问过的作弊者已经加入结果集，这样避免重复访问
                if (!cheatSet.contains(cheat)) {
                    cheatSet.add(cheat);
                    if (answer.containsKey(cheat)) {
                        for (Integer from : answer.get(cheat)) {
                            if (cheatAnswer.contains(from))
                                cheatQueue.add(from);
                            else
                                cheatAnswer.add(from);
                        }
                    }
                }
            }
//          输出结果
            System.out.println(cheatSet.size());
            if (!cheatSet.isEmpty()) {
                System.out.print(cheatSet.pollFirst());
                while (!cheatSet.isEmpty())
                    System.out.print(" " + cheatSet.pollFirst());
                System.out.println();
            }

        }
    }
}

编辑于 2017-09-05 12:58:50 回复(0)

JavaScript

寻壑

var readline = require('readline');
rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
var inputs = [];
var num = 0;
rl.on('line', function(data){
    if(num == 0){
        num = parseInt(data.trim());
    }else{
        inputs.push(data.trim());
        if(num == inputs.length) {
            var result = deal(inputs);
            if(result!==0){// js要控制输出真的麻烦。。
                console.log(result.length);
                if(result.length) {
                    result.sort(function(prev, next){
                        return prev-next;
                    });
                    var str = '';
                    result.forEach(function(item){str+=(' '+item)});
                    str = str.slice(1);
                    console.log(str);
                }
            }else{
                console.log(0);
            }
            inputs.length = 0;
            num = 0;
        }
    }
});
//总体思路为使用hashmap保存每个用户的问题下面的所有回答者，然后如果双方互相引用的话就加入作弊者列表
//对于未加入作弊者列表的用户，看其问题回答者是否有两个以上作弊者
function deal(inputsArr) {
    if(inputsArr.length<=1) return 0;
    var targets = [];
    var questions = {};
    inputsArr.forEach(function(item) {
        var question = item.split(' ');
        questions[question[0]] = questions[question[0]]?questions[question[0]].concat(question.slice(1)):question.slice(1);
    });
    for(var ques in questions){
        for(var j=0;j<questions[ques].length;j++){
            var item = questions[ques][j];
            if(item==ques) continue;
            if(questions[item] && questions[item].length && questions[item].indexOf(ques)!=-1) {
                if(targets.indexOf(ques)==-1) targets.push(ques);
                if(targets.indexOf(item)==-1) targets.push(item);
            }
        }
    }
    if(!targets.length) return 0;
    for(var unknown in questions){
        if(targets.indexOf(unknown)==-1){
            var count = 0;
            for(var i=0;i<questions[unknown].length;i++){
                if(targets.indexOf(questions[i])) count++;
                if(count==2) {
                    targets.push(unknown);
                    break;
                }
            }
        }
    }
    return targets;
}

发表于 2017-08-11 09:50:31 回复(0)

会呼吸旳痛

//按照逻辑实现即可，未遇坑
#include <vector>
#include <iostream>
#include <set>
using namespace std;


int main()
{
	int n;
	while(cin>>n)
	{
		vector<vector<int>> ps(n,vector<int>(n,0));
		while(n--)
		{
			int i,m;
			cin>>i>>m;
			while(m--)
			{
				int k;
				cin>>k;
				ps[i-1][k-1] = 1;
			}
		}
		set<int> cs;
		for(int i = 0;i<ps.size();i++)
			for(int j=i+1;j<ps.size();j++)
			{	
				if(ps[i][j] && ps[j][i])
				{
					cs.insert(i);
					cs.insert(j);
				}

			}
		bool find = true;
		while(find)
		{
			for(int i=0;i<ps.size();i++)
			{
				if(cs.count(i))continue;
				int cc=0;
				for(auto it=cs.begin();it!=cs.end();it++)
				{
					if(ps[i][*it]==1) cc++;
					if(cc>=2)
						break;
				}
				if(cc>=2)
				{
					cs.insert(i);
					i=0;
					find = true;
					continue;
				}
			}
			find = false;
		}
        cout<<cs.size()<<endl;
		int cc=0;
		for(auto it=cs.begin();it!=cs.end();it++){
			if(++cc == cs.size())
				cout<<*it+1<<endl;
		    else cout<<*it+1<<" ";
        }

	}
	return 0;
}

发表于 2016-08-22 21:46:10 回复(1)

小海胆胆

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
bool map[1030][1030],cheat[3030],vis[3030];
int n;
bool search(int cur){
	int tmp = 0;
	vis[cur] = true;
	for(int i = 1;i <= n && tmp < 2;++ i)
	if(cur != i && map[cur][i]){
	if(cheat[i])
		++ tmp;
	else if(!vis[i] && (cheat[i] = search(i)))
		++ tmp;
	}
	return cheat[cur] = tmp >= 2; 
}
int main(){
	while(scanf("%d",&n) != EOF){
		memset(map,0,sizeof(map)); memset(cheat,0,sizeof(cheat));
		for(int i = 0;i < n;++ i){
			int x,y,cnt;
			scanf("%d%d",&x,&cnt);
			for(int j = 0;j < cnt;++ j)
				scanf("%d",&y),map[x][y] = true;
		}
		for(int i = 1;i <= n + 2;++ i){
			for(int j = 1;j <= n + 2;++ j)
			if(j != i && map[i][j] && map[j][i]){
				cheat[i] = true; break;
			}
		}
		memset(vis,0,sizeof(vis));
		for(int i = 1;i <= n + 2;++ i)
		if(!cheat[i] && !vis[i])
			search(i);
		int tot = 0;
		for(int i = 1;i <= n + 2;++ i)
		if(cheat[i])
			++ tot;
		printf("%d\n",tot);
		for(int i = 1;i <= n + 2;++ i)
		if(cheat[i])
			printf("%d\n",i);
	}
	return 0;
}

发表于 2015-10-22 09:58:53 回复(0)

hellowword

#include <iostream>

#include <vector>

#include <string>

using namespace std;

struct Item{

string q_id;

int num;

vector<string> a_id;

};

bool findid(vector<string> id,string s);

vector<string> findb1(Item* Q,int m);

void findb2(vector<string>& baduser,Item* Q,int m);

void sort(vector<string>& bad);

int main()

{

int m;

while(cin >> m){

Item *Qestions = new Item[m];

string q_id;

vector<string> baduser;

int n;

vector<string> a_id;

for(int i=0;i<m;i++){

cin>>q_id >> n;

string s;

for(int j=0;j<n;j++){

cin >> s;

a_id.push_back(s);

}

Qestions[i].q_id = q_id;

Qestions[i].num = n;

Qestions[i].a_id = a_id;

a_id.clear();

}

baduser = findb1(Qestions,m);

findb2(baduser,Qestions,m);

if(baduser.empty()){

cout << "0" << endl;

}

else{

cout << baduser.size() << endl;

sort(baduser);

for(int i=0;i<baduser.size();i++){

cout << baduser[i] <<endl;

}

baduser.clear();

}

return 0;

}

vector<string> findb1(Item* Q,int m){

vector<string> baduser;

vector<string> a_id;

string s1,s2;

for(int i=0;i<m;i++){

s1 = Q[i].q_id;

for(int j =0;j<Q[i].num;j++){

s2 = Q[i].a_id[j];

for(int k =0;k<m;k++){

if(k == i){

continue ;

}

if(Q[k].q_id == s2){

a_id = Q[k].a_id;

if(findid(a_id,s1)&&s1!=s2){

if(!findid(baduser,s1)){

baduser.push_back(s1);

}

if(!findid(baduser,s2)){

baduser.push_back(s2);

}

break;

}

return baduser;

}

void findb2(vector<string>& baduser,Item* Q,int m){

vector<string> a_id;

string s1;

int f;

for(int i =0;i<m;i++){

a_id = Q[i].a_id;

s1 = Q[i].q_id;

f = 0;

for(int j =0;j<a_id.size();j++){

if(findid(baduser,a_id[j])){

f++;

}

if(f == 2){

if(!findid(baduser,s1)){

baduser.push_back(s1);

break;

}

return;

}

void sort(vector<string>& bad){

for(int i = 0;i <bad.size();i++){

for(int j=i+1;j<bad.size();j++){

if(bad[i].compare(bad[j])>0){

swap(bad[i],bad[j]);

}

bool findid(vector<string> id,string s){

int n = id.size();

for(int i =0;i<n;i++){

if(id[i] == s)

return true;

}

return false;

}

发表于 2015-10-22 20:39:31 回复(0)

董泽锋

如果输入是这样呢？

4

1 1 2

2 1 1

3 2 1 4

4 2 1 2

按照很多人的做法，得出来结果是3（判题结果也是3），但我认为应该是 4。

由于1 和 2 互相回答对方问题，所以 1 和 2 作弊；

由于4 的提问被1 和 2 回答，所以 4 作弊；

这时候，我们知道 1 ， 2 和 4 作弊。

考察 3， 3 的问题被 1 和 4 回答，所以 3也作弊。

这样就是 4个人都作弊了。

但是题目却没有考虑这种情况。

所以，我认为这题目有错。

发表于 2016-07-17 20:09:04 回复(8)

Alex-大伟

import java.util.ArrayList;
import java.util.Scanner;

public class Sohu1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			// 建立有向连接图比较合适这个问题。1->2 表示 2回答了1的问题 2->1表示1回答了2的问题
			int[][] map = new int[n + 1][n + 1];
			for (int i = 0; i < n; i++) {
				int id = scanner.nextInt();
				int ansNum = scanner.nextInt();
				int[] ids = new int[ansNum];
				for (int j = 0; j < ansNum; j++) {
					ids[j] = scanner.nextInt();
					map[id][ids[j]] = 1;
				}
			}
			cheatNum(n, map);
		}
	}

	public static void cheatNum(int n, int[][] map) {
		int cheatNum = 0;
		boolean[] isCheak = new boolean[n + 1];// 来判断每个id是否作弊
		for (int i = 1; i <= n; i++) {
			int count = 0;
			for (int j = 1; j <= n; j++) {
				if (j != i && map[i][j] == 1 && map[j][i] == 1) { // i 和 j 都作弊
														// (A回答了B的问题，同时B回答了A的问题)
					isCheak[i] = true;
					isCheak[j] = true;
				}
				// 还有一种作弊情况：作弊ID用户A和作弊ID用户B同时回答了C的问题
				if (j != i && map[i][j] == 1 && isCheak[j]) { // 统计有多少作弊用户答了i用户提的问题
					count++;
				}
			}
			if (count >= 2) { // 如果超过两个作弊用户答了i用户提的问题
				isCheak[i] = true;
			}
		}
		for (int i = 1; i <= n; i++) {
			if (isCheak[i]) {
				cheatNum++;
			}
		}
		System.out.println(cheatNum);
		int temp = 0;
		for (int i = 1; i <= n; i++) {
			if (isCheak[i]) {
				temp++;
				System.out.print(i);
				if(temp != cheatNum){
					//System.out.println(i + " ");  这样输出不行  试了10几次  心都碎了 
					System.out.print(" ");
				}
				else{
					System.out.println();
				}
			}
		}
	}
}

发表于 2016-10-02 21:38:09 回复(3)

卷积神经网络哦

题目说有N<20万然而开1000的数组大小都够了
用邻接矩阵表示有向图
比如3*3的矩阵
1的问题 2回答了就是ma[1][2] = 1否则是0
当ma[i][j] == ma[j][i] == 1时就要把i和j同时认作作弊
第二个条件：
当某个ID的问题被超过一个人回答时直接认为他作弊

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
const int maxn = 1e3 + 5;
int ma[maxn][maxn];
set<int> ans;
set<int>::iterator it;
int main(){
    int N;
    while(scanf("%d", &N) != EOF){
        memset(ma, 0, sizeof(ma));
        ans.clear();
        int  max_id = 0, min_id = 1e6 + 2;
        for(int k = 0; k < N; k++){
            int a, b, c;
            scanf("%d%d", &a, &b);
            max_id = max(max_id, a);
            min_id = min(min_id, a);
            if(b > 1) ans.insert(a);
            for(int i = 0;i < b; i++) {
                scanf("%d", &c);
                ma[a][c] = 1;
            }
        }
        if(max_id == min_id) {cout<<0<<endl;continue;}
        for(int i = min_id; i <= max_id; i++)
            for(int j = min_id; j <= max_id; j++){
                if(ma[i][j] == 1 && ma[j][i] == 1) ans.insert(i);
            }
        int si = ans.size();
        printf("%d\n", si);
        if(si > 0){
            it = ans.begin();
            for(int i = 0; i < si - 1; i++){printf("%d ", *it);it++;}
            printf("%d\n", *it);
        }

    }
}

发表于 2018-10-17 20:35:52 回复(0)

C++

Taiga_A

这题输出的回车尤其要注意，如果没有错误样例的预期输出我绝对过不了

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

struct Q {
    set<int> a;
    int q;
    int t = 0;
};

void sol(int N) {
    map<int, Q> qa;    // 问题 - 回答
    map<int, set<int>> an; // user - 回答的问题
    map<int, set<int>> anp; // user - 回答过的users
    set<int> ans;
    queue<int> que;
    while(N--) {
        int q, n; cin >> q >> n;
        auto& tq = qa[N];
        tq.q = q;
        int a;
        while(n--) {
            cin >> a; tq.a.insert(a);
            an[a].insert(N);
            anp[a].insert(q);
            // 判断第一种作弊
            if (q != a && anp[q].count(a)) {
                if(ans.insert(q).second) {
                    que.push(q);
                };
                if (ans.insert(a).second) {
                    que.push(a);
                };
            }
        }
    }

    // 判断第二种作弊
    while(!que.empty()) {
        int id = que.front(); que.pop();
        for (auto qid : an[id]) {
            auto& n = qa[qid];
            n.t++;
            if (n.t == 2 && ans.insert(n.q).second) {
                que.push(n.q);
            }
        }
    }

    cout << ans.size() << endl;
    for (int i : ans) cout << i << " ";
    if (ans.size()) cout << endl;
}

int main() {
    int N; 
    while(cin >> N) sol(N);
    return 0;
}

发表于 2025-02-10 02:00:13 回复(0)

Java

牛客486456043号

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //邻接表
    static List<List<Integer>> graph;
    static int[] visited;
    static boolean[] hasZuoBi;
    static int res;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            //为了防止多个case需要在这里进行初始化
            int N = sc.nextInt();
            graph = new ArrayList<>(); // 初始化邻接表
            visited = new int[N];
            hasZuoBi = new boolean[N];
            res = 0;
            for (int i = 0; i < N; i++) {
                graph.add(new ArrayList<>());
            }
            for (int i = 0; i < N; i++) {
                graph.add(new ArrayList<>());
                int node = sc.nextInt() - 1;
                int k = sc.nextInt();
                for (int j = 0; j < k; j++) {
                    int nodeNext = sc.nextInt() - 1;
                    graph.get(node).add(nodeNext);
                }
            }
            // System.out.println(graph);
            //第一轮去找双向箭头的节点即成环的
            for (int i = 0; i < N; i++) {
                dfs(i, graph);
            }
            // System.out.println(Arrays.toString(hasZuoBi));
            //找到连接两个作弊的节点
            for (int i = 0; i < N; i++) {
                //这个点已经作弊了就跳过
                if (hasZuoBi[i]) {
                    continue;
                } else {
                    List<Integer> temp = graph.get(i);
                    if (temp.size() >= 2) {
                        boolean tag = true;
                        for (int nodeNext : temp) {
                            //如果有一个没作弊
                            if (!hasZuoBi[nodeNext]) {
                                tag = false;
                                break;
                            }
                        }
                        hasZuoBi[i] = tag;
                    }
                }
            }
            //计算作弊的人数
            for (int i = 0; i < N; i++) {
                if (hasZuoBi[i]) {
                    res++;
                }
            }
            System.out.println(res);
            if (res != 0) {
                for (int i = 0; i < N; i++) {
                    if (hasZuoBi[i]) {
                        System.out.print((i + 1) + " ");
                    }
                }
                //在多个case里面进行换行
                System.out.println(); // 换行
            }
        }
    }

    private static void dfs(int node, List<List<Integer>> graph) {
        if (visited[node] == -1) {
            return;
        }
        visited[node] = 1;
        for (int nodeNext : graph.get(node)) {
            //不判断自身构成环
            if (node == nodeNext) continue;
            if (visited[nodeNext] == 1) {
                //两个人都作弊
                hasZuoBi[nodeNext] = true;
                hasZuoBi[node] = true;
                return;
            } else if (visited[nodeNext] == 0) {
                dfs(nodeNext, graph);
            }
        }
        visited[node] = -1;
    }
}

发表于 2024-07-25 21:02:29 回复(0)

Go

cloud_yellow

同样的代码本地IDE通过了但是在这上面总提示越界，扔讨论里看看。

做个map然后出题人是key，答题人是value切片。

先检查答题人出的提里是否有出题人的回答，如果有的话就把这俩都计入作弊ID的集合里。

然后检查还没被列为作弊人的题目里是否有两个以上的作弊者来答题，如果有那就把他也列入作弊者，重复检查直到没有新增作弊者。

按要求输出作弊者数量和排序后id。

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	n := 0

	fmt.Scanln(&n)

	record := make(map[string][]string)

	for ; n > 0; n-- {
		res := bufio.NewReader(os.Stdin)
		read, _ := res.ReadString('\n')
		read = strings.TrimSpace(read)

		sli := strings.Split(read, " ")
		leng, _ := strconv.Atoi(sli[1])
        // leng :=0
		record[sli[0]] = make([]string, leng)

		for i := 2; i < len(sli); i++ {
			record[sli[0]][i-2] = sli[i]
            // record[sli[0]] = append(record[sli[0]], sli[i])
		}

	}
	cheatId := []string{}
	//相互回答检查
	for k, v := range record {
		for j := 0; j < len(v); j++ {
			if _, ok := record[v[j]]; ok {
				for _, val := range record[v[j]] {
					if val == k {
						bol := ""
						for _, valCheck := range cheatId {
							if valCheck == k {
								bol += "k"
							}

							if valCheck == v[j] {
								bol += "v"
							}
						}
						switch {
						case bol == "k":
							cheatId = append(cheatId, v[j])
						case bol == "v":
							cheatId = append(cheatId, k)
						case bol == "kv" || bol == "vk":
							continue
						case bol == "":
							cheatId = append(cheatId, k, v[j])
						}
						// cheatId = append(cheatId, k,v[j])
					}
				}
			}
		}
	}

	//共同回答检查
	for {
		addCount := 0

		for k1, v1 := range record {
			//判定是否已经列入作弊者
			cheatCheckBol := false
			for _, cheatCheck := range cheatId {
				if k1 == cheatCheck {
					cheatCheckBol = true
					break
				}
			}

			if cheatCheckBol {
				continue
			}

			checkCount := 0
			for _, val := range v1 {
				for _, valCheck := range cheatId {
					if val == valCheck {
						checkCount++
					}
				}

			}

			if checkCount >= 2 {
				cheatId = append(cheatId, k1)
				addCount++
			}
		}

        if addCount == 0{
            break
        }

	}

    sort.Strings(cheatId)
    ans := cheatId[0]
    for i:=1;i<len(cheatId);i++{
        ans = ans + " " + cheatId[i]
    }
    fmt.Println(ans)

}

发表于 2023-08-06 13:34:37 回复(0)

火眼金睛

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题